### 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 language | English |
---|---|

Title of host publication | Italian Conference on Theoretical Computer Science |

Subtitle of host publication | Proceedings of the 19th Italian Conference on Theoretical Computer Science. Urbino, Italy, September 18-20, 2018. |

Editors | Alessandro Aldini, Marco Bernardo |

Pages | 36-47 |

Number of pages | 12 |

Publication status | Published - 2018 |

Event | 19th Italian Conference on Theoretical Computer Science, ICTCS 2018 - Urbino, Italy Duration: 18 Sep 2018 → 20 Sep 2018 |

### Publication series

Name | CEUR Workshop Proceedings |
---|---|

Publisher | CEUR |

Volume | 2243 |

ISSN (Print) | 1613-0073 |

### Conference

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

Country | Italy |

City | Urbino |

Period | 18/09/18 → 20/09/18 |

### Fingerprint

### Cite this

*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).

}

*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.

Research output: Chapter in Book / Report / Conference proceeding › Conference contribution › Academic › peer-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 -