×

zbMATH — the first resource for mathematics

Ad exchange: envy-free auctions with mediators. (English) Zbl 1406.91157
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 104-117 (2015).
Summary: Ad exchanges are an emerging platform for trading advertisement slots on the web with billions of dollars revenue per year. Every time a user visits a web page, the publisher of that web page can ask an ad exchange to auction off the ad slots on this page to determine which advertisements are shown at which price. Due to the high volume of traffic, ad networks typically act as mediators for individual advertisers at ad exchanges. If multiple advertisers in an ad network are interested in the ad slots of the same auction, the ad network might use a “local” auction to resell the obtained ad slots among its advertisers.
In this work, we want to deepen the theoretical understanding of these new markets by analyzing them from the viewpoint of combinatorial auctions. Prior work studied mostly single-item auctions, while we allow the advertisers to express richer preferences over multiple items. We develop a game-theoretic model for the entanglement of the central auction at the ad exchange with the local auctions at the ad networks. We consider the incentives of all three involved parties and suggest a three-party competitive equilibrium, an extension of the Walrasian equilibrium that ensures envy-freeness for all participants. We show the existence of a three-party competitive equilibrium and a polynomial-time algorithm to find one for gross-substitute bidder valuations.
For the entire collection see [Zbl 1326.68026].

MSC:
91B26 Auctions, bargaining, bidding and selling, and other market models
91B50 General equilibrium theory
90B60 Marketing, advertising
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Balseiro, S., Besbes, O., Weintraub, G.Y.: Auctions for online display advertising exchanges: approximations and design. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce (EC 2013), pp. 53–54. ACM, New York (2013) · doi:10.1145/2492002.2482576
[2] Balseiro, S.R., Feldman, J., Mirrokni, V.S., Muthukrishnan, S.: Yield optimization of display advertising with ad exchange. Manage. Sci. 60(12), 2886–2907 (2014). Preliminary version in EC 2011 · doi:10.1287/mnsc.2014.2017
[3] Blumrosen, L., Nisan, N.: Combinatorial auctions. In: Nisan, N., Roughgarden, T., Tardos, É., Vazirani, V.V. (eds.) Algorithmic Game Theory, Chap. 11, pp. 267–299. Cambridge University Press, Cambridge (2007) · Zbl 1152.91453 · doi:10.1017/CBO9780511800481.013
[4] Business Insider: How Massive Real-Time Bidding Has Gotten in Online Advertising. http://www.businessinsider.com/dollar-numbers-for-real-time-bidding-in-digital-advertising-2012-6
. Accessed 28 July 2014
[5] Feldman, J., Mirrokni, V., Muthukrishnan, S., Pai, M.M.: Auctions with intermediaries: extended abstract. In: Proceedings of the 11th ACM Conference on Electronic Commerce (EC 2010), pp. 23–32. ACM, New York (2010) · doi:10.1145/1807342.1807346
[6] GDN: About the Display Network ad auction. https://support.google.com/adwords/answer/2996564
. Accessed 30 January 2014
[7] Gul, F., Stacchetti, E.: Walrasian equilibrium with gross substitutes. J. Econ. Theor. 87(1), 95–124 (1999) · Zbl 0998.91010 · doi:10.1006/jeth.1999.2531
[8] Guruswami, V., Hartline, J.D., Karlin, A.R., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1164–1173. SIAM, Philadelphia (2005) · Zbl 1297.91072
[9] Hatfield, J.W., Kominers, S.D., Nichifor, A., Ostrovsky, M., Westkamp, A.: Stability and competitive equilibrium in trading networks. J. Polit. Econ. 121(5), 966–1005 (2013) · doi:10.1086/673402
[10] Hatfield, J.W., Milgrom, P.R.: Matching with contracts. Am. Econ. Rev. 95(4), 913–935 (2005) · doi:10.1257/0002828054825466
[11] Kelso, A.S.J., Crawford, V.P.: Job matching, coalition formation, and gross substitutes. Econometrica 50(6), 1483–1504 (1982) · Zbl 0503.90019 · doi:10.2307/1913392
[12] Lehmann, B., Lehmann, D.J., Nisan, N.: Combinatorial auctions with decreasing marginal utilities. Games Econ. Behav. 55(2), 270–296 (2006) · Zbl 1125.91043 · doi:10.1016/j.geb.2005.02.006
[13] Mansour, Y., Muthukrishnan, S., Nisan, N.: Doubleclick ad exchange auction (2012). http://arxiv.org/abs/1204.0535
[14] Muthukrishnan, S.: Ad exchanges: research issues. In: Leonardi, S. (ed.) WINE 2009. LNCS, vol. 5929, pp. 1–12. Springer, Heidelberg (2009)
[15] Nisan, N., Segal, I.: The communication requirements of efficient allocations and supporting prices. J. Econ. Theor. 129, 192–224 (2006) · Zbl 1132.91531 · doi:10.1016/j.jet.2004.10.007
[16] Ostrovsky, M.: Stability in supply chain networks. Am. Econ. Rev. 98(3), 897–923 (2008) · doi:10.1257/aer.98.3.897
[17] Paes Leme, R.: Gross substitutability: an algorithmic survey (2014). http://www.renatoppl.com/papers/gs-survey-jul-14.pdf · Zbl 1414.91268
[18] Stavrogiannis, L.C., Gerding, E.H., Polukarov, M.: Competing intermediary auctions. In: International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), pp. 667–674. International Foundation for Autonomous Agents and Multiagent Systems, Richland (2013)
[19] Stavrogiannis, L.C., Gerding, E.H., Polukarov, M.: Auction mechanisms for demand-side intermediaries in online advertising exchanges. In: International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2014), pp. 1037–1044. International Foundation for Autonomous Agents and Multiagent Systems, Richland (2014)
[20] Walras, L.: Éléments d’Économie Politique Pure, ou Théorie de la Richesse Sociale. Corbaz, Lausanne (1874)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.