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