Learning the Empirical
Hardness of Combinatorial Auctions
Introduction
Why?
Related Work
Combinatorial Auctions
Winner Determination
Problem
WDP Case Study
Methodology
Methodology
Methodology
WDP Distributions
Methodology
Problem Size
Raw vs. Non-Dominated
Bids
(64 goods, target of 2000 non-dominated bids)
Methodology
Features
Features
Methodology
Experimental Setup
Gross Hardness (256
goods, 1000 bids)
Methodology
Learning
LR: Error
LR: Subset Selection
LR: Cost of Omission (subset
size 7)
Non-Linear Approaches
Quadratic vs Linear
Regression
Quadratic vs Linear
Regression
QR: RMSE vs. Subset Size
Cost of Omission (subset
size 6)
What’s Next?
Summary