         ## Talk: Eliciting Bid Taker Non-price Preferences in (Combinatorial) Auctions

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

• 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

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