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