# Presentation: 520480

## Winner Determination in Combinatorial Exchanges

**Tuomas Sandholm**
- Associate Professor
- Computer Science Department
- Carnegie Mellon University
- 	and
- Founder, Chairman, and Chief Technology Officer
- CombineNet, Inc.

## Outline

**CombineNet company overview**
**Performance on real-world combinatorial procurement auctions**
**Exchange formulation & problem hardness**
**Exchange instance generator**
**Experiments with different solution technologies & instance types**
**Factors affecting problem difficulty**
**Discussion of the expected FCC exchange model**

## CombineNet, Inc.

**Leading vendor of markets with expressive competition**
**Technology development started 1997**
**Company founded April 2000**
**55 full-time employees and 9 professors**
- Tuomas Sandholm, Subhash Suri, Egon Balas, Craig Boutilier, John Coyle, Holger Hoos, George Nemhauser, David Parkes, Rakesh Vohra
**1 patent issued and 13 pending**
- Bidding languages
- Market designs
- Algorithms
- Preference elicitation
- Methods around basic combinatorial bidding that make it practical
- ...
**Headquartered in Pittsburgh, with offices in London, San Francisco, Atlanta, Brussels**

## CombineNet event summary (latest 2 years)

**~100 combinatorial procurement auctions fielded**
- Transportation:  truckload, less than truckload, ocean freight, air freight
- Direct sourcing: materials, packaging, production
- Indirect sourcing:  facilities, maintenance and repair operations, utilities
- Services:  temporary labor
- ...
**Total transaction volume: $6 B**
- Individual auctions range from $8 M to $730 M
**Total savings: $1.02 B**

## CombineNet applied technologies

**Operations research**
- LP relaxation techniques
- Branch and bound, Branch and cut
- Multiple (efficient) formulations
- ...
**Artificial intelligence**
- Search techniques
- Constraint propagation
- ...
**Software engineering**
- Modularity supports application of most appropriate solving techniques and refinements, some of which depend on problem instance
- C++ is effective (fast) implementation language, STL is indispensable
- XML is effective (extensible) input/output metalanguage
- Off-the-shelf XML parsers are too slow and heavy for large (100s of MB) inputs, so we built our own
- ...

## Largest expressive competition problem we have encountered

**Transportation services procurement auction**
**~ 3000 trucking lanes to be bought, multiple units of each**
**~ 120,000 bids, no package bids**
**~ 130,000 side constraints**
**CPLEX did not solve in 48 hours **
**Our technology clears this optimally & proves optimality in 4****1⁄2**** minutes**
- Significant algorithm design & software engineering effort 1997-2003

## One of the hardest expressive competition problems we have encountered

**Transportation services procurement auction**
**22,665 trucking lanes to be bought, multiple units of each**
**323,015 bids, no package bids**
**8 max winners constraints (overall & regional)**

## Combinatorial exchanges

## Combinatorial exchanges are a key effort at CombineNet

**CombineNet has ~40 engineers, almost half of whom work on winner determination technology**
**The main backend hosted product, ClearBox, does combinatorial auctions, reverse auctions, and exchanges**
- With hundreds of types of side constraints
- With multiple attributes and a fully expressive language for taking them into account
**$1.84 M NIST ATP grant for a 3-year effort for speeding up combinatorial exchanges**
- One year completed
**Fastest engine (by 1-2 orders of magnitude) for clearing combinatorial exchanges**

## Exchange model formulation (simple formulation without side constraints shown)

**= surplus (alternatively, could maximize liquidity)**

- Sandholm ICE-98, AAAI-99 workshop on AI in Ecommerce, AGENTS-00, CI-02
- Sandholm & Suri AAAI-00, AIJ-03** **

## Exchange problem hardness [Sandholm, Suri, Gilpin & Levine AAMAS-02]

**Thrm. NP-complete**
**Thrm. Inapproximable to a ratio better than #bids****1-******
**Thrm. Without free disposal, even finding a feasible (non-zero trade) solution is NP-complete**

## Exchange instance generator

**1**

**2**

**3**

**4**

**5**

**7**

**6**

** ****Model of item co-occurrence: building a bundle for a bid**

** ****Each bidder has his own subgraph of items**
** ****Each item in a bidder’s subgraph is only bought *****or***** sold by that bidder**
** ****Complementarity in bids and substitutability in asks determined by ****	****edges between items in bundle**
**	**Edges assigned weights, sum of weights on a node’s edges provides factor 	used in calculation

## Example of pricing bundle bids in the instance generator

**Items in the bundle****	****	****2, ****	****3, ****	****4, and ****	****5**
- Bidder action		Buy	Buy	Sell	Sell
- Item quantity ( = 0.6)	3	1	4	1
- Market Price		2.34	9.01	6.53	0.14
- Bidder’s Price (+/- 25%)	-  5%	+  7%	+21%	-16%					2.23	9.64	7.90	0.12
- Bid Price (+/- 3%)		-  1%	+  1.5%	+  2.5%	-  1.5%					2.21	9.78	8.03	 0.12
- Graph factor		+ 2%	+ 2%	-  3%	-  1%
- 					2.25	9.98	7.79	0.12
- Final Price  =  -14.55 	=	3 * 2.25  +  1 * 9.98  -  4 * 7.79  -  1 * 0.12
**Ask bid at $14.55**

## Exchange experiment setup

**Basics about instances**
- 50 items, 10 bidders, 50 bids per bidder (= 500 bids)
- Each bid must be accepted all or nothing
- Bundle bids permitted, with average of 2.5 items per bundle
- Multi-unit, with average item quantity of 2.5
- Free disposal permitted by buyers and sellers
- Exchange types: 1) Buyer/Seller, 2) Pure bids, 3) Buy&Sell
- All runs completed in under 3 hours
**Constraints **
- Max winners constraint for whole exchange
- At most 5 of 10 bidders accepted
- Cost constraint for one bidder
- First bidder is awarded at least  20% of market by $ value
- Discount schedule for one bidder
- Percentage discounts based on  $ awarded

## Speed of different solution technologies

**All timing results are for finding an optimal allocation & proving optimality**
**Solution technologies compared**
- CPLEX 8.1 out-of-the-box vs. CombineNet’s technology
- Tuned CPLEX is within 10% of CPLEX out-of-the-box
**Results over all exchange types**
- 					Avg run time (60 instances)
- CPLEX			           	    400 s
- CombineNet technology    	     	      27 s

## Speed by instance type

**All exchanges, constrained vs unconstrained**
- 				CONSTRAINED	UNCONSTRAINED
- 	CPLEX			    408 s		    393 s
- 	CombineNet technology 	      29 s		      24 s
**All exchanges, different exchange types **
- 				  BUYER/SELLER	   PURE	     BUY&SELL
- 	CPLEX 			      349 s	   164 s	         689 s
- 	CombineNet technology	        19 s	     14 s	           47 s

## Factors that affect problem difficulty

- 	In order of impact:
**Amount of demand for a given item**
- Higher average bid item quantities make problems much harder
- Single-unit exchanges are much less complex than multi-unit exchanges
**Competitiveness of bids**
- Close bid prices make problem much tougher
- More possible solutions are close in value
**Side constraints**
- May either help or hurt, depending on the problem and constraints
- Usually hurt, but not relatively as much as in reverse auctions
**Free disposal**
**Size of subset of items bidder is interested in**
- Larger subsets will mean there are more bidders on each item
- The more bidders on an item, the tougher the problem
**Buy&Sell bundles**

## Conclusions

**Combinatorial markets of different types have become a reality and CombineNet has a lot of experience designing, building, fielding & hosting them**
**Combinatorial exchanges are very complex to clear**
- NP-complete, inapproximable
- Orders of magnitude more complex than combinatorial auctions or reverse auctions of the same size
**CombineNet technology is the fastest for the problem by 1-2 orders of magnitude**
**Optimal clearing scales to reasonable problem sizes**
**Complexity depends on certain features of the instances, as presented**

## Expected FCC exchange model

**General points**
- Each license for a frequency range in a region is an item
- There are # ranges (~35)  X  # regions (500?) items
**Aspects that decrease complexity**
- Each item has a single unit only
- There is a single seller for each item (though multiple buyers possible)
- There is a definite structure to bids, by region and frequency range
- Small sellers and large buyers provide asymmetry
**Aspects that increase complexity**
- Substitutability of frequency ranges may explode the size of bids
- Large bundles are likely for the buyers
- Potentially several large buyers for each item