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 Dive into the research topics of 'On the effectiveness of connection tolls in fair cost facility location games'. Together they form a unique fingerprint.

  • 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). http://ceur-ws.org/Vol-2243/paper2.pdf