• Previous Article
    Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method
  • JIMO Home
  • This Issue
  • Next Article
    Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks
April  2011, 7(2): 347-364. doi: 10.3934/jimo.2011.7.347

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

1. 

School of Mathematical Sciences and Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046, China

2. 

Department of Mathematics, Hong Kong Baptist University, Hong Kong

Received  January 2010 Revised  January 2011 Published  April 2011

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.
Citation: Deren Han, Xiaoming Yuan. Existence of anonymous link tolls for decentralizing an oligopolistic game and the efficiency analysis. Journal of Industrial & Management Optimization, 2011, 7 (2) : 347-364. doi: 10.3934/jimo.2011.7.347
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.   Google Scholar

[2]

M. S. Bazarra, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", John Wiley and Sons, (1993).   Google Scholar

[3]

P. Bergendorff, D. W. Hearn and M. V. Ramana, Congestion toll pricing of traffic networks,, in, (1997), 51.   Google Scholar

[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.  doi: 10.1016/S0167-6377(03)00030-0.  Google Scholar

[5]

R. Cole, Y. Dodis and T. Roughgarden, Pricing network edges for heterogeneous selfish users,, in, (2003), 521.   Google Scholar

[6]

R. Cole, Y. Dodis and T. Roughgarden, How much can tolls help selfish routing,, in, (2003), 98.  doi: 10.1145/779928.779941.  Google Scholar

[7]

R. Cominetti, J. R. Correa and N. E. Stier-Moses, The impact of oligopolistic competition in networks,, Operation Research, 57 (2009), 1421.  doi: 10.1287/opre.1080.0653.  Google Scholar

[8]

J. Correa, A. Schulz and N. Stier Moses, Selfish routing in capacitated networks,, Mathematics of Operations Research, 29 (2004), 961.  doi: 10.1287/moor.1040.0098.  Google Scholar

[9]

J. Correa, A. Schulz and N. Stier Moses, Computational complexity, fairness, and the price of anarchy of the maximum latency problem,, in, (2004), 59.  doi: 10.1007/978-3-540-25960-2_5.  Google Scholar

[10]

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria,, in, (2002), 413.   Google Scholar

[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.   Google Scholar

[12]

S. C. Dafermos, An extended traffic assignment modal with applications to two-way traffic,, Transportation Science, 5 (1971), 366.  doi: 10.1287/trsc.5.4.366.  Google Scholar

[13]

S. C. Dafermos, The traffic assignment problem for multiclass-user transportation network,, Transportation Science, 6 (1972), 73.  doi: 10.1287/trsc.6.1.73.  Google Scholar

[14]

S. Dafermos, Toll pattern for multiclass-user transportation network,, Transportation Science, 7 (1973), 211.  doi: 10.1287/trsc.7.3.211.  Google Scholar

[15]

S. Devarajan, A note on network equilibrium and non-cooperative games,, Transportaion Research B, 15 (1981), 421.  doi: 10.1016/0191-2615(81)90026-6.  Google Scholar

[16]

R. B. Dial, Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case,, Transportation Research B, 33 (1999), 189.  doi: 10.1016/S0191-2615(98)00026-5.  Google Scholar

[17]

R. B. Dial, Minimal-revenue congestion pricing Part II: An efficient algorithm for the general case,, Transportation Research B, 34 (2000), 645.  doi: 10.1016/S0191-2615(99)00046-6.  Google Scholar

[18]

S. D. Flam and Charles Horvath, Network games; adaptations to Nash-Cournot equilibrium,, Annals of Operations Research, 64 (1996), 179.  doi: 10.1007/BF02187645.  Google Scholar

[19]

L. Fleischer, K. Jain and M. Mahdain, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games,, in, (2004).  doi: 10.1109/FOCS.2004.69.  Google Scholar

[20]

D. R. Han, J. Sun and M. Ang, New bounds for the price of anarchy under nonlinear and asymmetric costs,, Optimization, ().   Google Scholar

[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.  doi: 10.1016/j.ejor.2007.01.027.  Google Scholar

[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.  doi: 10.1504/IJMMNO.2010.031751.  Google Scholar

[23]

P. T. Harker, Multiple equlibrium behaviors on Networks,, Transportation Science, 22 (1988), 39.  doi: 10.1287/trsc.22.1.39.  Google Scholar

[24]

A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equlibria,, Networks, 15 (1985), 295.  doi: 10.1002/net.3230150303.  Google Scholar

[25]

D. W. Hearn and M. B. Yildirim, A toll pricing framework for traffic assignment problem with elastic demand,, in, (2002), 135.   Google Scholar

[26]

G. Karakostas and S. G. Kolliopoulos, The efficiency of optimal taxes,, in, (2004), 3.   Google Scholar

[27]

G. Karakostas and S. Kolliopoulos, Edge pricing of multicommodity networks for heterogeneous users,, in, (2004), 268.  doi: 10.1109/FOCS.2004.26.  Google Scholar

[28]

E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, in, 1563 (1999), 404.  doi: 10.1007/3-540-49116-3_38.  Google Scholar

[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.   Google Scholar

[30]

S. Mehrotra and J. Sun, An interior point algorithm for solving smooth convex programs based on Newton's method,, in, 114 (1991), 265.   Google Scholar

[31]

M. Netter, Equilibrium and marginal-cost pricing on a road network with several traffic flow types,, in, (1971), 155.   Google Scholar

[32]

M. Patriksson, "The Traffic Assignment Problem--Models and Methods,", VSP BV, ().   Google Scholar

[33]

G. Perakis, The "price of anarchy" under nonlinear and asymmetric costs,, Mathematics of Operations Research, 32 (2007), 614.  doi: 10.1287/moor.1070.0258.  Google Scholar

[34]

R. W. Rosenthal, The network equilibrium problem in integers,, Networks, 3 (1973), 53.  doi: 10.1002/net.3230030104.  Google Scholar

[35]

T. Roughgarden and E. Tardos, How bad is selfish routing,, Journal of the ACM, 49 (2002), 236.  doi: 10.1145/506147.506153.  Google Scholar

[36]

T. Roughgarden, "Selfish Routing and the Price of Anarchy,", MIT Press, (2005).   Google Scholar

[37]

Y. Sheffi, "Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods,", Prentice-Hall, (1985).   Google Scholar

[38]

M. Shubik, "Game Theory in the Social Sciences: Concepts and Solutions,", Cambridge, (1985).   Google Scholar

[39]

J. Sun, A convergence analysis for a convex version of Dikin's algorithm,, Annals of Operations Research, 62 (1996), 357.  doi: 10.1007/BF02206823.  Google Scholar

[40]

C. Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games,, in, (2007), 1133.   Google Scholar

[41]

J. G. Wardrop, Some theoretical aspects of road traffic research,, in, (1952), 325.   Google Scholar

[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.  doi: 10.1016/S0965-8564(97)00018-9.  Google Scholar

[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.  doi: 10.1016/S0191-2615(02)00074-7.  Google Scholar

[44]

H. Yang and H. J. Huang, "Mathematical and Economic Theory of Road Pricing,", Elsevier, (2005).   Google Scholar

[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.  doi: 10.1016/j.trb.2007.07.001.  Google Scholar

[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.  doi: 10.1016/j.ejor.2007.05.004.  Google Scholar

show all references

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.   Google Scholar

[2]

M. S. Bazarra, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", John Wiley and Sons, (1993).   Google Scholar

[3]

P. Bergendorff, D. W. Hearn and M. V. Ramana, Congestion toll pricing of traffic networks,, in, (1997), 51.   Google Scholar

[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.  doi: 10.1016/S0167-6377(03)00030-0.  Google Scholar

[5]

R. Cole, Y. Dodis and T. Roughgarden, Pricing network edges for heterogeneous selfish users,, in, (2003), 521.   Google Scholar

[6]

R. Cole, Y. Dodis and T. Roughgarden, How much can tolls help selfish routing,, in, (2003), 98.  doi: 10.1145/779928.779941.  Google Scholar

[7]

R. Cominetti, J. R. Correa and N. E. Stier-Moses, The impact of oligopolistic competition in networks,, Operation Research, 57 (2009), 1421.  doi: 10.1287/opre.1080.0653.  Google Scholar

[8]

J. Correa, A. Schulz and N. Stier Moses, Selfish routing in capacitated networks,, Mathematics of Operations Research, 29 (2004), 961.  doi: 10.1287/moor.1040.0098.  Google Scholar

[9]

J. Correa, A. Schulz and N. Stier Moses, Computational complexity, fairness, and the price of anarchy of the maximum latency problem,, in, (2004), 59.  doi: 10.1007/978-3-540-25960-2_5.  Google Scholar

[10]

A. Czumaj and B. Vöcking, Tight bounds for worst-case equilibria,, in, (2002), 413.   Google Scholar

[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.   Google Scholar

[12]

S. C. Dafermos, An extended traffic assignment modal with applications to two-way traffic,, Transportation Science, 5 (1971), 366.  doi: 10.1287/trsc.5.4.366.  Google Scholar

[13]

S. C. Dafermos, The traffic assignment problem for multiclass-user transportation network,, Transportation Science, 6 (1972), 73.  doi: 10.1287/trsc.6.1.73.  Google Scholar

[14]

S. Dafermos, Toll pattern for multiclass-user transportation network,, Transportation Science, 7 (1973), 211.  doi: 10.1287/trsc.7.3.211.  Google Scholar

[15]

S. Devarajan, A note on network equilibrium and non-cooperative games,, Transportaion Research B, 15 (1981), 421.  doi: 10.1016/0191-2615(81)90026-6.  Google Scholar

[16]

R. B. Dial, Minimal-revenue congestion pricing part I: A fast algorithm for the single-origin case,, Transportation Research B, 33 (1999), 189.  doi: 10.1016/S0191-2615(98)00026-5.  Google Scholar

[17]

R. B. Dial, Minimal-revenue congestion pricing Part II: An efficient algorithm for the general case,, Transportation Research B, 34 (2000), 645.  doi: 10.1016/S0191-2615(99)00046-6.  Google Scholar

[18]

S. D. Flam and Charles Horvath, Network games; adaptations to Nash-Cournot equilibrium,, Annals of Operations Research, 64 (1996), 179.  doi: 10.1007/BF02187645.  Google Scholar

[19]

L. Fleischer, K. Jain and M. Mahdain, Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games,, in, (2004).  doi: 10.1109/FOCS.2004.69.  Google Scholar

[20]

D. R. Han, J. Sun and M. Ang, New bounds for the price of anarchy under nonlinear and asymmetric costs,, Optimization, ().   Google Scholar

[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.  doi: 10.1016/j.ejor.2007.01.027.  Google Scholar

[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.  doi: 10.1504/IJMMNO.2010.031751.  Google Scholar

[23]

P. T. Harker, Multiple equlibrium behaviors on Networks,, Transportation Science, 22 (1988), 39.  doi: 10.1287/trsc.22.1.39.  Google Scholar

[24]

A. Haurie and P. Marcotte, On the relationship between Nash-Cournot and Wardrop equlibria,, Networks, 15 (1985), 295.  doi: 10.1002/net.3230150303.  Google Scholar

[25]

D. W. Hearn and M. B. Yildirim, A toll pricing framework for traffic assignment problem with elastic demand,, in, (2002), 135.   Google Scholar

[26]

G. Karakostas and S. G. Kolliopoulos, The efficiency of optimal taxes,, in, (2004), 3.   Google Scholar

[27]

G. Karakostas and S. Kolliopoulos, Edge pricing of multicommodity networks for heterogeneous users,, in, (2004), 268.  doi: 10.1109/FOCS.2004.26.  Google Scholar

[28]

E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, in, 1563 (1999), 404.  doi: 10.1007/3-540-49116-3_38.  Google Scholar

[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.   Google Scholar

[30]

S. Mehrotra and J. Sun, An interior point algorithm for solving smooth convex programs based on Newton's method,, in, 114 (1991), 265.   Google Scholar

[31]

M. Netter, Equilibrium and marginal-cost pricing on a road network with several traffic flow types,, in, (1971), 155.   Google Scholar

[32]

M. Patriksson, "The Traffic Assignment Problem--Models and Methods,", VSP BV, ().   Google Scholar

[33]

G. Perakis, The "price of anarchy" under nonlinear and asymmetric costs,, Mathematics of Operations Research, 32 (2007), 614.  doi: 10.1287/moor.1070.0258.  Google Scholar

[34]

R. W. Rosenthal, The network equilibrium problem in integers,, Networks, 3 (1973), 53.  doi: 10.1002/net.3230030104.  Google Scholar

[35]

T. Roughgarden and E. Tardos, How bad is selfish routing,, Journal of the ACM, 49 (2002), 236.  doi: 10.1145/506147.506153.  Google Scholar

[36]

T. Roughgarden, "Selfish Routing and the Price of Anarchy,", MIT Press, (2005).   Google Scholar

[37]

Y. Sheffi, "Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods,", Prentice-Hall, (1985).   Google Scholar

[38]

M. Shubik, "Game Theory in the Social Sciences: Concepts and Solutions,", Cambridge, (1985).   Google Scholar

[39]

J. Sun, A convergence analysis for a convex version of Dikin's algorithm,, Annals of Operations Research, 62 (1996), 357.  doi: 10.1007/BF02206823.  Google Scholar

[40]

C. Swamy, The effectiveness of Stackelberg strategies and tolls for network congestion games,, in, (2007), 1133.   Google Scholar

[41]

J. G. Wardrop, Some theoretical aspects of road traffic research,, in, (1952), 325.   Google Scholar

[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.  doi: 10.1016/S0965-8564(97)00018-9.  Google Scholar

[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.  doi: 10.1016/S0191-2615(02)00074-7.  Google Scholar

[44]

H. Yang and H. J. Huang, "Mathematical and Economic Theory of Road Pricing,", Elsevier, (2005).   Google Scholar

[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.  doi: 10.1016/j.trb.2007.07.001.  Google Scholar

[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.  doi: 10.1016/j.ejor.2007.05.004.  Google Scholar

[1]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006

[2]

Marco Cirant, Diogo A. Gomes, Edgard A. Pimentel, Héctor Sánchez-Morgado. On some singular mean-field games. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021006

[3]

Gaurav Nagpal, Udayan Chanda, Nitant Upasani. Inventory replenishment policies for two successive generations price-sensitive technology products. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021036

[4]

Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022

[5]

Liangliang Ma. Stability of hydrostatic equilibrium to the 2D fractional Boussinesq equations. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021068

[6]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190

[7]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[8]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

[9]

M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849

[10]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935

[11]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228

[12]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[13]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[14]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379

[15]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267

[16]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393

[17]

Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035

[18]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197

[19]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[20]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (49)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]