Document Open Access Logo

Maximizing Revenue in the Presence of Intermediaries

Authors Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, Andres Perlroth

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.1.pdf
  • Filesize: 0.72 MB
  • 22 pages

Document Identifiers

Author Details

Gagan Aggarwal
  • Google Research, Mountain View, CA, USA
Kshipra Bhawalkar
  • Google Research, Mountain View, CA, USA
Guru Guruganesh
  • Google Research, Mountain View, CA, USA
Andres Perlroth
  • Google Research, Mountain View, CA, USA

Cite As Get BibTex

Gagan Aggarwal, Kshipra Bhawalkar, Guru Guruganesh, and Andres Perlroth. Maximizing Revenue in the Presence of Intermediaries. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ITCS.2022.1

Abstract

We study the mechanism design problem of selling k items to unit-demand buyers with private valuations for the items. A buyer either participates directly in the auction or is represented by an intermediary, who represents a subset of buyers. Our goal is to design robust mechanisms that are independent of the demand structure (i.e. how the buyers are partitioned across intermediaries), and perform well under a wide variety of possible contracts between intermediaries and buyers.
We first consider the case of k identical items where each buyer draws its private valuation for an item i.i.d. from a known λ-regular distribution. We construct a robust mechanism that, independent of the demand structure and under certain conditions on the contracts between intermediaries and buyers, obtains a constant factor of the revenue that the mechanism designer could obtain had she known the buyers' valuations. In other words, our mechanism’s expected revenue achieves a constant factor of the optimal welfare, regardless of the demand structure. Our mechanism is a simple posted-price mechanism that sets a take-it-or-leave-it per-item price that depends on k and the total number of buyers, but does not depend on the demand structure or the downstream contracts.
Next we generalize our result to the case when the items are not identical. We assume that the item valuations are separable, i.e. v_{i j} = η_j v_i for buyer i and item j, with each private v_i drawn i.i.d. from a known λ-regular distribution. For this case, we design a mechanism that obtains at least a constant fraction of the optimal welfare, by using a menu of posted prices. This mechanism is also independent of the demand structure, but makes a relatively stronger assumption on the contracts between intermediaries and buyers, namely that each intermediary prefers outcomes with a higher sum of utilities of the subset of buyers represented by it.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory and mechanism design
Keywords
  • Mechanism Design
  • Revenue Maximization
  • Posted Price Mechanisms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian. Bayesian optimal auctions via multi- to single-agent reduction. In Proceedings of the 13th ACM Conference on Electronic Commerce, EC '12, page 17, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2229012.2229017.
  2. Amine Allouah and Omar Besbes. Auctions in the online display advertising chain: A case for independent campaign management. Technical Report 17-60, Columbia Business School Research Paper, 2017. URL: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2919665.
  3. Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. A simple and approximately optimal mechanism for an additive buyer. J. ACM, 67(4), June 2020. URL: https://doi.org/10.1145/3398745.
  4. Santiago R Balseiro and Ozan Candogan. Optimal contracts for intermediaries in online advertising. Operations Research, 65(4):878-896, 2017. URL: https://doi.org/10.1287/opre.2017.1618.
  5. Santiago R. Balseiro, Ozan Candogan, and Huseyin Gurkan. Intermediation in Online Advertising, pages 505-528. Springer International Publishing, Cham, 2019. URL: https://doi.org/10.1007/978-3-030-01863-4_21.
  6. Dirk Bergemann, Benjamin Brooks, and Stephen Morris. Selling to intermediaries: Optimal auction design in a common value model. Technical report, Cowles Foundation for Research in Economics, Yale University, 2017. URL: https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3018883.
  7. Patrick Briest, Shuchi Chawla, Robert Kleinberg, and S. Matthew Weinberg. Pricing randomized allocations. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 585-597. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.49.
  8. Michel Broniatowski and Michel Weber. Strong laws for sums of extreme values. Theory of Probability & Its Applications, 42(3):395-404, 1998. URL: https://doi.org/10.1137/S0040585X97976283.
  9. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. An algorithmic characterization of multi-dimensional mechanisms. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 459-478. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214021.
  10. Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg. Optimal multi-dimensional mechanism design: Reducing revenue to welfare maximization. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 130-139. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.88.
  11. Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg. A duality based unified approach to bayesian mechanism design. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 926-939. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897645.
  12. Yang Cai and Mingfei Zhao. Simple mechanisms for subadditive buyers via duality. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170-183. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055465.
  13. Gabriel Carroll. Robustness and separation in multidimensional screening. Econometrica, 85(2):453-488, 2017. URL: https://doi.org/10.3982/ECTA14165.
  14. Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg. Algorithmic pricing via virtual valuations. In Jeffrey K. MacKie-Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, June 11-15, 2007, pages 243-251. ACM, 2007. URL: https://doi.org/10.1145/1250910.1250946.
  15. Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan. Multi-parameter mechanism design and sequential posted pricing. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 311-320. ACM, 2010. URL: https://doi.org/10.1145/1806689.1806733.
  16. Shuchi Chawla, David L. Malec, and Balasubramanian Sivan. The power of randomness in bayesian optimal mechanism design. In David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz, editors, Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010, pages 149-158. ACM, 2010. URL: https://doi.org/10.1145/1807342.1807366.
  17. Shuchi Chawla and J. Benjamin Miller. Mechanism design for subadditive agents via an ex ante relaxation. In Vincent Conitzer, Dirk Bergemann, and Yiling Chen, editors, Proceedings of the 2016 ACM Conference on Economics and Computation, EC '16, Maastricht, The Netherlands, July 24-28, 2016, pages 579-596. ACM, 2016. URL: https://doi.org/10.1145/2940716.2940756.
  18. Yeon-Koo Che, Daniele Condorelli, and Jinwoo Kim. Weak cartels and collusion-proof auctions. Journal of Economic Theory, 178:398-435, 2018. URL: https://doi.org/10.1016/j.jet.2018.09.005.
  19. Yeon-Koo Che and Jinwoo Kim. Robustly collusion-proof implementation. Econometrica, 74(4):1063-1107, 2006. URL: https://doi.org/10.1111/j.1468-0262.2006.00694.x.
  20. Yeon-Koo Che and Jinwoo Kim. Optimal collusion-proof auctions. Journal of Economic Theory, 144(2):565-603, 2009. URL: https://doi.org/10.1016/j.jet.2008.07.004.
  21. Hana Choi, Carl F. Mela, Santiago R. Balseiro, and Adam Leary. Online Display Advertising Markets: A Literature Review and Future Directions. Information Systems Research, 31(2):556-575, June 2020. URL: https://doi.org/10.1287/isre.2019.0902.
  22. Sandor Csorgo. Limit theorems for sums of order statistics. Technical report, North Carolina State University. Dept. of Statistics, 1989. URL: https://repository.lib.ncsu.edu/bitstream/handle/1840.4/3676/ISMS_1989_1795.pdf?sequence=1.
  23. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. The complexity of optimal mechanism design. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1302-1318. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.96.
  24. Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos. Strong duality for a multiple-good monopolist. Econometrica, 85(3):735-767, 2017. URL: https://doi.org/10.3982/ECTA12618.
  25. Darrell Duffie, Nicolae Gârleanu, and Lasse Heje Pedersen. Over-the-counter markets. Econometrica, 73(6):1815-1847, 2005. URL: https://doi.org/10.1111/j.1468-0262.2005.00639.x.
  26. Jon Feldman, Vahab Mirrokni, S Muthukrishnan, and Mallesh M Pai. Auctions with intermediaries. In Proceedings of the 11th ACM conference on Electronic commerce, pages 23-32, 2010. URL: https://doi.org/10.1145/1807342.1807346.
  27. Andrew V. Goldberg and Jason D. Hartline. Collusion-resistant mechanisms for single-parameter agents. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 620-629, USA, 2005. Society for Industrial and Applied Mathematics. Google Scholar
  28. Sergiu Hart and Noam Nisan. The menu-size complexity of auctions. In Michael J. Kearns, R. Preston McAfee, and Éva Tardos, editors, Proceedings of the fourteenth ACM Conference on Electronic Commerce, EC 2013, Philadelphia, PA, USA, June 16-20, 2013, pages 565-566. ACM, 2013. URL: https://doi.org/10.1145/2492002.2482544.
  29. Sergiu Hart and Noam Nisan. Approximate revenue maximization with multiple items. Journal of Economic Theory, 172:313-347, 2017. URL: https://doi.org/10.1016/j.jet.2017.09.001.
  30. Sergiu Hart and Philip J. Reny. Maximal revenue with multiple goods: Nonmonotonicity and other observations. Theoretical Economics, 10(3):893-922, 2015. URL: https://doi.org/10.3982/TE1517.
  31. Patrick Hummel, R Preston McAfee, and Sergei Vassilvitskii. Incentivizing advertiser networks to submit multiple bids. International Journal of Game Theory, 45(4):1031-1052, 2016. Google Scholar
  32. Robert Kleinberg and S. Matthew Weinberg. Matroid prophet inequalities. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 123-136. ACM, 2012. URL: https://doi.org/10.1145/2213977.2213991.
  33. Robert Kleinberg and Yang Yuan. On the ratio of revenue to welfare in single-parameter mechanism design. In Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC '13, pages 589-602, New York, NY, USA, 2013. Association for Computing Machinery. URL: https://doi.org/10.1145/2492002.2482584.
  34. Vijay Krishna. Auction Theory. Number 9780123745071 in Elsevier Monographs. Elsevier, December 2009. URL: https://ideas.repec.org/b/eee/monogr/9780123745071.html.
  35. Shengwu Li. Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257-87, November 2017. URL: https://doi.org/10.1257/aer.20160425.
  36. Xinye Li and Andrew Chi-Chih Yao. On revenue maximization for selling multiple independently distributed items. Proc. Natl. Acad. Sci. USA, 110(28):11232-11237, 2013. URL: https://doi.org/10.1073/pnas.1309533110.
  37. Alejandro M. Manelli and Daniel R. Vincent. Bundling as an optimal selling mechanism for a multiple-good monopolist. J. Econ. Theory, 127(1):1-35, 2006. URL: https://doi.org/10.1016/j.jet.2005.08.007.
  38. R. Preston McAfee, John McMillan, and Michael D. Whinston. Multiproduct Monopoly, Commodity Bundling, and Correlation of Values*. The Quarterly Journal of Economics, 104(2):371-383, May 1989. URL: https://doi.org/10.2307/2937852.
  39. S. Muthukrishnan. Ad exchanges: Research issues. In Stefano Leonardi, editor, Internet and Network Economics, pages 1-12, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-10841-9_1.
  40. Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58-73, 1981. URL: https://doi.org/10.1287/moor.6.1.58.
  41. Gregory Pavlov. Auction design in the presence of collusion. Theoretical Economics, 3(3):383-429, 2008. URL: https://doi.org/1555-7561/20080383.
  42. Aviad Rubinstein and S. Matthew Weinberg. Simple mechanisms for a subadditive buyer and applications to revenue monotonicity. In Tim Roughgarden, Michal Feldman, and Michael Schwarz, editors, Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC '15, Portland, OR, USA, June 15-19, 2015, pages 377-394. ACM, 2015. URL: https://doi.org/10.1145/2764468.2764510.
  43. Nikolaus Schweizer and Nora Szech. Performance bounds for optimal sales mechanisms beyond the monotone hazard rate condition. Journal of Mathematical Economics, 82:202-213, 2019. URL: https://doi.org/10.1016/j.jmateco.2019.02.007.
  44. Lampros C. Stavrogiannis, Enrico H. Gerding, and Maria Polukarov. Competing intermediary auctions. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems, AAMAS '13, pages 667-674, New York, NY, USA, 2013. Association for Computing Machinery. Google Scholar
  45. John Thanassoulis. Haggling over substitutes. Journal of Economic Theory, 117(2):217-245, 2004. URL: https://doi.org/https://doi.org/10.1016/j.jet.2003.09.002.
  46. Andrew Chi-Chih Yao. An n-to-1 bidder reduction for multi-item auctions and its applications. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 92-109. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact