Game Development Reference

In-Depth Information

Is the lack of Nash equilibrium a problem? Perhaps not. For one thing, it

can be shown that if, in a precise sense, randomisation is free, then there is

always a Nash equilibrium (see [Halpern and Pass, 2010]; note that this does

not follow from Nash's theorem [1950a] showing that every finite standard

game has a Nash equilibrium since it says, among other things, that the

Nash equilibrium is computable - it can be played by Turing machines).

Moreover, taking computation into account should cause us to rethink things.

In particular, we may want to consider other solution concepts. But, as

the examples above show, Nash equilibrium does seem to make reasonable

predictions in a number of games of interest. Perhaps of even more interest,

using computational Nash equilibrium lets us provide a game-theoretic

account of security.

The standard framework for multiparty security does not take into account

whether players have an incentive to execute the protocol. That is, if there

were a trusted mediator, would player
i
actually use the recommended

protocol even if
i
would be happy to use the services of the mediator to

compute the function
f
? Nor does it take into account whether the adversary

has an incentive to undermine the protocol.

Roughly speaking, the game-theoretic definition says that Π is a
game-

theoretically secure
(cheap-talk) protocol for computing
f
if, for all choices

of the utility function, if it is a Nash equilibrium to play with the mediator

to compute
f
, then it is also a Nash equilibrium to use Π to compute
f
. Note

that this definition does not mention privacy. It does not need to; this is

taken care of by choosing the utilities appropriately. Pass and I [2010] show

that, under minimal assumptions, this definition is essentially equivalent

to a variant of
zero knowledge
[Goldwasser et al., 1989] called
precise

zero knowledge
[Micali and Pass, 2006]. Thus, the two approaches used

for dealing with 'deviating' players in two game theory and cryptography -

Nash equilibrium
and
zero-knowledge 'simulation'
- are intimately connected;

indeed, they are essentially equivalent once we take computation into account

appropriately.

8.4 Taking (lack of) awareness into account

Standard game theory models implicitly assume that all significant aspects of

the game (payoffs, moves available, etc.) are common knowledge among the

players. However, this is not always a reasonable assumption. For example,

sleazy companies assume that consumers are not aware that they can lodge

complaints if there are problems; in a war setting, having technology that an

Search Nedrilad ::

Custom Search