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]

Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[2]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[3]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[4]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[5]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[6]

M. Grasselli, V. Pata. Asymptotic behavior of a parabolic-hyperbolic system. Communications on Pure & Applied Analysis, 2004, 3 (4) : 849-881. doi: 10.3934/cpaa.2004.3.849
[7]

Elena Bonetti, Pierluigi Colli, Gianni Gilardi. Singular limit of an integrodifferential system related to the entropy balance. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1935-1953. doi: 10.3934/dcdsb.2014.19.1935
[8]

Dmitry Treschev. A locally integrable multi-dimensional billiard system. Discrete & Continuous Dynamical Systems - A, 2017, 37 (10) : 5271-5284. doi: 10.3934/dcds.2017228
[9]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379
[10]

Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[11]

Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control & Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393
[12]

Guo-Bao Zhang, Ruyun Ma, Xue-Shi Li. Traveling waves of a Lotka-Volterra strong competition system with nonlocal dispersal. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 587-608. doi: 10.3934/dcdsb.2018035
[13]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995
[14]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81
[15]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[16]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences