# Presentation: 270066

## Tradeoffs in Combinatorial Auction Design 

- Implications for the FCC spectrum auctions

- Saša Pekeč
- 	   Decision Sciences
- 	   The Fuqua School of Business
- 	   Duke University

**Joint work with ****Michael H. Rothkopf****, Rutgers University**

## Overview

-  **Disclaimer: auction design is not a secondary issue**
** ****Desirable properties of (combinatorial) auction models**
** ****Difficulties in multiround combinatorial auction design**
** ****Tradeoffs:**
** ****Computational issues**
** ****Any hope for ascending combinatorial auctions?**
** ****Coping with inherent cooperative nature**
** ****Some comments on two-sided combinatorial auctions**
** ****Summary of proposals**

## Disclaimer

**Auction design is not a secondary issue**
** ****Overall 3G strategy**
**	****- **issues of standardization
- 	- simultaneous or sequential sales
** ****Selling licenses or selling rights to be blackmailed?**
- 	- UHF broadcasters
- 	- carte blanche or designated use of frequencies

- Required reading : *Some Heretical Thoughts on the Design of Combinatorial Auctions for the FCC *by* *M.H. Rothkopf (see conference web site)

## Disclaimer

**Working assumptions**
-  analysis of design and modeling issues:
- not focused on economic theory of auctions
- not focused on CS/OR theory
-  focused on specific application: the FCC auction design problem
-  some issues might be irrelevant in different contexts
-         (e.g., B2B like procurement, repeated sales, small stakes, ...)
- - as in any model analysis, bits and pieces can’t be taken out from  different models and patched together to one’s liking.

## Running Example

- FCC’s upcoming 700MHZ auction (June 2002?)

## Combinatorial Auction

- Set of items to be sold: [n] = {1,2,...,n}
*“**All or nothing”* bids allowed for any combination S    [n]
- 	**Each item can be sold to at most one bidder.**
- 	 		    Winner determination problem (WDP)
- 	      		       If the goal is to maximize the total revenue, then WDP is                  	                     equivalent to weighted set packing on hypergraphs.
-                                                        			(Rothkopf et al. 95,98)

- • Interesting algorithmic issues. Does standard TCS approach help?
- • Any good auction theory for combinational auctions?

## Why Comb. Auctions?

-  Gives more expressive power to bidders
-  Inherent complexity plagues design and implementation
- 	How much and what type of trade-off?

- Why not prepackage and avoid complexity issues?
- Why not deal with complexity (heuristics, approximation,...)?
- Why not limit behavior by imposing procedural rules?

- Application specific design issues

## Desirable Properties?

**Fairness**
**Failure-freeness**
**Allocation Efficiency**
**Revenue Optimization**
**Low Transaction Costs**
**Transparency**
**Scalability****	**
**...****.**

## Fairness

**Settling for a suboptimal allocation**
**	****Heuristics**
**	****Relegating complexity to the bidders (e.g., AUSM, PAUSE)**
**	****“****Political” solutions**
**	****...**
**Allocate items to those who value them the most.**** **

**OR**
**... ****to those who are the luckiest**
**... ****to those who compute the best**
**... ****to those who complicate/manipulate the auction procedure the most**

## Failure-freeness

**Heuristics (IP attacks; AI)**
**Approximation algorithms**
**...**
**	****	****Work  most of the time**

-  Fine in small stakes auctions. Could be fine in procurement.
-  How about missing the optimal allocation for a $30 billion auction?
-  How about miscalculating current winners in only one round of a             multiround auction?

## Auction designer’s dilemma

- Are you ready to accept the following gamble:

**p****failure**

**1-p****failure**

**Revenue within (1-********) of optimal**
**“****nearly” optimal allocation**

**Revenue maximized**
**Optimal allocation**

- _Depends on_
****
**p****failure**
**alternatives**

## Auction designer’s dilemma

- Are you ready to accept the following gamble:

**p****failure**

**1-p****failure**

**Lawsuit, long delay in allocation**
**Ramifications for the industry,**
**	****consumers, taxpayers**
**Public embarrassment**

**Revenue maximized**
**Optimal allocation**

- _Depends on_
**p****failure**
**alternatives**

## Auction designer’s dilemma

**Estimating p****failure****:**** **
- - experimental data? benchmark instances?
-  modeling bidder behavior with probability distributions
-  beware of malicious bidders (could enter auction as such or could change its goal during the course of the auction).
-  multiple rounds: multiple possibilities of failure

## Rev. Max. vs. Efficiency

-  **Theoretical results vs. implementability in real life**
** ****The most important segment:**
- 		citizens?
-                        	taxpayers?
- 		consumers?
- 		industry?

## VCG mechanisms

**Bidders have to have valuations for all possible allocations.**
**Allocation?**
**a) ****	****Partition of sets of winning combinations  that belong to the same bidder**
**or**
**b)  Partition of winning combinations (two or more can belong to the same bidder)**
**or ...**
**VCG mechanism is context dependent**

## VCG mechanisms

- Find winning combinations/bidders by solving WDP (maximizing revenue)
- For each of the winners find the lowest amount that this bidder
-      could bid and still be a winner (keeping all other bids unchanged). This is the price paid by that bidder.
-        no incentive for strategic bids
-         outcome is efficient
- However:
- - McCabe et al. (1991), *Testing Vickrey’s and other simultaneous multiple unit versions of the English auction*
- - Hobbs et al (2000), *Evaluation of a Truthful Revelation Auction for Energy Markets with Nonconcave Benefits*

## VCG Example

- Suppose seven bids (in $billion) only:
- b1(            )=4,   b2(   ) = b3(   ) = b4(   ) = b5(   ) = b6(   )= b7(   )= 1
- bids 2,3,4,5,6,7 define the revenue maximizing collection
- EACH WINNER PAYS NOTHING!
- • Should bid-taker aim for an efficient outcome?
- • Should bid-taker care about VCG mechanisms?

## VCG Example 2

## VCG Example 2

## Transparency

**Trust issue: The auction rules and procedures ought to be**
**	****	****         ****transparent to all bidders **

**Complexity vs. Transparency**
**    ****	****WDP, min bid increment, tie-breaking,...**
**   ****	****	****Should we assume****  poly-time ******** transparent ****?**

** ****Transparency and bounded rationality**
** ****Programmed bounded rationality (AI)?**

## Scalability

-     **Important in repetitive use of the auction procedure**
-     For example:
-            high complexity procedures like B&B based IP solvers
- do the job for small n (single-round vs. multiround matters)
- there are no guarantees for large(r) n.

## Multiround?

- In multiround framework problems escalate:
-  	WDP, threshold problem, exposure problem
- The source of many problems: currently losing bid can become winner later due to action on other items.
- 	 invites bidder coordination and collusion
-  	 complicates the selection of active bids

## Threshold Problem

- Suppose seven bids (in $billion) only:
- b1(            )=7,   b2(   ) = b3(   ) = b4(   ) = b5(   ) = b6(   )= b7(   )= 1
-    Any of the bidders 2-7, if acting alone, has to double their bid.
- 	Allow coordination?
- 	Allow “deficiency sharing”?

- the difficulty that multiple bidders desiring combinations that constitute a larger one may have in outbidding a single bidder bidding for that larger combination

## Exposure Problem

- Suppose Alice wants to bid b(            )=5 XOR b(            )=3
-      			(does not want both                 and                )
-         Allow for contingencies (XOR bids, budget constraints,...)?
-         Problem in multiround format

- the risk of bidders winning items they do not desire

- (More serious problem in simultaneous single item auctions)

## Challenges in Multiround

- Procedures for prevention of strategic bidding and signaling
- Procedures for keeping bidding moving
- Procedures that mitigate the exposure problem
- Minimum bid increase determination procedures
- Tie-breaking procedures

## FCC Design: Version 5/00

- Limit biddable combinations to individual, regional, national, global licenses    (as in Rothkopf et al. 95,98)
- From round to round retain only high bids on each biddable combination
- Min bid in the next round:  x% higher than the current high bid on that combination.
- Auction ends after two rounds without new valid bids

- 	**Limited expressive power**
- 	**Exposure problem?**
**	****Slow pace?**

## FCC Design: Version 7/00

- Limit the number of bids on combinations (12/bidder)
- Only current wins retained from round to round
- (renewal also possible)
- Min bid in the next round:  max of
- 	- x% higher than the bidder’s previous high bid on that combination (can still be well below current high bid)
-      - #units * min per unit price of any current winner in last 5 rounds
- WDP: current winners but
-     - only bids from each bidder’s last two active rounds
-      - bids across rounds are mutually exclusive for each bidder

## FCC Design: Version 7/00

** ****what if only single item bids submitted? **
** ****endless gaming possibilities? (eligibility, activity credit)**
** ****slow pace?**
** ****scalability?**
** ****transparency?**
** ****tie-breaking rules?**
** ****dubious interpretations of algorithmic and complexity issues?**
- Required reading : *The FCC Rules For the 700MHz Auction: a Potential Disaster by *C. R. Plott
- (http://www.fcc.gov/wtb/auctions/31/releases/rules6.pdf)

## Tradeoff 

**Allowing bids on all packages**
**vs.**
**Failure-freeness, Fairness, Scalability**

- How theoretical computer scientist’s worst nightmare
- enters (without an invitation) the auction designer’s life

## Computational issues

**Uneasy facts of life:**
-  **WDP is NP-complete**
-  WDP is **as hard as NP-complete problems get** (somewhat irrelevant since any non-optimal allocation, whether the corresponding revenue is –close or far away from the optimal revenue, smells like a disaster in the FCC case)
-  Can solve instances that are not too “large”. However, if required to solve multiple instances (no matter how similar) **do not count on “economies of scale”**
-  **Beware of savvy salesmen** (“great heuristics” that work well on self-selected database of test problems) since track record on hard IPs (e.g., TSP, QAP) shows that *branch-n-cut* is the way to go and that one could take “forever” (from FCCs perspective).

## Who Cares? 

-  **Many of these issues/problems can be brushed off:**
-  1. Accept possibility of suboptimal WDP solutions
-  2. Provide only minimal feedback to the bidders:
-     - current winner (Yes or No)
-     - minimal bid increment  in order to remain active
- 					(calculated to your liking)

- Easy way that avoids some potential pitfalls. Is it the best way?
**More importantly: is FCC in position to do any of these?**** **

## Coping with Complexity

-  IP approaches (e.g., B&B. B&C)
-  Heuristics: approx. alg’s, AI approach,...
-  Relegating complexity to the bidders (AUSM, PAUSE,...)
-  Maintaining fairness in face of computational limits
-  Limiting biddable combinations
-  Limiting use of combinatorial bids

## Coping with Complexity

-  IP approaches (e.g., B&B. B&C)  scalability? transparency?
-  Heuristics: approx. alg’s, AI approach,... failure-freeness?
-  Relegating complexity to the bidders (AUSM, PAUSE,...) fairness?
-  Maintaining fairness in face of computational limits   fairness?
-  Limiting biddable combinations   fairness?
-  Limiting use of combinatorial bids  fairness? failure-freeness?

## Coping with Complexity

-  **Relegating complexity: **
-  - allocating to those who compute the best
-  - dealing with complexity should not be FCC’s task or responsibility
-  “**Political” solutions: **
** **- an elegant way out (is it good enough to deter lawsuits?)
-  **Limiting biddable combinations:**
** **- cannot be avoided (e.g., frequency blocks,  regional blocks)
-  - a matter of framing the issue?
-  - possibly the cheapest way out
- 	(since you have to bite the bullet somewhere)

## Outsource Computation

- Combinatorial Auctions  **** WDP **** Computational Issue
- Computational problem should not plague allocation decisions

- 			***WDP auction***
- Don’t have to be comb. auction bidder to participate
- Submissions are allocations in comb. auction
- Winner: bidder submitting an allocation with highest revenue
- 	  (one who computes WDP the best)
- Payout: flat fee, percentage of the revenue value, Vickrey-like,...???
- Mechanism: ???

- Instead of being courted by WDP computation experts, let the market decide.

## Tradeoff 

**Ascending Combinatorial Auctions:**
- Theory vs. Reality

- Free lunch – a myth or reality?

## Ascending Comb. Auctions

**Some serious complaints (not discussed here):**
-  allow gaming and bidder collusion
-  slow pace
-  redundant when combinatorial bidding allowed

- Required reading : *Some Heretical Thoughts on the Design of Combinatorial Auctions for the FCC *by* *M.H. Rothkopf (see conference web site)

## 2nd Price Comb. Auctions

**Winners: **
- bidders/combinations  defining revenue maximizing collection
**Revenue:**
- no less than the value of the revenue maximizing collection when
- only all non-winning bids (bidders) considered
**Problem:** distributing “surplus” (FP-SP) among winners
- 	Let P(wi1,...,wik) = max revenue if bids from winners wi1,...wik* *removed.
**	****For any collection *****C ***of winners, let **d(*****C*****)=FP-P(*****C*****)**
- 	Distributing “surplus”  a solution to cooperative game **d**
**	****Note: core of d is empty **(except in the trivial case)

## IP duality gap hits hard

- Required reading : *LP and Vickrey auctions *by* *Bikhchandani et al.
- http://www.anderson.ucla.edu/faculty/sushil.bikhchandani/papers/vick_lp.pdf
-  explores existence of primal-dual algorithms to construct ascending auctions that implement Vickrey outcome.
-  crucial property: “agents are substitutes”
*“**If the substitutes condition does not hold, we believe it is unlikely that an iterative auction (in which bidding sincerely is an equilibrium) yielding Vickrey outcome exists.”*
**BAD NEWS for comb. auctions** (straightforward to check)
**“****agents are substitutes” holds ******** Core of ****d**** is not empty**
-  Back to the complexity issue: WDP is an NP hard IP problem. Duality gap exists and this means that the machinery of primal-dual algorithms is not available.

## Ascending comb. auctions

-  Efficient outcome might require simplifying assumptions
- 	- E.g., IPV assumption might help but should FCC care?
-       Efficient ascending combinatorial spectrum auctions:
- a myth or reality?
-  Plenty of issues that have to be juggled (on top of WDP)
- 	- min bid increment/ eligibility / activity credit
- 	- exposure problem / threshold problem
-      Simple rules in ascending combinatorial spectrum auctions:
- a myth or reality?
- (good news for would be consultants)

## Tradeoff 

**Inherent Cooperative Nature of Combinatorial Auctions:**
- Mitigating exposure problem and threshold problem
- vs.
- Avoiding bidder collusion, signaling, and eligibility parking

## Procedural issues

** ****Eligibility/activity credit**: is extending SAA rules the only way?
** ****Minimum bid increment:**
**  **- a notion of “fair share”of “*shortfall*”
-   - has to ease threshold problem
-   - has to ease the exposure problem (does it really?)
-   - has to minimize gaming possibilities

## Contingencies

**XOR bids:** **b(C****1****)** XOR **b(C****2****)** XOR ... XOR **b(C****k****)**
**   ****- **how much is IP messed up with addition of XOR bids?
-    - introduce dummy items
-    - works w/o trouble for most relevant cases where WDP is tractable
- (e.g., FCC v.5/00, but have to be careful)

**Procedural constraints  **(e.g., FCC v.7/00)

## Min bid increment

*   **W* – winning (revenue maximizing) allocation
-    For any biddable combination C, calculate
**Gap(C)=Rev(*****W *****)-max{Rev(*****A*****): allocation *****A***** contains C}**
- 	- Algorithm for WDP can (and often has to) be used for calculating Gap
-       					     (Rothkopf et al. 95,98)
-      - If min bid increment is based on Gap(C), auctioneer should make sure that these calculations are (as) failure-free (as possible) and doable in time provided between the rounds.
-     (FCC v.7/00 has to be ready for potentially 4095 such calculations)

## Min bid increment

*   *

**Two extremes:**

**  ****Immediate impact:**
**    ****Set min bid increment for C at ****mbi(C) = Gap(C)**

**  ****No impact:**
**    ****Set min bid increment for C at ****mbi(C) = (x%)* b(C)**

- Neither of the rules relies on possible increases on complementary combinations that could help bridge the gap.

## Min bid increment

*   *

**How about bridging only a “fair share” of the gap?**
**  ****mbi(C) = m****C****(C) * Gap(C)**
**where m****C**** is  a measure, possibly different one for different C,  on the algebra of all combinations S that are disjoint from C or that contain C.**
**Examples: **
- 	mC(S)=|S|
- 	mC(S)=m(S) for some m that is fixed prior to auction
- 	mC(S)= b(S)/ max{Rev(*A*): *A* contains S}
-             Appropriate m?
- (mbi proposed by DeMartini et al. 1999
- and Vohra and Weber 2000 are special cases)

## Min bid increment

*   *

**The problem with mbi(C) = m****C****(C) * Gap(C) **
**    **-  implicitly assumes that Gap(S)=Gap(C) for all combinations S
-         in allocation *A** = arg max {rev(*A*): *A* contains C}
- For example, there can be S contained in both *A** and *W.*
* *C=this row:
-  S=this row:
- For such S, 0=Gap(S)<Gap(C). Thus, mbi(S)=0. So, even if  all other bids were increased by a “fair share” , mbi(C) would not be sufficient to bridge Gap(C).

-   **2       2       2       2       2       2**        10 = b(C)

-   1       1       1       1       1       1          **8 **= b(S)

- Rev(***W***)=20

## Min bid increment

*   *

**mbi(C) = m****C****(C) * Gap(C) **
- Should a “fair share” be computed more precisely?** **
- Should new bids stand a chance to be immediately competitive? **   **

**A better approximation: **
**                 ****set constraint on m****C****: **S in some ***W***   mC(S) = 0

**More general:**
- Find mbi(C)0 such that for every C
-  max{ Rev(*A*) +    ******  **mbi(S)  :  ***A ***contains*** C***}=Rev(*W*)

- S in ***A***

- Can do it by brute force. Tractable if WDP is tractable.
- Before releasing, update mbi(C) by adding, e.g.,  (x%)*Rev(*W*) to it.

## Min bid increment

*   *

-  If no consensus measure mC ,  then eligibility parking spots for some bidders (it seems that common value assumption is needed)
-  Incorporating temporal information?
-  - if no activity for some number of rounds on combination C, discount probability that there will be activity in the next round.
-  (could easily be incorporated in the proposed framework)

## Ties in comb. auctions

- More complex possibilities for ties
- Ties more likely with bidding agents (e.g. clickbox)
-     unless wise choice of opening bids and/or increments:
-          orders partitions
- 		   (determines tie-breaking up to the partition)
- 	 Should some partitions be favored?

-   6       **7**       **6**       7       **6**       5        **40**

-   2       **3**       **4**       2       **4**       4        **20**

-   **10       **9**      10     10     10     10****      ****60**

## Tie-breaking

**Labeling and Aggregation**
- Label each bid (e.g., time-stamp)
- Lexicographically order labels of all bids in an allocation
- Among tied allocations, find the extremal one in lex order. (e.g., allocation whose all bids were submitted first wins).
- 	Alternatives available: (weighted) average label
- Some bad ideas: uBid.com

## Tie-breaking

**Randomization**
- 	Select an allocation (uniformly) at random from the set of tied ones.
**or**
**	**In clickbox bidding: perturb available bid increments by adding, e.g., c(.5)B (c is a constant, B are different and selected at random for each biddable combination)
- Some bad ideas: FCC v.7/00
-                          (randomize input for WDP algorithm)

## Two-sided spectrum auctions

** ****asymmetry of participants (FCC and everyone else)**
** ****what is being auctioned off (frequencies or frequencies for specific use) **
** ****bundling rules (who, how and when)**
** ****initial offerings vs. resale**

## STEP 0: Initial offering

**Still one-sided auction**
- Note:
- Allowing broadcasters to sell their UHF rights to telecoms for 3G use is equivalent to allocating 3G spectrum to broadcasters
-   (might make some people very happy at the expense of taxpayers)
- Introducing two sided-auctions: have to think hard of implications to current spectrum holders.

## Playing with fire

- If two-sided spectrum auctions are introduced:
- 	**Will FCC be able to control what’s going on?**
-  beware of market manipulators
-  beware of collusion of big players
-  designating exchange facilitator, even if FCC decides to do this itself, might contribute to the market failure: the biggest players will eventually take over the market (numerous examples from B2B world)

## Two-sided comb. auctions

**The problem of dividing the winning package bid among multiple sellers:**
-  mandate using fixed underlying measure defined on all combinations? (e.g. MhzPops)
-       Opens gaming possibilities (reminiscent of min bid increment analysis)
-  risky: measure based on non-winning bids
- E.g., Bid(AB)=6, Bid(A)=1 Bid(B)=3
-          Seller of A gets 6* 1/(1+3) = 1.5, Seller of B gets 6*3/(1+3)=4.5
- Problems similar to dividing “surplus” in 2nd price comb. auction
- Possibilities for gaming: Seller of A could submit Bid(A) = 2.99

## Two-sided comb. auctions

- A possibility:
-  FCC should ensure efficiency of initial offerings
-  FCC should oversee transactions on secondary markets
-   - design rules and regulations
-   - allow only transactions that don’t change the designated use of frequencies
- (alternatively, sales of frequencies without designated use; should not be retroactive)

## Summary

**At least three models better than FCC design v. 7/00:**
-  FCC v. 5/00 after fixing (e.g., according to P. & Rothkopf comments)
-  SMR
-  1st price sealed-bid combinatorial auction that outsources  WDP computation.

## Summary

**Define Policy Guidelines:**
-  importance of: citizens, consumers, industry, taxpayers...
-  importance of various (un)desirable properties of allocation
-  need for proper definition of failure and proper assessment of the probability and implications of a possible failure

## Summary

**Auction Design guidelines:**
-  Abandon FCC design v. 7/00 (or at least open discussion about it)
-  rethink the need for multiple round auctions
-  	-clearly redundant if secondary markets will be created
-  avoid taking responsibility for resolving NP-hard computation problems
- 	- limit biddable combinations
- 	- outsource computation

## Do not forget

** ****bid withdrawals**
** ****opening bids**
** ****pace between rounds (if multiround)**
** ****stopping rules (if multiround)**
** ****defaulting (beware of malicious bidders)**
**...**
**Finally: Cannot study rules in isolation of other rules and the auction context**

**The devil is in the details.**

## Tradeoffs in Combinatorial Auction Design 

- Implications for the FCC spectrum auctions

- Saša Pekeč
- 	   Decision Sciences
- 	   The Fuqua School of Business
- 	   Duke University

**Joint work with ****Michael H. Rothkopf****, Rutgers University**