Dynamics of bid optimization in online advertisement auctions

TLDR

The perturbation approach is inspired by dynamical systems techniques that transform chaotic dynamics into stable attractors. The study aims to analyze how advertisers can optimize utility by balancing return‑on‑investment across keywords in budget‑constrained keyword auctions. They modify auction rules by injecting small random perturbations to stabilize bidding dynamics. The perturbed mechanisms converge to the unique market equilibrium in first‑price auctions and experimentally to a supply‑aware equilibrium in second‑price auctions, acting as a buyer‑side tâtonnement that yields stable allocations, pricing, and higher revenue.

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 tâtonnement process for convergence to market equilibriumin 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.