Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Blockchain Intra- and Interoperability Read chapter Read first chapter

2022 | OriginalPaper | Chapter

Market Equilibrium Models in Large-Scale Internet Markets

Authors : Christian Kroer, Nicolas E. Stier-Moses

Published in: Innovative Technology at the Interface of Finance and Operations

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Markets and their corresponding equilibrium concepts have traditionally been used as very powerful building blocks to find allocations and prices. This chapter provides examples of the use of Fisher markets in the technology industry. We focus on Internet advertising auctions, fair division problems, content recommendation systems, and robust abstractions of large-scale markets. After introducing these markets, we describe how these models fit the relevant application domains and what insights they can generate, exhibiting the most important theoretical and computational results from the recent literature on these topics.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Integrated Framework for Financial Risk Management, Operational Modeling, and IoT-Driven Execution
next chapter Large-Scale Price Optimization for an Online Fashion Retailer
Footnotes
1
In this case with continuous distributions, the probability of ties is zero.
 
2
See also Murray et al. (2020b).
 
3
Every optimal solution to EG must lie in this set, assuming that every good j has some i such that v ij > 0; if this does not hold then that good can simply be preprocessed away.
 
Literature
Aleksandrov, M., & Walsh, T. (2020). Online fair division: A survey. Proceedings of the AAAI Conference on Artificial Intelligence, 34(9), 13557–13562.CrossRef
Allouah, A., Avadhanula, V., Kroer, C., Pupyrev, S., Shah, P., & Zhang, X. (2022). Robust and fair work allocation. Mimeo.
Azizan, N., Su, Y., Dvijotham, K., & Wierman, A. (2020). Optimal pricing in markets with nonconvex costs. Operations Research, 68(2), 480–496.
Balseiro, S. R., & Gur, Y. (2019). Learning in repeated auctions with budgets: Regret minimization and equilibrium. Management Science, 65(9), 3952–3968.CrossRef
Balseiro, S. R., Besbes, O., & Weintraub, G. Y. (2015). Repeated auctions with budgets in ad exchanges: Approximations and design. Management Science, 61(4), 864–884.CrossRef
Balseiro, S. R., Kim, A., Mahdian, M., & Mirrokni, V. (2017). Budget management strategies in repeated auctions. In Proceedings of the 26th International Conference on World Wide Web (WWW’17), pp. 15–23.CrossRef
Bastani, H., Zhang, D. J., & Zhang, H. (2021). Applied machine learning in operations management. In V. Birge Babich & J. G. Hilary (Eds.), Innovative technology at the interface of finance and operations. Series in supply chain management. Berlin: Springer.
Bei, X., Garg, J., & Hoefer, M. (2019). Ascending-price algorithms for unknown markets. ACM Transactions on Algorithms, 15(3), 1–33.CrossRef
Bertsekas, D. P., Nedic, A., & Ozdaglar, A. (2003). Convex analysis and optimization. Nashua: Athena Scientific.
Birnbaum, B., Devanur, N. R., & Xiao, L. (2011). Distributed algorithms via gradient descent for Fisher markets. In Proceedings of the ACM Conference on Electronic Commerce (EC’11) (pp. 127–136). New York: ACM.CrossRef
Borgs, C., Chayes, J., Immorlica, N., Jain, K., Etesami, O., & Mahdian, M. (2007). Dynamics of bid optimization in online advertisement auctions. In Proceedings of the 16th International Conference on World Wide Web (WWW’07) (pp. 531–540).
Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (2016) Handbook of computational social choice. Cambridge: Cambridge University Press.CrossRef
Brown, N., & Sandholm, T. (2018). Superhuman AI for heads-up no-limit poker: Libratus beats top professionals. Science, 359(6374), 418–424.CrossRef
Brown, N., Ganzfried, S., & Sandholm, T. (2015). Hierarchical abstraction, distributed equilibrium computation, and post-processing, with application to a champion no-limit Texas hold’em agent. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS’15) (pp. 7–15). International Foundation for Autonomous Agents and Multiagent Systems.
Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends® in Machine Learning, 8(3–4), 231–357.CrossRef
Budish, E. (2011). The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6), 1061–1103.CrossRef
Budish, E., Cachon, G. P., Kessler, J. B., & Othman, A. (2016). Course match: A large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation. Operations Research, 65(2):314–336.CrossRef
Budish, E., Che, Y.-K., Kojima, F., & Milgrom, P. (2013). Designing random allocation mechanisms: Theory and applications. American Economic Review, 103(2), 585–623.CrossRef
Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6), 717.CrossRef
Candogan, O., Epitropou, M., & Vohra, R. V. (2016). Competitive equilibrium and trading networks: A network flow approach. In Proceedings of the ACM Conference on Economics and Computation (EC’16) (pp. 701–702).
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3), 1–32.CrossRef
Chen, L., Ye, Y., & Zhang, J. (2007). A note on equilibrium pricing as convex optimization. In International Workshop on Web and Internet Economics (WINE’07) (pp. 7–16). Berlin: Springer.
Chi, Y., Lu, Y. M., & Chen, Y. (2019). Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions on Signal Processing, 67(20), 5239–5269.CrossRef
Choi, H., Mela, C. F., Balseiro, S. R., & Leary, A. (2020). Online display advertising markets: A literature review and future directions. Information Systems Research, 31(2):556–575.CrossRef
Cole, R., Devanur, N. R., Gkatzelis, V., Jain, K., Mai, T., Vazirani, V. V., & Yazdanbod, S. (2017). Convex program duality, Fisher markets, and Nash social welfare. In ACM Conference on Economics and Computation (EC’17). New York: Association for Computing Machinery.
Conitzer, V., Kroer, C., Sodomka, E., & Stier-Moses, N. E. (2018). Multiplicative pacing equilibria in auction markets. In International Conference on Web and Internet Economics(WINE’18).
Conitzer, V., Kroer, C., Panigrahi, D., Schrijvers, O., Sodomka, E., Stier-Moses, N. E., & Wilkens, C. (2019). Pacing equilibrium in first-price auction markets. In Proceedings of the ACM Conference on Economics and Computation (EC’19). New York: ACM.
Debreu, G. (1952). A social equilibrium existence theorem. Proceedings of the National Academy of Sciences, 38(10), 886–893.CrossRef
Devanur, N.R., Papadimitriou, C.H., Saberi, A., & Vazirani, V. V. (2008). Market equilibrium via a primal–dual algorithm for a convex program. Journal of the ACM, 55(5), 1–18.CrossRef
Diamond, S., & Boyd, S. (2016). CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83), 1–5.
Eisenberg, E. (1961). Aggregation of utility functions. Management Science, 7(4), 337–350.CrossRef
Eisenberg, E., & Gale, D. (1959). Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1), 165–168.CrossRef
Fan, K. (1952). Fixed-point and minimax theorems in locally convex topological linear spaces. Proceedings of the National Academy of Sciences of the United States of America, 38(2), 121.CrossRef
Flajolet, A., & Jaillet,, P. (2017). Real-time bidding with side information. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NeurIPS’17) (5168–5178). Red Hook: Curran Associates.
Gao, Y., & Kroer, C. (2020). First-order methods for large-scale market equilibrium computation. In Advances in Neural Information Processing Systems (NeurIPS’20).
Ghodsi, M., HajiAghayi, M.-T., Seddighin, M., Seddighin, S., & Yami, H. (2018). Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the ACM Conference on Economics and Computation (EC’18) (pp. 539–556).
Gilpin, A., Sandholm, T., & Sørensen, T. B. (2007). Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of Texas hold’em poker. In Proceedings of the 22nd National Conference on Artificial Intelligence (vol. 1, pp. 50–57). Palo Alto: AAAI Press.
Glicksberg, I. L. (1952). A further generalization of the Kakutani fixed point theorem, with application to Nash equilibrium points. Proceedings of the American Mathematical Society, 3(1), 170–174.
Goldman, J., & Procaccia, A. D. (2015). Spliddit: Unleashing fair division algorithms. ACM SIGecom Exchanges, 13(2), 41–46.CrossRef
Kroer, C. (2020). IEOR8100: Economics, AI, and optimization lecture note 14: Large-scale fisher market equilibrium.
Kroer, C., & Peysakhovich, A. (2019). Scalable fair division for ‘at most one’ preferences. arXiv:1909.10925.
Kroer, C., & Sandholm, T. (2014). Extensive-form game abstraction with bounds. In Proceedings of the ACM Conference on Economics and Computation (EC’14) (pp. 621–638). New York: ACM.
Kroer, C., & Sandholm, T. (2016). Imperfect-recall abstractions with bounds in games. In Proceedings of the ACM Conference on Economics and Computation (EC’16) (pp. 459–476). New York: ACM.CrossRef
Kroer, C., & Sandholm, T. (2018). A unified framework for extensive-form game abstraction with bounds. In Advances in Neural Information Processing Systems (NeurIPS’18) (pp. 612–623).
Kroer, C., Peysakhovich, A., Sodomka, E., & Stier-Moses, N. E. (2019). Computing large market equilibria using abstractions. In Proceedings of the ACM Conference on Economics and Computation (EC’19) (pp. 745–746).
Lanctot, M., Gibson, R., Burch, N., Zinkevich, M., & Bowling, M. (2012). No-regret learning in extensive-form games with imperfect recall. In Proceedings of the 29th International Coference on Machine Learning (ICML’12) (pp. 1035–1042). Madison: Omnipress.
Levin, D., LaCurts, K., Spring, N., & Bhattacharjee, B. (2008). Bittorrent is an auction: Analyzing and improving bittorrent’s incentives. In Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication (pp. 243–254).
Lu, T., & Boutilier, C. (2015). Value-directed compression of large-scale assignment problems. In Twenty-Ninth AAAI Conference on Artificial Intelligence. Menlo Park: AAAI Press.
McElfresh, D. C., Kroer, C., Pupyrev, S., Sodomka, E., Sankararaman, K. A., Chauvin, Z., Dexter, N., & Dickerson, J. P. (2020). Matching algorithms for blood donation. In Proceedings of the ACM Conference on Economics and Computation (EC’20) (pp. 463–464).
Mehrotra, R., McInerney, J., Bouchard, H., Lalmas, M., & Diaz, F. (2018). Towards a fair marketplace: Counterfactual evaluation of the trade-off between relevance, fairness & satisfaction in recommendation systems. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management (pp. 2243–2251).
Murray, R., Kroer, C., Peysakhovich, A., & Shah, P. (2020a). Robust market equilibria with uncertain preferences. In Proceedings of the AAAI Conference on Artificial Intelligence.
Nisan, N., Roughgarden, T., Tardos, E., & Vazirani, V. V. (2007). Algorithmic game theory. Cambridge: Cambridge University Press.CrossRef
O’Donoghue, B., Chu, E., Parikh, N., & Boyd, S. (2016). Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3), 1042–1068.CrossRef
Paes Leme, R., Sivan, B., & Teng, Y. (2020). Why do competitive markets converge to first-price auctions? In Proceedings of The Web Conference 2020, WWW’20 (pp. 596–605). New York: Association for Computing Machinery.CrossRef
Parkes, D. C., Procaccia, A. D., & Shah, N. (2015). Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. ACM Transactions on Economics and Computation, 3(1), 1–22.CrossRef
Peng, F., & Sandholm, T. (2016). Scalable segment abstraction method for advertising campaign admission and inventory allocation optimization. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI’16) (pp. 655–661). Menlo Park: AAAI Press.
Procaccia, A. D. (2013). Cake cutting: Not just child’s play. Communications of the ACM, 56(7), 78–87.CrossRef
Recht, B. (2011). A simpler approach to matrix completion. Journal of Machine Learning Research, 12, 3413–3430.
Shmyrev, V. I. (2009). An algorithm for finding equilibrium in the linear exchange model with fixed budgets. Journal of Applied and Industrial Mathematics, 3(4), 505.CrossRef
Talluri, K., & Van Ryzin, G. (1998). An analysis of bid-price controls for network revenue management. Management Science, 44, 1577–1593.CrossRef
Udell, M. (2019). Big data is low rank. SIAG/OPT Views and News.
Udell, M., Horn, C., Zadeh, R., & Boyd, S. (2016). Generalized low rank models. Foundations and Trends® in Machine Learning, 9(1), 1–118.CrossRef
Varian, H. R. (1974). Equity, envy, and efficiency. Journal of Economic Theory, 9(1), 63–91.CrossRef
Vazirani, V. V. (2010). Spending constraint utilities with applications to the adwords market. Mathematics of Operations Research, 35(2):458–478.CrossRef
Walsh, T. (2020). Fair division: The computer scientist’s perspective. arXiv:2005.04855.
Walsh, W. E., Boutilier, C., Sandholm, T., Shields, R., Nemhauser, G., & Parkes, D. C. (2010). Automated channel abstraction for advertising auctions. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (pp. 887–894). Menlo Park: AAAI Press.
Wu, F., & Zhang, Li. (2007). Proportional response dynamics leads to market equilibrium. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC’07) (pp. 354–363).
Metadata
Title
Market Equilibrium Models in Large-Scale Internet Markets
Authors
Christian Kroer
Nicolas E. Stier-Moses
Copyright Year
2022
Book
Innovative Technology at the Interface of Finance and Operations

Print ISBN: 978-3-030-81944-6

Electronic ISBN: 978-3-030-81945-3

Copyright Year: 2022

DOI
https://doi.org/10.1007/978-3-030-81945-3_7