Truthful Facility Location with Additive Errors

Iddan Golomb, Christos TzamosarXiv 2017 · OpenReview

Abstract

We address the problem of locating facilities on the $[0,1]$ interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and the global objective is to minimize either the maximum cost of an agent or the social cost. As opposed to the extensive literature on facility location which considers the multiplicative error, we focus on minimizing the worst-case additive error. Minimizing the additive error incentivizes mechanisms to adapt to the size of the instance. I.e., mechanisms can sacrifice little efficiency in small instances (location profiles in which all agents are relatively close to one another), in order to gain more [absolute] efficiency in large instances. We argue that this measure is better suited for many manifestations of the facility location problem in various domains. We present tight bounds for mechanisms locating a single facility in both deterministic and randomized cases. We further provide several extensions for locating multiple facilities.

Introduction

In the classic Facility Location Problem, a central planner must position facilities (e.g., libraries, bus stops) along a line to serve strategic agents. Traditionally, the performance of truthful mechanisms—where agents have no incentive to misreport their locations—is evaluated using the approximation ratio (multiplicative error). However, this paper argues that in many real-world contexts, such as setting a room's temperature or allocating a budget, the absolute distance or additive error is a more natural measure of fairness and efficiency. Unlike multiplicative ratios, which can be overly sensitive in small-scale instances, additive error focuses on the tangible cost of a decision relative to the total domain size.

Methodology

The research employs tools from mechanism design and social choice theory to characterize optimal truthful mechanisms. A key finding is that for single-facility location, any optimal truthful mechanism can be simplified into a "5-point mechanism," where the facility is placed at one of five specific locations: the interval boundaries, the reported extremes, or their midpoint.

The authors introduce several novel mechanisms:

  • BLRC (Balanced Left-Right-Center): A randomized mechanism that combines the existing LRC mechanism with a fixed placement at the midpoint (1/2).
  • Phantom-half: A deterministic mechanism that selects the median of the leftmost report, the rightmost report, and a "phantom" agent at 0.5.
  • Equal Spread & EPEC: Extensions designed for multi-facility ($k$) settings to distribute facilities across the interval.

Main Results

The primary contribution of this work is the establishment of tight bounds for the maximum cost objective on the $[0, 1]$ interval. By requiring truthfulness, a certain degree of efficiency must be sacrificed. The results show that randomized mechanisms can achieve a lower additive error than deterministic ones.

Summary of tight bounds for single facility location with additive error.

As shown in the table above, the best possible additive error is $1/6$ for randomized mechanisms and $1/4$ for deterministic ones. These results significantly improve upon previous benchmarks, such as the $1/2$ error associated with simple dictatorship mechanisms in the deterministic case.

Multi-facility Extensions and Future Work

For settings with $k$ facilities, the authors prove a deterministic lower bound of $1/(6k)$. In the case of minimizing average cost with two facilities, they propose the "Fifths" mechanism, which achieves an additive error of $1/5$.

While these results provide a comprehensive look at the $[0, 1]$ interval, several avenues for future research remain. The current findings rely on a bounded domain; extending these additive error bounds to more complex metric spaces like trees, cycles, or general graphs presents a significant challenge. Additionally, exploring other objectives, such as the $L_2$ norm (minimizing the sum of squared distances), could provide further insights into the trade-offs between truthfulness and additive efficiency.

Summary updated

Abstract

We address the problem of locating facilities on the $[0,1]$ interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and the global objective is to minimize either the maximum cost of an agent or the social cost. As opposed to the extensive literature on facility location which considers the multiplicative error, we focus on minimizing the worst-case additive error. Minimizing the additive error incentivizes mechanisms to adapt to the size of the instance. I.e., mechanisms can sacrifice little efficiency in small instances (location profiles in which all agents are relatively close to one another), in order to gain more [absolute] efficiency in large instances. We argue that this measure is better suited for many manifestations of the facility location problem in various domains. We present tight bounds for mechanisms locating a single facility in both deterministic and randomized cases. We further provide several extensions for locating multiple facilities.
BibTeX
@misc{golomb2017truthful,
  author = {Iddan Golomb and Christos Tzamos},
  title = {{Truthful Facility Location with Additive Errors}},
  year = {2017},
  eprint = {1701.00529},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1701.00529},
}
Figure