CS 581, Homework 2

Expected Utility

(a)

CompletenessLemma 1
Every lottery has an expected utility, and every two real numbers are comparable under
TransitivityLemma 2
Every lottery has an expected utility, and is transitive for the real numbers.
IndependenceLemma 3
Assume for contradiction , which is a contradiction.
ContinuityLemma 4

Assume for contradiction If then any works. Otherwise,

Since , which is a contradiction.

(b)

The Allais lottery violates independence.

Let

For , and , and , thus For , and and , however this implies that , which is a contradiction.

Zero-sum games

P1,P2RockPaperScissors
Rock0,0−1, 12, −2
Paper1, −10,0−3, 3
Scissors−2, 23, −30,0

(a)

Fix Player 2. For each choice Player 1 makes, if are the probabilities of Rock and Paper respectively

Thus, for each player, the optimal strategy is , since the expected payoff of every each strategy is . This is the unique strategy, since the payoffs are zero and the three actions must be equally good, so the solution to these equations is the unique solution.

(b)

Assume two Nash equilibria in a zero-sum game, and .

We know that deviation from to is weakly worse for the row player and deviation from to are weakly worse for the column player. In other words, . Similarly, .

Thus . What’s more, by the sandwich, , thus and are Nash equilibria, since otherwise it would be possible to deviate from and do strictly better. However this implies that you could also have deviated from one of or , which contradicts that they were Nash equilibria.

Hotelling competition

(a)

For , fix agent at and at . For , the payoff is and , For any deviation is always optimal for any agent, and they will receive if since they split the customers, which is optimal and unique, since any deviation will receive strictly less tan .

(b)

In the social-cost minimizing placement, one firm is placed at and another is placed at . The expected distance from a random customer to her nearest firm is

For the Nash Equilibrium, the social cost is

Thus the price of anarchy is

(c)

For , assume for contradiction that a pure Nash Equilibrium exists. Then there is a where no deviation can improve the utility. If the points are distinct, and can simply move to and “steal” and more of the line respectively. If two points lie at least to the to the right of overlap at , then deviating to move to will capture at least of the customers. If all points overlap, then deviating to , since the customers are no longer split. Thus no pure Nash equilibrium exists.