• 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]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[2]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164

[3]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[4]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[5]

Reza Lotfi, Zahra Yadegari, Seyed Hossein Hosseini, Amir Hossein Khameneh, Erfan Babaee Tirkolaee, Gerhard-Wilhelm Weber. A robust time-cost-quality-energy-environment trade-off with resource-constrained in project management: A case study for a bridge construction project. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020158

[6]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[7]

Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045

[8]

Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020273

[9]

Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049

[10]

Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467

[11]

Yichen Zhang, Meiqiang Feng. A coupled $ p $-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075

[12]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[13]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[14]

Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $ \mathbb{R}^2 $. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447

[15]

Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382

[16]

Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468

[17]

Mathew Gluck. Classification of solutions to a system of $ n^{\rm th} $ order equations on $ \mathbb R^n $. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]