UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
April 2020 13:00 to 15:00
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. This is an OPEN BOOK examination.
Year 4 Courses
Convener: T.Komura
External Examiners: S.Rogers, S.Kalvala, H.Vandierendonck
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Consider the following 2-player normal form (bimatrix) game:
(3,4) (3,3) (4,7) (6,5) (5,8) (1,1) (7, 3) (3, 1) (3, 8)
Compute all in this game. Explain why there are no other Nash equilibria, other than the ones you have computed.
(b) Give an example of a 2-player finite extensive form game which does not satisfy perfect recall. (Describe the game by showing its game tree, labeled to indicate which player controls each node, what all the information sets and actions are, and what the payoffs at the leaves are, etc.) Explain why the game you have provided doesn’t satisfy perfect recall.
(c) Recall that a 2-player finite game, where player 1’s set of pure strategies is S1 and player 2’s set of pure strategies is S2, is called symmetric if S1 = S2 = A, and for all a, a′ ∈ A, u1(a, a′) = u2(a′, a). (Intuitively, the game “looks the same” from the point of view of both players.)
i. Prove or disprove the following statement:
Every 2-player symmetric game in which both players have ex- actly 2 pure strategies (i.e., where |S1| = |S2| = 2), has a pure .
ii. Prove or disprove the following statement:
Every 2-player symmetric game in which both players have ex- actly 3 pure strategies (i.e., where |S1| = |S2| = 3), has a pure .
Page 1 of 4
Consider the following Linear Program (LP).
Maximize −x1 + 2×2 Subject to:
−x1 + x2 + x3 ≤ 5 3×2 + x3 = 8
i. Find the dual LP for this LP.
ii. Compute an optimal feasible solution for both the original LP and the dual LP.
(b) Consider the following 2-player normal form (bimatrix) game:
(3,4) (6,2) (1,3) (2,8) (7,7) (3,7) (1, 1) (2, 2) (4, 1)
What is the price of anarchy in this game? Explain your answer.
(c) Consider a finite 2-player Bayesian Game, G, where the set of possible types of each player i is Ti = {−1, +1}, the set of actions that each player i has is Ai = {0, 1}, and where the utility functions of the two players are defined as follows: for all a1 ∈ A1,a2 ∈ A2,t1 ∈ T1, and t2 ∈ T2,
u1(a1, a2, t1, t2) = t2a1 + t1a2, and u2(a1, a2, t1, t2) = −(t2a1 + t1a2).
Finally, the common prior probability distribution, p, on the types of the players in the Bayesian game G is as follows: p(−1, −1) = 1/2 and p(+1, +1) = 1/2 (and all other combinations of types have probability 0).
Find a pure Bayesian Nash equilibrium for this game (it does exist).
What is the expected payoff to player 1 in this pure Bayesian Nash equilib- rium?
[5 marks ] [6 marks ]
[7 marks ]
Page 2 of 4
[5 marks ] [2 marks ]
Figure 1: extensive form game
Consider the 2-player extensive form game (of imperfect information) de- picted in Figure 1. (At leaves, the top payoff is for player 1, and the bottom payoff is for player 2.)
Compute all subgame-perfect (described in terms of behav- ior strategies) in this game.
In a VCG-based auction, three distinct paintings are being auctioned simul- taneously. Let us denote the set of these three paintings as E = {1, 2, 3}. Suppose there are three potential buyers (bidders), A, B, and C, who pro- vide their claimed valuation functions vA, vB, and vC for this auction. For each subset E ′ ⊆ E of paintings, vx (E ′ ) denotes the valuation in British pounds that player x has for obtaining the subset E′ of the paintings:
[10 marks]
bidder x vx({}) vx({1}) vx({2}) vx({3}) vx({1, 2}) vx({1, 3}) vx({2, 3})
x:=A x:=B x:=C
vx({1, 2, 3}) 0 4 2 5 7 6 8 10
0 3 6 7 8 8 8 9 0 3 8 3 10 12 13 14
A VCG allocation outcome for this auction is specified by a partition of the paintings {1,2,3} into three disjoint subsets EA,EB,EC ⊆ {1,2,3}, such that EA (EB and EC) is the set of paintings allocated to bidder A (respectively, to bidder B and to bidder C). Note: some of these sets may be empty. Each bidder will also be asked to pay a certain amount (in British pounds), pA, pB, and pC, respectively, for their allocation, by the VCG mechanism. (You can assume the bidders bid their true valuation functions, because VCG is incentive compatible.) What are VCG allocations and payments for this auction? In other words, which items will each bidder get, and what price will each pay for their items, if the VCG mechanism is used?
Page 3 of 4
[10 marks]
(c) Consider an n-player finite game, G, with players N = {1,…,n}, where the payoff functions ui(s) for all players i ∈ N have the folowing structure: for all combinations of pure strategies s = (s1,…,sn) ∈ S1 × … × Sn, ui(s) = f(s) + gi(s), where f(s) is the same function for all players, and where gi(s) is a function, specific to player i, whose value does not depend on player i’s own pure strategy si. In other words, for all players i ∈ N, for all si, s′i ∈ Si, and all s−i ∈ S−i, gi(s−i; si) = gi(s−i; s′i).
Prove that the finite game G, with payoff functions (u1, . . . , un), has a pure Nash equilibrium.
Page 4 of 4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com