UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Tuesday 16 th May 2017 14:30 to 16:30
INSTRUCTIONS TO CANDIDATES
Copyright By PowCoder代写 加微信 powcoder
Answer any TWO of the three questions. If more than two questions are answered, only QUESTION 1 and QUESTION 2 will be marked.
All questions carry equal weight. CALCULATORS MAY NOT BE USED IN THIS EXAMINATION
Year 4 Courses
Convener: I. Examiners: A. Cohn, A. Donaldson, S. Kalvala
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
1. Let A be the (n × m) integer payoff matrix that defines the payoffs for player 1 (the row player, who has n pure strategies) in a finite 2-player zero-sum matrix game.
(a) Give an expression for the expected payoff for player 2 in this game, if player 1 plays a mixed strategy given by an n-dimensional vector x and player 2 plays a mixed strategy given by an m-dimensional vector y.
(b) Define mathematically what a minimax profile for such a game is, and what the minimax value of such a game is.
(c) Consider now the following specific (2 × 3) payoff matrix, A, for player 1 (row player) in a 2-player zero-sum game:
524 A=365
Compute a minimax profile, and the minimax value, for this game. (Show your calculations.)
(d) Consider the following linear program (LP):
Maximize 5×1 + 3×2 Subject to:
2×1 + 3×2 ≤ 8
x1 + x2 ≤ 6
x1 + 4×2 = 4 x1,x2 ≥0
Compute the dual LP for this LP.
(e) Solve the LP given in part (d) of this question, meaning, compute an optimal solution for it (if one exists), and (if so) compute the optimal value of the objective. (You can use any method you like to solve this LP.)
[3 marks ] [5 marks ]
[7 marks ]
[5 marks ]
[5 marks ]
Page 1 of 3
v 2,4,6 v 14
3,5,9 2,3,8 1,3,9 2,3,5
s 1,4,7 v2 5,3,8
t 2,7,9 2,5,6 4,5,9
v3 11, 12, 13 v6
Figure 1: An atomic network congestion game
Consider the following 2-player normal form (bimatrix) game:
(8,1) (2,3) (10,4) (4,6) (3,12) (8,6) (5,3) (9,1) (5, 9) (4, 24) (11, 2) (6, 11)
Compute all Nash equilibria in this game. Justify why what you have com- puted constitutes all Nash equilibria.
(b) Compute the price of anarchy for the game given in part (a) of this question. (It suffices for you give an explicit expression using fractions for this quantity, without computing the exact value of the expression.)
(c) Consider the atomic network congestion game, with three players, described by the directed graph in Figure 1.
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.
Compute a pure strategy in this atomic network conges- tion game. Compute the total cost to each player in the Nash equilibrium you have computed.
Page 2 of 3
[10 marks]
Figure 2: extensive form game
Consider the 2-player extensive form game (of imperfect information) de- picted in Figure 2. (At leaves, the top payoff is for player 1, and the bottom payoff is for player 2.) Compute both: (i) a subgame-perfect equilibrium for this game, and (ii) a Nash equilibrium which is not subgame perfect.
In a VCG-based auction, four identical items are being auctioned simultane- ously. Suppose there are two buyers (bidders), A and B, who provide their claimed valuation functions vA and vB, as follows; vx(j) denotes the value, in pounds, that player x has for receiving j items:
bidder x vx(0) vx(1) vx(2) vx(3) vx(4)
x:=A 0 12 15 19 31
x:=B 0 7 18 29 35
An allocation outcome for this auction is specified by a pair of numbers jA,jB ∈ {0,1,2,3,4}, such that jA (jB) is the number of (identical) items allocated to bidder A (respectively, bidder B), and such that j1 + j2 ≤ 4. Each bidder will also be asked to pay a certain amount (in British pounds), pA and pB, respectively, for their allocation.
What are the VCG allocations, and VCG payments, for this auction? In other words, how many items will each bidder get, and what price will each pay for the items they get, if the VCG mechanism is used.
Suppose that player utilities are given by their true valuation for the outcome minus the price they have to pay for that outcome. Explain why it is then reasonable to assume that both bidders will provide their true valuation functions when they know the VCG mechanism is being used to determine the allocation and payment outcome in such an auction.
Give an example of a 2-player normal form game with exactly 3 Nash equi- libria. Provide the game’s payoff table, and all three of its different NEs.
Page 3 of 3
[10 marks]
[3 marks] [4 marks]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com