2014/12/02 by Vittorio Bilò, Bilò, Vittorio
Economics, Econometrics and Finance · Decision Sciences · #Economic theories and models #Game Theory and Voting Systems #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.1412.0845
One of the main results shown through Roughgarden's notions of smooth games\nand robust price of anarchy is that, for any sum-bounded utilitarian social\nfunction, the worst-case price of anarchy of coarse correlated equilibria\ncoincides with that of pure Nash equilibria in the class of weighted congestion\ngames with non-negative and non-decreasing latency functions and that such a\nvalue can always be derived through the, so called, smoothness argument. We\nsignificantly extend this result by proving that, for a variety of (even\nnon-sum-bounded) utilitarian and egalitarian social functions and for a broad\ngeneralization of the class of weighted congestion games with non-negative (and\npossibly decreasing) latency functions, the worst-case price of anarchy of\n\ε-approximate coarse correlated equilibria still coincides with that\nof \ε-approximate pure Nash equilibria, for any \ε\≥ 0. As a\nbyproduct of our proof, it also follows that such a value can always be\ndetermined by making use of the primal-dual method we introduced in a previous\nwork. It is important to note that our scenario of investigation is beyond the\nscope of application of the robust price of anarchy (for as it is currently\ndefined), so that our result seems unlikely to be alternatively proved via the\nsmoothness framework.\n