Facility Location with Minimax Envy

Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We study the problem of locating a public facility on a real line or an interval, when agents' costs are their (expected) distances from the location of the facility. Our goal is to minimize the maximum envy over all agents, which we will refer to as the minimax envy objective, while at the same time ensuring that agents will report their most preferred locations truthfully. First, for the problem of locating the facility on a real line, we propose a class of truthful-in-expectation mechanisms that generalize the well-known LRM mechanism, the best of which has performance arbitrarily close to the social optimum. Then, we restrict the possible locations of the facility to a real interval and consider two cases; when the interval is determined relatively to the agents' reports and when the interval is fixed in advance. For the former case, we prove that for any choice of such an interval, there is a mechanism in the aforementioned class with additive approximation arbitrarily close to the best approximation achieved by any truthful-in-expectation mechanism. For the latter case, we prove that the approximation of the best truthful-in-expectation mechanism is between 1/3 and 1/2.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence
Place of PublicationPalo Alto, CA, USA
PublisherAAAI Press / International Joint Conferences on Artificial Intelligence
Number of pages7
ISBN (Print)978-1-57735-770-4
Publication statusPublished - 15 Jul 2016
EventTwenty-Fifth International Joint Conference on Artificial Intelligence - New York City, United States
Duration: 9 Jul 201615 Jul 2016


ConferenceTwenty-Fifth International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2016
Country/TerritoryUnited States
CityNew York City
Internet address


Dive into the research topics of 'Facility Location with Minimax Envy'. Together they form a unique fingerprint.

Cite this