Multi-Unit Auctions:�Beyond Roberts
Shahar Dobzinski and Noam Nisan
“A 3 minutes video is worth a 20 minutes talk”
Noam Nisan’s Blog, March 5:
The main topic of this talk: a strange, unintuitive and useless mechanism for multi-unit auctions.
Multi-unit auctions: n bidders, m (identical) items.
vi(s) denotes the value of bidder i for a bundle�of s items. vi is represented by a black box.
Normalization: vi(0) = 0
Monotonicity: vi(s+1) ≥ vi(s)
Goal: find an allocation (s1,…,sn), Σsi≤m, that maximizes the welfare Σivi(si).
What is a Good Auction?�I.e., what is a good algorithm/mechanism?
Fast
Good Approx
Truthful
VCG
1.01-approx
Allocate�nothing
?
Fast: running time is polynomial in�n and log m.
Truthful: truth telling maximizes the profit
profit=value-price
dominant strategies, private values
Good Approximation: find a solution that is within a factor of 1.01 of the value of the optimal solution.
Theorem: No scalable truthful mechanism can achieve an approximation ratio better than 2 in poly time.
Theorem: There exists a polynomial time truthful 2-approximation mechanism [Dobzinski-Nisan’07].
Fact: the truthful poly time truthful 2-approx mechanism is maximal in range.
Theorem [Dobzinski-Nisan’07]: every poly-time MIR algorithm for multi-unit auctions has an approx ratio ≥ 2.
Main idea: extend the impossibility result for MIR to hold for any truthful mechanism using the characterize and optimize approach.
Conjecture [characterize]: every truthful mechanism for multi-unit auctions with an approx ratio < 2 is weighted MIR.
Theorem [optimize]: every poly-time (weighted) MIR algorithm for multi-unit auctions has an approx ratio ≥ 2.
Characterize
Optimize
Impossibility
+
=
Success stories: [Lavi-Mu’alem-Nisan], [Papadimitriou-Schapira-Singer], [Dobzinski-Sundararajan],… but no auction domains!
1.99-approx
Conjectured world:
Truthful
MIR
FALSE
Theorem [characterize]: every scalable 2-bidder truthful algorithm with an approximation ratio better than 2 is (almost) a triage auction.
The real world:
(almost…)
Truthful
1.99-approx
MIR
Triage
New family! Triage auctions are truthful but not MIR and provide a 1.01-approx (not in poly time)
Theorem: No poly-time scalable mechanism provides an approx ratio better than 2.
First impossibility result for an auction domain.
Characterize
Optimize
Impossibility
+
=
Proof: Modify the optimization theorem for the maximal-in-range case.
The Main Highlights of the Characterization
Start with the 2-item characterization and use induced mechanisms to obtain a characterization for m>2 items.
Scalability is used only in the 2-item characterization.
Manipulating the payment functions, not the allocation functions.�Very different machinery than Roberts’ theorem machinery.
Triage Auctions
Warm up: VCG in our Notation�(truthfulness as a menu)
v2
v1
0
v2
v2 - v1
0
Values
Prices (for u)
u2
u1
0
Values
u2
u2 - u1
0
Prices (for v)
The taxation principle: truthful mechanism 🡸🡺 each bidder faces a menu where each bundle has a price (possibly infinity), and is assigned the most profitable bundle.
This talk: triage auction, symmetric version, with parameter θ > ½.
The triage auction is feasible, its approximation ratio is 1/θ.
v2
v1
0
v2
θv2
0
Values
Prices
v2
v1
0
v2
v2 - v1
0
Values
Prices
v2
v1
0
v1/θ
v1/θ - v1
0
Values
Prices
Low range: v1 < (1-θ)v2
Mid range: (1-θ)v2 < v1 < θv2
High range: v1 > θv2
θ=0.75
Summary
Lesson I: there are “useful” non-VCG mechanisms.
Introduced triage auctions, characterized mechanisms for multi-unit auctions, got a lower bound on the power of poly time truthful scalable mechanisms.
Lesson II: and we can characterize them!