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

4.2 Multi-Step Mechanisms

Multi-step mechanisms are mechanisms in which the center gradually asks questions to
the agents in multiple rounds until enough preferences have been elicited to compute
the outcome (see e.g. , [CS01]). Ascending ( e.g. , English) or descending ( e.g. ,Dutch)
auctions are special cases of this definition. Besides the limited preference revelation,
multi-step mechanisms have an important advantage that is not considered in cryp-
tography: Agents do not need to completely determine their own preferences. This is
important because determining one's own preferences may be tedious task and can even
be intractable [San93].
While executing multi-step mechanisms in the single center models presented in
Section 3.1 is straightforward, it is interesting to examine whether the fully private em-
ulation of multi-step mechanisms is possible. By fully privately emulating a multi-step
mechanism, we can improve the level of privacy guaranteed in Proposition 1 because
some preferences might never be elicited and thus remain unconditionally private. How-
ever, the main problem is that queries may implicitly contain information on agents'
preferences revealed so far. We define a certain class of mechanisms which always ben-
efit from private elicitation.

Definition 3 (Privately Elicitable Mechanism). A mechanism is called privately elic-
itable if it satisfies the following two conditions:

- There are cases in which a subset of the preferences is sufficient to compute the
mechanism outcome. 10
- There is a function that maps the mechanism outcome and the preferences of one
agent to the complete sequence of queries that this agent received.

The second condition ensures that agents do not learn information about others' prefer-
ences from the queries they are asked (see the proof of Theorem 4 for details). English
auctions, for example, are privately elicitable mechanisms: The first condition holds be-
cause it is irrelevant (for the mechanism outcome) how much the highest bidder would
have bid, as long as it is made sure that everybody else bid less than him. The second
condition is satisfied because the only prices not “offered” to a bidder are prices above
the selling price.

Theorem 4. Privately elicitable mechanisms can be emulated by fully private protocols
so that it is impossible to reveal all preferences, even by exhaustive computation.

Proof. Without loss of generality, the preference elicitor can be emulated by the follow-
ing protocol. We jointly and iteratively compute a query function and a stop-function
for several rounds, and once, at the end of the protocol, evaluate the outcome function.
Let γ i

Γ i be the (iteratively updated) set of agent i 's statements on his prefer-
ences, γ =( γ 1 ,γ 2 ,...,γ n ),and Γ = Γ 1 ×

∈

Γ n .All γ i are initialized
as empty sets. The following procedure is repeated round by round. The query func-
tion q :

Γ 2 × ··· ×

{ 1 , 2 ,...,n }× Γ → Q , which is fully privately computed by all agents (using

10

Otherwise, preference elicitation would be pointless, regardless of privacy. Almost all practical
mechanisms satisfy this condition.