Game Development Reference

In-Depth Information

explained by faulty computers or a faulty network (this, of course, is the

concern that work on Byzantine agreement is trying to address), or a lack of

understanding of the game.

To give just one example of a stylised game where this issue might be

relevant, consider a group of
n
bargaining agents. If they all stay and bargain,

then all get 2. However, if any agent leaves the bargaining table, those

who leave get 1, while those who stay get 0. Clearly everyone staying at

the bargaining table is a
k
-resilient Nash equilibrium for all
k

0, and it

is Pareto optimal (everyone in fact gets the highest possible payoff). But,

especially if
n
is large, this equilibrium is rather 'fragile'; all it takes is one

person to leave the bargaining table for those who stay to get 0.

Whatever the reason, as pointed out by Abraham et al. [2006], it seems

important to design strategies that tolerate such unanticipated behaviour, so

that the payoffs of the users with 'standard' utilities do not get affected by

the non-standard players using different strategies. This can be viewed as a

way of adding fault tolerance to equilibrium notions. To capture this intuition,

Abraham et al. [2006] define a strategy profile to be
t
-immune
if a player

who does
not
deviate is no worse off if up to
t
players do deviate. Note the

difference between resilience and immunity. A strategy profile is resilient if

deviators do not gain by deviating; a profile is immune if non-deviators do not

get hurt by deviators. In the example above, although everyone bargaining

is a
k
-resilient Nash equilibrium for all
k

≥

0, it is not 1-immune.

Of course, we may want to combine resilience and immunity; a strategy

profile is (
k, t
)
-robust
if it is both
k
-resilient and
t
-immune. (All the informal

definitions here are completely formalised in [Abraham et al., 2006, 2008].)

A Nash equilibrium is just a (1,0)-robust equilibrium. Unfortunately, for

(
k, t
)

≥

=(1
,
0), a (
k, t
)-robust equilibrium does not exist in general, even if

we allow mixed strategies (i.e., even if players can randomise). Nevertheless,

there are a number of games of interest where they do exist; in particular,

they can exist if players can take advantage of a
mediator
, or trusted

third party. To take just one example, consider Byzantine agreement [Pease

et al., 1980]. Recall that in Byzantine agreement there are
n
soldiers, up

to
t
of which may be faulty (the
t
stands for
traitor
), one of which is the

general. The general has an initial preference to attack or retreat. We want

a protocol that guarantees that (1) all
non-faulty
soldiers reach the same

decision, and (2) if the general is non-faulty, then the decision is the general's

preference. It is trivial to solve Byzantine agreement with a mediator: the

general simply sends the mediator his preference, and the mediator sends it

to all the soldiers.

The obvious question of interest is whether we can
implement
the medi-

Search Nedrilad ::

Custom Search