UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
ALGORITHMIC GAME THEORY AND ITS APPLICATIONS
Thursday 19 th December 2013 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
MSc Courses
Convener: B. Examiners: A. Burns, S. Denham, P. Healey, T. HIS 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 ]
Show your work.
(e) Find the dual for the LP given in the previous question (part (d)).
[8 marks ] [5 marks ]
Page 1 of 4
[7 marks ]
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 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 function 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}) = 3, v1({B}) = 4, and v1({A,B}) = 11. Suppose v2(∅) = 0, v2({A}) = 8, v2({B}) = 3, and v2({A, B}) = 11.
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.)
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.
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).
Explain what it means for a social choice function to be a “dictatorship”.
Recall that the Gibbard-Satterthwaite theorem says that if there are at least 3 choices, i.e., if |C| ≥ 3, then any incentive compatible social choice function f : Ln → C, n ≥ 1, for which all outcomes are possible (i.e., f is a surjective (onto) function), is a dictatorship. Suppose instead there are only two outcomes possible, i.e., that |C| = 2, and furthermore that the number of individuals is n is odd and n > 1. Show that in this case there exists an incentive compatible social choice function which is not a dictatorship.
[3 marks ]
[7 marks ]
[5 marks ]
[4 marks ] [2 marks ]
[4 marks ]
Page 2 of 4
Describe an iterative algorithm for computing who has a winning strategy starting at each vertex of a finitistic win-lose game on a graph.
Figure 1: Atomic network congestion game
(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 verticies 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) Consider the atomic network congestion game, with three players, described by the directed graph in Figure 1.
In this game, player i (for every i = 1, 2, 3) needs to obtain as a “resource” a directed path from source Si to target Ti (any path will do). Thus, player i’s set of possible actions (i.e., its set of pure strategies) are all possible directed paths from Si to T i.
Given a profile (s1, s2, s3) of strategies for all the players, the cost to player i Page 3 of 4
[7 marks] [3 marks]
is the total number of players that have chosen that edge in their chosen path (i.e., in their chosen strategy). (Note that directed edges going in opposite directions between two nodes are considered distinct edges.) The total cost to player i is the sum of the costs (in the given profile of strategies) of all the edges that it has chosen in its path si from Si to Ti.
Each player of course wants to minimize their own total cost.
Find a pure strategy NE in this atomic network congestion game. Also say what the total cost is to each player under this pure strategy NE.
(e) Is there any other pure strategy NE in the congestion game described in part (a)? Explain your answer.
[7 marks] [3 marks]
Page 4 of 4
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com