UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Monday 29 th April 2019 09:30 to 11: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: H.Sun
External Examiners: S. Rogers, S. Kalvala , H.Vandierendonck
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Consider the following 2-player normal form (bimatrix) game:
(6,7) (7,3) (3,2) (4,9) (9,8) (4,7) (2, 3) (8, 4) (7, 6)
Compute all in this game. Explain why there are no other Nash equilibria, other than the ones you have computed.
(b) Consider the following Linear Program (LP).
Minimize x1 Subject to:
x1 −4×2 −6×3 ≥8 x2 + x3 ≥ 2
Use one iteration of Fourier-Motzkin elimination to eliminate the variable x2 from this LP. Show the resulting LP (whose variables are only x1 and x3).
Compute an optimal feasible solution for this original LP.
(c) Consider the following mathematical optimization problem, where A is a (m × n) matrix of integers, b is a m-vector of integers, and x = (x1, . . . , xn)T is a n-vector of variables.
Minimize |x1| + |x2| Subject to:
Note that the objective of this optimization problem is not a linear objective: it asks to minimize the sum of the absolute values of x1 and x2 (and absolute values are not linear functions).
Show that nevertheless the above mathematical optimization problem can be re-written, as an “equivalent” linear programming problem (LP), meaning such that an optimal solution to the new LP can be used to recover an optimal solution to this optimization problem, and vice versa, an optimal solution to this optimization problem can also be used to recover an optimal solution to the new LP. (Hint: you may use auxiliary variables in the new LP.) Explain why the LP you have given satisfies this “equivalence”.
Page 1 of 4
[5 marks] [4 marks]
[10 marks]
v 3,4,7 v 14
3,5,4 4,3,3 2,3,9 8,2,8
8,4,7 7,9,6 s v2
t 2,7,9 5,4,6 6,6,9
v3 6,5,7 v6
Figure 1: An atomic network congestion game
(b) Consider the following 2-player normal form (bimatrix) game:
Define the price of anarchy in a normal form game where all payoffs to all players, under all combinations of pure strategies, are positive numbers.
(2,3) (9,1) (1, 9) (8, 7)
What is the price of anarchy in this game? Explain your answer.
(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 con- gestion game. Compute the total cost to each player in the NE you have computed.
(d) Explain an algorithm for computing a pure in an atomic network congestion game. (You do not need to prove why the algorithm is correct, but do indicate which result proved in lectures implies that it is correct.)
Page 2 of 4
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.)
i. This game has infinitely many mixed . Describe all of them. (You can do this by giving inequalities that the probability of certain pure strategies need to satisfy in the mixed strategy profile, in order for it to be an NE.)
ii. Compute a subgame perfect equilibrium in this game, and compute the expected payoffs to the two players for that subgame perfect equilibrium.
iii. Which of the equilibria in this game involve “non-credible threats”?
Explain your answer.
In a VCG-based auction, three identical items are being auctioned simul- taneously. Suppose there are three buyers (bidders), A, B, and C, who provide their claimed valuation functions vA, vB, and vC, as follows; vx(j) denotes the value, in pounds, that player x has for receiving j items:
QUESTION CONTINUES ON NEXT PAGE
Page 3 of 4
[6 marks] [4 marks] [3 marks]
QUESTION CONTINUED FROM PREVIOUS PAGE
bidder x vx(0) vx(1) vx(2) vx(3)
x:=A 0 4 11 15 x:=B 0 7 8 16 x:=C 0 6 10 17
An allocation outcome for this auction is specified by three non-negative integers jA,jB,jC ∈ {0,1,2,3}, such that jA is the number of identical items allocated to bidder A, and likewise jB is the number of items allocated to B, and jC is the number of items allocated to C, such that jA +jB +jC ≤ 3. Each bidder will also be asked to pay a certain amount (in pounds), pA, pB, and pC, respectively, for their allocation.
What are 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.
(c) State the Gibbard-Satterthwaite Theorem regarding social choice functions that aggregrate the preference orders on candidates specified by a number of voters, to determine a “societal choice” winning candidate.
Page 4 of 4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com