# 博弈论代写 | 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