Clinching Auctions with Online Supply
Venue
SODA (2013), pp. 605-619
Publication Year
2013
Authors
Gagan Goel, Vahab Mirrokni, Renato Paes Leme
BibTeX
Abstract
Auctions for perishable goods such as internet ad inventory need to make real-time
allocation and pricing decisions as the supply of the good arrives in an online
manner, without knowing the entire supply in advance. These allocation and pricing
decisions get complicated when buyers have some global constraints. In this work,
we consider a multi-unit model where buyers have global {\em budget} constraints,
and the supply arrives in an online manner. Our main contribution is to show that
for this setting there is an individually-rational, incentive-compatible and
Pareto-optimal auction that allocates these units and calculates prices on the fly,
without knowledge of the total supply. We do so by showing that the Adaptive
Clinching Auction satisfies a {\em supply-monotonicity} property. We also analyze
and discuss, using examples, how the insights gained by the allocation and payment
rule can be applied to design better ad allocation heuristics in practice. Finally,
while our main technical result concerns multi-unit supply, we propose a formal
model of online supply that captures scenarios beyond multi-unit supply and has
applications to sponsored search. We conjecture that our results for multi-unit
auctions can be extended to these more general models.
