这个作业是解决博弈论相关的问题

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

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。