Fast core pricing for rich advertising auctions. (English) Zbl 1484.91217
Summary: Standard ad auction formats do not immediately extend to settings where multiple size configurations and layouts are available to advertisers. In these settings, the sale of web advertising space increasingly resembles a combinatorial auction with complementarities, where truthful auctions such as the Vickrey-Clarke-Groves (VCG) auction can yield unacceptably low revenue. We therefore study core-selecting auctions, which boost revenue by setting payments so that no group of agents, including the auctioneer, can jointly improve their utilities by switching to a different outcome. Our main result is a combinatorial algorithm that finds an approximate bidder-optimal core point with an almost linear number of calls to the welfare-maximization oracle. Our algorithm is faster than previously proposed heuristics in the literature and has theoretical guarantees. We conclude that core pricing is implementable even for very time-sensitive practical use cases such as real-time auctions for online advertising and can yield more revenue. We justify this claim experimentally using Microsoft Bing Ad Auction data, through which we show our core pricing algorithm generates almost 26% more revenue than the VCG auction on average, about 9% more revenue than other core pricing rules known in the literature, and almost matches the revenue of the standard generalized second price auction.
MSC:
| 91B26 | Auctions, bargaining, bidding and selling, and other market models |
| 90B60 | Marketing, advertising |
Keywords:
revenue management and market analytics; sponsored search auctions; core pricing; VCG auction; GSP auction; sale of ad space; combinatorial auctionReferences:
| [1] | Aggarwal G, Badanidiyuru A, Mehta A (2019) Autobidding with constraints. Caragiannis I, Mirrokni V, Nikolova E, eds. Internat. Conf. Web Internet Econom. (Springer, Cham, Switzerland), 17-30.Google Scholar · Zbl 1435.91091 |
| [2] | Aggarwal G, Goel A, Motwani R (2006) Truthful auctions for pricing search keywords. Proc. Seventh ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 1-7.Google Scholar |
| [3] | Ausubel L, Baranov OV (2010) Core-selecting auctions with incomplete information. Working paper, University of Maryland, College Park.Google Scholar |
| [4] | Ausubel L, Cramton P (1999) The optimality of being efficient. Working paper, University of Maryland, College Park.Google Scholar |
| [5] | Ausubel L, Milgrom P (2002) Ascending auctions with package bidding. B.E. J. Theoret. Econom. 1(1):1-44.Google Scholar |
| [6] | Ausubel L, Milgrom P (2006) The lovely but lonely Vickrey auction. Cramton P, Shoham Y, Steinberg R, eds. Combinatorial Auctions (MIT Press, Cambridge, MA), 22-26.Google Scholar |
| [7] | Babaioff M, Kleinberg RD, Slivkins A (2015) Truthful mechanisms with implicit payment computation. J. ACM 62(2):1-37.Crossref, Google Scholar · Zbl 1333.91013 · doi:10.1145/2724705 |
| [8] | Beck M, Ott M (2009) Revenue monotonicity in core-selecting package auctions. Working paper.Google Scholar |
| [9] | Bosshard V, Bünz B, Lubin B, Seuken S (2017) Computing Bayes-Nash equilibria in combinatorial auctions with continuous value and action spaces. Proc. 26th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence), 119-127.Google Scholar |
| [10] | Bubeck S (2015) Convex optimization: Algorithms and complexity. Found. Trends Machine Learn. 8(3-4):231-357.Crossref, Google Scholar · Zbl 1365.90196 · doi:10.1561/2200000050 |
| [11] | Bünz B, Seuken S, Lubin B (2015) A faster core constraint generation algorithm for combinatorial auctions. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 827-834.Google Scholar |
| [12] | Bünz B, Lubin B, Seuken S (2018a) Designing core-selecting payment rules: A computational search approach. Preprint, submitted May 25, DOI: http://dx.doi.org/10.2139/ssrn.3178454.Google Scholar |
| [13] | Bünz B, Lubin B, Seuken S (2018b) Designing core-selecting payment rules: A computational search approach. Proc. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 109.Google Scholar |
| [14] | Cavallo R, Krishnamurthy P, Sviridenko M, Wilkens CA (2017) Sponsored search auctions with rich ads. Proc. 26th Internat. Conf. World Wide Web (International World Wide Web Conferences Steering Committee, Geneva), 43-51.Google Scholar |
| [15] | Clarke EH (1971) Multipart pricing of public goods. Public Choice 11(1):17-33.Crossref, Google Scholar · doi:10.1007/BF01726210 |
| [16] | Cramton P (2013) Spectrum auction design. Rev. Indust. Organ. 42(2):161-190.Crossref, Google Scholar · doi:10.1007/s11151-013-9376-x |
| [17] | Day R, Cramton P (2012) Quadratic core-selecting payment rules for combinatorial auctions. Oper. Res. 60(3):588-603.Link, Google Scholar · Zbl 1251.90302 |
| [18] | Day R, Milgrom P (2008) Core-selecting package auctions. Internat. J. Game Theory 36(3-4):393-407.Crossref, Google Scholar · Zbl 1151.91073 · doi:10.1007/s00182-007-0100-7 |
| [19] | Day R, Raghavan S (2007) Fair payments for efficient allocations in public sector combinatorial auctions. Management Sci. 53(9):1389-1406.Link, Google Scholar · Zbl 1232.91286 |
| [20] | Dobzinski S, Nisan N (2007) Mechanisms for multi-unit auctions. Proc. Eighth ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 346-351.Google Scholar |
| [21] | Edelman B, Ostrovsky M (2007) Strategic bidder behavior in sponsored search auctions. Decision Support Systems 43(1):192-198.Crossref, Google Scholar · doi:10.1016/j.dss.2006.08.008 |
| [22] | Edelman B, Ostrovsky M, Schwarz M (2007) Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords. Amer. Econom. Rev. 97(1):242-259.Crossref, Google Scholar · doi:10.1257/aer.97.1.242 |
| [23] | Erdil A, Klemperer P (2010) A new payment rule for core-selecting package auctions. J. Eur. Econom. Assoc. 8(2-3):537-547.Crossref, Google Scholar · doi:10.1111/j.1542-4774.2010.tb00524.x |
| [24] | Goel G, Khani MR (2014) Revenue monotone mechanisms for online advertising. Proc. 23rd Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 723-734.Google Scholar |
| [25] | Goel G, Khani MR, Leme RP (2015) Core-competitive auctions. Proc. 16th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 149-166.Google Scholar |
| [26] | Goeree JK, Lien Y (2016) On the impossibility of core-selecting auctions. Theoret. Econom. 11(1):41-52.Crossref, Google Scholar · Zbl 1395.91228 · doi:10.3982/TE1198 |
| [27] | Gould N, Toint PL (2004) Preprocessing for quadratic programming. Math. Programming 100(1):95-132.Crossref, Google Scholar · Zbl 1146.90491 · doi:10.1007/s10107-003-0487-2 |
| [28] | Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169-197.Crossref, Google Scholar · Zbl 0492.90056 · doi:10.1007/BF02579273 |
| [29] | Groves T (1973) Incentives in teams. Econometrica 41(4):617-631.Crossref, Google Scholar · Zbl 0311.90002 · doi:10.2307/1914085 |
| [30] | Lamy L (2010) Core-selecting package auctions: a comment on revenue-monotonicity. Internat. J. Game Theory 39(3):503-510.Crossref, Google Scholar · Zbl 1211.91139 · doi:10.1007/s00182-009-0188-z |
| [31] | Lee YT, Sidford A, Wong SCW (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. Proc. IEEE 56th Annual Sympos. Found. Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 1049-1065.Google Scholar |
| [32] | Lubin B, Parkes DC (2009) Quantifying the strategyproofness of mechanisms via metrics on payoff distributions. Proc. 25th Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 349-358.Google Scholar |
| [33] | Lubin B, Býnz B, Seuken S (2015) New core-selecting payment rules with better fairness and incentive properties. Kominers SD, Xia L, eds. Proc. Third Conf. Auctions, Market Mechanisms Their Appl. (Association for Computing Machinery, New York).Google Scholar |
| [34] | Mehrotra S (1992) On the implementation of a primal-dual interior point method. SIAM J. Optim. 2(4):575-601.Crossref, Google Scholar · Zbl 0773.90047 · doi:10.1137/0802028 |
| [35] | Milgrom P (2007) Package auctions and exchanges. Econometrica 75(4):935-965.Crossref, Google Scholar · Zbl 1133.91019 · doi:10.1111/j.1468-0262.2007.00778.x |
| [36] | Nisan N, Ronen A (2007) Computationally feasible VCG mechanisms. J. Artificial Intelligence Res. 29:19-47.Crossref, Google Scholar · Zbl 1165.91387 · doi:10.1613/jair.2046 |
| [37] | Osborne MJ, Rubinstein A (1994) A Course in Game Theory (MIT Press, Cambridge, MA).Google Scholar · Zbl 1194.91003 |
| [38] | Rastegari B, Condon A, Leyton-Brown K (2011) Revenue monotonicity in deterministic, dominant-strategy combinatorial auctions. Artificial Intelligence 175(2):441-456.Crossref, Google Scholar · Zbl 1214.91047 · doi:10.1016/j.artint.2010.08.005 |
| [39] | Sandholm T (2002) Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence 135(1-2):1-54.Crossref, Google Scholar · Zbl 0984.68039 · doi:10.1016/S0004-3702(01)00159-X |
| [40] | Sano R (2012) Non-bidding equilibrium in an ascending core-selecting auction. Games Econom. Behav. 74(2):637-650.Crossref, Google Scholar · Zbl 1279.91090 · doi:10.1016/j.geb.2011.08.016 |
| [41] | Sayedi A (2018) Real-time bidding in online display advertising. Marketing Sci. 37(4):553-568.Link, Google Scholar |
| [42] | Sinha P, Zoltners AA (1979) The multiple-choice knapsack problem. Oper. Res. 27(3):503-515.Link, Google Scholar · Zbl 0406.90052 |
| [43] | Vaidya PM (1989) A new algorithm for minimizing convex functions over convex sets. Proc. 30th Annual Sympos. Found. Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 338-343.Google Scholar |
| [44] | Vaidya PM (1996) A new algorithm for minimizing convex functions over convex sets. Math. Programming 73(3):291-341.Crossref, Google Scholar · Zbl 0852.90112 · doi:10.1007/BF02592216 |
| [45] | Vickrey W (1961) Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1):8-37.Crossref, Google Scholar · doi:10.1111/j.1540-6261.1961.tb02789.x |
| [46] | Wilkens CA, Sivan B (2015) Single-call mechanisms. ACM Trans. Econom. Comput. 3(2):10.Google Scholar |
| [47] | Wilkens CA, Cavallo R, Niazadeh R (2017) GSP: The Cinderella of mechanism design. Proc. 26th Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 25-32.Google Scholar |
| [48] | Wilkens CA, Cavallo R, Niazadeh R, Taggart S (2016) Mechanism design for value maximizers. Preprint, submitted July 15, https://arxiv.org/abs/1607.04362.Google Scholar |
| [49] | Xu H, Gao B, Yang D, Liu TY (2013) Predicting advertiser bidding behaviors in sponsored search by rationality modeling. Proc. 22nd Internat. Conf. World Wide Web (Association for Computing Machinery, New York), 1433-1444.Google Scholar |
| [50] | Zhang Y (1998) Solving large-scale linear programs by interior-point methods under the Matlab environment. Optim. Methods Software 10(1):1-31.Crossref, Google Scholar · Zbl 0916.90208 · doi:10.1080/10556789808805699 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
