Game Development Reference

In-Depth Information

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

Search Nedrilad ::

Custom Search