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.