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

*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