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
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