TY - GEN

T1 - On the effectiveness of connection tolls in fair cost facility location games

AU - Rodrigues, Félix Carvalho

AU - Schäfer, Guido

AU - Xavier, Eduardo Candido

PY - 2018

Y1 - 2018

N2 - We investigate the effectiveness of tolls to reduce the inefficiency of Nash equilibria in the classical fair cost facility location game. In this game, every terminal corresponds to a selfish player who wants to connect to some facility at minimum cost. The cost of a player is determined by the connection cost to the chosen facility plus an equal share of its opening cost. We are interested in the problem of imposing tolls on the connections to induce a socially optimal Nash equilibrium such that the total amount of tolls is minimized. It turns out that this problem is challenging to solve even for simple special cases. We provide polynomial-time algorithms for (i) instances with two facilities, and (ii) instances with a constant number of facilities arranged as a star. Our algorithm for (ii) exploits a relation between our tolling problem and a novel bipartite matching problem without crossings, which we prove to be NP-hard.

AB - We investigate the effectiveness of tolls to reduce the inefficiency of Nash equilibria in the classical fair cost facility location game. In this game, every terminal corresponds to a selfish player who wants to connect to some facility at minimum cost. The cost of a player is determined by the connection cost to the chosen facility plus an equal share of its opening cost. We are interested in the problem of imposing tolls on the connections to induce a socially optimal Nash equilibrium such that the total amount of tolls is minimized. It turns out that this problem is challenging to solve even for simple special cases. We provide polynomial-time algorithms for (i) instances with two facilities, and (ii) instances with a constant number of facilities arranged as a star. Our algorithm for (ii) exploits a relation between our tolling problem and a novel bipartite matching problem without crossings, which we prove to be NP-hard.

UR - http://www.scopus.com/inward/record.url?scp=85056875469&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056875469&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85056875469

T3 - CEUR Workshop Proceedings

SP - 36

EP - 47

BT - Italian Conference on Theoretical Computer Science

A2 - Aldini, Alessandro

A2 - Bernardo, Marco

T2 - 19th Italian Conference on Theoretical Computer Science, ICTCS 2018

Y2 - 18 September 2018 through 20 September 2018

ER -