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

PAPER CODE NO. EXAMINER: Antony McCabe Tel. No. 0151 794 4504
COMP326 DEPARTMENT: Computer Science
SECOND SEMESTER EXAMINATIONS 2022/23
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 = 12 w2 = 4 w3 = 8 w4 = 5 w5 = 2 w6 = 5
m = 3 machines with speeds
s1 = 3 s2 = 2 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
2
x + 14
8x 2×2
3x + 2
Figure 1: Wardrop Game
(a) (2 marks) Show that in a Wardrop equilibrium no flow will be sent along the edge (u,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. More
precisely, for any strategy profile, S = (P1, …Pk ), of k players, if ke players use edge e of cost
ce, each of the ke players pays ce/ke for that edge. Show that the price of anarchy is at least
k, where k is the total number of players.
Hint: Show that there exists an instance G of k players that has a Nash equilibrium A with
cost(A) ≥ k · opt(G).
PAPER CODE COMP326 page 2 of 5 Continued
QUESTION TWO
1. (5 marks) Recall that the Monotonic property for a social choice function, f, is defined as :
”For any L and L
′
if f(L) = a and for every individual i and every alternative b if a >i b and
a >i
′ b then f(L
′
) = a.”
Does the Facility Location setting verify the Monotonic property i.e., When all preferences
are single-peaked, does every social choice function defined as f(L) = med(p1 … , pn, y0, … , yn)
where the yi are constants and pi
is the peak of Li satisfy the Monotonic property Explain
your answer.
2. 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. Consider the social
choice rule f defined as follows:
f( ) = sup{y|y ≤ |{pi ≥ y}|}.
(a) (10 marks) Show that f is strategy-proof.
(b) (7 marks) Show that there exist fixed points y0, … , yn, such that
f( ) = med{p1, p2, … , pn, y0, … , yn}.
(c) (3 marks) Is this mechanism 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_xfffe_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
3
3
4
8
2
3
8
Figure 2: Path-Auction problem
2. Consider a multi-unit auction with three identical items and five players. The valuations for
each player getting an item are as follows: v1 = 2, v2 = 8, v3 = 6, v4 = 10, v5 = 1.
(a) (2 marks) Compute the allocation and the payments for the Vickrey-Clarke-Groves (VCG)
mechanism with Clarke pivot payments.
(b) Consider a mechanism that runs three consecutive rounds of the (single-item) Vickrey
auction.
i. (2 marks) Compute the allocation and the payments for this mechanism. Assume
that the players each bid their valuation, and that any player who has received an
item has a valuation of 0 for any further item.
ii. (5 marks) Is this mechanism truthful Justify your answer.
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 ences as follows
h4 1 h3 1 h1 1 h5 1 h2
h1 2 h5 2 h2 2 h3 2 h4
h4 3 h1 3 h3 3 h5 3 h2
h3 4 h4 4 h2 4 h5 4 h1
h2 5 h4 5 h3 5 h1 5 h5
PAPER CODE COMP326 page 4 of 5 Continued
QUESTION FOUR
1. (a) (5 marks) Run the male-proposal Gale-Shapley algorithm (show all steps) for the follow ing instance
w4 m1 w1 m1 w3 m1 w2
w3 m2 w1 m2 w2 m2 w4
w3 m3 w4 m3 w1 m3 w2
w1 m4 w3 m4 w4 m4 w2
m4 w1 m2 w1 m3 w1 m1
m3 w2 m1 w2 m4 w2 m2
m4 w3 m2 w3 m3 w3 m1
m1 w4 m4 w4 m3 w4 m2
(b) (3 marks) Does the Gale-Shapley algorithm always terminate Justify your answer.
2. (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
= 8, S

1 = {c},
v2
= 11, S

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

3 = {a, b},
v4
= 6, S

4 = {b, c},
v5
= 15, 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) What does the virtual valuation for a bidder i represent
(b) Consider an auction with three players and one item. All the valuations are drawn from
the uniform distribution in [0, 1], v1, v2, v3 ～ U[0, 1].
i. (7 marks) Compute the expected revenue of the Vickrey auction with reserve price
r = 3/4.
PAPER CODE COMP326 page 5 of 5 End