Gagan Aggarwal
ABSTRACT
In sponsored search, a number of advertising slots is available on a search results page, and have to be allocated among a set of advertisers competing to display an ad on the page. This gives rise to a bipartite matching market that is typically cleared by the way of an automated auction. Several auction mechanisms have been proposed, with variants of the Generalized Second Price (GSP) being widely used in practice. There is a rich body of work on bipartite matching markets that builds upon the stable marriage model of Gale and Shapley and the assignment model of Shapley and Shubik. This line of research offers deep insights into the structure of stable outcomes in such markets and their incentive properties. In this paper, we model advertising auctions in terms of an assignment model with linear utilities, extended with bidder and item specific maximum and minimum prices. Auction mechanisms like the commonly used GSP or the well-known Vickrey-Clarke-Groves (VCG) can be interpreted as simply computing a bidder-optimal stable matching in this model, for a suitably defined set of bidder preferences, but our model includes much richer bidders and preferences. We prove that in our model the existence of a stable matching is guaranteed, and under a non-degeneracy assumption a bidder-optimal stable matching exists as well. We give an algorithm to find such matching in polynomial time, and use it to design truthful mechanism that generalizes GSP, is truthful for profit-maximizing bidders, correctly implements features like bidder-specific minimum prices and position-specific bids, and works for rich mixtures of bidders and preferences. Our main technical contributions are the existence of bidder-optimal matchings and strategyproofness of the resulting mechanism, and are proved by induction on the progress of the matching algorithm.
- Gagan Aggarwal. Privacy Protection and Advertising in a Networked World. PhD thesis, Stanford University, 2005. Google Scholar
Digital Library
- Gagan Aggarwal, Ashish Goel, and Rajeev Motwani. Truthful auctions for pricing search keywords. In ACM Conf on Electronic commerce, pages 1--7, 2006. Google ScholarDigital Library
- Gagan Aggarwal, S. Muthukrishnan, and Jon Feldman. Bidding to the top: VCG and equilibria of position-based auctions. In WAOA, 2006. Google ScholarDigital Library
- Ahmet Alkan. Existence and computation of matching equilibria. European Journal of Political Economy, 5(2-3):285--296, 1989.Google ScholarCross Ref
- Ahmet Alkan and David Gale. The core of the matching game. Games and Economic Behavior, 2(3):203--212, 1990.Google ScholarCross Ref
- Sushil Bikhchandani and Joseph M. Ostroy. From the assignment model to combinatorial auctions. In Combinatorial Auctions. MIT Press, 2006.Google Scholar
- Edward H. Clarke. Multipart pricing of public goods. Public Choice, 11(1):17--33, 1971.Google ScholarCross Ref
- G. Demange and D. Gale. The strategy structure of two-sided matching markets. Econometrica, 53(4):873--888, 1985.Google ScholarCross Ref
- Gabrielle Demange, David Gale, and Marilda Sotomayor. Multi-item auctions. Journal of Political Economy, 94(4):863--872, 1986.Google ScholarCross Ref
- Gabrielle Demange, David Gale, and Marilda Sotomayor. A further note on the stable matching problem. Discrete Applied Mathematics, 16:217--222, 1987. Google ScholarDigital Library
- Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords. American Economic Review, 97(1):242--259, March 2007.Google ScholarCross Ref
- Eyal Even-Dar, Jon Feldman, Yishay Mansour, and S. Muthukrishnan. On the effect of minimum prices on position auctions. WINE, 2008.Google Scholar
- Satoru Fujishige and Akihisa Tamura. A two-sided discrete-concave market with possibly bounded side payments: An approach by discrete convex analysis. Mathematics of Operations Research, 32(1):136--155, 2007. Google ScholarDigital Library
- David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. Am Math Monthly, 69(1):9--15, 1962.Google ScholarCross Ref
- David Gale and Marilda Sotomayor. Some remarks on the stable marriage problem. Discrete Applied Mathematics, 11:223--232, 1985.Google ScholarCross Ref
- Theodore Groves. Incentives in teams. Econometrica, 41(4):617--631, 1973.Google ScholarCross Ref
- J. A. S. Kelso and V. P. Crawford. Job matching, coalition formation, and gross substitutes. Econometrica, 50:1483--1504, 1982.Google ScholarCross Ref
- Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Logistics Quarterly, 2:83--97, 1955.Google ScholarCross Ref
- Herman B. Leonard. Elicitation of honest preferences for the assignment of individuals to positions. Journal of Political Economy, 91:461--479, 1983.Google ScholarCross Ref
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors. Algorithmic Game Theory. Cambridge University Press, Septermber 2007. Google ScholarDigital Library
- M. Quinzii. Core and competitive equilibria with indivisibilities. International Journal of Game Theory, 13(1):41--60, 1984.Google ScholarDigital Library
- Alvin E. Roth. The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4):617--628, 1982.Google ScholarDigital Library
- Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-sided matching: A study in game-theoretic modeling and analysis. Cambridge University Press, 1990.Google Scholar
- Lloyd S. Shapley and Martin Shubik. The assignment game i: The core. Intl J. of Game Theory, 1(1):111--130, 1971.Google ScholarCross Ref
- Hal R. Varian. Position auctions. International Journal of Industrial Organization, 2006.Google Scholar
- William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. J.of Finance, 16(1):8--37, 1961.Google ScholarCross Ref
- Wikipedia. http://en.wikipedia.org/wiki/Hungarian_algorithm.Google Scholar
Index Terms
- General auction mechanism for search advertising
Recommendations
On revenue in the generalized second price auction
WWW '12: Proceedings of the 21st international conference on World Wide WebThe Generalized Second Price (GSP) auction is the primary auction used for selling sponsored search advertisements. In this paper we consider the revenue of this auction at equilibrium. We prove that if agent values are drawn from identical regular ...
Nash Bargaining Based Ad Networks for Sponsored Search Auctions
CEC '09: Proceedings of the 2009 IEEE Conference on Commerce and Enterprise ComputingIn this paper, we consider an emerging scenario in sponsored web search auctions where ad networks would be involved as intermediaries between a search engine and its advertisers. In this context, we address the problem of the ad network identifying a ...
On Multiple Keyword Sponsored Search Auctions with Budgets
We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their ...
Comments