\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Bounds on price of anarchy on linear cost functions

Abstract / Introduction Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 91A10, 90b20; Secondary: 65F10, 65k10.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(102) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return