Information Technology Reference
In-Depth Information
On Correctness and Privacy in
Distributed Mechanisms
Felix Brandt and Tuomas Sandholm
Carnegie Mellon University, Pittsburgh PA 15213, USA
{
brandtf, sandholm
}
@cs.cmu.edu
Abstract.
Mechanisms that aggregate the possibly conflicting preferences of in-
dividual agents are studied extensively in economics, operations research, and
lately computer science. Perhaps surprisingly, the classic literature assumes
par-
ticipating agents
to act selfishly, possibly untruthfully, if it is to their advantage,
whereas the
mechanism center
is usually assumed to be honest and trustworthy.
We argue that cryptography offers various concepts and building blocks to ensure
the secure,
i.e.
, correct and private, execution of mechanisms. We propose mod-
els with and without a center that guarantee correctness and preserve the privacy
of preferences relying on diverse assumptions such as the trustworthiness of the
center or the hardness of computation. The decentralized model in which agents
jointly “emulate” a virtual mechanism center is particularly interesting for two
reasons. For one, it provides privacy without relying on a trusted third-party. Sec-
ond, it enables the provably correct execution of
randomized
mechanisms (which
is not the case in the centralized model). We furthermore point out how untruthful
and multi-step mechanisms can improve privacy. In particular, we show that the
fully private emulation of a preference elicitor can result in unconditional privacy
of a (non-empty) subset of preferences.
1
Introduction
Mechanisms that aggregate the possibly conflicting preferences of individual agents
are studied extensively in economics, operations research, and lately computer science.
Distributed mechanisms are used in such diverse application areas as auctions, voting,
resource sharing, routing, or task assignment.
In the heart of a mechanism lies the so-called “mechanism center” or “mechanism
infrastructure” to which agents privately send reports about their preferences and that
computes the mechanism outcome (
e.g.
, allocation of goods, election winner, network
route,
etc.
). The main focus of existing work has been on creating mechanisms whose
outcome has various desirable properties (efficient computability has been added re-
cently) and in which agents have an incentive to submit their preferences truthfully.
Perhaps surprisingly, the classic literature assumes
participating agents
to act selfishly,
possibly untruthfully, if it is to their advantage, whereas the
mechanism center
is usually
assumed to be honest and trustworthy, even when it has an incentive to be untruthful,
e.g.
, by overstating the second-highest bid in Vickrey auctions if it gains a fraction of
the selling price (see for example [PS03]).
This paper was originally presented at AMEC-04.
