• Previous Article
    Sample average approximation method for stochastic complementarity problems with applications to supply chain supernetworks
  • JIMO Home
  • This Issue
  • Next Article
    Multi-objective aggregate production planning decisions using two-phase fuzzy goal programming method
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]

Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1165-1173. doi: 10.3934/jimo.2015.11.1165

[2]

Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics & Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003

[3]

Mitali Sarkar, Young Hae Lee. Optimum pricing strategy for complementary products with reservation price in a supply chain model. Journal of Industrial & Management Optimization, 2017, 13 (3) : 1553-1586. doi: 10.3934/jimo.2017007

[4]

Xiong Li. The stability of the equilibrium for a perturbed asymmetric oscillator. Communications on Pure & Applied Analysis, 2006, 5 (3) : 515-528. doi: 10.3934/cpaa.2006.5.515

[5]

Xiong Li. The stability of the equilibrium for a perturbed asymmetric oscillator. Communications on Pure & Applied Analysis, 2007, 6 (1) : 69-82. doi: 10.3934/cpaa.2007.6.69

[6]

R. Enkhbat , N. Tungalag, A. S. Strekalovsky. Pseudoconvexity properties of average cost functions. Numerical Algebra, Control & Optimization, 2015, 5 (3) : 233-236. doi: 10.3934/naco.2015.5.233

[7]

Shichen Zhang, Jianxiong Zhang, Jiang Shen, Wansheng Tang. A joint dynamic pricing and production model with asymmetric reference price effect. Journal of Industrial & Management Optimization, 2019, 15 (2) : 667-688. doi: 10.3934/jimo.2018064

[8]

Gerard Gómez, Josep–Maria Mondelo, Carles Simó. A collocation method for the numerical Fourier analysis of quasi-periodic functions. I: Numerical tests and examples. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 41-74. doi: 10.3934/dcdsb.2010.14.41

[9]

Gerard Gómez, Josep–Maria Mondelo, Carles Simó. A collocation method for the numerical Fourier analysis of quasi-periodic functions. II: Analytical error estimates. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 75-109. doi: 10.3934/dcdsb.2010.14.75

[10]

Hongyu He, Naohiro Kato. Equilibrium submanifold for a biological system. Discrete & Continuous Dynamical Systems - S, 2011, 4 (6) : 1429-1441. doi: 10.3934/dcdss.2011.4.1429

[11]

Chien Hsun Tseng. Applications of a nonlinear optimization solver and two-stage comprehensive Denoising techniques for optimum underwater wideband sonar echolocation system. Journal of Industrial & Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205

[12]

F. Zeyenp Sargut, H. Edwin Romeijn. Capacitated requirements planning with pricing flexibility and general cost and revenue functions. Journal of Industrial & Management Optimization, 2007, 3 (1) : 87-98. doi: 10.3934/jimo.2007.3.87

[13]

Sebastian Albrecht, Marion Leibold, Michael Ulbrich. A bilevel optimization approach to obtain optimal cost functions for human arm movements. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 105-127. doi: 10.3934/naco.2012.2.105

[14]

Dean A. Carlson. Finding open-loop Nash equilibrium for variational games. Conference Publications, 2005, 2005 (Special) : 153-163. doi: 10.3934/proc.2005.2005.153

[15]

Yu Chen. Delegation principle for multi-agency games under ex post equilibrium. Journal of Dynamics & Games, 2018, 5 (4) : 311-329. doi: 10.3934/jdg.2018019

[16]

Kenji Kimura, Yeong-Cheng Liou, David S. Shyu, Jen-Chih Yao. Simultaneous system of vector equilibrium problems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 161-174. doi: 10.3934/jimo.2009.5.161

[17]

Xiaolin Xu, Xiaoqiang Cai. Price and delivery-time competition of perishable products: Existence and uniqueness of Nash equilibrium. Journal of Industrial & Management Optimization, 2008, 4 (4) : 843-859. doi: 10.3934/jimo.2008.4.843

[18]

Manisha Pujari, Rushed Kanawati. Link prediction in multiplex networks. Networks & Heterogeneous Media, 2015, 10 (1) : 17-35. doi: 10.3934/nhm.2015.10.17

[19]

Laltu Sardar, Sushmita Ruj. The secure link prediction problem. Advances in Mathematics of Communications, 2019, 13 (4) : 733-757. doi: 10.3934/amc.2019043

[20]

Gang Qian, Deren Han, Hongjin He. Congestion control with pricing in the absence of demand and cost functions: An improved trial and error method. Journal of Industrial & Management Optimization, 2010, 6 (1) : 103-121. doi: 10.3934/jimo.2010.6.103

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]