UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Tuesday 8 th May 2018 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: S. Rogers, A. Donaldson, S. Kalvala
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Consider the finite 2-player zero-sum game specified by the following (3 × 2) payoff matrix, A, for player 1 (the row player):
5 8 A=5 5
The entry Ai,j of this matrix specifies the payoff to player 1 if it plays its i’th pure strategy (i’th row), and player 2 plays its j’th pure strategy (j’th column).
i. Specify a corresponding linear program (LP), such that the objective value of the LP in any optimal feasible solution is precisely the “mini- max value” of this 2-player zero-sum game, and such that any optimal feasible solution for the LP also provides an optimal “maxminimizer” mixed strategy for player 2 (the column player), whose goal is to mini- mize the expected payoff of player 1.
ii. Calculate the minimax value for this game, and also calculate a Nash equilibrium for this game.
(b) Consider the following linear programming problem, given as a “feasible dic- tionary”, with “basis” {x1, x2}:
Maximize: 5 + 6×3 + 2×4 Subject to:
x1 = 8−2×3−3×4 x2 = 6−3×3−7×4
x1 ≥0,×2≥0,×3≥0,×4≥0
i. What is the “basic feasible solution” (BFS) corresponding to the basis
{x1 , x2 } of this feasible dictionary?
ii. Apply one “pivot” step (of the simplex algorithm) to this feasible dic- tionary, in order to move the variable x3 into the basis and move the variable x2 out of the basis.
Show the resulting dictionary after this pivot step, including the result- ing new objective function.
iii. Is the new dictionary obtained via this pivot step a feasible dictionary? Explain your answer.
iv. What is the optimal (maximum) feasible value for the objective of this LP? Explain your answer.
Page 1 of 3
[2 marks ]
[6 marks ] [2 marks ] [4 marks ]
[4 marks ] [7 marks ]
Figure 1: extensive form game
Consider the following 2-player normal form (bimatrix) game:
(9,2) (4,9) (3,8) (2,2) (5,5) (5,5) (8, 6) (5, 5) (7, 7)
Compute all Nash equilibria (pure or mixed) in this game. Justify why what you have computed constitutes all NEs.
(b) Prove that for any positive integer n ≥ 1, there exists a 2-player finite game with exactly n pure Nash equilibria and no other (mixed) Nash equilibria.
(c) 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 a subgame-perfect equilibrium for this game.
[5 marks] [10 marks]
[10 marks]
Page 2 of 3
Recall that if C is a finite set of outcomes, and L is the set of all possible linear orderings of C, a social choice function, f : Ln → C, aggregates the orderings on C given by n different individuals (voters) into a “social choice” outcome.
Explain what it means to say that social choice function f can be “strate- gically manipulated” by voter i ∈ {1, . . . , n}.
State the Gibbard-Satterthwaite Theorem (regarding the existence/non- existence of incentive-compatible social choice functions with certain prop- erties).
In a VCG-based auction, three distinct Faberge eggs are all being auctioned simultaneously. Let us denote the set of these three eggs 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 eggs, vx(E′) denotes the valuation in (millions of) British pounds that player x has for obtaining the subset E′ of the eggs:
[3 marks ]
bidder x vx({}) vx({1}) vx({2}) vx({3}) vx({1, 2}) vx({1, 3}) vx({2, 3})
vx({1, 2, 3}) x:=A 0 9 6 10 16 20 17 24 x:=B 0 5 8 9 14 21 15 23 x:=C 0 1 11 1 12 2 12 13
A VCG allocation outcome for this auction is specified by a partition of the eggs {1,2,3} into three disjoint subsets EA,EB,EC ⊆ {1,2,3}, such that EA (EB and EC) is the set of eggs allocated to bidder A (respectively, to bidder B and to bidder C). Note that some of these sets may be empty. Each bidder will also be asked to pay a certain amount (in millions of British pounds), pA, pB, and pC, respectively, for their allocation, by the VCG mechanism. (You can assume the bidders will bid their true valuation functions, because the VCG mechanism is incentive compatible.)
What are the VCG allocations, and VCG payments, for this auction? In other words, which items will each bidder get, and what price will each pay for the items they get, if the VCG mechanism is used?
(d) Suppose instead that a simultaneous auction is being conducted for a set E of hundreds of items, with hundreds of bidders. Suppose that bidders are all “single-minded”, meaning that for each bidder x, there is a particular subset Ex ⊆ E, and a positive real value wx > 0, such that for all E′ ⊆ E, if Ex ⊆ E′, then vx(E′) = wx, and otherwise (if Ex ̸⊆ E′) then vx(E′) = 0. Thus, in order to completely specify their valuation functions, each bidder x simply provides their set Ex and their value wx > 0 for that set.
Explain why for such a large auction, even if all bidders are known to be single-minded and will specify their valuations compactly as above, it may not be a good idea to use the VCG mechanism.
Page 3 of 3
[15 marks]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com