Cost-Sharing Games with Rank-Based Utilities

Studies in behavioural science show that individuals are often concerned primarily about their relative welfare, rather than their absolute well-being. In this paper we define and study a variant of congestion game that reflects this phenomenon. In a cost-sharing game with rank-based utilities (CSRB-game, for short), the players are partitioned into competition sets, and the goal of every player is to minimize its cost relative to its competitors. Specifically, the primary goal of a player is to minimize the rank of its cost among its competitors, while minimizing the cost itself is a secondary objective. We show that CSRB-games are significantly different from classical cost-sharing games, and that competition may lead to a poor outcome. In particular, singleton CSRB-games need not have a pure Nash equilibrium, and even when a NE exists, natural dynamics may not converge to a NE, and the price of stability is linear in the number of players. We then analyze several natural restricted classes of singleton CSRB-games, for which we present positive results. We provide tight characterization of classes for which a NE exists and can be computed efficiently, and bound the equilibrium inefficiency, based on the competition structure, the number of players and resources, the uniformity of resources' costs, and the strategy space of competing players.