Busca avançada
Ano de início
Entree


On Fair Cost Facility Location Games with Non-singleton Players

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