INFR11020 Algorithmic Game Theory and Applications - Homework 2: Network Congestion Game, Pareto Optimal and VCG Mechanism
Algorithmic Game Theory and Applications: Coursework 2
1. Recall that a Nash equilibrium in an extensive 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 information 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.
Figure 1: Question 2
2. Consider the finite extensive form game of imperfect information depicted 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 your answer.
(b) [24 points] Identify all SPNEs in this game, in terms of “behavior strategies”. Explain why what you have identified constitutes all SPNEs.
(c) [10 points] Are there any other Nash equilibria, other than the SPNEs you have identified, in this game? Explain your answer.
(d) [10 points] Are all the equilibria in this game are “credible”? Ex- plain.
3. (a) [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:
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:
(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 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 network congestion game, giving also the total cost for each player in that pure NE. Explain why what you have computed 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.
4. 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 mechanism 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 trip- tych, as part of the bidding process. Suppose that the valuation func- tions vS , vL, and vB that you receive from the three bidders, S, L, and B, respectively, are as follows (the numbers denote 105 pounds):
- (a) [28 points] Give a VCG outcome for this auction. In other words, specify, in that 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.
- (b) [16 points] Is the VCG outcome you have calculated in part (a) unique? Are the VCG prices paid by the player’s uniquely deter- mined? Justify your answer, and show your calculations.
- (c) [6 points] Comment on the wisdom of choosing the VCG mechanism for this or any auction. Do you think it is a good idea to do so? What if instead of this triptych, Christie’s wanted to do a simultaneous auction of 20 Andy Warhol paintings, and they knew that at least 30 viable bidders want to bid for (subsets of) those paintings. Would you suggest using the VCG mechanism for such an auction? What alternative auction would you use, and why? Explain, briefly.
