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