UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR11020 ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Thursday 7 th May 2015 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. Cohn, T. Field
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
Describe what it means for a 2-player zero-sum win-lose extensive form game of perfect information (not necessarily finite) and without any chance nodes, to be determined.
(b) Are all such games described in (a) determined?
(c) Consider the following bimatrix (i.e., 2-player) game:
(2,4) (7,1) (1,7) (8,4) (8,4) (1,8) (8,1) (5,4) (4, 4) (4, 4) (4, 5) (7, 2)
Compute all the Nash equilibria in this game, and justify why they constitute all NEs. Furthermore, compute the expected payoffs to both players under each NE.
(d) Consider the following LP:
Minimize x4 Subject to:
2×1 +6×2 +7×3 ≤x4 8×1 +4×2 +6×3 ≤x4 4×1 +5×2 +6×3 ≤x4 x1 + x2 + x3 = 1 x1,x2,x3 ≥0
Use any method you wish in order solve this LP, meaning find an optimal feasible solution for this LP, and compute the optimal objective value.
[3 marks ] [2 marks ]
[7 marks ]
Show your work.
(e) Find the dual for the LP given in the previous question (part (d)). (Just state the dual LP. You do not need to do anything with it.)
[8 marks ] [5 marks ]
Page 1 of 3
2. (a) (b)
Define what a pure strategy is for a player in a Bayesian game.
Suppose there are two items A and B, being auctioned, and two bidders, 1 and 2. The auction will use the Vickrey-Clarke-Groves (VCG) mechanism to calculate both the payments that each bidder will pay and the allocations of the items to the two bidders. We assume each bidder i has a valuation func- tion vi(X) which defines how much (in British pounds) getting the subset X ⊆ {A, B} is worth to player i.
Suppose v1(∅) = 0, v1({A}) = 4, v1({B}) = 5, and v1({A, B}) = 14. Suppose v2(∅) = 0, v2({A}) = 10, v2({B}) = 3, and v2({A, B}) = 13.
Calculate the VCG allocations, and VCG payments by the two bidders, for this auction. Explain why your answers are correct.
(You can assume that the bidders will bid their true valuation functions since, as we know from class, the VCG mechanism is incentive compatible.)
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 into a “social choice” outcome.
Explain what it means to say that a social choice function f “can be strate- gically manipulated”, and what it means to say that f is “incentive com- patible” (or, equivalently, strategy proof).
For a finite normal form game, state what it means for a mixed strategy profile x to be Pareto efficient (or Pareto optimal).
Give an example of a finite 2-player game which has infinitely many (NE), but such that none of its NEs are Pareto optimal. Justify why your example satisfies both these conditions.
[3 marks ]
[8 marks ]
[4 marks ] [3 marks ]
[7 marks ]
Page 2 of 3
Describe an iterative algorithm for computing who has a winning strategy starting at each vertex of a finitistic win-lose game on a graph.
(b) Are finitistic win-lose games on graphs memorylessly determined? Explain your answer.
(c) Consider a 2-player “reachability” game on a graph. This is given by G = (V = V1 ∪ V2, E, s, t), where the vertices V of the graph are partitioned into two sets V1 and V2, belonging to players 1 and 2, respectively, and E is the edgerelationE⊆V ×V,s∈V isthestartvertex,andt∈V isthetarget vertex. Player 1’s objective is to reach the target node, t, whereas player 2’s objective is to avoid it. Suppose there are n vertices, i.e., n = |V |. This is clearly a finitistic win-lose game on a graph.
Describe a Linear Program (LP) with one variable xi for each vertex i of V , such that the (unique) optimal solution x∗ of this LP has for each vertex i, x∗i = 1 if and only if player 1 has a winning strategy in the game starting at vertex i.
(d) Explain Braess’s Paradox, by giving examples of routing networks whose links have delays which are a function of the link congestion, and which exhibit this “paradox”. Explain what the “paradox” is.
[6 marks] [3 marks]
Page 3 of 3
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com