COMP326 Assignment 2 (10% of the final mark)
Due: 12:00 (noon) on Monday, 29 April 2019
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.
Please be aware of the University guidelines on plagiarism and collusion. The marks for late
submissions will be affected in accordance with the University’s Code of Practice on Assessment.
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
• (5 marks) Describe the valuations of each player over A.
• (15 marks) ”Run” the VCG mechanism (compute the allocation and the Clarke
payments).
2. (20 marks) Run the Gale-Shapley algorithm for the example in page 13 of [1].
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) (10 marks) strategy-proof, (b) (5 marks) onto,
(c) (5 marks) anonymous.
4. (20 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: < v1∗ = 12,S1∗ = {a,c,d,e} >,< v2∗ = 14,S2∗ = {b,c,e,f} >,< v3∗ = 6,S3∗ = {a} >,< v4∗ = 5,S4∗ = {e} >,< v5∗ = 9,S5∗ = {f} >,< v6∗ = 20,S6∗ = {c,d,e,f} >.
1
5. (20 marks) Consider the algorithm of Lehmann, Lehmann and Nisan (LLN) [3], that we discussed in the second set of slides for Combinatorial Auctions.
(a) Show that the LLN algorithm cannot be truthfully implemented for submodular valuations, that is there is no way to define payments to make this allocation rule truthful.
(b) Construct an instance for which the LLN algorithm has approximation ratio of 2 for submodular valuations.
Hint: For (a) use Weak Monotonicity (Section. 9.5.2, Theorem 9.29 in [2]. Try to use a submodular valuation which is not additive.).
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.
[3] B. Lehmann, D. J. Lehmann and N. Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior 55(2): 270-296 (2006).
2