Craig Boutilier, University of Toronto Tuomas Sandholm, CMU Rob Shields, CombineNet, Inc.

I like combinatorial auctions as they blend two fields I'm interested in. You get a Computer Science optimization problem (Knapsack problem) combined with Economic auctions.

### Combinatorial auctions

*expressive bidding* in auctions becoming common: combinatorial bids, side-constraints, discount schedules.
* direct expression of utility/cost: economic efficiency

Advances in *winner determination* (determining least cost allocation)
* determine least-cost allocation of business to bidders
* new optimization methods key to acceptance
* applied to large-scale problems (e.g. procurement)

### Non-price preferences

Example: "That gives too much business to Joe" (expose to too much risk with one supplier)

Typical WD algorithms *minimize cost alone*
* bid-takers find this unsatisfying
* preferences for non-price attributes play key role

Examples * percentage volume business to specific supplier * average quality of product * geography

### Manual scenario navigation

- current practice
- impose constraints on winning allocation (not a hard constraint)
- re-run winner determination
- new allocation satisfying constraint: higher cost
- assess tradeoff and repeat (often hundreds of times) until satisfied with some allocation (by eyeballing)

### Utility functions

Bid taker is indirectly assessing a *utility function*
* tradeoff between attribute value, allocation cost

Difficult to express utility function, unwilling to commit

### Automated scenario navigation

Manual scenario generation problematic: insufficient/inefficient coverage of allocation space

Automated scenario navigation (utility elicitation): bid taker identifies utility-bearing attributes, we help assess *relevant* tradeoff weights/utilities

Minimax regret computation: identify *robust* allocations with only partial preference information. In many cases don't need to know utility function precisely to find optimum allocation.

Example: * "Given partial utility info, I suggest allocation x (*least max-regret). It could be up to $8000 from optimal. Accept?" * "No, that's too much potential error." * "OK, let's refine your utility function. would you prefer x ($, %Joe, AvgQual) or x' ($', ...) * "I definitely prefer x'" * "OK, I suggest allocation x'' (least max regret. It could be up to $4500 optimal. Accept?"

### Reverse Combinatorial Auctions

- Buyer: desires collection of items G
- Sellers: offer bids where b subset G
- WD: determine least cost allocation

### Utility for non-price attributes

- assume utility for allocation is linear
- non-neg weights (w) for features
- Assume linear, independent utility for features; linearly definable features (both can be relaxed).

### Optimization with uncertain utility

Utility function is unknown * only has partial information about weights * collection W, feasible weight vectors

Difficulty: optimization with imprecise objective

Minimax regret: robust optimization * find allocation with minimum worse-case error (minimax regret). adversary choosing utility function * Regret of x under w * Max regret of x under W * Minimax regret and optimal allocation

#### Computing minimax regret

- Difficulties: minimax program req'd (rather than straight min or max). potentially quadratic objective.
- Solution: natural structure: direct IP formulation, use of WD. upper, lower bounds on utility weights. convert minimax program to linear min using standard trick
- Clever encoding allows linear formulation (MIP)

#### Constraint generation

very few constraints will be active in sol'n. iterative approach solving relaxed IP (using subset of constraints). if constraint violated in solution, re-add and repeat.

performance: 10 suppliers, 50 items, 500 bids, six features: average WD ~19 sec

### Preference elicitation

- initial bounds on w often uncertain: buyer unwilling to commit, hard to visualize impact.
- two interaction modes: direct weight bound manipulation (sliders for upper and lower, display implications of bound refinement), comparison queries (current minimax optimal with adversarial allocation)

Experimental results: max and true regret plummet with # interactions, true regret much less

### Summary

- moving beyond cost-space optimization in expressive auctions is critical
- various natural elicitation techniques work well

### Q and A

- could model utility fn as POMDP, but preferred linear programming approach, bid-taker wants worst case guarantees, also don't know utility distribution so prefer ranges so that it can be capped to avoid risk