How egalitarian are Nash equilibria in network cost-sharing games?

Abstract

We consider the egalitarian social cost, which is the maximum individual cost (instead of the sum), when analyzing Nash equilibria in fair network cost-sharing games. Intuitively, the egalitarian price of anarchy reflects how uneven cost is distributed among players at equilibrium. We first show a tight upper bound of kin general fair network cost-sharing games, where k is the total number of players. For fair network cost-sharing games with a single source-sink pair and a relaxed benchmark, we then show an upper bound of n - 1 on the egalitarian price of anarchy defined using such benchmark, where n is the network size. This gives a possibly better bound that does not depend on the number of players nor the costs. (C) 2015 Elsevier B.V. All rights reserved.