GTCS Assignment 2

From Theory

Notes for CS 8803 - Game Theory and Computer Science. Spring 2008

---

Contents 1 Problem 1 2 Problem 2 3 Problem 3 4 Problem 4 5 Problem 5 6 Problem 6

Problem 1

Find all the Nash Equilibria of the following game (Owen):

	A	B	C
A	3,2	4,5	1,3
B	2,4	1,2	3,5

Problem 2

Find all N.E. of the following games.

1. Two players simultaneously pick an integer between 1 and 5, inclusive. Whoever picks the larger number gets that number as a payoff (utility), and the other player gets 0. In the case of a tie, both players get 0.
2. Now consider the same game but the case that the player who picks the smaller integer receives what he picked (again 0 in the case of a tie or picking the larger number). What are all the N.E. of this game?
3. Finally, consider the case where the number can be picked in the open interval (1,5) (and the player with the larger payoff wins).

Problem 3

Suppose a gamble is offered that with 50% probability, you get $1, and with 50% probability, you lose $1. Suppose you have more than 1 dollar to start. For each of the following five utility functions, should you take the gamble?

1. u(x) = log(x)
2. 
3. u(x) = x²
4. 
5. u(x) = x + 1

Justify your answers.

Problem 4

(Due to E. Lauer) Suppose your utility for money is linear, u(x) = x. Suppose you are playing the following game. Somebody puts two amounts of money, x and 2x in two different envelopes, shuffles them at random, and gives one to you and one to your neighbor. You open your envelope and observe how much money is inside. You are then given the option to switch with your neighbor or not. (Your neighbor has no option and must go along with whatever happens.) After that decision, the game ends and each player keeps what is inside her envelope.

Suppose you play this game once, and you open your envelope and find $20 inside. Should you switch?

Problem 5

Prove that the mixed-strategy max-min values in the adversarial routing game are ( − 1 / S,1 / S), where S is the size of the minimum s − t cut, i.e., the minimum number of edges that need to be removed from the graph so that there is no path from s to t. Hint: use a max-flow and a min-cut, and the max-flow min-cut theorem.

Problem 6

Let G be the game of chess: a two-person zero-sum extensive-form game with perfect information (and complete information -- we haven't gotten to incomplete information yet), where all payoffs are in { − 1,0,1}. Show that G can be solved in two rounds of iterated elimination of dominated strategies..

---

The production of this material was supported in part by NSF award SES-0734780.