Game Development Reference
ator. That is, can the players in the system, just talking among themselves
(using what economists call 'cheap talk'), simulate the effects of the mediator.
This is a question that has been of interest to both the computer science
community and the game theory community. In game theory, the focus has
been on whether a Nash equilibrium in a game with a mediator can be imple-
mented using cheap talk (cf. [Barany, 1992, Ben-Porath, 2003, Forges, 1990,
Gerardi, 2004, Heller, 2005, Urbano and Vila, 2002, 2004]). In cryptography,
the focus has been on secure multiparty computation [Goldreich et al.,
1987, Shamir et al., 1981, Yao, 1982]. Here it is assumed that each agent i
has some private information x i (such private information, like the general's
preference, is typically called the player's type in game theory).
Fix a function f . The goal is to have agent i learn f ( x 1 ,...,x n ) without
learning anything about x j for j
= i beyond what is revealed by the value of
f ( x 1 ,...,x n ). With a trusted mediator, this is trivial: each agent i just gives
the mediator its private value x i ; the mediator then sends each agent i the
value f ( x 1 ,...,x n ). Work on multiparty computation provides general con-
ditions under which this can be done (see [Goldreich, 2004] for an overview).
Somewhat surprisingly, despite there being over 20 years of work on this
problem in both computer science and game theory, until recently, there has
been no interaction between the communities on this topic.
Abraham et al. [2006, 2008] essentially characterise when mediators can
be implemented. To understand the results, three games need to be con-
sidered: an underlying game Γ, an extension Γ d of Γ with a mediator,
and a cheap-talk extension Γ CT of Γ. Γ is assumed to be a (normal-form)
Bayesian game : each player has a type from some type space with a known
distribution over types, and must choose an action (where the choice can
depend on his type). The utilities of the players depend on the types and
actions taken. For example, in Byzantine agreement, the possible types of
the general are 0 and 1, his possible initial preferences (the types of the
other players are irrelevant). The players' actions are to attack or retreat.
The assumption that there is a distribution over the general's preferences
is standard in game theory, although not so much in distributed comput-
ing. Nonetheless, in many applications of Byzantine agreement, it seems
reasonable to assume such a distribution. A cheap talk game implements a
Nash equilibrium σ of a game with a mediator if the cheap talk game has a
Nash equilibrium σ such that σ and σ induce the same distribution over
actions in the underlying game, for each type vector of the players. With
this background, I can summarise the results of Abraham et al.
If n> 3 k +3 t ,a( k, t )-robust strategy σ with a mediator can be implemented