Bounds on price of anarchy on linear cost functions

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

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 and 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-8. 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, MIT, 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-284. 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-778.
[5]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, Computer Science Review, 32 (2009), 65-69. 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-628. doi: 10.1287/moor.1070.0258.
[7]	T. Roughgarden and E. Tardos, How bad is selfish routing, Journal of the ACM, 49 (2002), 236-259. 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-151. 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-374. doi: 10.1007/BF02206823.
[10]	Y. Viossat, Game dynamics and Nash equilibria, Journal of Industrial & Management Optimization, 1 (2014), 537-553. 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-8. 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, MIT, 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-284. 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-778.
[5]	E. Koutsoupias and C. H. Papadimitriou, Worst-case equilibria, Computer Science Review, 32 (2009), 65-69. 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-628. doi: 10.1287/moor.1070.0258.
[7]	T. Roughgarden and E. Tardos, How bad is selfish routing, Journal of the ACM, 49 (2002), 236-259. 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-151. 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-374. doi: 10.1007/BF02206823.
[10]	Y. Viossat, Game dynamics and Nash equilibria, Journal of Industrial & Management Optimization, 1 (2014), 537-553. doi: 10.3934/jdg.2014.1.537.

[1]	Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial and 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 and 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 and 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 and 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 and Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617
[6]	Shi'an Wang, N. U. Ahmed. Optimum management of the network of city bus routes based on a stochastic dynamic model. Journal of Industrial and Management Optimization, 2019, 15 (2) : 619-631. doi: 10.3934/jimo.2018061
[7]	Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[8]	Yanhong Yuan, Hongwei Zhang, Liwei Zhang. A penalty method for generalized Nash equilibrium problems. Journal of Industrial and Management Optimization, 2012, 8 (1) : 51-65. doi: 10.3934/jimo.2012.8.51
[9]	Elvio Accinelli, Bruno Bazzano, Franco Robledo, Pablo Romero. Nash Equilibrium in evolutionary competitive models of firms and workers under external regulation. Journal of Dynamics and Games, 2015, 2 (1) : 1-32. doi: 10.3934/jdg.2015.2.1
[10]	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
[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 and Management Optimization, 2020, 16 (5) : 2407-2424. doi: 10.3934/jimo.2019060
[12]	Enkhbat Rentsen, Battur Gompil. Generalized Nash equilibrium problem based on malfatti's problem. Numerical Algebra, Control and Optimization, 2021, 11 (2) : 209-220. doi: 10.3934/naco.2020022
[13]	Xiaona Fan, Li Jiang, Mengsi Li. Homotopy method for solving generalized Nash equilibrium problem with equality and inequality constraints. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1795-1807. doi: 10.3934/jimo.2018123
[14]	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 and Management Optimization, 2020, 16 (4) : 1999-2027. doi: 10.3934/jimo.2019040
[15]	Narges Torabi Golsefid, Maziar Salahi. Second order cone programming formulation of the fixed cost allocation in DEA based on Nash bargaining game. Numerical Algebra, Control and Optimization, 2021 doi: 10.3934/naco.2021032
[16]	Shaokun Tao, Xianjin Du, Suresh P. Sethi, Xiuli He, Yu Li. Equilibrium decisions on pricing and innovation that impact reference price dynamics. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021157
[17]	De-Jun Feng, Antti Käenmäki. Equilibrium states of the pressure function for products of matrices. Discrete and Continuous Dynamical Systems, 2011, 30 (3) : 699-708. doi: 10.3934/dcds.2011.30.699
[18]	Yunan Wu, Guangya Chen, T. C. Edwin Cheng. A vector network equilibrium problem with a unilateral constraint. Journal of Industrial and Management Optimization, 2010, 6 (3) : 453-464. doi: 10.3934/jimo.2010.6.453
[19]	Liping Zhang. A nonlinear complementarity model for supply chain network equilibrium. Journal of Industrial and Management Optimization, 2007, 3 (4) : 727-737. doi: 10.3934/jimo.2007.3.727
[20]	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 and Management Optimization, 2013, 9 (1) : 205-225. doi: 10.3934/jimo.2013.9.205

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Fan Sha Deren Han Weijun Zhong
on Google Scholar
Fan Sha Deren Han Weijun Zhong

[Back to Top]