Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis

Deren Han; Xiaoming Yuan

doi:10.3934/jimo.2011.7.347

Article Contents

2011, Volume 7, Issue 2: 347-364. Doi: 10.3934/jimo.2011.7.347

This issue Previous Article Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks Next Article Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method

Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis

Deren Han^1, and
Xiaoming Yuan^2,

1.
School of Mathematical Sciences and Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046
2.
Department of Mathematics, Hong Kong Baptist University, Hong Kong

Received: December 31, 2009

Revised: December 31, 2010

Published: March 2011

Abstract Related Papers Cited by

Abstract

To apply the traditional marginal-cost pricing to drive a user equilibrium of the oligopolistic game to the system optimum, it requires to classify the users into different classes and then charge discriminatory tolls across user classes. By realizing the difficulty of discriminating users when they differ in some unobservable ways, Yang and Zhang investigated existence of anonymous link tolls for transportation networks recently. In this paper, we consider the anonymous link tolls for the oligopolistic game with nonseparable, nonlinear and asymmetric cost functions with fixed demands. With similar techniques developed by Yang and Zhang, we first prove the existence of anonymous link tolls to decentralize the system optimum to a user equilibrium. Then, by deriving some bounds on the so-called price of anarchy, we analyze the efficiency of such a toll strategy when the tolls are considered as part of the system cost.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	R. P. Agdeppa, N. Yamashita and M. Fukushima, An implicit programming approach for the road pricing problem with nonadditive route costs, Journal of Industrial and Management Optimization, 4 (2008), 183-197.
[2]	M. S. Bazarra, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms," John Wiley and Sons, Inc., New York, 1993.
[3]	P. Bergendorff, D. W. Hearn and M. V. Ramana, Congestion toll pricing of traffic networks, in "Network Optimization" (eds. P. M. Pardalos, D. W. Hearn and W. W. Hager), Springer, (1997), 51-71.
[4]	C. K. Chau and K. M. Sim, The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands, Operations Research Letters, 31 (2003), 327-334.doi: 10.1016/S0167-6377(03)00030-0.
[5]	R. Cole, Y. Dodis and T. Roughgarden, Pricing network edges for heterogeneous selfish users, in "Proceedings of the 4th ACM Conference on Electronic Commerce," (2003), 521-530.
[6]	R. Cole, Y. Dodis and T. Roughgarden, How much can tolls help selfish routing, in "Proceedings of the 4th ACM Conference on Electronic Commerce," (2003), 98-107.doi: 10.1145/779928.779941.
[7]	R. Cominetti, J. R. Correa and N. E. Stier-Moses, The impact of oligopolistic competition in networks, Operation Research, 57 (2009), 1421-1437.doi: 10.1287/opre.1080.0653.
[8]	J. Correa, A. Schulz and N. Stier Moses, Selfish routing in capacitated networks, Mathematics of Operations Research, 29 (2004), 961-976.doi: 10.1287/moor.1040.0098.
[9]	J. Correa, A. Schulz and N. Stier Moses, Computational complexity, fairness, and the price of anarchy of the maximum latency problem, in "Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science" (eds. D. Bienstock and G. Nemhauser), Springer Berlin, (2004), 59-73.doi: 10.1007/978-3-540-25960-2_5.
[10]	A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria, in "Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms," (2002), 413-420.
[11]	S. C. Dafermos and F. T. Sparrow, Optimal resource allocation and toll patterns in user-optimized transport network, Journal of Transport Economics and Policy, 5 (1971), 198-200.
[12]	S. C. Dafermos, An extended traffic assignment modal with applications to two-way traffic, Transportation Science, 5 (1971), 366-389.doi: 10.1287/trsc.5.4.366.
[13]	S. C. Dafermos, The traffic assignment problem for multiclass-user transportation network, Transportation Science, 6 (1972), 73-87.doi: 10.1287/trsc.6.1.73.
[14]	S. Dafermos, Toll pattern for multiclass-user transportation network, Transportation Science, 7 (1973), 211-223.doi: 10.1287/trsc.7.3.211.
[15]	S. Devarajan, A note on network equilibrium and non-cooperative games, Transportaion Research B, 15 (1981), 421-426.doi: 10.1016/0191-2615(81)90026-6.
[16]	R. B. Dial, Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case, Transportation Research B, 33 (1999), 189-202.doi: 10.1016/S0191-2615(98)00026-5.
[17]	R. B. Dial, Minimal-revenue congestion pricing Part II: An efficient algorithm for the general case, Transportation Research B, 34 (2000), 645-665.doi: 10.1016/S0191-2615(99)00046-6.
[18]	S. D. Flam and Charles Horvath, Network games; adaptations to Nash-Cournot equilibrium, Annals of Operations Research, 64 (1996), 179-195.doi: 10.1007/BF02187645.
[19]	L. Fleischer, K. Jain and M. Mahdain, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games, in "Proceedings of the 45th Annual IEEE Symposium on Foundations of Compuer Science," 2004.doi: 10.1109/FOCS.2004.69.
[20]	D. R. Han, J. Sun and M. Ang, New bounds for the price of anarchy under nonlinear and asymmetric costs, Optimization, to appear.
[21]	D. R. Han, H. K. Lo, J. Sun and H. Yang, The toll effect on price of anarchy when costs are nonlinear and asymmetric, European Journal of Operational Research, 186 (2008), 300-316.doi: 10.1016/j.ejor.2007.01.027.
[22]	D. R. Han, H. Yang and X. M. Yuan, The efficiency analysis for oligopolistic games when cost functions are nonseparable, International Journal of Mathematical Modelling and Numerical Optimisation, 1 (2010), 237-257.doi: 10.1504/IJMMNO.2010.031751.
[23]	P. T. Harker, Multiple equlibrium behaviors on Networks, Transportation Science, 22 (1988), 39-46.doi: 10.1287/trsc.22.1.39.
[24]	A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equlibria, Networks, 15 (1985), 295-308.doi: 10.1002/net.3230150303.
[25]	D. W. Hearn and M. B. Yildirim, A toll pricing framework for traffic assignment problem with elastic demand, in "Current Trends in Transportation and Network Analysis-Papers in Honor of Michael Florian" (eds. M. Gendreau and P. Marcotte), Kluwer Academic Publishers, Norwell (2002), 135-145.
[26]	G. Karakostas and S. G. Kolliopoulos, The efficiency of optimal taxes, in "Proceedings of 1st Workshop on Combinatorial and Algorithmic Aspects of Networking," (2004), 3-12.
[27]	G. Karakostas and S. Kolliopoulos, Edge pricing of multicommodity networks for heterogeneous users, in "Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science," (2004), 268-276.doi: 10.1109/FOCS.2004.26.
[28]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, in "Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science," 1563 (1999), 404-413.doi: 10.1007/3-540-49116-3_38.
[29]	G. S. Liu and J. Z. Zhang, Decision making of transportation plan, a bilevel transportation problem approach, Journal of Industrial and Management Optimization, 1 (2005), 305-314.
[30]	S. Mehrotra and J. Sun, An interior point algorithm for solving smooth convex programs based on Newton's method, in "Contemporary Mathematics" (eds. B. Lagarias and M. Todd), 114 (1991), 265-284.
[31]	M. Netter, Equilibrium and marginal-cost pricing on a road network with several traffic flow types, in "Proceedings of 5th International Symposium on Transportation and Traffic Theory," (1971), 155-163.
[32]	M. Patriksson, "The Traffic Assignment Problem--Models and Methods," VSP BV, Utrecht, The Netherlands.
[33]	G. Perakis, The "price of anarchy" under nonlinear and asymmetric costs, Mathematics of Operations Research, 32 (2007), 614-628.doi: 10.1287/moor.1070.0258.
[34]	R. W. Rosenthal, The network equilibrium problem in integers, Networks, 3 (1973), 53-59.doi: 10.1002/net.3230030104.
[35]	T. Roughgarden and E. Tardos, How bad is selfish routing, Journal of the ACM, 49 (2002), 236-259.doi: 10.1145/506147.506153.
[36]	T. Roughgarden, "Selfish Routing and the Price of Anarchy," MIT Press, 2005.
[37]	Y. Sheffi, "Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods," Prentice-Hall, 1985.
[38]	M. Shubik, "Game Theory in the Social Sciences: Concepts and Solutions," Cambridge, MA and London: The MIT Press, 1985.
[39]	J. Sun, A convergence analysis for a convex version of Dikin's algorithm, Annals of Operations Research, 62 (1996), 357-374.doi: 10.1007/BF02206823.
[40]	C. Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games, in "Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms," (2007), 1133-1142.
[41]	J. G. Wardrop, Some theoretical aspects of road traffic research, in "Proceedings of the Institution of Civil Engineers," Part II, (1952), 325-378.
[42]	H. Yang and H. J. Huang, Principle of marginal-cost pricing: How does it work in a general network?, Transportation Research A, 32 (1998), 45-54.doi: 10.1016/S0965-8564(97)00018-9.
[43]	H. Yang and H. J. Huang, The multi-class, multi-criteria traffic network equilibrium and system optimum problem, Transportation Research B, 38 (2004), 1-15.doi: 10.1016/S0191-2615(02)00074-7.
[44]	H. Yang and H. J. Huang, "Mathematical and Economic Theory of Road Pricing," Elsevier, 2005.
[45]	H. Yang and X. N. Zhang, Existence of anonymous link tolls for system optimum on networks with mixed equilibrium behaviors, Transportation Research B, 42 (2008), 99-112.doi: 10.1016/j.trb.2007.07.001.
[46]	X. N. Zhang, H. Yang and H. J. Huang, Multiclass multicriteria mixed equilibrium on networks and uniform link tolls for system optimum, European Journal of Operational Research, 189 (2008), 146-158.doi: 10.1016/j.ejor.2007.05.004.