Transcript Document
Truthful Mechanisms for
Combinatorial Auctions
with Subadditive Bidders
Speaker: Shahar Dobzinski
Based on joint works with Noam Nisan & Michael Schapira
Combinatorial Auctions
m items, n bidders, each bidder i has a
valuation function vi:2M->R+.
Common assumptions:
Normalization: vi()=0
Monotonicity: ST vi(T) ≥ vi(S)
Goal: find a partition S1,…,Sn such that the
total social welfare Svi(Si) is maximized.
Algorithms must run in time polynomial in n
and m.
In this talk the valuations are subadditive:
for every S,T M: v(S)+v(T) ≥ v(ST)
(but all of our results also hold for submodular valuations)
Truthful Approximations?
A 2 approximation algorithm exists [Feige],
and a matching lower bound is also
known [Dobzinski-Nisan-Schapira].
What about truthful approximations?
The private information of each bidder is his
valuation.
Outline
A deterministic VCG-based O(m½)approximation mechanism
An W(m1/6) lower bound on VCG-based
mechanisms.
A randomized almost-logarithmic
approximation mechanism.
Reminder: Maximal in
Range Algorithms
VCG: Allocate Oi to bidder i. Bidder i gets a
payment of Sk≠ivk(Ok).
(O1,…,On) is the optimal solution.
Still truthful if we limit the range.
Range := { A=(A1,…,An) |v1,…,vn: A(v1,…,vn)=A }
The Algorithm [Dobzinski-Nisan-Schapira]:
Choose the best allocation where either:
One bidder gets all items OR
Each bidder gets at most one item.
Clearly, the algorithm is maximal-in-range and
can be implemented in polynomial time.
Proof of the
Approximation Ratio
Theorem: If all valuations are subadditive, the algorithm provides an
O(m1/2)-approximation.
Proof: Let OPT=(L1,..,Ll,S1,...,Sk), where for each Li, |Li|>m1/2, and for
each Si, |Si|≤m1/2. |OPT|= Sivi(Li) + Sivi(Si)
Case 2:
1: Siivvii(S
(Lii)) >≥ Siivi(L
(Si)i)
(“small”
(“large” bundles contribute most of the optimal social welfare)
Sivi(S
(Lii) >≥|OPT|/2
|OPT|/2
Claim:
At mostLet
m1/2
v be
bidders
a subadditive
get at least
valuation
m1/2 items
andinS OPT.
a bundle. Then there
exists an item jS s.t. v({j}) ≥ v(S)/|S|.
Proof:
There
immediate
is a bidder
from
i s.t.:
subadditivity.
vi(M) ≥ vi(Li) ≥ |OPT|/2m1/2.
Thus, for each bidder i that was assigned a small bundle, there is an
item ciSi, such that: vi({ci}) > vi(Si) / m1/2. Allocate ci to bidder i.
Outline
A deterministic VCG-based O(m½)approximation mechanism
An W(m1/6) lower bound for VCG-based
mechanisms.
A randomized almost-logarithmic
approximation mechanism.
About the Lower Bound
Why lower bounds on VCG-Based
mechanisms (a.k.a. maximal-in-range
algorithms)?
Conjectured characterization: All mechanisms
that give a good approximation ratio for
combinatorial auctions with subadditive bidders are
maximal in their range.
Even if the conjecture is false, still the only
technique that we currently know.
An W(m1/6) lower bound on
VCG-based mechanisms
[Dobzinski-Nisan]
We define two complexity:
Cover Number: (approximately) the range size
must be “large” in order to obtain a good approximation ratio.
Intersection Number: a lower bound on the communication
complexity.
We therefore want it to be “small” (polynomial)
Lemma (informal): If the cover number is large then
the intersection number must be large too.
From now on, only 2 bidders, thus a lower bound of 2.
The Cover Number
Intuitively, the size of the range
But we don’t want to count “degenerate
allocations”…
A set of allocations C covers a set of
allocations R if for each allocation S in R there
is an allocation T in C such that TiCi for
i={1,2}.
cover(R) is the size of the smallest set C that covers
R.
Observation: An MIR on range C provides a
better approximation ratio than on R.
The Cover Number
Lemma: Let A be an MIR algorithm with range R. If
cover(R) < em/400, then A provides an approximation
ratio of at most 1.99.
Proof: Using the probabilistic method.
Fix an allocation T=(T1,T2) from the minimal cover C.
Construct an instance with additive bidders: v(S) = SjS v({j})
For each item j, set with probability ½ v1({j})=1 and v2({j})=0 (or
vice versa with probability ½ ).
The optimal welfare in this instance is m, but each item j
contributes 1 to the welfare provided by T only if we hit the
corresponding bundle in T (with probability 1/2).
The expected welfare that T provides is m/2, and we can get a
better welfare only with exponential small probability.
The Intersection Number
A set of allocations D is called an
intersection set if for each
(A1,A2)≠(B1,B2)D we have that A1
intersects B2 and A2 intersects B1.
Let intersect(R) be the size of the largest
intersection set in R.
The Intersection Number
Lemma: Let A be an MIR algorithm with range R. Let
intersect(R)=d. Then, the communication complexity of
A is at least d.
Proof:
Reduction from disjointness: Alice holds a=a1…ad, Bob holds
b=b1…bd. Is there some t with at=bt=1? Requires t bits of
communication.
Given a disjointness instance, construct a combinatorial
auction with subadditive bidders:
Let {(A1,B1),…,(Ad,Bd)} be the intersection set.
Set vA(S)=2 if there is an index i s.t. ai=1 and Ai S. Otherwise
vA(S)=1. Similar valuation for Bob.
The valuations are subadditive.
A common 1 bit optimal welfare of 4. Our algorithm is
maximal in range, and the optimal allocation is in the range, so
our algorithm always return the optimal solution. But this
requires d bits of communication.
Putting it Together
In order to obtain an approximation ratio better than 2,
the cover number must be exponentially large.
If the MIR algorithm runs in polynomial time then the
intersection number must be polynomial too.
Lemma (informal): If the cover number is exponentially
large then the intersection number is exponentially
large too.
Corollary: No polynomial time VCG-based algorithm
provides an approximation ratio better than 2.
Summary
A deterministic VCG-based O(m½)approximation mechanism
An W(m1/6) lower bound on VCG-based
mechanisms.
A randomized almost-logarithmic
approximation mechanism.
Open Questions
Deterministic mechanisms\lower bounds
for combinatorial auctions with general
valuations?
Is the gap between randomized and
deterministic mechanisms essential?
Randomness and
Mechanism Design
Randomization might help in mechanism
design settings.
Two notions of randomization:
“The universal sense”: a distribution over
deterministic mechanisms (stronger)
“In expectation”: truthful behavior maximizes the
expectation of the profit (weaker)
Risk-averse bidders might benefit from untruthful behavior.
The outcomes of the random coins must be kept secret.
Results
Feige shows a randomized
O(logm/loglogm)-truthful in expectation
mechanism.
We show that there exists an
O(logm*loglogm) truthful in the universal
sense mechanism.
The Framework
Two cases:
Case 1: There is a dominant bidder.
A bidder with v(M) > OPT/(100log m loglog m)
(denote the denominator by c)
We can simply allocate all items to this bidder.
Case 2: There is no dominant bidder.
In this case we can use random sampling: partition the
bidders into two sets, acquire statistics from one set, and
use it to get an approximate solution with the other set.
How to put the two cases together?
Flipping a coin works, but with probability of only ½.
Next we will see how to increase the probability of
success to 1-e.
The Mechanism
A second price
I have an
Partition
the bidders
into 3 sets:
auction
with
a
SECPRIC
estimate of
STAT
with probability
e/2, SECPRICE with
probability 1-e, and FIXED
reserve
price
of
OPT
E
group
with probability
OPT/c e/2.
Statistics
First case: there is a dominant bidder.
Group
The Mechanism
Second case: there is no dominant bidder.
FIXED
group
A second price
auction with a
reserve price of
OPT/c
I have a
(good)
estimate of
OPT
Statistics
Group
Case 2: No “Dominant”
Bidder
Assumption: For all
bidders
vi(OPTi) < OPT / c
In the FIXED group:
a fixed-price auction
where each item has
a price of p (depends
on the statistics
group)
Everything costs p
My price
is 2*p
Take your
most
profitable
bundle
Too
I paid p
Expensive
!
Still Missing…
Why does the fixed price auction (with a
“good price”) provides a good
approximation ratio?
Can we find this “good price” using the
statistics group?
A Combinatorial Property
of Subadditive Valuations
Lemma: Let v be a subadditive valuation
and S a bundle of items. Then we can
assign each item in S a price in {0,p}
such that:
For each TS: v(T) > SjT|T|*p
|S|*p > v(S)/(100*logm)