American Institute of Mathematical Sciences

Advanced
October  2015, 11(4): 1165-1173. doi: 10.3934/jimo.2015.11.1165

Bounds on price of anarchy on linear cost functions

Fan Sha 1, , Deren Han 2, and  Weijun Zhong 1,

1. 

Department of Management Science and Engineering, School of Economics and Management, Southeast University, Nanjing, 210096, China, China
2. 

School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing, 210023

Received  September 2013 Revised  August 2014 Published  March 2015

The price of anarchy (POA) is a quite powerful tool to characterize the efficiency loss of competition on networks. In this paper, we derive a bound for POA for the case that the cost function is linear but asymmetric. The result is a generalization of that of Han et. al. in the sense that the involved matrix is only assumed to be positive semidefinite, but not positive definite. Consequently, the range of application of the result is widened. We give two simple examples to illustrate our result.
Keywords: price of anarchy, system optimum, cost function., Nash equilibrium, network.
Mathematics Subject Classification: Primary: 91A10, 90b20; Secondary: 65F10, 65k1.
Citation: 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
References:
[1]

P. Dubey, Inefficiency of Nash equilibria,, Mathematics of Operations Research, 11 (1986), 1.  doi: 10.1287/moor.11.1.1.  Google Scholar

[2]

J. H. Hammond, Solving Asymmetric Variational Inequality problems and Systems of Equations with Generalized Nonlinear Programming Algorithms,, PhD Thesis, (1985).   Google Scholar

[3]

D. Han, J. Sun and M. Ang, New bounds for the price of anarchy under nonlinear and asymmetric costs,, Optimization, 63 (2014), 271.  doi: 10.1080/02331934.2011.641017.  Google Scholar

[4]

R. Jahari and J. N. Tsitsiklis, Network resource allocation and a congestion game,, Proceedings of the Annual Allerton Conference on Communication Control and Computing, 41 (2003), 769.   Google Scholar

[5]

E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, Computer Science Review, 32 (2009), 65.  doi: 10.1016/j.cosrev.2009.04.003.  Google Scholar

[6]

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

[7]

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

[8]

R. Soeiro, A. Mousa and T. R. Oliveira and A. A. Pinto, Dynamics of human decisions,, Journal of Industrial & Management Optimization, 1 (2014), 121.  doi: 10.3934/jdg.2014.1.121.  Google Scholar

[9]

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

[10]

Y. Viossat, Game dynamics and Nash equilibria,, Journal of Industrial & Management Optimization, 1 (2014), 537.  doi: 10.3934/jdg.2014.1.537.  Google Scholar

show all references

References:
[1]

P. Dubey, Inefficiency of Nash equilibria,, Mathematics of Operations Research, 11 (1986), 1.  doi: 10.1287/moor.11.1.1.  Google Scholar

[2]

J. H. Hammond, Solving Asymmetric Variational Inequality problems and Systems of Equations with Generalized Nonlinear Programming Algorithms,, PhD Thesis, (1985).   Google Scholar

[3]

D. Han, J. Sun and M. Ang, New bounds for the price of anarchy under nonlinear and asymmetric costs,, Optimization, 63 (2014), 271.  doi: 10.1080/02331934.2011.641017.  Google Scholar

[4]

R. Jahari and J. N. Tsitsiklis, Network resource allocation and a congestion game,, Proceedings of the Annual Allerton Conference on Communication Control and Computing, 41 (2003), 769.   Google Scholar

[5]

E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, Computer Science Review, 32 (2009), 65.  doi: 10.1016/j.cosrev.2009.04.003.  Google Scholar

[6]

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

[7]

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

[8]

R. Soeiro, A. Mousa and T. R. Oliveira and A. A. Pinto, Dynamics of human decisions,, Journal of Industrial & Management Optimization, 1 (2014), 121.  doi: 10.3934/jdg.2014.1.121.  Google Scholar

[9]

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

[10]

Y. Viossat, Game dynamics and Nash equilibria,, Journal of Industrial & Management Optimization, 1 (2014), 537.  doi: 10.3934/jdg.2014.1.537.  Google Scholar

[1]

Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091
[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]

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
[4]

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
[5]

Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial & Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617
[6]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[7]

Shi'an Wang, N. U. Ahmed. Optimum management of the network of city bus routes based on a stochastic dynamic model. Journal of Industrial & Management Optimization, 2019, 15 (2) : 619-631. doi: 10.3934/jimo.2018061
[8]

Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics & Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1
[9]

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
[10]

Shunfu Jin, Haixing Wu, Wuyi Yue, Yutaka Takahashi. Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2019060
[11]

Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[12]

Xue-Yan Wu, Zhi-Ping Fan, Bing-Bing Cao. Cost-sharing strategy for carbon emission reduction and sales effort: A nash game with government subsidy. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-29. doi: 10.3934/jimo.2019040
[13]

Yunan Wu, Guangya Chen, T. C. Edwin Cheng. A vector network equilibrium problem with a unilateral constraint. Journal of Industrial & Management Optimization, 2010, 6 (3) : 453-464. doi: 10.3934/jimo.2010.6.453
[14]

Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial & Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727
[15]

De-Jun Feng, Antti Käenmäki. Equilibrium states of the pressure function for products of matrices. Discrete & Continuous Dynamical Systems - A, 2011, 30 (3) : 699-708. doi: 10.3934/dcds.2011.30.699
[16]

I-Lin Wang, Shiou-Jie Lin. A network simplex algorithm for solving the minimum distribution cost problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 929-950. doi: 10.3934/jimo.2009.5.929
[17]

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
[18]

Rui Mu, Zhen Wu. Nash equilibrium points of recursive nonzero-sum stochastic differential games with unbounded coefficients and related multiple\\ dimensional BSDEs. Mathematical Control & Related Fields, 2017, 7 (2) : 289-304. doi: 10.3934/mcrf.2017010
[19]

Mei Ju Luo, Yi Zeng Chen. Smoothing and sample average approximation methods for solving stochastic generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 1-15. doi: 10.3934/jimo.2016.12.1
[20]

Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A smoothing Newton method for generalized Nash equilibrium problems with second-order cone constraints. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 1-18. doi: 10.3934/naco.2012.2.1

2018 Impact Factor: 1.025

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences