| Texto completo | |
| Autor(es): |
Rodrigues, Felix Carvalho
;
Xavier, Eduardo C.
;
Schafer, Guido
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE; v. 342, p. 18-pg., 2019-04-28. |
| Resumo | |
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. (AU) | |
| Processo FAPESP: | 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural |
| Beneficiário: | Flávio Keidi Miyazawa |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 16/23552-7 - Problemas de Corte e Empacotamento: Abordagens Práticas e Teóricas |
| Beneficiário: | Rafael Crivellari Saliba Schouery |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |