Game Development Reference
In-Depth Information
These results provide an excellent illustration of how the interaction between
computer science and game theory can lead to fruitful insights. Related work
on implementing mediators can be found in [Gordon and Katz, 2006, Halpern
and Teadgue, 2004, Izmalkov et al., 2005, Kol and Naor, 2008, Lepinski et al.,
2004, Lysyanskaya and Triandopoulos, 2006].
8.3 Taking computation into account
Nash equilibrium does not take computation into account. To see why this
might be a problem, consider the following example, taken from [Halpern
and Pass, 2010].
Example 8.1 You are given an n -bit number x . You can guess whether
it is prime, or play safe and say nothing. If you guess right, you get \$10; if
you guess wrong, you lose \$10; if you play safe, you get \$1. There is only
one Nash equilibrium in this one-player game: giving the right answer. But
if n is large, this is almost certainly not what people will do. Even though
primality testing can be done in polynomial time, the costs for doing so
(buying a larger computer, for example, or writing an appropriate program),
will probably not be worth it for most people. The point here is that Nash
equilibrium is not taking the cost of computing whether x is prime into
account.
There have been attempts in the game theory community to define solution
concepts that take computation into account, going back to the work of
Rubinstein [1986]. (See [Kalai, 1990] for an overview of the work in this area
in the 1980s, and [Ben-Sasson et al., 2007] for more recent work.) Rubinstein
assumed that players choose a finite automaton to play the game rather than
choosing a strategy directly; a player's utility depends both on the move
made by the automaton and the complexity of the automaton (identified
with the number of states of the automaton). Intuitively, automata that use
more states are seen as representing more complicated procedures. Rafael
Pass and I [2010] provide a general game-theoretic framework that takes
computation into account. (All the discussion in this section is taken from
[Halpern and Pass, 2010].) Like Rubinstein, we view all players as choosing
a machine, but we use Turing machines, rather than finite automata. We
associate a complexity, not just with a machine, but with the machine and its
input. This is important in Example 8.1, where the complexity of computing
whether x is prime depends, in general, on the length of x .
The complexity could represent the running time of or space used by
Search Nedrilad ::

Custom Search