博弈论代写 | COMP326 Assignment 2 (10% of the final mark)

这个作业是解决博弈论相关的问题
COMP326 Assignment 2 (10% of the final mark)
Due: 12:00 (noon) on Wednesday, 22 April 2020
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) = P
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:
< 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} >.
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. Cambridge 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