On Fair Cost Facility Location Games with Non-singleton Players

被引:0
作者
Rodrigues, Felix Carvalho [1 ]
Xavier, Eduardo C. [1 ]
Schafer, Guido [2 ]
机构
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP, Brazil
[2] CWI, Networks & Optimizat N&O Grp, Amsterdam, Netherlands
基金
巴西圣保罗研究基金会;
关键词
price of stability; facility location; algorithmic game theory; NETWORK DESIGN; EQUILIBRIA;
D O I
10.1016/j.entcs.2019.04.003
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.
引用
收藏
页码:21 / 38
页数:18
相关论文
共 18 条
[1]  
[Anonymous], 2003, P S THEOR COMP ASS
[2]   The price of stability for network design with fair cost allocation [J].
Anshelevich, E ;
Dasgupta, A ;
Kleinberg, J ;
Tardos, É ;
Wexler, T ;
Roughgarden, T .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :295-304
[3]   Non-cooperative facility location and covering games [J].
Cardinal, Jean ;
Hoefer, Martin .
THEORETICAL COMPUTER SCIENCE, 2010, 411 (16-18) :1855-1876
[4]   Network Design with Weighted Players [J].
Chen, Ho-Lin ;
Roughgarden, Tim .
THEORY OF COMPUTING SYSTEMS, 2009, 45 (02) :302-324
[5]  
Devanur N.R., 2003, Proceedings of the 4th ACM Conference on Electronic Commerce, P108
[6]   Efficient graph topologies in network routing games [J].
Epstein, Amir ;
Feldman, Michal ;
Mansour, Yishay .
GAMES AND ECONOMIC BEHAVIOR, 2009, 66 (01) :115-125
[7]  
Fanelli A, 2010, LECT NOTES COMPUT SC, V6484, P222, DOI 10.1007/978-3-642-17572-5_18
[8]  
Goemans MX, 2004, J ALGORITHM, V50, P194, DOI 10.1016/S0196-6774(03)00098-1
[9]  
Hansen TD, 2009, LECT NOTES COMPUT SC, V5573, P174, DOI 10.1007/978-3-642-02026-1_16
[10]  
Hansen TD, 2008, LECT NOTES COMPUT SC, V5385, P490, DOI 10.1007/978-3-540-92185-1_54