Information Technology Reference
In-Depth Information
It turns out that replacing intractability assumptions with the existence of uncondition-
ally private channels (like in Section 3.1), only enables the fully private emulation of a
restricted
set of mechanisms. These mechanisms will be called “simple mechanisms”
in the following.
Definition 2 (Simple Mechanism).
A mechanism is
simple
if its outcome function is
privately computable in the sense of [Kus89, CK89].
E.g.
, the only Boolean outcome
functions that are privately computable are of the form
f
(
θ
)=
B
1
(
θ
1
)
⊕
B
2
(
θ
2
)
⊕
···⊕
B
n
(
θ
n
)
where
B
i
(
θ
i
)
are Boolean predicates and
⊕
is the Boolean exclusive-or
operator.
There is yet no complete characterization of privately computable functions (except for
special cases like Boolean [CK89] and 2-ary functions [Kus89]). However, by using
known necessary conditions for private computability, it has been shown that first-price
sealed-bid auctions are simple mechanisms whereas second-price sealed-bid auctions
are not [BS04].
Proposition 2.
Correct mechanism execution can be guaranteed for simple mecha-
nisms without a center given that there are private channels between all agents and
one-way permutations exist. Privacy cannot be breached.
7
As in the previous section, both models also allow the (correct) computation of
different
outcomes (or parts of an outcome) for each agent,
e.g.
, so that losing bidders in an
auction do not learn the selling price.
4
Intertwining Cryptography and Mechanism Design
In this section, we will relax three restrictions that we made so far, namely that mech-
anisms are deterministic, single-step, and incentive-compatible. The revelation prin-
ciple, a central theorem of mechanism design, suggests that one restrict attention to
direct-revelation mechanisms,
i.e.
, truthful, single-step mechanisms, as all remaining
mechanisms can be simulated by (possibly randomized) direct-revelation mechanisms.
Although this a striking result in mechanism design, its consequences are debatable as
it does not consider the following important aspects: communication complexity, com-
putational abilities of the agents and the center (see also [CS03b]), and, which is our
main concern here, privacy of agents' preferences. But first of all, let us consider the
effects of randomization on the correctness of a mechanism.
4.1
Randomized Mechanisms
Randomized mechanisms,
i.e.
, mechanisms in which the outcome function is proba-
bilistic, are of increasing interest. It has been shown in [CS02a] that the automated
design of an optimal deterministic mechanism for a constant number of agents is
-
complete in most settings whereas the design of randomized mechanisms for the same
purpose is always tractable (by linear programming). Furthermore, randomized mech-
anisms are always as good or better than deterministic ones in terms of the expected
value of the designer's objective (
e.g.
, a 2-item revenue maximizing auction has to be
NP
