# Presentation: 223375

## Ascending Auctions with Package Bidding

- By Larry Ausubel and Paul Milgrom
- October 27, 2001

- This presentation reports research results. Some of the methods and features discussed are proprietary, that is, subject to issued patents or pending applications. The reporting of these results is not a license.

## Package Bidding

- Past FCC auctions:
- Independent bids
- Approximately-uniform pricing
- Bidder cannot make bid on B conditional on winning A
- Package bidding may:
- Reduce demand reduction
- Solve the problems of complementarity
- “exposure” problem: risks in bidding
- “pricing” problem: non-existence of CE prices

## Package Auctions:Some Formats

## Vickrey Auction

- A.k.a “pivot mechanism” or “VCG mechanism”
- One or more goods of one or more kinds
- Each bidder *i* makes bids *b**i*(*x*) on all bundles
- Auctioneer chooses the feasible allocation *x*****X* that maximizes the total bid accepted
*X* can incorporate policy rules
- Vickrey (“pivot”) payments for each bidder *i* are:

## Basic Ascending Package Auction

- A set of items is offered for sale
- A bid (*A,b**jA*) by bidder *j* specifies a set of items *A* and a corresponding *bid amount*.
- Bidding proceeds in a series of rounds
- Auction ends after no new bids
- Bids are all mutually exclusive and all are retained
- By contrast, in FCC Auction 31 design:
- Bids are only mutually-exclusive between rounds
- Only some bids are retained

## Ascending Proxy Auction

- A (Multi-Stage) Direct Revelation Game
- Each bidder reports a valuation function (and budget limit) to a “proxy agent”
- The proxy... (with one stage only)
- *makes no new bid when the proxy has a provisional winner*
- calculates the “potential profit”—what each bid would earn if it wins
- makes the feasible, acceptable bid with the highest potential profit
- Dual purpose of model
- Possibly models behavior “late” in experiments
- May be a practical design because it...
- eliminates certain retaliatory strategies
- runs quickly compared to multi-round auctions
- is adaptable to a multi-round version

## Bases of Evaluation

- Mechanism Performance: Theory/Lab/Real-World
- Ease of bidding
- Efficiency
- Revenues
- Resistance to collusion
- Robustness to Various Conditions
- Value conditions
- Substitutes only, no budget constraints
- Some complements or budget constraints
- Information conditions
- Complete and incomplete information
- Private and common value elements
- Competitive conditions

## Evaluating Revenues 

- Looking Ahead: Vickrey is distinguished from the ascending proxy auction _only_ by its handling of the “threshold problem”—a source of inefficiency.

## A Competitive “Benchmark”

- Consider a “cohesive” TU game (N,w).
- Construct an economy in which brokers bid for the players’ services.
- A competitive equilibrium is a price vector and allocation such that
- No positive profit opportunities:
- No losses incurred:
- _Proposition_: A value allocation ** is in the core if and only if ** is a competitive equilibrium price vector.
- So, the core identifies “competitive” pricing.

## Vickrey Auction Payoffs

- _Theorem_. Each bidder’s Vickrey payoff is *v**i* = *w*(*N*)-*w*(*N*\*i*) = max{***i* |*** **** Core*(*N*,*w*)}.* *
- _Proof_.
- If ***i *>*v**i* and ** is feasible, then coalition *N *\ *i* gets *w*(*N*) - *i* < *w*(*N *\ *i*), so ** is not in the core. For the converse, observe that the profile in which i gets *v**i*;  the seller gets *w*(*N*) - *v**i*; and others get zero is in the core.  **QED**

## Vickrey and Submodularity

- _Definition_. The coalitional value function *w* is *submodular* *for bidders* if for all coalitions *S* and *T*,
- _Theorem_. The following statements are equivalent:
- The coalitional value function is submodular for bidders.
- For every coalition S, there is a unique point in Core(S,w) that is Pareto best for the bidders.
- For every coalition S, the corresponding Vickrey payoff vector is in *Core*(*S*,*w*), that is,

## Proof

- Suppose the value function is submodular, let 0 denote the seller; Sn = {0,1,...,n}, and S=Sk. Then,
- 	But the ordering of players was arbitrary...
- Conversely, if *w* is not submodular, then for some S and i,jS,
- 	so *S *\ *ij* blocks the Vickrey allocation.  **QED**

**Notes:**
The first equation is feasibility.The second is the definition of Vickrey payoffs. The inequality is submodularity.

## Substitutes

- Suppose bidder preferences are quasi-linear. Let
**P** = set of possible bidder valuations.
**P**sub = set of valuations for which goods are substitutes
**P**add = set of additive valuations
- _Theorem_. Suppose that there are at least 3 bidders and **P**add**P.** Then the following four are equivalent:
**P**  **P**sub
- For every profile of bidder valuations drawn from **P****N\0**,  w is submodular for bidders.
- For every profile..., *v*  *Core*(*N*,*w*).
- For very profile..., competitive equilibrium goods prices exist.

## Ascending Proxy Auctions asDeferred Acceptance Algorithms

- Simplifying assumptions
- Negligibly small bid increments
- Pre-determined tie-breaking rule

## Deferred Acceptance Algorithms

- Marriage problem: the Gale-Shapley algorithm
- Process involves deferred acceptance
- Outcome is a “stable match,” and best such match for the side that makes the offers.
- Truthful reporting is a dominant strategy for offering side
- English auctions
- Process involves deferred acceptance
- Outcome is in the core of the economy: best point for bidders
- Truthful reporting to proxy bidder is a dominant strategy
- Others
- Medical resident matching program
- Kelso-Crawford labor markets model
**Ascending proxy auction (**_***even w/ complementarities***_**!)**

## Package Auction as DAA

- Is the package auction a DAA?
- Process involves deferred acceptance
- But offers may not be made in order of preference
- Introduce straightforward bidding to guide the analysis
- Is outcome in core of the economy?
- Yes!
- Core point is one at which the seller’s revenue is minimized.
- Is truthful bidding a dominant strategy?
- Yes, if goods are substitutes and offers are restricted. Else, still Nash equilibrium strategies.
- Do bidders in experiments bid “straightforwardly” or to the core?
- Should be investigated

## Truthful Outcomes 

- _Theorem_. If each bidder reports truthfully to its proxy and treating bid increments as negligible, the outcome of truthful reporting is a point in Core(N,w) that is not Pareto-dominated for bidders by any other point in Core(N,w).
- _Notes_:
- Unique among deferred acceptance algorithms because it uses no “substitutes” condition. The single seller replaces the substitutes condition in the formal arguments.
- Not yet an _equilibrium_ result, so not yet to be applied to the revenue issue.

## Proof

- _The insight_: Follow the progress of the algorithm in utility/payoff space.
- At round t, each bidder makes all package bids with potential profit of at least it.
- At each round, t is unblocked.
- Auction ends when t is feasible: all “losing bidders” have zero profits.

- Seller’s revenue at round t is given by:
*The argument generalizes to accommodate budget constraints using NTU core.*

## Truthful Equilibria

- _Theorem_. The following statements are equivalent:
- Truthful reporting is an ex post Nash equilibrium of the ascending proxy auction (and leads to Vickrey outcomes)
- The Vickrey outcome satisfies vCore(N,w),
- When vCore(N,w), the ascending proxy auction contains an implicit demand-bargaining protocol among bidders over points in Core(N,w).

## General Valuations

- _Theorem_. Let  be a Pareto-undominated point for the bidders in *Core*(*N*,*w*). Then there is a Nash equilibrium in which each bidder i with actual package values pi(.) reports to its proxy that its values are pi(.)-i.
- _Observations about this equilibrium_.
- Corresponds to Roth’s observations about equilibrium in matching models.
- Corresponds to Bernheim-Whinston bidding strategies in their “menu auction.”
- Selected as an “undiscouraged bidder equilibrium.”
- “Coalition-proof” provided undiscouraged bidder condition is consistently applied.

## Technology Neutrality

- Suppose that the values are as follows.
- By merging and coordinating technologies, bidders 1 and 2 can create a package of value 100.
- ... but they will still find the merger unprofitable.

| Bidder | East | West | Package |
| --- | --- | --- | --- |
| 1 | 40 | 0 | 40 |
| 2 | 0 | 40 | 40 |
| 3 | 0 | 0 | 50 |

## Budget Constraints

- Consider the problem of bidder #1 in a _Vickrey auction_ with 2 items for sale when player #3’s participation is uncertain.
- Should #1 bid (5,30) or (25,30) below?
- If #3 participates, then #1 “should” to express a marginal value of at least 20 for one items.
- Otherwise, #1 “should” express a marginal value of at least 20 for the second item.

| Bidder | 1 item | 2 items | Budget |
| --- | --- | --- | --- |
| 1 | 25 | 50 | 30 |
| 2 | 20 | 25 | 30 |
| 3 | 30 | 30 | 30 |

## Lessons for Auction Practice

- Bids are mutually exclusive
- Richer language
- Enables core outcome results
- Mandatory proxy intermediation
- Quite useful in package bidding auctions
- May also be useful in other auction formats
- Bid improvement rules
- Relatively aggressive bid improvement rules are consistent with obtaining core outcomes
- Revealed-preference activity rules
- (ptpt)(xtxt)  0

## The End