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:
- Identify Extremes: The mechanism identifies the most extreme reported positions: the leftmost agent ($lm$) and the rightmost agent ($rm$).
- Calculate Midpoint: It calculates the midpoint ($mid = (lm + rm) / 2$), which is the mathematically optimal envy-minimizing location.
- 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