VC v. VCG:
Inapproximability of Combinatorial Auctions via Generalizations of the VC Dimension
Michael Schapira
Yale University and UC Berkeley
Joint work with Christos Papadimitriou and Yaron Singer (2008) and Elchanan Mossel, Christos Papadimitriou and Yaron Singer (2009)
Auctions: Different Concerns
Computational concerns:
bounded computational resources
optimization
…
Economic concerns:
truthful behaviour
fairness
…
computational efficiency
incentive-compatibility
Algorithmic Mechanism Design
Can these different desiderata coexist
The central problem in Algorithmic Mechanism Design [Nisan-Ronen]
Illustration: Restricted Combinatorial Auctions
A set of m items for sale {1,…m}.
n bidders {1,…,n}. Each bidder i has an additive valuation with a spending constraint vi.
per-item values ai1,…,aim
"maximum spending" value bi
For every bundle S, vi(S)=min {S j in S aij , bi},
Goal: find a partition of the items between the bidders S1,…,Sn such that social welfare Si vi(Si) is maximized
What Do We Want
___PPTMAC11
Quality of the solution: As close to the optimum as possible.
Computationally tractable: Polynomial running time (in n and m).
Truthful: Motivate (via payments) agents to report their true values.
The utility of each user is ui = vi(S) – pi
Solution concepts: dominant strategies, ex-post Nash.
State of the Art
Easy from an economic perspective.
VCG!
Easy to solve computationally.
NP-hard (even for n=2) [Lehmann-Lehmann-Nisan] but…
We can get arbitrarily close to the optimum for any constant n (PTAS)! [Andelman-Mansour]
Can both be achieved simultaneously
Huge Gap!

下一页