COMP326程序代写、代写Java，Python编程

日期：2022-03-20 02:43

COMP326 Assignment 2 (15% of the final mark)

Due: 17:00 on Friday, 1 April 2022

Please submit your solutions electronically (only in PDF format) in CANVAS. Please do

not use red colour in your solutions and include your name and student number.

Failure in the assessment may be compensated for by higher marks in other components of the

module. Marking of subquestions will be based on the marking descriptors of the University’s

Code of Practice on Assessment.

Standard UoL penalty applies for late submission in accordance with the University’s Code of

Practice on Assessment. The strict deadline even for late submissions is two weeks later: 17:00

on Friday 15 April 2022.

Please be aware of the University guidelines on plagiarism and collusion.

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) = 8, v2(a) = 12, v2(b) = 17, v2(c) =

4, v3(a) = 9, v3(b) = 5, v3(c) = 12. 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.

? (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) Consider a multi-unit auction with 2 copies of an item and n ≥ 3 bidders.

Recall that in a multi-unit auction each bidder is interested in a single copy and assume

that each bidder submits a single bid. Show that the social choice rule that always

allocates the copies to the smallest and the second smallest bidder cannot be truthfully

implemented. Hint: Use Weak Monotonicity (Section. 9.5.2, Theorem 9.29 in [1]).

3. Show that if the social choice function 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.

1

4. (20 marks) Run the Gale-Shapley algorithm for the instance below.

w1 m1 w2 m1 w3 m1 w4

w1 m2 w2 m2 w3 m2 w4

w2 m3 w3 m3 w1 m3 w4

w3 m4 w1 m4 w2 m4 w4

m3 w1 m4 w1 m1 w1 m2

m4 w2 m1 w2 m2 w2 m3

m1 w3 m2 w3 m3 w3 m4

m4 w4 m3 w4 m2 w4 m1

5. (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, b, c, d} >,< v?2 = 14, S?2 = {b, c, e, f} >,< v?3 = 5, S?3 = {b} >,< v?4 =

4, S?4 = {e} >,< v?5 = 9, S?5 = {f} >,< v?6 = 20, S?6 = {a, c, d, e} >.

References

[1] N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic Game Theory. Cam-

bridge University Press, 2007.