document: Dynamics of bid optimization in online advertisement auctions 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 .
doc_bio_tags: O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O