On fair cost facility location games with non-singleton players
In the fair cost facility location game, players control terminals and must open and connect each terminal to a facility, while paying connection costs and equally sharing the opening costs associated with the facilities it connects to. In most of the literature, it is assumed that each player control a single terminal. We explore a more general version of the game where each player may control multiple terminals. We prove that this game does not always possess pure Nash equilibria, and deciding whether an instance has equilibria is NP-Hard, even in metric instances. Furthermore, we present results regarding the efficiency of equilibria, showing that the price of stability of this game is equal to the price of anarchy, in both uncapacitated and capacitated settings.
|Keywords||Algorithmic game theory, Facility location, Price of stability|
|Series||Electronic Notes in Theoretical Computer Science|
|Conference||The Latin American Computing Conference|
Carvalho Rodrigues, F, Xavier, E.C, & Schäfer, G. (2019). On fair cost facility location games with non-singleton players. In Proceedings of CLEI 2018, the XLIV Latin American Computing Conference (pp. 21–38). doi:10.1016/j.entcs.2019.04.003