Bounds on price of anarchy on linear cost functions

Previous Article
Modelling and optimal control of blood glucose levels in the human body
JIMO Home
This Issue
Next Article
The inventory model under supplier's partial trade credit policy in a supply chain system

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

Abstract
Related Papers

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.
[2]	J. H. Hammond, Solving Asymmetric Variational Inequality problems and Systems of Equations with Generalized Nonlinear Programming Algorithms,, PhD Thesis, (1985).
[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.
[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.
[5]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, Computer Science Review, 32 (2009), 65. doi: 10.1016/j.cosrev.2009.04.003.
[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.
[7]	T. Roughgarden and E. Tardos, How bad is selfish routing,, Journal of the ACM, 49 (2002), 236. doi: 10.1145/506147.506153.
[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.
[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.
[10]	Y. Viossat, Game dynamics and Nash equilibria,, Journal of Industrial & Management Optimization, 1 (2014), 537. doi: 10.3934/jdg.2014.1.537.

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.
[2]	J. H. Hammond, Solving Asymmetric Variational Inequality problems and Systems of Equations with Generalized Nonlinear Programming Algorithms,, PhD Thesis, (1985).
[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.
[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.
[5]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria,, Computer Science Review, 32 (2009), 65. doi: 10.1016/j.cosrev.2009.04.003.
[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.
[7]	T. Roughgarden and E. Tardos, How bad is selfish routing,, Journal of the ACM, 49 (2002), 236. doi: 10.1145/506147.506153.
[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.
[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.
[10]	Y. Viossat, Game dynamics and Nash equilibria,, Journal of Industrial & Management Optimization, 1 (2014), 537. doi: 10.3934/jdg.2014.1.537.

[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]	Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018123
[11]	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
[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]	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
[14]	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
[15]	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
[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]	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
[19]	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
[20]	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

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences