Facility Location with Minimax Envy

Qingpeng Cai, Aris Filos-Ratsikas, Pingzhong Tang

Abstract

In the classic facility location problem, the goal is typically to minimize total or maximum travel costs. However, these metrics often overlook individual fairness. This paper investigates the "minimax envy" objective, which seeks to minimize the maximum difference in travel costs between any two agents. We explore this objective within the framework of approximate mechanism design without money, focusing on the requirement of strategy-proofness. Our results demonstrate that while deterministic mechanisms are inherently limited, randomized mechanisms—specifically the $\alpha$-LRM class—can achieve near-optimal additive approximation on the real line.

1. Introduction

The facility location problem is a cornerstone of social choice theory and operations research. Consider a scenario where a central authority must place a public resource, such as a library or a transit stop, along a linear corridor. Each resident desires the facility to be as close to their home as possible. Traditionally, two primary objectives have dominated the literature: minimizing the sum of distances (social cost) or minimizing the maximum distance any single individual must travel (egalitarian cost).

While these objectives address efficiency and basic equity, they do not account for relative fairness. An agent may feel "envious" if the chosen location grants another agent a significantly shorter commute. This paper introduces and analyzes the minimax envy objective: finding a facility location that minimizes the largest gap in travel costs between any two participants.

2. The Challenge of Truthfulness

A significant hurdle in facility location is that the central planner often lacks information regarding the agents' true locations. To make an informed decision, the planner must solicit reports from the agents. This introduces the risk of strategic manipulation: an agent might misreport their location to pull the facility closer to their actual home.

A mechanism is considered truthful (or strategy-proof) if no agent can decrease their expected distance to the facility by lying about their position. The central tension of this research lies in balancing the minimization of envy with the strict requirement of truthfulness.

3. Methodology: Additive Approximation

In many optimization problems, performance is measured using a multiplicative approximation ratio. However, in the context of minimax envy, the optimal envy can be zero (e.g., when the facility is placed exactly at the midpoint of two agents). Because division by zero is undefined, a multiplicative ratio becomes mathematically uninformative.

To circumvent this, the authors employ additive approximation. This metric measures the absolute difference between the envy produced by a mechanism and the theoretical minimum envy possible for a given set of reports.

4. The $\alpha$-LRM Mechanism

The core contribution of this work is the development of the $\alpha$-LRM (Left-Right-Median) mechanism. This randomized approach generalizes the standard median-based mechanisms to incorporate fairness.

The mechanism operates as follows:

  1. Identify Extremes: The mechanism identifies the most extreme reported positions: the leftmost agent ($lm$) and the rightmost agent ($rm$).
  2. Calculate Midpoint: It calculates the midpoint ($mid = (lm + rm) / 2$), which is the mathematically optimal envy-minimizing location.
  3. Randomized Placement: The facility is placed at the midpoint with probability $1 - 2\alpha$. With probability $\alpha$ each, the facility is placed at two specific "buffer" points outside the range of reported locations.

By introducing these small probabilities of placing the facility at the extremes, the mechanism removes the incentive for agents to lie. If an agent tries to shift the midpoint by reporting an even more extreme position, they increase the likelihood that the facility is placed at a "buffer" point far from their true location, resulting in a higher expected cost for them.

5. Key Results

5.1 Deterministic Limitations

The authors prove a strict lower bound for deterministic mechanisms: any truthful deterministic mechanism will always have a maximum envy of 1 in the worst case. In a normalized setting where 1 represents the maximum possible envy, this indicates that deterministic approaches are fundamentally incapable of providing meaningful fairness.

5.2 The Power of Randomization

On an unbounded real line, the $\alpha$-LRM mechanism is shown to be near-optimal. For any $\epsilon > 0$, there exists a configuration of $\alpha$ such that the mechanism achieves an additive approximation of $\epsilon$. This suggests that randomization is the essential tool for unlocking fair and truthful outcomes.

5.3 Constrained Environments

The problem becomes more complex when the facility must be placed within a fixed interval (e.g., a specific city block $[0, 1]$). In these scenarios, the planner loses the "freedom" to place the facility far outside the reported range to discourage misreporting. Consequently, the best possible truthful-in-expectation mechanism in a fixed interval has an additive approximation bound between $1/3$ and $1/2$.

6. Conclusion and Future Directions

This research provides a rigorous foundation for incorporating envy-freeness into facility location problems. While the current study focuses on one-dimensional space, it opens several avenues for future exploration:

  • General Metric Spaces: Moving beyond the real line to 2D planes or complex graphs.
  • Multiple Facilities: How to minimize envy when building two or more facilities where agents are served by the nearest one.
  • Alternative Fairness Notions: Applying these truthfulness constraints to other fair-division criteria from economic literature.

By shifting the focus from aggregate costs to relative envy, this work offers a more nuanced framework for designing public systems that are both efficient and perceived as fair by the participants.

Summary updated

Abstract

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 [Procaccia and Tennenholtz, 2009; Alon et al., 2009], 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.
BibTeX
@inproceedings{cai2016facility,
  author = {Qingpeng Cai and Aris Filos-Ratsikas and Pingzhong Tang},
  title = {{Facility Location with Minimax Envy}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure