Christian Borgs
Mohammad Mahdian
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.
- G. Aggarwal, A. Goel, and R. Motwani. Truthful auctions for pricing search keywords. In Proceedings of the 7th ACM Conference on Electronic Commerce, 2006. Google Scholar
Digital Library
- K. Arrow and G. Debreu. Existence of an equilibrium for a competitive economy. Econometrica, 22:265--290, 1954.Google ScholarCross Ref
- M. Dellnitz, M. Field, M. Golubitsky, A. Hohmann, and J. Ma. Cycling chaos. Intern. J. Bifur. & Chaos, 5:1243--1247, 1995.Google ScholarCross Ref
- N. R. Devanur, C. H. Papadimitriou, A. Saberi, and V. V. Vazirani. Market equilibrium via a primal-dual-type algorithm. In Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002. Google ScholarDigital Library
- J. Feng, H. K. Bhargava, and D. Pennock. Comparison of allocation rules for paid placement advertising in search engines. In Proceedings of the 5th International Conference on Electronic Commerce, 2003. Google ScholarDigital Library
- M. J. Field. Equivariant dynamical systems. Trans. Amer. Math. Soc., 259:185--205, 1980.Google ScholarCross Ref
- T. Ibaraki and N. Katoh. Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, MA, 1988. Google ScholarDigital Library
- O. H. Ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463--468, 1975. Google ScholarDigital Library
- K. Jain and K. Talwar. Truth revealing market equilibria. Manuscript, 2004.Google Scholar
- C. Meek, D. Chickering, and D. Wilson. Stochastic and contingent-payment auctions. In 1st Workshop on Sponsored Search Auctions, 2005.Google Scholar
- M. Ostrovsky, B. Edelman, and M. Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. In 2nd Workshop on Sponsored Search Auctions, 2006.Google Scholar
- E. Ott, C. Grebogi, and J. A. Yorke. Controlling chaos. Physics Review Letters, 64, 1990.Google Scholar
- A. Palacios. Cycling chaos in one-dimensional couple interated maps. Intern. J. Bifur. & Chaos, 12m:1859--1868, 2002.Google ScholarCross Ref
- A. Palacios. Heteroclinic cycles in coupled systems of diference equations. J. Diference Eqs & Appl., 9:671--686, 2002.Google ScholarCross Ref
- P. Rusmevichientong and D. Williamson. An adaptive algorithm for selecting profitable keywords for search-based advertising services. In Proceedings of the 7th ACM Conference on Electronic Commerce, 2006. Google ScholarDigital Library
- H. Varian. Position auctions. Manuscript, 2006.Google Scholar
- X. M. Zhang and J. Feng. Price cycles in online advertising auctions. In Proceedings of the 26th International Conference on Information Systems (ICIS), 2005.Google Scholar
Index Terms
- Dynamics of bid optimization in online advertisement auctions
Recommendations
Outperforming the competition in multi-unit sealed bid auctions
AAMAS '07: Proceedings of the 6th international joint conference on Autonomous agents and multiagent systemsIn this paper, we examine the behavior of bidding agents that are in direct competition with the other participants in an auction setting. Thus the agents are not simply trying to maximize their own utility, rather they wish to maximize a weighted ...
Towards agents participating in realistic multi-unit sealed-bid auctions
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 3When autonomous agents decide on their bidding strategies in real world auctions, they have a number of concerns that go beyond the models that are normally analyzed in traditional auction theory. Oftentimes, the agents have budget constraints and the ...
Vindictive bidding in keyword auctions
ICEC '07: Proceedings of the ninth international conference on Electronic commerceWe study vindictive bidding, a strategic bidding behavior in keyword auctions where a bidder forces his competitor to pay more without affecting his own payment. We show that most Nash equilibria (NE) are vulnerable to vindictive bidding and are thus ...
Comments