Information Technology Reference
In-Depth Information
In this paper, we investigate how to ensure the correctness of the mechanism out-
come and the privacy of individual preferences by using various building blocks that
have been developed in the field of cryptography over the years. As a matter of fact,
cryptography and mechanism design have major objectives in common. To a large
extent, both fields are concerned about agents who deviate from a given distributed
mechanism (respectively protocol) in an undesirable manner (violating global objec-
tives such as social welfare maximization or privacy). One could say that mechanisms
allocate utility optimally with respect to certain constraints such as individual rational-
ity, social welfare maximization, or budget-balance. For example, utility is allocated by
redistributing goods or imposing payments on participants. Cryptographic protocols,
on the other hand, allocate information optimally with respect to constraints like pri-
vacy, correctness, or fairness. However, while mechanism design assumes adversaries
to be rational (according to some definition of utility), cryptography traditionally deals
with “ worst-case ” adversaries, i.e. , any strategy, regardless of rationality is considered.
In fact, in cryptography, it is considered a bad concept to assume rationality of the
adversary ( e.g. , [Gol01]). Yet, the mechanism design approach has its merits. For ex-
ample, cryptographic protocols are incapable of eliciting truthful behavior since they
cannot provide incentives. Generally speaking, proper behavior of agents in a mech-
anism is enforced by making deviations “uneconomic”, i.e. , no utility can be gained
by manipulating the mechanism. In cryptography, on the other hand, the correctness
of a protocol is ensured by forcing agents to prove the correctness of each of their
actions without revealing any information but the correctness itself. This is achieved
by relying on computational intractability, i.e. , the existence of computationally hard
problems, the polynomially bounded computational power of agents, etc. . Interestingly,
using computational intractability as a barrier against undesirable behavior, which has
a long tradition in cryptography since Diffie and Hellman's seminal paper [DH76], was
recently also applied in mechanism design [BTT89, CS03c].
This paper establishes a link between cryptography and mechanism by using crypto-
graphic primitives to provide correctness and privacy in distributed mechanisms. Cor-
rectness and privacy are defined as follows. Correctness means that in the end of a
mechanism each agent is convinced that the outcome was computed correctly whereas
privacy states that an agent does not learn anything about others' preferences that he
cannot infer from the (correct) outcome and his own preferences. Correctness and pri-
vacy are not only complementary but also deeply intertwined (see Section 3). In mecha-
nisms, privacy of preferences is crucial not only because sensible information might be
of importance for future mechanisms or negotiations but also because a lack of privacy
heavily affects the equilibria of mechanisms in execution. We will use the following
notations. Agent i 's preferences are denoted by θ i
Θ i . The outcome function of a
mechanism is f : Θ 1 ×
O . θ is a short notation for ( θ 1 2 ,...,θ n ).
n is the number of agents participating in a mechanism.
The remainder of this paper is structured as follows. Section 2 summarizes existing
work at the boundary between cryptography and mechanism design. Section 3 intro-
duces basic security models that ensure correct mechanism execution, with or without
a center. In Section 4, we consider randomized, multi-step, and untruthful mechanisms
Θ 2 ×···×
Θ n
Search WWH ::




Custom Search