Algorithmic Game Theory and Applications: Coursework 2
PLEASE ANSWER *** ONLY 2 *** OUT OF THE FOUR QUES- TIONS on this coursework. DO NOT SUBMIT ANSWERS TO MORE THAN TWO OF THE QUESTIONS (ONLY TWO WILL BE MARKED).
This homework is due at 12:00 (noon), on Friday, March 29th.
Please submit your solutions online as PDF files, using a separate PDF file for each question that you submit an answer for, using the LEARN page for AGTA. (This will be via GradesScope, with the same instructions to how to submit the two PDF files as for Coursework 1.) Do not collaborate with other students on the coursework. Your solutions must be your own.
Each question counts for 50 points, for a total of 100 points for AN- SWERING *** TWO *** QUESTIONS ONLY.
1. Recall that a Nash equilibrium in an extensive form game is subgame perfect nash equilibrium (SPNE) if it is also a Nash equilibrium in every subgame of the original game. Formally, a subgame, is a game defined by a subtree, Tv of the original game tree, T, such that the subtree Tv, rooted at a node v, has the property that for every decendent u of v in the game tree (including v itself), every node in the same information set as u is also in the subtree Tv.
(a) [14 points] Give an example of a pure NE which is not a SPNE, for a finite extensive form game of perfect information.
(b) [20 points] Prove that every finite extensive game of perfect infor- mation where there are no chance nodes and where no player gets the same payoff at any two distinct leaves, must have a unique pure-strategy SPNE.
(c) [16 points] Give an example of a finite extensive form game that contains a pure Nash Equilibrium but does not contain any subgame- perfect pure Nash Equilibrium. Justify your answer.
Player 1
LMR
Player 2 → Player 2 ablrlr
(4, 5) (7, 6)
← Player 1 →
x1 y1 x2 y2
(3,7) (4,4) (5,6) (6,4) Figure 1: Question 2
← Player 2 →
c1 d1 c2 d2
(3,2) (5,6) (6,2) (6,6)
2. Consider the finite extensive form game of imperfect information de- picted in Figure 1. (When a leaf node is labeled by a pair (i,j) of integers, that means the payoff at that leaf to player 1 is i and the payoff to player 2 is j.)
(a) [6 points] Does this game satisfy “perfect recall”? Explain.
(b) [24 points] Identify all SPNEs in this game, in terms of “behavior strategies”. Explain why what you have identified are all SPNEs.
Next, consider the following 2-player zero-sum finite extensive form game of perfect information. There are two players, player 1 (you), and player 2 (your opponent). There are three 6-sided dice, D1, D2, and D3. However, these dice are not “ordinary” dice, in the sense that their sides are not labeled with all the numbers 1 through 6. Instead:
• Die D1 has five of its sides labeled by the number 4 and one of its sides labeled by the number 1.
• Die D2 has three of its sides labeled by the number 2 and three of its sides labeled by the number 5.
• Die D3 has five of its sides labeled by the number 3, and one of its sides labeled by the number 6.
All three dice D1, D2, and D3, have the following usual property of an ordinary die: each time you role any of these dice, each of the six
sides of that die are equally likely (with probability 1/6) to show up on top when the die has stopped rolling.
The game between player 1 and 2 is played as follows:
• Player 1 (you) has the first “move”. Player 1 can either choose one of the three dice, D1 or D2 or D3, or else it can “pass” and allow player 2 (the opponent) to choose one of the three dice first.
• Next, it is player 2’s turn. If player 1 has already chosen a die, then player 2 must choose one of the other two remaining dice not chosen already by player 1. If instead player 1 has “passed” in the prior move, then Player 2 must now choose one of the three dice (any one). Player 2 cannot “pass”.
Afterwards, if player 1 had not already chosen a die (meaning it had passed earlier and allowed player 2 to choose first), then player 1 now has to choose one of the other two remaining dice, not chosen already by player 2.
• Afterwards, when both players have each chosen their respective die, each player roles their own die, and whoever rolls a higher number wins a “payoff” of 1 Dollar from the other player. (So, the payoff of the player who rolled a higher number is +1 and the payoff of the player who rolled a lower number is −1. Note that it isn’t possible for both players to roll the same number, because no two dice among D1, D2, and D3 have a common number labeling any one of their sides.)
Note that since this defines a finite 2-player zero-sum extensive form game of perfect information, by Kuhn’s theorem there exists a pure minimax profile in this game (i.e., a pure Nash equilibrium).
(c) [20 points] Compute the minimax value of this two player zero- sum extensive form game (from the perspective of player 1 (you), the maximizer), and compute a pure minimax profile in this game (i.e., a pair of pure minmaximizer and pure maxminimizer strate- gies, for player 1 and player 2, respectively).
Do not draw the extensive form game tree explicitly (it is too big), and do not try to describe the pure minimax profile in terms of moves from explicit nodes on the explicit game tree (again, that would be too big and unmanagable). Instead, de- scribe the pure strategies of the two players in the minimax profile
8,8,4 5,4,5
v1 2,2,7
5, 5, 5 7, 9, 7
s v2 t
3. (a)
more intuitively and succinctly, by describing exactly how each player should move and react to the other player’s prior possi- ble moves/choice(s). Explain why the pure strategies you have described constitute a minimax profile.
[20 points] Recall Rosenthal’s Theorem, namely that every finite congestion game has a pure Nash Equilibrium. In the proof we gave in the lecture slides for Rosenthal’s theorem, we defined the potential function φ(s), which for any pure strategy profile s is defined as:
nr (s)
φ(s) := X X dr(i)
r∈R i=1
Later in the proof we claimed that φ(s) can also be expressed as a different nested sum, but we didn’t prove that fact, and instead said “check this yourself”. This question asks you to prove that fact: Prove that for any pure strategy profile s the following equality holds:
n
φ(s) = X X d (n(i)(s)) rr
i=1 r∈si
5,4,8
8,9,4 v3
Figure 2: Question 3
3, 6, 7
(b) Consider the atomic network congestion game, with three players, described by the directed graph in Figure 2.
In this game, every player i (for i = 1,2,3) needs to choose a directed path from the source s to the target t. Thus, every
4. (a)
player i’s set of possible actions (i.e., its set of pure strategies) is the set of all possible directed paths from s to t.
Each edge e is labeled with a sequence of three numbers (c1, c2, c3). Given a profile π = (π1, π2, π3) of pure strategies (i.e., s-t-paths) for all three players, the cost to player i of each directed edge, e, that is contained in player i’s path πi, is ck, where k is the total number of players that have chosen edge e in their path. The total cost to player i, in the given profile π, is the sum of the costs of all the edges in its path πi from s to t. Each player of course wants to minimize its own total cost.
i. [20 points] Compute a pure strategy NE in this atomic net- work congestion game, giving also the total cost for each player in that pure NE. Explain why what you have com- puted is a pure NE.
ii. [10 points] Is the pure NE you have computed in part (i.) pareto optimal in terms of costs, amongst the set of all pure strategy combinations for the players? Explain.
[18 points] Consider a Bayesian game where player 1 (the row player) has 2 possible types, I and II, whereas player 2 (the col- umn player) has only one possible type, J. There is a joint com- mon prior probability distribution p over types given by p(I, J) = 2/3 and p(II, J) = 1/3. In other words, player 1 has probability 2/3 of having type I and probability 1/3 of having type II (and player 2 of course always has the same type J with probability 1), and both players know this common prior probability distribution on types.
Note that after the type of each player has been sampled from the distribution p, player 1 gets to find out its own type, and of course both players also know player 2’s unique type J, but player 2 doesn’t get to find out player 1’s type (it only knows the probabilities with which player 1 has each of its two types). Player 1 has two actions, A and B, and player 2 has two actions, C and D. The payoff bimatrix in the case where player 1 has type I is given by:
CD
A (2, 1) (0, 2)
B (0, 0) (2, 0)
On the other hand, the payoff bimatrix in the case where player 5
(b)
1 has type II is given by:
A (1, 2) (2, 6)
B (2, 4) (3, 1)
Find a Bayesian Nash equilibrium (BNE) in this game, and say what the expected payoff to both players is under that BNE. Justify your answer, and show your calculations.
The auction house Christie’s of London is auctioning a triptych (a series of three related painting) by the famous artist Fracis Bacon, entitled “Three Studies of Isabel Rawsthorne”. We will refer to the three paintings in the triptych series as T1, T2, and T3, respectively.
Suppose that Christie’s hires you as an auction designer, and suppose that you decide to use the Vickery-Clarke-Groves mech- anism as an auction, in order to determine which bidder should get which part(s) of the triptych, and at what price. Suppose that there are only three bidders. The three bidders’ names are: Susanne (S), Lakshmi (L), and Bill (B).
Since you are running a VCG-based auction, you ask each bidder to give you their valuation for every subset of the paintings in the triptych, as part of the bidding process. Suppose that the valuation functions vS , vL, and vB that you receive from the three bidders, S, L, and B, respectively, are as follows (the numbers denote 106 pounds):
valuation
i. [20 points] Give a VCG outcome for this auction. In other words, specify, in the VCG outcome, which bidders will get which of the painting(s), and what price they will each pay for the painting(s) they get. Justify your answer, and show your calculations.
ii. [12 points] Is the VCG outcome you have calculated in part (a) unique? If not, are the VCG prices paid by each player
CD
vi(∅) vi(T1) vi(T2) vi(T3) vi(T1, T2) vi(T1, T3) vi(T2, T3) vi(T1, T2, T3)
bidder i
i:=S 0 8 9 3 25 17 18 30 i:=L 0 5 6 7 16 12 23 27 i:=B 0 4 6 6 15 21 18 29
the same in all VCG outcomes? Justify your answer, and show your calculations.
