联系我们： 手动添加方式: 微信>添加朋友>企业微信联系人>13262280223 或者 QQ: 1483266981

PAPER CODE NO. EXAMINER: Alkmini Sgouritsa Tel. No. 0151 795 4259
COMP326 DEPARTMENT: Computer Science
SECOND SEMESTER EXAMINATIONS 2021/22
Computational Game Theory and Mechanism Design
TIME ALLOWED : Two and a Half Hours
INSTRUCTIONS TO CANDIDATES
Answer ALL questions.
Calculators are permitted.
PAPER CODE COMP326 page 1 of 5 Continued
QUESTION ONE
1. (5 marks) Consider the following instance of the load balancing game:
n = 6 tasks with weights
w1 = 9 w2 = 5 w3 = 12 w4 = 6 w5 = 3 w6 = 5
m = 3 machines with speeds
s1 = 2 s2 = 3 s3 = 5
Run the LPT algorithm on this instance and give the resulting assignment in graphical form.
What is the makespan of this assignment
2. Consider the following instance, Figure 1, of a single commodity Wardrop game (G, r, c)
where a flow of 1 has to be sent from s to t:
s t
u
v
4 2×2
6x x + 17
4x + 2
Figure 1: Wardrop Game
(a) (2 marks) Show that in a Wardrop equilibrium no flow will be sent along the edge (v,t).
(b) (3 marks) Determine the Wardrop equilibrium for (G, r, c).
(c) (4 marks) Construct a new instance (G, r, c

) by replacing each cost function ce with its
marginal cost function ce

.
(d) (3 marks) Determine an optimal flow for the original instance (G, r, c).
(e) (3 marks) Compute the price of anarchy ρ(G, r, c).
3. (5 marks) Consider the global connection games with the equal-division mechanism. Show
that the Price of Stability is at least Hk , where Hk = 1+1/2+1/3+…+1/k is the k-th harmonic
number and k is the number of players.
PAPER CODE COMP326 page 2 of 5 Continued
QUESTION TWO
1. (6 marks) Does the Gibbard-Satterthwaite Theorem apply to the Facility Location setting
Explain your answer.
2. Consider the Facility Location setting on the line and suppose that there are n players with
Single-Peaked preferences _x0017_ 1, … , n with peaks p1, … , pn respectively. Consider the social
choice rule f that assigns the facility to the rightmost declared position.
(a) (7 marks) Show that f is strategy-proof.
(b) (6 marks) Show that there exist fixed points y1, … , yn 1, such that
f( ) = med{p1, p2, … , pn, y1, … , yn 1}.
3. (6 marks) Consider the Facility Location setting on the line and suppose that there are n
players with Single-Peaked preferences 1, … , n with peaks p1, … , pn respectively. Show
that if a social choice rule is Pareto-optimal then it is unanimous and onto.
PAPER CODE COMP326 page 3 of 5 Continued
QUESTION THREE
1. (8 marks) Apply the VCG mechanism (compute the path and the payments) for the Path Auction problem of Figure 2, where the numbers on the edges denote the true costs of the
agents. (Recall, that in the Path-Auction problem, the agents own the edges of the graph, and
they are cost minimizers. Assume that the designer wants to send a single message from
node s to node t and the total cost is the sum of costs of the edges on the used s-t path.)
s t
v u
w
2
2
3
7
1
2
7
Figure 2: Path-Auction problem
2. (a) (5 marks) Show that VCG satisfies Weak Monotonicity.
(b) (4 marks) Consider a combinatorial auction setting with a set of items M = {1, … , m}
and n bidders with general valuations vi
: 2M → R+, for i = 1, … , n, and n ≥ 2. Consider
the allocation rule that assigns all the items to the player with minimum vi(M). Can we
truthfully implement this rule Justify your answer.
Hint: You can use Weak Monotonicity.
3. (8 marks) Run the Top Trading Cycle Algorithm (show all steps) for the following instance of
the House Allocation problem with 5 owners (1, … , 5) and 5 houses (h1 … , h5), and prefer_xfffe_ences as follows
h1 _x001f_ 1 h2 1 h3 _x001f_ 1 h4 _x001f_ 1 h5
h1 _x001f_ 2 h3 _x001f_ 2 h5 _x001f_ 2 h2 _x001f_ 2 h4
h4 3 h2 3 h5 3 h1 3 h3
h5 4 h4 4 h2 4 h3 4 h1
h1 5 h3 5 h2 5 h5 5 h4
PAPER CODE COMP326 page 4 of 5 Continued
QUESTION FOUR
1. (5 marks) Run the male-proposal Gale-Shapley algorithm (show all steps) for the following
instance
w1 _x001f_ m1 w4 _x001f_ m1 w3 m1 w2
w2 m2 w1 m2 w3 m2 w4
w2 m3 w4 m3 w1 m3 w3
w1 m4 w3 m4 w2 m4 w4
m2 w1 m1 w1 m4 w1 m3
m4 w2 m1 w2 m3 w2 m2
m4 w3 m2 w3 m3 w3 m1
m3 w4 m1 w4 m4 w4 m2
2. (a) (3 marks) Consider a Combinatorial Auctions setting. Give the definition of a single minded valuation.
(b) (7 marks) Run the Greedy mechanism (compute the allocation and the payments) for
the following instance of a Combinatorial Auction with 5 single-minded bidders and 6
items:
v1
= 10, S

1 = {c},
v2
= 12, S

2 = {a, c, d, e},
v3
= 5, S

3 = {a},
v4
= 6, S

4 = {b, c},
v5
= 14, S

5 = {b, d, e, f }.
3. In the lectures on profit maximization, we assumed a setting with one item and n bidders with
valuations v1, … , vn, which are drawn independently at random from some known continuous
probability distributions. Let Fi(z) = Pr[vi ≤ z] be the probability distribution function from
which bidder i’s valuation is drawn and let fi(z) = dFi(z)/dz be its density function.
(a) (3 marks) Give the formula of the virtual valuation for a bidder i with valuation vi
.
(b) Consider an auction with two players and one item. Both the valuations are drawn from
the uniform distribution in [0, 1], v1, v2 ～ U[0, 1]. Recall that in that case it holds Fi(z) =
z, fi(z) = 1, for i = 1, 2.
i. (5 marks) Compute the expected revenue of the Vickrey auction.
ii. (1 mark) Is there any truthful auction with even higher revenue Justify your answer.
iii. (1 mark) Provide the virtual valuations for the two players.
PAPER CODE COMP326 page 5 of 5 End