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