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

日期：2022-05-27 12:26

COMP326/COMP559 Tutorial 6 Solutions

1. Roberts’ Theorem states that under certain conditions the only incentive-compatible

mechanisms are the affine maximizers. The Greedy algorithm is an incentive-compatible

mechanism for single-minded bidders that is not an affine maximizer. Explain why

Roberts’ Theorem does not apply.

Solution: Roberts’ Theorem applies for the unrestricted domain of valuations with at

least 3 alternatives.

For example, for every player i, and for any outcome a, vi(a) can potentially take any real

value. This is not the case for combinatorial auctions, and especially for single-minded

valuations.

In the latter case, a bidder i, has some target set S?i . Take an arbitrary outcome a (that

it has to be an allocation of the items). The value for player i for a cannot be any real

value. In particular, it is 0 if his own allocation does not contain the set S?i in a, and

otherwise it is some nonnegative real value, say vi . Also for every other outcome b where

player i gets S?i (or a superset of S

?

i ) her value is again vi and not some arbitrary value.

Therefore the Roberts’ Theorem does not apply, and it is not surprising that there is an

truthful mechanism that is not an affine maximizer.

2. Run the Greedy mechanism (compute the allocation and the payments) for the following

instance with 5 single-minded bidders and 6 items: < v?1 = 10, S?1 = {a, c, d, e} >,< v?2 =

7, S?2 = {b, c, e} >,< v?3 = 4, S?3 = {a} >,< v?4 = 4, S?4 = {e} >,< v?5 = 6, S?5 = {f} >.

Solution:

This is a practice exercise, and it’s a trivial application of the Greedy mechanism. The

Greedy mechanism will assign S?5 to bidder 5 and S?1 to bidder 1 only. These players will

have to pay p5 = 0 and p1 =

7√

3

4

, and all the rest 0.

3. The approximation ratio of the Greedy algorithm is at most

√

m. Construct an example

where the Greedy mechanism achieves an approximation ratio of

√

m for m items.

Hint: You can generalise the example of the slides with 4 items and 5 bidders that gives

an approximation ratio 1.95; the value of the last player can be changed to 40 + ε (for

ε > 0) in order to give an approximation ratio arbitrarily close to 2.

Can you construct an example where the Greedy mechanism achieves an approximation

ratio of

√

m for m items and only 2 bidders?

Solution: First we show how to generalise the example of the slides. For this we consider

m items and m+1 bidders. Bidder i ∈ {1, . . . ,m} has v?i = 1 and S?i = {i}, meaning that

each of the first m bidders wants a different single item for value of 1. The last bidder has

value

√

m+ ε, for an arbitrarily small ε > 0, and wants all items, i.e. v?m+1 =

√

m+ ε and

S?m+1 = M = {1, . . . ,m}. The optimal allocation assigns S?i to bidder i, for i ∈ {1, . . . ,m},

and achieves a social welfare of m. However, the Greedy mechanism assigns all items, i.e.

S?m+1, to the last bidder m + 1 and achieves a social welfare of

√

m + ε, therefore the

approximation ratio tends to

√

m when ε goes to 0.

1

Next we show that the approximation ratio of the Greedy mechanism can be as high

as

√

m, for an instance with m items and 2 bidders. Suppose that the valuations of

the single-minded bidders are described by the pairs < v?1 = m,S1 = {1, ...,m} > and

< v?2 =

√

m + ε, S2 = {1} >, where ε > 0 is an arbitrarily small constant. The optimal

allocation assigns all items to bidder 1, and achieves a social welfare of m. However, the

Greedy mechanism assigns item 1 to bidderr 2, and nothing to bidder 1 (bidder 1, would

value 0 any subset of S?1 anyway). This allocation has social welfare equal to

√

m + ε,

therefore the approximation ratio tends to

√

m when ε goes to 0.

4. (Optional) Show that the Greedy Mechanism is monotone and uses critical payments.

Solution: The answer is in the AGT book, in the paragraph that follows Lemma 11.9.

5. The incentive-compatible algorithm (DNS) in [1] has approximation ratio O(

√

m).

(a) Show an example with 4 items where the approximation ratio is 2.

(b) Generalize the example for m = k2 items, and show an approximation ratio of k.

Solution: Lets show the statement directly for an instance with m = k2 items and k

bidders. For each player i, let the subadditive valuation of each player be

vi(S) =

{

|S| if |S| ≤ k

k if |S > k (1)

First notice that for any subset S, it holds that vi(S) ≤ |S|. Notice also that the valuations

are trivially subbaditive. To see that, take some arbitrary subsets S, T . If max{|S|, |T |} ≥

k, then

vi(S ∪ T ) = k ≤ k + min{vi(S), vi(T )} = vi(S) + vi(T ).

If both |S| ≤ k and |T | ≤ k, then

vi(S ∪ T ) ≤ |S ∪ T | ≤ |S|+ |T | = vi(S) + vi(T ).

Now, observe that the optimum allocation assigns exactly k items to each player, and the

social welfare is k2 . The DNS mechanism either allocates all items to a single player, or

it assigns a matching (each player gets exactly one item). In both cases the social welfare

achieved is k. Therefore the approximation ratio is k =

√

m.

6. The DNS mechanism in [1] is incentive-compatible mechanism and has approximation

ratio O(

√

m) when the valuations are subadditive.

(a) Explain briefly why the mechanism is incentive compatible.

(b) Describe in detail how the mechanism allocates the items in the following instance

with four players and three items a, b, c, where the valuations are given by the fol-

lowing table

{a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}

v1 14 15 16 17 17 17 18

v2 5 10 10 10 15 10 16

v3 12 7 12 17 18 18 18

v4 12 14 15 17 17 17 18

Solution:

(a): The mechanism is incentive compatible because it is maximal in range. A maximal in

range mechanism limits the possible allocations and finds the optimal solution over these

2

allocations. DNS does exactly this: Finds the optimal allocation between the allocations

that give all the items to one bidder, and those that give exactly 1 item to the bidders.

Since, DNS is maximal in range, VCG payments can be used to make the mechanism

incentive compatible.

(b): The mechanism will query the bidders for the set {a, b, c} and the sets {a}, {b} and

{c}. Then a bipartite graph B = (N,M,E) is created, where N = 1, 2, 3, 4, M = a, b, c.

Then for each edge (v, u) for a ∈ N and i ∈ M , DNS adds as weight the valuation vi(a).

In this example the weight in edge (v1, a) is 14. Then, the mechanism computes the

maximum weighted matching. In this example this is {(v1, c), (v3, a), (v4, b)} with value

16+12+14 = 42. (or {(v1, b), (v3, a), (v4, c)} with the same value). Since there is no bundle

of three items with higher value, then the items are allocated as in {(v1, c), (v3, a), (v4, b)}

(or {(v1, b), (v3, a), (v4, c)}).

References

[1] Shahar Dobzinski, Noam Nisan, and Michael Schapira. Approximation algorithms for com-

binatorial auctions with complement-free bidders. In Proceedings of the 37th Annual ACM

Symposium on Theory of Computing (STOC), pages 610–618, 2005.