# Presentation: 269683

## Multiround Combinatorial Auction Design 

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

- * Partially supported by Center for International Business Education and Research (CIBER)

## 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

## Coping with Complexity

-  IP approaches (e.g., B&B), 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

## Desirable Properties

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

## Multiround?

- (_[FCC combinatorial auction](slide25.xml)_ debate)
- In multiround framework problems escalate:
-  	WDP, _[threshold problem](slide23.xml)_, _[exposure problem](slide24.xml)_
- 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

## 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

## A Proposal: Separation

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

- How about two simultaneous auctions:
-         Each round of combinatorial auction followed by

- 			***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: ???

- Fairness, Failure-freeness,...

## 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?

## Primordial Soup

**Combinatorial Auction Design**
- open field
**Multiround Comb. Auctions**
- wide open
- many issues not well understood
- incubator for new problems
**Badly needed**
- testing ground (real life applications, experiments)
- economic theory of combinatorial auctions
- CS/OR theory with a bit more taste for modeling

**The devil is in the details.**

## Multiround Combinatorial Auction Design 

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

- * Partially supported by Center for International Business Education and Research (CIBER)

## 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

## Running Example

- FCC’s upcoming 700MHZ auction (Sept. 2001?)

## 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

## 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?

## Fairness

**Settling for a suboptimal allocation**
**	****Heuristics**
**	****Relegating complexity to the bidders**
**	****“****Political” solutions**
**	****...**
**Allocate items to those who value them the most.**** **

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

## Example: AUSM

- Continuous bidding
- All bids stay in the system and are publicly known until withdrawn
- New bid submission: accompanied with complementary bids
- 				defining an allocation** **(that increases revenue)
**Should bidders who are skillful in calculating WDP be favored?**

- Banks et al. 1989

- Adaptive User Selection Mechanism

## 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.

## 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)

## Example

- FCC’s upcoming 700MHZ auction (Sept. 2001?)

## 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

**endless gaming possibilities, slow pace, scalability, transparency**,...

- 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

## 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.
-      (E.g., 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.

## Tie-breaking

- 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)