On Correctness and Privacy in Distributed Mechanisms - Agent-Mediated Electronic Commerce - page 219

randomized [AH00, CS03a]). Finally, as mentioned above, the revelation principle only
holds if we allow for the possibility that the resulting direct-revelation mechanism may
be randomized.
Randomization has severe consequences on the notion of correctness. Whereas a
single mechanism center can prove the correctness of the outcome of a deterministic
mechanism (see Section 3.1), this is not possible for randomized mechanisms. There
is no way a mechanism center can actually prove that it is using real random numbers
in order to compute the outcome (without introducing a third-party that is assumed to
reliably supply random data). The advantages of randomized mechanisms ( e.g. ,that
manipulating the mechanism can be -hard [CS03c]) in fact rely on the trustworthi-

ness of the mechanism center. These advantages become void if the center is corrupt.
Forcing the center to commit to its random choice before the agents submit their pref-
erences only reduces the problem as the center might still choose a random value that
is beneficial to itself (and possibly colluding agents). 8
In the decentralized model proposed in Section 3.2, on the other hand, the “compe-
tition” between agents allows the unbiased joint generation of random numbers (unless
all agents collude).

NP

Theorem 3. Randomized mechanisms can be emulated correctly by computationally
fully private protocols. Randomized simple mechanisms can be emulated correctly by
unconditionally fully private protocols.

Proof. The following construction builds on a cryptographic primitive that is called
“coin tossing into the well” [Blu82]. Before computing the mechanism outcome, each
agent broadcasts an unconditionally hiding commitment to a freely chosen bit-string r i
and proves the correctness of the commitment ( i.e. , that he knows what is inside) with
a perfect zero-knowledge argument. These proofs are arranged sequentially to avoid
proof duplication as in Theorem 1. After that, agents commit to their preferences and
start emulating the mechanism. In the following computation of the outcome, agents
can use r = r 1 ⊕

r n (which can be privately computed, even in the un-
conditionally private model according to Definition 2) as a source of pure random data.
We stress the fact, that this procedure works for the computationally private emula-
tion of arbitrary mechanisms as well as the unconditionally private emulation of simple
mechanisms. As the agents generate the random bit-string before committing to their
preferences, the correctness of the (randomized) outcome can still be guaranteed if all
agents collude after knowing the submitted preferences of each other for sure (in the
form of commitments). This is desirable as there are mechanisms in which it might
be beneficial for all agents to manipulate the randomization of the outcome after they
know their submissions. 9

r 2 ⊕ ··· ⊕

8

Even though truthfulness is preserved when the random choice is known beforehand in
strongly truthful mechanisms [MV04], other properties such as revenue maximization might
be lost when agents are able to manipulate the random choice by colluding with the mechanism
center.

9

There might also be randomized mechanisms where the opposite is true, i.e. , all agents benefit
from a manipulation of their preferences after they know the common random string, but we
doubt that they are of any significance.