Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimal Nash Equilibria for Bandwidth Allocation

  • Conference paper
  • First Online:
Web and Internet Economics (WINE 2020)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 12495))

Included in the following conference series:

Abstract

In bandwidth allocation, competing agents wish to transmit data along paths of links in a network, and each agent’s utility is equal to the minimum bandwidth she receives among all links in her desired path. Recent market mechanisms for this problem have either focused on only Nash welfare  [9], or ignored strategic behavior  [21]. We propose a nonlinear variant of the classic trading post mechanism, and show that for almost the entire family of CES welfare functions (which includes maxmin welfare, Nash welfare, and utilitarian welfare), every Nash equilibrium of our mechanism is optimal. We also prove that fully strategyproof mechanisms for this problem are impossible in general, with the exception of maxmin welfare. More broadly, our work shows that even small modifications (such as allowing nonlinear constraints) can dramatically increase the power of market mechanisms like trading post.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    The price of anarchy  [25] concept applies only when \(\varPsi \) can be written as the maximization of some cardinal function. This is true when \(\varPsi \) denotes Nash welfare maximization, but is not true in general.

  2. 2.

    This happens when there is a good that has large enough supply that is not the “rate limiting factor” for any agent; see Sect. 3 and the full version of the paper  [35] for additional discussion.

  3. 3.

    They study Leontief utilities, which is a generalization of bandwidth allocation to the setting where agents may desire goods in different proportions.

  4. 4.

    A slightly weaker version of continuity is often used: given an allocation \(\mathbf {x}\), the sets \(\{\mathbf {y}: \varPhi (\mathbf {x}) \ge \varPhi (\mathbf {y})\}\) and \(\{\mathbf {y}: \varPhi (\mathbf {x}) \le \varPhi (\mathbf {y})\}\) should be closed. This weaker version only requires a welfare ordering and does not require that this ordering be expressed by a function. However, any such ordering which also satisfies the rest of our axioms is indeed representable by a welfare function  [30], and so both sets of axioms end up specifying the same set of welfare functions/orderings.

  5. 5.

    Without the Pigou-Dalton principle, \(\rho > 1\) is also allowed. This can result in unnatural cases where it is optimal to give one agent everything and the rest none, even when this does not maximize the sum of utilities.

  6. 6.

    This actually does not include maxmin welfare, which obeys weak monotonicity but not strict monotonicity.

  7. 7.

    The reader may notice that for \(\rho = 0\) – which corresponds to Nash welfare – this constraint reduces to the standard linear constraint of \(\sum _j b_{ij} \le 1\), which is what we should expect: we know from  [9] that trading post with the linear constraint leads to good Nash welfare.

  8. 8.

    It is worth noting that the result of [9] holds for Leontief utilities, a generalization of bandwidth allocation utilities.

  9. 9.

    The mechanism for this result is unrelated to trading post: our trading post approach breaks down for both maxmin welfare and utilitarian welfare. This is because \(g_j(x) = q_j x^{1-\rho }\) is not a valid price curve when \(\rho \rightarrow -\infty \) or when \(\rho = 1\).

  10. 10.

    A plethora of other names have been applied to this mechanism as well, including the proportional share mechanism  [18], the Chinese auction  [28], and the Tullock contest in rent seeking  [10].

  11. 11.

    Recently, this topic has garnered significant attention in the computer science community as well (see  [42] for an algorithmic exposition).

  12. 12.

    There is some work treating price-taking market models as strategic games; see e.g., [1, 8, 9].

  13. 13.

    Specifically, an equilibrium is guaranteed to exist as long agent utilities are continuous, quasi-concave, and non-satiated. The full Arrow-Debreu model also allows for agents to enter to market with goods themselves and not only money; the necessary conditions on utilities are slightly more complex in that setting.

  14. 14.

    The conditions for the correspondence between Fisher market equilibria and Nash welfare are slightly stricter than those for market equilibrium existence, but are still quite general. Sufficient criteria were given in [16] and generalized slightly by [22].

References

  1. Adsul, B., Babu, C.S., Garg, J., Mehta, R., Sohoni, M.: Nash equilibria in fisher market. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 30–41. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16170-4_4

    Chapter  Google Scholar 

  2. Arrow, K.J., Debreu, G.: Existence of an equilibrium for a competitive economy. Econometrica 22(3), 265–290 (1954)

    Article  MathSciNet  Google Scholar 

  3. Atkinson, A.B.: On the measurement of inequality. J. Econ. Theor. 2(3), 244–263 (1970)

    Article  MathSciNet  Google Scholar 

  4. Bergson, A.: A reformulation of certain aspects of welfare economics. Quart. J. Econ. 52(2), 310–334 (1938)

    Article  Google Scholar 

  5. Blackorby, C., Donaldson, D.: Measures of relative equality and their meaning in terms of social welfare. J. Econ. Theor. 18(1), 59–80 (1978)

    Article  MathSciNet  Google Scholar 

  6. Bonald, T., Massoulié, L.: Impact of fairness on internet performance. SIGMETRICS Perform. Eval. Rev. 29(1), 82–91 (2001)

    Article  Google Scholar 

  7. Brainard, W.C., Scarf, H.E.: How to compute equilibrium prices in 1891. Am. J. Econ. Sociol. 64(1), 57–83 (2005)

    Article  Google Scholar 

  8. Brânzei, S., Chen, Y., Deng, X., Filos-Ratsikas, A., Frederiksen, S.K.S., Zhang, J.: The fisher market game: equilibrium and welfare. In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI 2014, pp. 587–593. AAAI Press (2014)

    Google Scholar 

  9. Branzei, S., Gkatzelis, V., Mehta, R.: Nash social welfare approximation for strategic agents. In: Proceedings of the 2017 ACM Conference on Economics and Computation, EC 2017, pp. 611–628. ACM, New York (2017)

    Google Scholar 

  10. Buchanan, J.M., Tollison, R.D., Tullock, G.: Toward a Theory of the Rent-Seeking Society. vol. 4. Texas A & M University Press, College Station (1980)

    Google Scholar 

  11. Cerf, V., Kahn, R.: A protocol for packet network intercommunication. IEEE Trans. Commun. 22(5), 637–648 (1974)

    Article  Google Scholar 

  12. Cole, R., Gkatzelis, V., Goel, G.: Mechanism design for fair division: allocating divisible items without payments. In: EC 2013 (2013)

    Google Scholar 

  13. Dalton, H.: The measurement of the inequality of incomes. Econ. J. 30(119), 348–361 (1920)

    Article  Google Scholar 

  14. Dasgupta, P., Hammond, P., Maskin, E.: The implementation of social choice rules: some general results on incentive compatibility. Rev. Econ. Stud. 46(2), 185–216 (1979)

    Article  MathSciNet  Google Scholar 

  15. Dubey, P., Shubik, M.: A theory of money and financial institutions. 28. the non-cooperative equilibria of a closed trading economy with market supply and bidding strategies. J. Econ. Theor. 17(1), 1–20 (1978)

    Google Scholar 

  16. Eisenberg, E.: Aggregation of utility functions. Manage. Sci. 7(4), 337–350 (1961)

    Article  Google Scholar 

  17. Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Stat. 30(1), 165–168 (1959)

    Article  MathSciNet  Google Scholar 

  18. Feldman, M., Lai, K., Zhang, L.: The proportional-share allocation market for computational resources. Trans. Parallel Distrib. Syst. 20(8), 1075–1088 (2009)

    Article  Google Scholar 

  19. Floyd, S., Jacobson, V.: Random early detection gateways for congestion avoidance. IEEE/ACM Trans. Netw. 1(4), 397–413 (1993)

    Article  Google Scholar 

  20. Giraud, G.: Strategic market games: an introduction. J. Math. Econ. 39(5), 355–375 (2003)

    Google Scholar 

  21. Goel, A., Hulett, R., Plaut, B.: Markets beyond nash welfare for leontief utilities. CoRR abs/1807.05293 (2018)

    Google Scholar 

  22. Jain, K., Vazirani, V.V.: Eisenberg–gale markets: algorithms and game-theoretic properties. Games Econ. Behav. 70(1), 84–106 (2010)

    Google Scholar 

  23. Kaneko, M., Nakamura, K.: The nash social welfare function. Econometrica 47(2), 423–35 (1979)

    Article  MathSciNet  Google Scholar 

  24. Kelly, F.P., Maulloo, A.K., Tan, D.K.H.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soci. 49(3), 237–252 (1998)

    Article  Google Scholar 

  25. Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-49116-3_38

    Chapter  Google Scholar 

  26. Maskin, E.: Nash equilibrium and welfare optimality. Rev. Econ. Stud. 66(1), 23–38 (1999)

    Article  MathSciNet  Google Scholar 

  27. Maskin, E., Sjöström, T.: Implementation Theory, pp. 237–288. North Holland, Amsterdam (2002)

    Google Scholar 

  28. Matros, A.: Chinese auctions. In: Petrosyan, L.A., Zenkevich, N.A. (eds.) GAME THEORY AND MANAGEMENT. Collected abstracts of papers presented on the Fifth International Conference Game Theory and Management. SPb.: Graduate School of Management SPbU, 2011, 268 p. The collection contains abstracts of papers accepted for the Fifth International, p. 153 (2011)

    Google Scholar 

  29. Mo, J., Walrand, J.: Fair end-to-end window-based congestion control. IEEE/ACM Trans. Netw. 8(5) (2000)

    Google Scholar 

  30. Moulin, H.: Fair Division and Collective Welfare, Chap. 3. MIT Press, Cambridge (2003)

    Google Scholar 

  31. Nash, J.: The bargaining problem. Econometrica 18(2), 155–162 (1950)

    Article  MathSciNet  Google Scholar 

  32. Padhye, J., Firoiu, V., Towsley, D., Kurose, J.: Modeling TCP throughput: a simple model and its empirical validation. SIGCOMM Comput. Commun. Rev. 28(4), 303–314 (1998)

    Article  Google Scholar 

  33. Pan, R., Prabhakar, B., Psounis, K.: Choke - a stateless active queue management scheme for approximating fair bandwidth allocation. In: Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No. 00CH37064), vol. 2, pp. 942–951 (2000)

    Google Scholar 

  34. Pigou, A.: Wealth and Welfare. Macmillan and Company, limited, PCMI collection (1912)

    Google Scholar 

  35. Plaut, B.: Optimal nash equilibria for bandwidth allocation. arXiv preprint arXiv:1904.03322 (2019)

  36. Rawls, J.: A Theory of Justice, 1st edn. Belknap Press of Harvard University Press, Cambridge (1971)

    Google Scholar 

  37. Samuelson, P.A.: Foundations of economic analysis (1947)

    Google Scholar 

  38. Sen, A.: Welfare inequalities and rawlsian axiomatics. Theor. Decis. 7(4), 243–262 (1976)

    Article  Google Scholar 

  39. Sen, A.: Social choice theory: a re-examination. Econometrica 45(1), 53–89 (1977)

    Article  MathSciNet  Google Scholar 

  40. Shapley, L., Shubik, M.: Trade using one commodity as a means of payment. J. Polit. Econ. 85(5), 937–68 (1977)

    Article  Google Scholar 

  41. Varian, H.: Equity, envy, and efficiency. J. Econ. Theor. 9(1), 63–91 (1974)

    Article  MathSciNet  Google Scholar 

  42. Vazirani, V.V.: Combinatorial algorithms for market equilibria. In: Algorithmic Game Theory, pp. 103–134 (2007)

    Google Scholar 

  43. Walras, L.: Éléments d’économie politique pure; ou, Théorie de la richesse sociale. No. vol. 1–2, Corbaz (1874)

    Google Scholar 

Download references

Acknowledgements

This work would not have been possible without my advisor Ashish Goel, who I would like to thank for continued guidance and feedback. This research was supported by NSF Graduate Research Fellowship under grant DGE-1656518.

Author information

Authors and Affiliations

  1. Stanford University, Stanford, USA

    Benjamin Plaut

Authors
  1. Benjamin Plaut
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Benjamin Plaut .

Editor information

Editors and Affiliations

  1. Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China

    Xujin Chen

  2. Shanghai University of Finance and Economics, Shanghai, China

    Nikolai Gravin

  3. Goethe University Frankfurt, Frankfurt am Main, Germany

    Martin Hoefer

  4. University of Illinois at Urbana-Champaign, Urbana, IL, USA

    Ruta Mehta

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Plaut, B. (2020). Optimal Nash Equilibria for Bandwidth Allocation. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-64946-3_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-64945-6

  • Online ISBN: 978-3-030-64946-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation