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

Félix Carvalho Rodrigues, Guido Schäfer, Eduardo Candido Xavier

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationItalian Conference on Theoretical Computer Science
Subtitle of host publicationProceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018.
EditorsAlessandro Aldini, Marco Bernardo
Pages36-47
Number of pages12
Publication statusPublished - 2018
Event19th Italian Conference on Theoretical Computer Science, ICTCS 2018 - Urbino, Italy
Duration: 18 Sep 201820 Sep 2018

Publication series

NameCEUR Workshop Proceedings
PublisherCEUR
Volume2243
ISSN (Print)1613-0073

Conference

Conference19th Italian Conference on Theoretical Computer Science, ICTCS 2018
CountryItaly
CityUrbino
Period18/09/1820/09/18

Fingerprint

Costs
Stars
Polynomials

Cite this

Rodrigues, F. C., Schäfer, G., & Xavier, E. C. (2018). On the effectiveness of connection tolls in fair cost facility location games. In A. Aldini, & M. Bernardo (Eds.), Italian Conference on Theoretical Computer Science: Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018. (pp. 36-47). (CEUR Workshop Proceedings; Vol. 2243).
Rodrigues, Félix Carvalho ; Schäfer, Guido ; Xavier, Eduardo Candido. / On the effectiveness of connection tolls in fair cost facility location games. Italian Conference on Theoretical Computer Science: Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018.. editor / Alessandro Aldini ; Marco Bernardo. 2018. pp. 36-47 (CEUR Workshop Proceedings).
@inproceedings{60439f62cdc64c4985e079c5c407fbf5,
title = "On the effectiveness of connection tolls in fair cost facility location games",
abstract = "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.",
author = "Rodrigues, {F{\'e}lix Carvalho} and Guido Sch{\"a}fer and Xavier, {Eduardo Candido}",
year = "2018",
language = "English",
series = "CEUR Workshop Proceedings",
publisher = "CEUR",
pages = "36--47",
editor = "Alessandro Aldini and Marco Bernardo",
booktitle = "Italian Conference on Theoretical Computer Science",

}

Rodrigues, FC, Schäfer, G & Xavier, EC 2018, On the effectiveness of connection tolls in fair cost facility location games. in A Aldini & M Bernardo (eds), Italian Conference on Theoretical Computer Science: Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018.. CEUR Workshop Proceedings, vol. 2243, pp. 36-47, 19th Italian Conference on Theoretical Computer Science, ICTCS 2018, Urbino, Italy, 18/09/18.

On the effectiveness of connection tolls in fair cost facility location games. / Rodrigues, Félix Carvalho; Schäfer, Guido; Xavier, Eduardo Candido.

Italian Conference on Theoretical Computer Science: Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018.. ed. / Alessandro Aldini; Marco Bernardo. 2018. p. 36-47 (CEUR Workshop Proceedings; Vol. 2243).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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

T3 - CEUR Workshop Proceedings

SP - 36

EP - 47

BT - Italian Conference on Theoretical Computer Science

A2 - Aldini, Alessandro

A2 - Bernardo, Marco

ER -

Rodrigues FC, Schäfer G, Xavier EC. On the effectiveness of connection tolls in fair cost facility location games. In Aldini A, Bernardo M, editors, Italian Conference on Theoretical Computer Science: Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018.. 2018. p. 36-47. (CEUR Workshop Proceedings).