Abstract
We study the design of price mechanisms for communication network problems in which a user’s utility depends on the amount of flow she sends through the network, and the congestion on each link depends on the total traffic flows over it. The price mechanisms are characterized by a set of axioms that have been adopted in the cost-sharing games, and we search for the price mechanisms that provide the minimum price of anarchy. We show that, given the non-decreasing and concave utilities of users and the convex quadratic congestion costs in each link, if the price mechanism cannot depend on utility functions, the best achievable price of anarchy is \({{4(3-2 \sqrt{2}) \approx 31.4 \% }}\). Thus, the popular marginal cost pricing with price of anarchy less than 1/3 ≈ 33.3% is nearly optimal. We also investigate the scenario in which the price mechanisms can be made contingent on the users’ preference profile while such information is available.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Athey S.: Single crossing properties and the existence of pure strategy equilibria in games of incomplete information. Econometrica 69(4), 861–889 (2001)
Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: The Annual ACM Symposium on Theory of Computing (STOC), pp. 57–66 (2005)
Billera L., Heath D.: Allocation of shared costs: a set of axioms yielding a unique procedure. Math. Oper. Res. 7, 32–39 (1982)
Brown S.J., Sibley D.S.: The Theory of Public Utility Pricing. Cambridge University Press, Cambridge (1986)
Cachon G., Lariviere M.: Capacity choice and allocation: strategic behavior and supply chain performance. Manage. Sci. 45, 1091–1108 (1999)
Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: The Annual ACM Symposium on Theory of Computing (STOC), pp. 67–73 (2005)
Friedman E., Moulin H.: Three methods to share joint costs or surplus. J. Econ. Theory 87, 275–312 (1999)
Fudenberg D., Tirole J.: Game Theory. The MIT Press, Cambridge (1994)
Hamilton J., Slutsky S.: Nonlinear price discrimination with a finite number of consumers and constrained recontracting. Int. J. Ind. Organ. 22(6), 737–757 (2004)
Johari R., Tsitsiklis J.: Efficiency loss in a network resource allocation game. Math. Oper. Res. 29, 407–435 (2004)
Johari R., Tsitsiklis J.: A scalable network resource allocation mechanism with bounded efficiency loss. IEEE J. Sel. Areas Commun. 24, 992–999 (2006)
Kelly F., Maulloo A., Tan D.: Rate control for communication networks: shadow prices, proportional fairness, and stability. J. Oper. Res. Soc. 49, 237–252 (1998)
Kolpin V.: Multi-product serial cost sharing: an incompatibility with the additivity axiom. J. Econ. Theory 69(1), 227–233 (1996)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Proceedings of 16th Symposium on Theoretical Aspects of Computer Science, LNCS 1563, 404–413 (1999)
Krishna V.: Auction Theory. Academic Press, New York (2002)
Laffont J., Martimort D.: The Theory of Incentives: The Principal-Agent Model. Princeton University Press, USA (2002)
Maskin E.: Nash equilibria and welfare optimality. Rev. Econ. Stud. 66, 23–38 (1999)
Mirman L., Tauman Y.: Demand compatible equitable cost sharing prices. Math. Oper. Res. 7, 40–56 (1982)
Monderer D., Neyman A.: Values of Smooth Nonatomic Games: The Method of Multilinear approximation. The Shapley Value: Essays in Honor of Lloyd S. Shapley. Cambridge Univ. Press, New York (1988)
Moulin H.: The price of anarchy of serial, average and incremental cost sharing. Econ. Theory 36, 379–405 (2008)
Moulin H., Shenker S.: Serial cost sharing. Econometrica 60, 1009–1037 (1992)
Moulin H., Shenker S.: Average cost pricing versus serial cost sharing: an axiomatic comparison. J. Econ. Theory 64, 178–201 (1994)
Nisan N., Roughgarden T., Tardos E., Vazirani V.: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)
Parry I.: Comparing the efficiency of alternative policies for reducing traffic congestion. J. Public Econ. 85, 333–362 (2002)
Piketty T.: Implementation of first-best allocations via generalized tax schedules. J. Econ. Theory 61(1), 23–41 (1993)
Roughgarden T., Tardos E.: How bad is selfish routing? J. ACM 49, 236–259 (2002)
Roughgarden T., Tardos E.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ. Behav. 47, 389–403 (2004)
Samet D., Tauman Y.: The determination of marginal cost prices under a set of axioms. Econometrica 50, 895–909 (1982)
Sheshinski E.: On atmosphere externality and corrective. J. Public Econ. 88, 727–734 (2004)
Sudholter P.: Axiomatizations of game theoretical solutions for one-output cost sharing problems. Games Econ. Behav. 24, 142–171 (1998)
Tadenuma K., Thomson W.: No-envy and consistency in economies with indivisible goods. Econometrica 59(6), 1755–1767 (1991)
Tauman Y.: The aumann-shapley prices: a survey. In: Roth, A. (eds) The Shapley Value: In Honor of Lioyd Shapley, Cambridge University Press, Cambridge (1988)
Watts A.: On the uniqueness of equilibrium in Cournot oligopoly and other games. Games Econ. Behav. 13, 269–285 (1996)
Yang, S., Hajek, B.: Revenue and stability of a mechanism for efficient allocation of a divisible good. Working paper, University of Illinois at Urbana-Champaign (2006)
Young H.: Cost allocation. In: Aumann, R., Hart, S. (eds) Handbook of Game Theory with Economic Applications, vol. 2, pp. 1193–1235. Elsevier, Netherlands (1988)
Acknowledgments
We thank the anonymous reviewers for very insightful and constructive comments that significantly improved the quality of this paper. We also benefited from the discussions with Herve Moulin and seminar participants at NYU. Ying-Ju Chen gratefully acknowledges the financial support from Chiang Ching-Kuo Foundation (JS002-A-08), and Faculty Research Grant from Committee on Research at UC Berkeley. Jiawei Zhang would like to acknowledge the support by NSF grant 0654116. All remaining errors are our own.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Chen, YJ., Zhang, J. Design of price mechanisms for network resource allocation via price of anarchy. Math. Program. 131, 333–364 (2012). https://doi.org/10.1007/s10107-010-0379-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0379-1