Game Theory1

Game Theory • Developed to explain the optimal strategy in two-person interactions. • Initially, von Neumann and Morganstern – Zero-sum games

• John Nash – Nonzero-sum games

• Harsanyi, Selten – Incomplete information

An example: Big Monkey and Little Monkey • Monkeys usually eat ground-level fruit • Occasionally climb a tree to get a coconut (1 per tree) • A Coconut yields 10 Calories • Big Monkey expends 2 Calories climbing the tree. • Little Monkey expends 0 Calories climbing the tree.

An example: Big Monkey and Little Monkey • If BM climbs the tree – BM gets 6 C, LM gets 4 C – LM eats some before BM gets down

• If LM climbs the tree – BM gets 9 C, LM gets 1 C – BM eats almost all before LM gets down

• If both climb the tree – BM gets 7 C, LM gets 3 C – BM hogs coconut

• How should the monkeys each act so as to maximize their own calorie gain?

An example: Big Monkey and Little Monkey • Assume BM decides first – Two choices: wait or climb

• LM has four choices: – Always wait, always climb, same as BM, opposite of BM.

• These choices are called actions – A sequence of actions is called a strategy

An example: Big Monkey and Little Monkey

Little monkey

c

w

Big monkey w

c

w

c

0,0 9,1 6-2,4 7-2,3 What should Big Monkey do? • If BM waits, LM will climb – BM gets 9 • If BM climbs, LM will wait – BM gets 4 • BM should wait. • What about LM? • Opposite of BM (even though we’ll never get to the right side of the tree)

An example: Big Monkey and Little Monkey • These strategies (w and cw) are called best responses. – Given what the other guy is doing, this is the best thing to do.

• A solution where everyone is playing a best response is called a Nash equilibrium. – No one can unilaterally change and improve things.

• This representation of a game is called extensive form.

An example: Big Monkey and Little Monkey • What if the monkeys have to decide simultaneously?

Little monkey

c

w

Big monkey w 0,0

c

w

c

9,1 6-2,4 7-2,3

Now Little Monkey has to choose before he sees Big Monkey move Two Nash equilibria (c,w), (w,c) Also a third Nash equilibrium: Big Monkey chooses between c & w with probability 0.5 (mixed strategy)

An example: Big Monkey and Little Monkey • It can often be easier to analyze a game through a different representation, called normal form Little Monkey

Big Monkey

c

v

c

5,3

4,4

v

9,1

0,0

Choosing Strategies • In the simultaneous game, it’s harder to see what each monkey should do – Mixed strategy is optimal.

• Trick: How can a monkey maximize its payoff, given that it knows the other monkeys will play a Nash strategy? • Oftentimes, other techniques can be used to prune the number of possible actions.

Eliminating Dominated Strategies • The first step is to eliminate actions that are worse than another action, no matter what. Big monkey

c

w

w Little monkey 0,0 Little Monkey will Never choose this path.

c

w

c

9,1 6-2,4 7-2,3 Or this one

w

c

9,1

4,4

We can see that Big Monkey will always choose w. So the tree reduces to: 9,1

Eliminating Dominated Strategies • We can also use this technique in normalform games: Column a

b

a

9,1

4,4

b

5,3

0,0

Row

Eliminating Dominated Strategies • We can also use this technique in normalform games: a

b

a

9,1

4,4

b

5,3

0,0

For any column action, row will prefer a.

Eliminating Dominated Strategies • We can also use this technique in normalform games: a

b

a

9,1

4,4

b

5,3

0,0

Given that row will pick a, column will pick b. (a,b) is the unique Nash equilibrium.

Prisoner’s Dilemma • Each player can cooperate or defect Column cooperate

defect

cooperate

-1,-1

-10,0

defect

0,-10

-8,-8

Row

Prisoner’s Dilemma • Each player can cooperate or defect Column cooperate

defect

cooperate

-1,-1

-10,0

defect

0,-10

-8,-8

Row

Defecting is a dominant strategy for row

Prisoner’s Dilemma • Each player can cooperate or defect Column cooperate

defect

cooperate

-1,-1

-10,0

defect

0,-10

-8,-8

Row

Defecting is also a dominant strategy for column

Prisoner’s Dilemma • Even though both players would be better off cooperating, mutual defection is the dominant strategy. • What drives this? – One-shot game – Inability to trust your opponent – Perfect rationality

Prisoner’s Dilemma • Relevant to: – – – –

Arms negotiations Online Payment Product descriptions Workplace relations

• How do players escape this dilemma? – Play repeatedly – Find a way to ‘guarantee’ cooperation – Change payment structure

Tragedy of the Commons • Game theory can be used to explain overuse of shared resources. • Extend the Prisoner’s Dilemma to more than two players. • A cow costs a dollars and can be grazed on common land. • The value of milk produced (f(c) ) depends on the number of cows on the common land. – Per cow: f(c) / c

Tragedy of the Commons • To maximize total wealth of the entire village: max f(c) – ac. – Maximized when marginal product = a – Adding another cow is exactly equal to the cost of the cow.

• What if each villager gets to decide whether to add a cow? • Each villager will add a cow as long as the cost of adding that cow to that villager is outweighed by the gain in milk.

Tragedy of the Commons • When a villager adds a cow: – Output goes from f(c) /c to f(c+1) / (c+1) – Cost is a – Notice: change in output to each farmer is less than global change in output.

• Each villager will add cows until output- cost = 0. • Problem: each villager is making a local decision (will I gain by adding cows), but creating a net global effect (everyone suffers)

Tragedy of the Commons • Problem: cost of maintenance is externalized – Farmers don’t adequately pay for their impact. – Resources are overused due to inaccurate estimates of cost.

• Relevant to: – – – –

IT budgeting Bandwidth and resource usage, spam Shared communication channels Environmental laws, overfishing, whaling, pollution, etc.

Avoiding Tragedy of the Commons • Private ownership – Prevents TOC, but may have other negative effects.

• Social rules/norms, external control – Nice if they can be enforced.

• Taxation – Try to internalize costs; accounting system needed.

• Solutions require changing the rules of the game – Change individual payoffs – Mechanism design

Coming next time • How to select an optimal strategy • How to deal with incomplete information • How to handle multi-stage games