# Presentation: 589364

## The Power and Limitations of Item Price Combinatorial Auctions

- Noam Nisan
- Hebrew University, Jerusalem

## Talk Structure

- Types of Iterative Auctions
- Computational Power of Item-Price Auctions
- Complexity: item-price vs. Bundle-price auctions
- Some approximations by item-price auctions

## Combinatorial Auctions

*m* indivisible non-identical items for sale
*n* bidders compete for subsets of these items
- Each bidder *i* has a valuation for each set of items:  *v**i**(S)* = value that *i *assigns to acquiring the set *S*
*v**i *is non-decreasing (“free disposal”)
*v**i**(**Ø) = 0 *
**Objective:** Find a partition *(S**1**...S**n**)* of *{1..m} *that maximizes the social welfare:  ***i* *v**i**(S**i**)*
**Issues: **communication, allocation, strategies

## Iterative Auction Mechanisms

- At each stage, the mechanism presents to the next bidder *i *a set of tentative bundle prices {*p**i,S*}* *.
- The bidder at this stage ***should*** bid for the set *S* that maximizes his utility at these prices: *v**i**(S) - p**i,S **.*
- The mechanism rules determine: the prices at each stage, who bids at each stage, when to stop.  Upon termination it should determine the final allocation and the payments.
- Types of natural restrictions:
**Item-prices** (linear prices): *p**i,S = ****j****S* *p**i,j*
**Anonymous prices**: *p**i,S = **p**i’,S  *
**Ascending Auctions**: *p**i,S  *non-decreasing with time

## Why “should” bidders follow protocol?

- Many possible answers, with varying degrees of plausibility:
- Incentive Compatible (in dominant strategies)
- Charge VCG prices –  ex-post-Nash incentive compatibility
- Proxies – whether actual or cryptographically simulated
- Myopic – this is exactly why these bids are intuitive
- Obedient – A purely computational perspective
- In this talk we stay agnostic about incentives
- Present whatever incentive properties obtained in each case
- Impossibility results apply regardless of incentives

## Can the efficient outcome be obtained?

- Parkes-Ungar and Ausubel-Milgron mechanisms reach the efficient allocation.  They are ascending, non-anonymous,  and use (non-linear) bundle-prices.
**Open**: are there ascending *anonymous* mechanisms that reach the efficient allocation?
**Our question**: are there *item-price* auctions that reach the efficient allocation?
- If valuations are substitutes  yes                              Kelso&Crawford
- What about the general case?
- Walrasian equilibrium with item prices does not exist.

## Demand oracle view of item-price auctions

_**Demand Oracle Query**_:
- _Input:_ *m* item prices: *p**1**...p**m*
- _Output:_ *D(p**1**...p**m**)* --   Demand at these prices.  I.e. the set *S* that maximizes *v(S)-**Σ**j****S** p**j*
- A general item-price iterative auction may be viewed as an allocation algorithm whose input is a demand oracle for each bidder.
**Lemma:** A demand oracle can simulate a valuation oracle.  (And, the simulation is computationally efficient.)
-  _**Valuation Oracle Query**_:
- _Input:_ subset *S      *
- _Output:_ *v(S) *
**Corollary: (**Weird)* *item-price auctions can reach the efficient outcome and produce VCG prices.

## Simulating a Valuation Oracle

- Algorithm for computing *v(S)* using a demand oracle:
_**marginal-valuation(**__***j,S***__**):**_
- For all goods *j****S* set *p**j**=0;* for all other goods set *p**j**=∞*
- Perform a binary search on *p**j* to find lowest value with *D(p**1**...p**m**)=S*
_***v(S):***_
- Initialize: result=0
- For all goods *j****S* do
- result  result + marginal-valuation( *j, {j’****S |  j’<j } )*

## Ascending Item-price auctions?      No.     Blumrosen & Nisan

| 
      (0,1) | 
       (0,1)
 | 
          2 |
| --- | --- | --- |
| 
         2 | 
          2 | 
           2 |

**v(a)             v(b)             v(ab)**

**Player 1**
**Player 2**

- Finding an efficient allocation requires answering: *v**1**(a) <> v**1**(b)?*
- Assume wlog that p1b rose to 1 before p1a rose to 1.
- Until this time, no information was gained (answer always {ab}).
- From this time on, no information on v1(b) can be gained.

## Analyzing complexity of auction mechanisms

- Consider only informational costs; ignore computation
- “preference elicitation”, “communication complexity”
- Basic lower bound: every combinatorial auction requires exponential communication in worst case             Nisan&Segal
- How to compare mechanisms?
- How well they perform in real applications
- We don’t know.  Not enough data.  Life is hard.
- How well they theoretically perform on classes of valuations
- Semantic classes: “substitutes”, “sub-modular”, ...
- Syntactic classes: XORs of few bundles, ORs of few bundles, ...
- What can we measure:
- How much information transfer is needed to find socially efficient outcome.
- How close to optimal can we get using “reasonable” information transfer.

## Item-price vs. Bundle price auctions

- Bundle-price auctions can be exponentially faster then item-price auctions.
- Assume all valuations are XOR bids of at most *s* bundles
- No bidder will ever bid another bundle
- All reasonable bundle-price ascending auctions will terminate in at most *s*n*max-bid/min-bid-increment* steps.
- Theorem (Blum, Jackson, Sandholm, Zinkevich): exponentially many demand-oracle queries are needed, when *s=√m*.
- Can item-price auctions be faster than bundle-price auctions?
- Depends what you count as “information” in bundle-price auctions
- Allow concise representation of bundle prices  at least as powerful as item-price auctions
- Require to list each non-0 bundle price  yes.

## Finding a “hidden” subset

- Consider the following case:
*v**1**(S) = 2|S|,*
- Except for a single “hidden” set H with *v**1**(H) = 2|H| + 1*.
*v**2**(S) = (1+****)2|S|,* for all *S*.
- Efficient allocation requires finding *H *and giving it to* 1*.
- A Walrasian equilibrium with a price of *(2+****) *per item exists, and can be found quickly by item-price auctions.
- Assume even *|H|=m/2* is known by a bundle price auction.
- No information about the identity of H can be obtained unless *p**1**(S) ≥ |S|* for all sets *S* of size *m/2+1*.
- But this requires exponentially many bundle prices.

## Suggestions so far

- A hybrid approach may be better than either item-price auctions or pure bundle-price auctions.
- Allowing bundle-price auctions to represent bundle prices succinctly suffices.
- How succinctly?
- Either item prices or bundle prices
- Arbitrary ORs of sub-bundle prices
- General formula in some bidding language
- Most extreme case: the aggregated bid of all others so far
- Try to evaluate auction mechanisms according to what types of valuations they can handle with reasonable information transfer.
- Challenge: a mechanism that can handle any XOR/OR-formula bids (in time polynomial in the bid size).

## Approximation Algorithm

- For *c = ****, 2****, ..., max-bid*
- For each bidder *i *
- Let *S**i* be the demand (*if not ****)* where all item prices are *c *
-        If demand became ** for the first time allocate *S**i* to *i *(taking
-                           away any items that were previously allocated)
- If (total value of solution found) *< v**i**({1...m})* for some *i* then
-      Ignore current solution and allocate everything to* **i** *
_**Theorem:**_ This gives a min(n,O(√m)) approximation
_**Theorem:**_ Any auction that gives a better approximation                               requires an exponential number of queries.         Nisan&Segal

## Sub-modular Valuations

_**Algorithm**_:
-            Initialize, *pi,j = ****  *for all bidders *i *and items* j*
- For every item* j *do
-       Perform Dutch auction on item *j*; let *i* be the winner
-       *S**i** **** S**i** U j;       p**i,j** = 0*
_**Theorem:**_ If all valuations are sub-modular then this is a 2-approximation.                                            Lehman&Lehman&Nisan
_**Theorem:**_ Any auction requires an exponential amount of communication to find an exact solution even for sub-modular valuations.                                         Nisan&Segal

## Auctions with Duplicate Items                 Bartal&Gonen&Nisan

- Assume that there are *k* units of each good.
- Each bidder wants at most one from each good type – i.e. *v**i**()* is still a functions of sets (rather than multi-sets).
_**Online Algorithm:**_
- Initialize item prices: *p**1**=...=p**m** = v**min** / (2km)*
- For all bidders *i *in order of arrival:
-        *S**i** **** D**i**(p**1**...p**m**)*
-        For all items *j****S**i* do
-                        *p**j **= **** p**j       *(for some well chosen *** )*
_**Theorem:**_ This auction is valid, incentive compatible, and gives as good approximation as computationally possible.