BREAKING THE LOGARITHMIC BARRIER FOR TRUTHFUL COMBINATORIAL AUCTIONS WITH SUBMODULAR BIDDERS
Shahar Dobzinski
Combinatorial Auctions
The non-decreasing set function vi(S) denotes the value of bidder i for the bundle S.
Output. An allocation (S1,…,Sn)
Access to valuations. �Value queries: given S, what is vi(S)?
Demand queries: given item prices p1,…,pm, return a bundle that maximizes the profit vi(S)-Σjpj.
Normalization: vi(∅) = 0
Submodularity: S⊆T, vi(S+{j}) - vi(S) ≥ vi(T+{j}) - vi(T)
n bidders, m different items.
What is a Good Mechanism?
Fast
Effective
Incentive�Compatible
VCG
Allocate�nothing
Fast: number of queries is poly(n,m)
Incentive Compatible: truth telling maximizes the profit
profit=value-price
Effective: good approx to the social welfare Σivi(Si).
�
Lehmann-Lehmann-Nisan’02,�Khot-Lipton-Markakis-Mehta’05,
Dobzinski-Schapira’06,
Mirrokni-Vondrak-Schapira’08,
Vondrak’08: e/(e-1)-approx
Dobzinski’11:�no m½-ε-approx
submodular valuations with value queries
What is a Good Mechanism?
Fast
Effective
Incentive�Compatible
VCG
Allocate�nothing
Fast: number of queries is poly(n,m)
Incentive Compatible: truth telling maximizes the profit
profit=value-price
Effective: good approx to the social welfare Σivi(Si).
Feige-Vondrak’06: �(e-10-3)/(e-1)-approx�Dobzinski-Vondrak’13: �no 2e/(2e-1)-approx
submodular valuations with demand queries
?
Dobzinski-Nisan-Schapira’06:�O(log2m)-approx�Dobzinksi’07:
O(logm*loglogm)-approx
Krysta-Vocking’12:�O(logm)-approx
Warm-up: a Truthful O(logm)-Approx
Simplifications:
Additive valuations: vi(S) = Σj in Svi({j}).
vi({j}) is in {0,1,2,4,8,…,m}.
A fixed price auction: the price of every item is p, bidders sequentially choose a profit-maximizing bundle from the set of available items.
| a | b | c | d | e |
red | m | 1 | 1 | m/2 | 4 |
blue | 32 | 1 | 1 | m/2 | 4 |
green | 8 | 2 | 1 | m/2 | m/2 |
orange | 32 | 2 | 1 | m/2 | 1 |
purple | 1 | 4 | 1 | 2 | m |
| a | b | c | d | e |
red | m | 1 | 1 | m/2 | 4 |
blue | 32 | 1 | 1 | m/2 | 4 |
green | 8 | 2 | 1 | m/2 | m/2 |
orange | 32 | 2 | 1 | m/2 | 1 |
purple | 1 | 4 | 1 | 2 | m |
An instance:
1
Bin 1
Bin 2
4
Bin 4
m/2
Bin m/2
Bin m
m/2
m
A partitioning of OPT:
Lemma: the welfare generated by a fixed price auction with price p-ε is at least the contribution of bin p.
Easily extends to submodular valuations with a constant factor loss in the approximation ratio.
Corollary: a fixed price auction with a random price gives a truthful O(log m) approximation.
Is O(logm) optimal?
Main Obstacle: O(log m) is the best we can get for a “single price” auction (because the price of some items is too low/high)
Theorem: there is a truthful O(√logm)-approximation mechanism for combinatorial auctions with submodular (or even XOS) valuations that makes poly(m,n) demand queries.
1
Bin 1
Bin 2
4
Bin 4
m/2
Bin m/2
Bin m
m/2
m
A partitioning of OPT:
Idea: the price of an item should depend on its bin.
A Truthful O(√logm)-Approximation I
1
Bin 1
4
Bin�√logm
Bin�m-√logm+1
Bin m
m
A partitioning of OPT:
chunk 1�(√logm bins)
chunk √logm�(√logm bins)
Randomly choose one of the √logm chunks, let p be its first bin.
An instance is easy if the expected approximation ratio of a fixed price auction with price p-ε is O(√logm).
Simplifications:
Additive valuations: vi(S) = Σj in Svi({j}).
vi({j}) is in {0,1,2,4,8,…,m}.
Almost equivalently, the expected welfare of choosing a chunk at random and running the above fixed price auction is at least proportional to the contribution of the chunk.
A Truthful O(√logm)-Approximation II
1
Bin 1
4
Bin�√logm
Bin�m-√logm+1
Bin m
m
A partitioning of OPT:
chunk 1
chunk √logm
Observation: in a fixed price auction with price p-ε, every item in bin p or higher is allocated.
Simplifications:
Additive valuations: vi(S) = Σj in Svi({j}).
vi({j}) is in {0,1,2,4,8,…,m}.
A similar observation holds for submodular valuations if the instance is not easy.
items won in a fixed price�auction with price 1-ε�=�items in chunks ≥ 1
items won in a fixed price�auction with price 2√logm+1-ε�=�items in chunks ≥ 2
items won in a fixed price�auction with price 22√logm+1-ε�=�items in chunks ≥ 3
First step: classify items into their chunks.
A Truthful O(√logm)-Approximation III
Easy instance: choose a random chunk and run a fixed price auction.
Hard instance: use √logm “fictitious” fixed-price auctions to divide items to chunks. Randomly put each item in one of the √logm bins of its chunk.
The expected contribution of items that were classified to the correct bin is ~OPT/√logm. A fixed price auction gives O(√logm)-approx.
Additional issues:
Q: How to choose between the cases? A: flip a coin.
Q: Players might cheat in the fictitious auctions in order to reduce prices in the real auction. A: divide players into two, use half for the fictitious auctions and half for the real auction.
Summary & Open Questions
Theorem: there is a randomized truthful O(√logm)-approximation mechanism for combinatorial auctions with submodular (XOS) vlauations that uses poly(m,n) demand queries.
Deterministic mechanisms? Subadditive valuations?
Truthful in expectation mechanisms? See [Dughmi-Roughgarden-Yan’11] for coverage valuations.
See “Computational Efficiency Requires Simple Taxation” for two new methods of proving impossibilities.
Open Questions