COMP559 Assignment 2 - Part 1 (5% of the final grade)
Due: 12:00 (noon) on Thursday, 29 April 2021
Please submit your solutions electronically (in PDF format) at the electronic submission system
of the Computer Science Department which you can find at the following url.
https://sam.csc.liv.ac.uk/COMP/Submissions.pl.
Marking of subquestions will be based on the marking descriptors for level ’M’ modules pub-
lished in Section D.2.5 in the Postgraduate Student Handbook. Please be aware of the University
guidelines on plagiarism and collusion. The marks for late submissions will be affected in ac-
cordance with the University’s Code of Practice on Assessment published in Section 2.2 of the
Postgraduate Student Handbook.
Total: 100 marks
1. Consider an auction with three items a,b,c and three players. The valuations for getting
a single item is as follows v1(a) = 7, v1(b) = 11, v1(c) = 5, v2(a) = 10, v2(b) = 5, v2(c) =
12, v3(a) = 13, v3(b) = 12, v3(c) = 4. Assume that the valuation for getting a set S of
more than a single item for each player i are given by
(a) vi(S) =
∑
j∈S vi(j).
(b) vi(S) = maxj∈S{vi(j)}.
First, describe in detail the set of possible outcomes A, assuming that we care only about
allocations that assign all the items. Then, for all the above cases
• (10 marks) Describe the valuations of each player over A.
• (15 marks) ”Run” the VCG mechanism (compute the allocation and the Clarke
payments).
2. (25 marks) Consider a single item setting with n ≥ 2 bidders. Show that the social
choice rule that always allocates the item to the smallest bidder cannot be truthfully
implemented. Hint: Use Weak Monotonicity (Section. 9.5.2, Theorem 9.29 in [2]. ).
3. Show the only if direction of Theorem 10.2. That is, show that if the social choice is
f() = med{p1, p2, . . . , pn, y1, . . . , yn−1},
then f is
(a) (13 marks) strategy-proof,
(b) (6 marks) onto,
(c) (6 marks) anonymous.
1
4. (25 marks) Run the Greedy mechanism (compute the allocation and the payments) for
the following Combinatorial Auction instance with 6 single-minded bidders and 6 items:
< v∗1 = 12, S∗1 = {a, c, d, e} >,< v∗2 = 14, S∗2 = {b, c, e, f} >,< v∗3 = 6, S∗3 = {a} >,< v∗4 =
5, S∗4 = {e} >,< v∗5 = 9, S∗5 = {f} >,< v∗6 = 20, S∗6 = {c, d, e, f} >.
References
[1] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American
Mathematical Monthly, 69(1):9–15, 1962.
[2] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-
bridge University Press, 2007.
2












































学霸联盟