AdWords and generalized online matching

ABSTRACT

How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/e for this problem.

REFERENCES

• 1: Gagan Aggarwal , Ashish Goel , Rajeev Motwani, Truthful auctions for pricing search keywords, Proceedings of the 7th ACM conference on Electronic commerce, p.1-7, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134708]
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 3: Yossi Azar , Arik Litichevskey, Maximizing throughput in multi-queue switches, Algorithmica, v.45 n.1, p.69-90, April 2006 [doi>10.1007/s00453-005-1190-x]
• 4: Paramvir (Victor) Bahl , Mohammad T. Hajiaghayi , Kamal Jain , Sayyed Vahab Mirrokni , Lili Qiu , Amin Saberi, Cell Breathing in Wireless LANs: Algorithms and Evaluation, IEEE Transactions on Mobile Computing, v.6 n.2, p.164-178, February 2007 [doi>10.1109/TMC.2007.20]
• 5: Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., and Sviridenko, M. 2004. Further improvements in competitive guarantees for QoS buffering. In ICALP. LNCS, vol. 3142. Springer, 196--207.
• 6: John Battelle, The Search: How Google and Its Rivals Rewrote the Rules of Business and Transformed Our Culture, Portfolio Hardcover, 2005
• 7: Christian Borgs , Jennifer Chayes , Nicole Immorlica , Mohammad Mahdian , Amin Saberi, Multi-unit auctions with budget-constrained bidders, Proceedings of the 6th ACM conference on Electronic commerce, p.44-51, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064014]
• 8: Buchbinder, N., Jain, K., and Naor, J. S. 2007. Online primal-dual algorithms for maximizing ad auctions revenue. In Proceedings of the 15th Annual European Symposium on Algorithms (Eilat, Israel, Oct. 8--10). To appear.
• 9: Crawford, V. P., and Knoer, E. M. 1981. Job matching with heterogeneous firms and workers. Econometrica 49, 2, 437--450.
• 10: Demange, G., Gale, D., and Sotomayor, M. 1986. Multi-Item Auctions. J. Polit. Econ. 94, 4, 863--872.
• 11: Edelman, B., Ostrovsky, M., and Schwarz, M. 2005. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. NBER working paper 11765.
• 12: Gagan Goel , Aranyak Mehta, Online budgeted matching in random input models with applications to Adwords, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.982-991, January 20-22, 2008, San Francisco, California
• 13: Goemans, M., and Kleinberg, J. 1998. An improved approximation algorithm for the minimum latency problem. Math. Prog. 82, 111--124.
• 14: Gonen, R., and Pavlov, E. 2007. An incentive-compatible multi-armed bandit mechanism. In Proceedings of the 3rd Workshop on Sponsored Search Auctions.
• 15: Immorlica, N., Jain, K., Mahdian, M., and Talwar, K. 2005. Click fraud resistant methods for learning click-through rates. In Lecture Notes In Computer Science. Springer-Verlag, New York, 34--45.
• 16: Iyengar, G., and Kumar, A. 2006. Optimal keyword auctions. In Proceedings of the 2nd Workshop on Sponsored Search Auctions.
• 17: Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003 [doi>10.1145/950620.950621]
• 18: Kamal Jain , Mohammad Mahdian , Amin Saberi, A new greedy approach for facility location problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510012]
• 19: Bala Kalyanasundaram , Kirk Pruhs, On-line Network Optimization Problems, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.268-280, January 1998
• 20: Bala Kalyanasundaram , Kirk R. Pruhs, An optimal deterministic algorithm for online b-matching, Theoretical Computer Science, v.233 n.1-2, p.319-325, Feb. 28 2000 [doi>10.1016/S0304-3975(99)00140-1]
• 21: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 22: Lahaie, S., Pennock, D., Saberi, A., and Vohra, R. 2007. Sponsored Search. In N. Nisan, T. Roughgarden, E. Tardos, V.V. Vazirani, Eds, Algorithmic Game Theory, Cambridge University Press, Cambridge, UK.
• 23: Benny Lehmann , Daniel Lehmann , Noam Nisan, Combinatorial auctions with decreasing marginal utilities, Proceedings of the 3rd ACM conference on Electronic Commerce, p.18-28, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501161]
• 24: Mahdian, M., Markakis, E., Saberi, A., and Vazirani, V. 2001. A greedy facility location algorithm analyzed using dual fitting. In RANDOM-APPROX, Lecture Notes in Computer Science, vol. 2129. Springer, New York.
• 25: Mohammad Mahdian , Hamid Nazerzadeh , Amin Saberi, Allocating online advertisement space with unreliable estimates, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250952]
• 26: McEliece, R., Rodemich, E., Rumsey, H., and Welch, L. 1977. New upper bounds on the rate of a code via the Delsarte -- MacWilliams inequalities. IEEE Trans. Inform. Theory, 23, 2 (Mar.) 157--166.
• 27: Aranyak Mehta , Amin Saberi , Umesh Vazirani , Vijay Vazirani, AdWords and Generalized On-line Matching, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.264-273, October 23-25, 2005 [doi>10.1109/SFCS.2005.12]
• 28: Varian, H. R. 2006. Position auctions. Int. J. Indust. Org., To appear.
• 29: Vazirani, V. V. 2006. Spending constraint utilities, with applications to the AdWords market. Math. Oper. Res., (submitted). Available at http://www.cc.gatech.edu/vijay.vazirani/spending.pdf.
• 30: Yao, A. C. 1977. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, CA.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Economics, Theory

Keywords:
Keyword auctions, online algorithms, search engines