Bounds on price of anarchyon linear cost functions

Fan Sha; Deren Han; Weijun Zhong

doi:10.3934/jimo.2015.11.1165

Article Contents

2015, Volume 11, Issue 4: 1165-1173. Doi: 10.3934/jimo.2015.11.1165

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

Bounds on price of anarchy on linear cost functions

1.
Department of Management Science and Engineering, School of Economics and Management, Southeast University, Nanjing, 210096
2.
School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing, 210023

Received: September 2013

Revised: August 2014

Published: October 2015

Abstract / Introduction Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 91A10, 90b20; Secondary: 65F10, 65k10.

Citation:

Related Papers

Cited by

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.