Track: Search
Paper Title:
Dynamics of bid optimization in online advertisement auctions
Authors:
Abstract:
We consider the problem of online keyword advertising auctions among
multiple bidders with limited budgets, and study a natural bidding
heuristic in which advertisers attempt to optimize their utility by
equalizing their return-on-investment across all keywords. We show
that existing auction mechanisms combined with this heuristic can
experience cycling (as has been observed in many current systems),
and therefore propose a modified class of mechanisms with small
random perturbations. This perturbation is reminiscent of the small
time-dependent perturbations employed in the dynamical systems
literature to convert many types of chaos into attracting motions.
We show that the perturbed mechanism provably converges in the case
of first-price auctions and experimentally converges in the case of
second-price auctions. Moreover, the point of convergence has a
natural economic interpretation as the unique market equilibrium in
the case of first-price mechanisms. In the case of second-price
auctions, we conjecture that it converges to the ``supply-aware''
market equilibrium. Thus, our results can be alternatively described
as a tatonnement process for convergence to market equilibrium
in which prices are adjusted on the side of the buyers rather than
the sellers. We also observe that perturbation in mechanism design
is useful in a broader context: In general, it can allow bidders to
``share'' a particular item, leading to stable allocations and
pricing for the bidders, and improved revenue for the auctioneer.
