xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

程序代写案例-COMP559-Assignment 2

时间：2021-04-18

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

学霸联盟

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

学霸联盟