Multi-Unit Auctions with Budget Limits

Shahar Dobzinski, Ron Lavi, and Noam Nisan

Valuations

• How can we model:
• An advertising agency is given a budget of 1,000,000$
• A daily budget for online advertising
• “I am paying up to 200$ for a TV”.

​

• The starting point of all auction theory is the valuation of the single bidder.
• The quasi-linear model: � (my utility) = (my value) – (my price)

Budgets

• “Approximation” in the quasi-linear setting
• Define: v’(S) = min( v(S), budget ) � Mehta-Saberi-Vazirani-Vazirani, Lehamann-Lehmann-Nisan
• Doesn’t really capture the issue.
• E.g., marginal utilities.

​

Our Model

• Utility of winning a set of items S and paying p:
• If p≤b : v(S) – p
• If p>b : -∞ (infeasible)

​

• Inherently different from the quasi linear setting.
• Maximizing social welfare does not make sense.
• What to do with bidder with large value and small budget?
• VCG doesn’t work.
• The usual characterizations of truthful mechanisms do not hold anymore.
• E.g., cycle montonicity, weak monotonicity, ...
• ...

Previous Work

• Budgets are central element in general equilibrium / market models
• Budgets in auctions -- economists:

Benot-Krishna 2001, Chae-Gale 1996, 2000, Maskin 2000, Laffont-Robert 1996, few more

• Analysis/comparison of natural auctions
• Budgets in auctions – CS:
• Borgs et al 2005 Design auctions with “good” revenue
• Feldman et al. 2008, Sponsored search auctions
• This work: design efficient auctions
• Again, what is efficiency if bidders have budget limits?
• But we also discuss revenue considerations.

Multi-Unit Auctions with Budgets

• m identical indivisible units for sale.
• Each bidder i has a value vi for each unit and budget limit bi.
• Utility of winning x items and paying p:
• If p≤bi : xvi-p
• If p>bi : -∞ (infeasible)

​

• In the divisible setting we have only one unit.
• The value of i for receiving a fraction of x is xvi.

​

• We want truthful mechanisms.
• The vi’s and the bi’s are private information.

What is Efficiency?

• Minimal requirement – Pareto
• Usually means that there is no other allocation such that all bidders prefer.
• Instead of the standard definition, we use an equivalent definition (in our setting): no trade.
• Dfn: an allocation and a vector of prices satisfy the no-trade property if all items are allocated and there is no pair of bidders (i,j) such that
• Bidder j is allocated at least one item
• vi>vj,
• Bidder i has a remaining budget of at least vj

Main Theorem

Theorem: There is no truthful Pareto-optimal auction.

• the bi’s and the vi’s are private.

​

Positive News:

• Nice weird auction when bi's are public knowledge.
• Uniqueness implies main theorem.
• Obtains (almost) the optimal revenue.

Ausubel's Clinching Auction

• Ascending auction implementation of VCG prices:
• Increase p as long as demand > supply.
• Bidder i clinches a unit at price p if � (total demand of others at p) < supply, �and pay for the clinched unit a price of p.
• Reduce the supply.
• Ausubel: This gives exactly VCG prices, ends in the optimal allocation, hence truthful.

The Adaptive Clinching Auction (approx.)

• The “demand of i at price p” depends on the remaining budget:
• If p≤vi : min(remaining items,floor(remaining budget /p)), else: 0.
• The auction:
• Increase p as long as demand > supply.
• Bidder i clinches a unit at price p if � (total demand of others at p) < supply, �and pay for the clinched unit a price of p.
• Reduce the supply.
• Not truthful in general anymore!
• Theorem The mechanism is truthful if budgets are public, the resulting allocation is Pareto-efficient, and the revenue is close to the optimal one.
• Theorem: The only truthful and pareto optimal mechanism.

Example

• 2 bidders, 3 items.
• v1 = 5, b1 = 1; v2 = 3, b2=7/6

0

0

3

3

7

/

6

3

1

0

+

of 1

of 2

of 2

Truthfulness

• Basic observation: the only decision of the bidder is when to declare “I quit”.
• Because the demand (almost) doesn’t depend on the value
• If p≤vi : min(# of remaining items, floor(remaining budget/p) )
• Else: 0
• No point in quitting after the time
• Until p=vi the auction is the same.
• The player can only lose from winning items when p>vi.
• No point in quitting ahead of time.
• The auction is the same until the bidder quits.
• The bidder might win more items by staying.

Pareto-Efficiency

• We need to show that the “no-trade” condition holds.
• Lemma: (no proof) The adaptive clinching auction always allocates all items.
• Consider bidder j who clinched at least one item. Let the highest price an item was clinched by bidder j be p (so vj≥p).
• Let the total number of items demanded by the others at price p be qp.
• There are exactly qp items left after j clinches his item.
• There are at least qp items left after j clinches his item (by the definition of the auction).
• There cannot be more items left since all items are allocated at the end of the auction, but j is not allocated any more items, and the demand of the others cannot increase.
• Hence each bidder is allocated the items he demands at price p.
• At the end of the auction a player that have a value>p, have a remaining budget<p≤vj.

Revenue

• Dfn: The optimal revenue (in the divisible case) is the revenue obtained from the monopolist price. Borgs et al
• The monopolist price: the price p the maximizes � p*(fraction of the good sold).
• Dfn: Bidder dominance α=maxi((fraction sold to i at the monopolist price)/(total fraction sold at the monopolist price)
• Borgs et al: there is a randomized mechanism such that If α approaches 0 then the revenue approaches the optimum.
• Some improved bounds by Abrams.
• Thm: The revenue obtained by the adaptive clinching auction is (1-α) of the optimum.
• Efficiency and revenue, simultaneously!

Revenue (cont.)

• Let the optimal monopolist price be p.
• We’ll prove that the adaptive clinching auction sells all the good at price at least (1-α)p
• We’ll show that at price (1-α)p, for each bidder i, the total demand of the others is more than 1.
• So for each fraction x we get at least x(1-α)p.
• Lemma: WLOG, at price p all the good is allocated.
• If bi>vi, then done. Else, the demand of each bidder is bi/p, hence the price can be reduced until all the good is allocated while still exhausting all budgets of demanding bidders.
• Fix bidder i, at price p the demand of the others is at least (1-α). The demand of each bidder is bi/p, so in price (1-α)p the total demand of the other is 1.

Summary

• Auction theory needs to be extended to handle budgets.
• We considered a simple multi-unit auction setting.
• Bad news: no truthful and pareto-efficient auction.
• Good news: with public budgets, there is a unique truthful and pareto-efficient auction
• (almost) optimal revenue.
• What’s next?
• Relax the pareto efficiency requirement
• Approximate pareto efficiency? Randomization?
• Other settings
• Combinatorial auctions? Sponsored Search?

Two bidders, b1=b2=1

• One divisible good
• The following auction is IC + Pareto:
• If min(v1,v2)≤1 use 2^nd price auction
• Else, assuming 1<v1<v2:
• x1= ½ – 1/(2•v1•v1) , p1=1-1/v1
• x2= ½ + 1/(2•v1•v1) , p2=1

Two bidders, b1=1, b2=∞

• One divisible good.
• The following auction is IC + Pareto:
• If min(v1,v2)≤1 use 2^nd price auction
• Else, if 1<v1<v2:
• x1= 0
• x2= 1 , p2=1+ln(v1)
• Else, if 1<v2<v1:
• x1=1/v2, p1=1
• x2= 1-1/v2, p2=ln(v2)

Warm Up: Market Equilibrium

• One divisible good.
• A competitive equilibrium is reached at price p:
• If the total demand at price p is 1.
• Each bidder gets his demand at price p.
• Demand of i at price p is
• If p≤vi : min(1,bi/p)
• Else: 0

​

​

Warm Up: Market Equilibrium

• At equilibrium, p=(∑bi), xi=bi/(∑bi)
• Sum over i's with vi≥p
• Pareto
• We need to verify that the “no-trade” condition holds.
• Ascending auction implementation:
• Increase p as long as supply<demand
• Allocate demands at price p
• Observation: truthful if vi<<bi or vi>>bi
• If “budgets don’t matter” or “values don’t matter”