UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Thursday 12 th May 2016 09:30 to 11:30
INSTRUCTIONS TO CANDIDATES
Copyright By PowCoder代写 加微信 powcoder
Answer any TWO questions.
All questions carry equal weight. CALCULATORS MAY NOT BE USED IN THIS EXAMINATION
Year 4 Courses
Convener: I. Examiners: A. Burns, A. Cohn, P. Healey, T. Field, T. HIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Consider an n-player strategic form (i.e., normal form) game, where Si = {1,…,mi} is the set of pure strategies for player i. Let s = (s1,…,sn) ∈ S := S1 × . . . Sn, be a combination of pure strategies for all players, and let ui(s) denote the payoff to player i under that combination.
Consider a profile of mixed strategies, x = (x1, . . . , xn), for the players in this game. For each player i, xi defines a probability distribution on the pure strategies Si, i.e., xi(j) ≥ 0 for all i ∈ Si, and nj=1 xi(j) = 1.
Give an algebraic expression for the expected payoff, Ui(x), to player i under the profile x of mixed strategies, in terms of x and ui(·).
In such a game, for a positive real number ε > 0, define mathematically what it means for a profile x′ = (x′1, . . . , x′n), to be a ε-Nash equilibrium.
Consider the following bimatrix (i.e., 2-player) game: (4,4) (1,1)
(2, 2) (3, 3)
Compute all the different Nash equilibria in this game. Justify why what you have computed constitutes all NEs. Also, compute the expected payoffs to both players under each NE.
Recall that the price of anarchy in a game is the maximum total social wel- fare (sum of everyone’s expected payoffs) obtained using any mixed strategy profile, divided by the minimum total social welfare obtained using any Nash equilibrium profile.
Compute the price of anarchy in the bimatrix game given in part (c) of this question.
Consider the zero-sum 2-player matrix game specified by the following payoff matrix for player 1 (the row player):
135 A=724
Describe a linear program (an LP) with 3 variables, (x1, x2, v), such that an optimal feasible solution (x∗1, x∗2, v∗) for this LP gives a minmaximizer mixed strategy for player 1 in (x∗1, x∗2), and such that the optimal value of the LP’s objective, v∗, is precisely the value of above zero-sum game.
Compute the value of the above zero sum game, and compute a minmaxi- mizer strategy for player 1.
Calculate the dual LP for the LP you have given in the answer to part (e).
Page 1 of 3
[2 marks ] [3 marks ]
[7 marks ]
[3 marks ]
[6 marks ] [4 marks ]
Describe the rules of a Vickrey auction for a single item, and describe the crucial “incentive compatibility” (or truthfulness) property that this kind of auction posesses, when viewed as a game between bidders who are maximiz- ing their utility (which is equal to their private valuation for the outcome minus their cost).
(b) Suppose there are two indistinguishable items being auctioned simultane- ously (for example, two identical silver candle sticks), and two bidders, 1 and 2.
The outcome of this auction is specified by a pair of numbers: j1,j2 ∈ {0,1,2}, such that j1 (j2, respectively) is the number of items allocated to bidder 1 (bidder 2, respectively), and such that j1 + j2 ≤ 2.
Each bidder i ∈ {1, 2} has a valuation function, vi(ji), which is its value (in British pounds) for getting ji ∈ {0, 1, 2} items.
Suppose their valuation functions are defined by: v1(0) = 0, v1(1) = 9, v1(2) = 13, v2(0) = 0, v2(1) = 10, v2(2) = 15.
Calculate the VCG allocations, and VCG payments by the two bidders, for this auction.
Explain why we can assume that the bidders will bid their true valuation functions, given the known properties of the VCG mechanism.
(c) Recall that if C is a finite set of outcomes, and if L is the set of all possible linear orderings of the set C, then a social choice function is a function f : Ln → C that aggregates the orderings on C given by n different individuals into a “social choice” outcome.
Explain what it means to say that social choice function f is “incentive compatible” (or, equivalently, “strategy proof”).
(d) Explain what it means for a social choice function to be a “dictatorship”.
(e) State the Gibbard-Satterthwaite Theorem (which states the impossibility of a social choice function that has several desirable properties).
[10 marks ]
[4 marks ] [3 marks ]
[4 marks ]
Page 2 of 3
[4 marks ]
Kuhn’s theorem for finite extensive form games of perfect information says that every such game has a Nash equilibrium in pure strategies. The proof of Kuhn’s theorem yields an algorithm for computing such a pure NE, and in fact for computing a pure subgame-perfect NE.
Describe the algorithm for computing a subgame-perfect NE. (Do so in English; you do not need to give pseudo-code; just explain it enough so that it is clear how it works).
(b) Define a coarse correlated equilibrium for a finite n-player normal form game, and describe a method to compute a coarse correlated equilibrium.
(c) Recall that an atomic network congestion game with n players is specified by a directed graph, where each player i needs to obtain as a “resource” a directed path from a given source vertex Si to a given target vertex Ti. Thus, player i’s set of possible actions (i.e., its set of pure strategies) are all possible directed paths from Si to Ti.
Suppose there is indeed a directed path from Si to Ti for all players i.
Suppose that, given a profile s = (s1,s2,…,sn) of strategies for all the players, the cost to player i in the profile s is the sum, over all edges e that are in its chosen path si from Si to Ti, of the total number of players who have chosen that edge e in their chosen path (i.e., in their chosen strategy).
Each player of course wants to minimize their own total cost.
Describe an algorithm for computing a pure NE in such an atomic network congestion game.
(d) Give an example of a bimatrix game which has exactly two Nash equilibria (of any kind, pure or mixed). Give the two NEs, and explain briefly why there are no others.
[7 marks] [7 marks]
Page 3 of 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com