Facility's Perspective to Fair Facility Location Problems

Chenhao Wang, Xiaoying Wu, Minming Li, Hau ChanAAAI 2021 · DOI

Introduction

Traditional facility location problems primarily focus on minimizing user travel distance or maximizing accessibility. However, this perspective often overlooks the preferences of the facility managers themselves. In many real-world scenarios—such as school districting, service center task allocation, or the placement of public amenities—facility managers have specific utilities associated with the items or users they serve. This paper introduces a novel framework for Fair Facility Location from the facility's perspective, balancing geographic constraints with fair resource allocation.

Problem Formulation and Methodology

The authors model the environment as a 1D real line $[0, 1]$ containing $n$ items with fixed positions. The central challenge is to place $m$ facilities such that the resulting allocation of items is fair to the managers. A critical constraint in this model is the closest assignment rule: every item must be served by its nearest facility. This requirement creates a geometric dependency that distinguishes the problem from standard fair division (e.g., cake cutting), where items can typically be assigned to any agent regardless of their location.

To analyze this problem, the researchers utilize several theoretical frameworks:

  • Fairness Notions: The study adapts classical concepts from fair division, specifically Proportionality (Prop)—where each facility receives at least $1/m$ of its total utility—and Envy-Freeness (EF)—where no facility prefers the bundle assigned to another.
  • Validity Checking via Linear Programming: A core technical hurdle is determining whether a specific contiguous partition of items can be "realized" by placing facilities. The authors demonstrate that this "validity" problem can be solved efficiently using Linear Programming (LP) by modeling the constraints on facility coordinates.
  • Complexity Analysis: By employing reductions from the EXACT-3-COVER (X3C) problem, the paper proves that determining the existence of a perfectly fair (Prop or EF) allocation is NP-complete.
  • Algorithmic Design: The authors propose a polynomial-time greedy algorithm designed to find Pareto-optimal valid allocations, ensuring that no facility's utility can be improved without diminishing another's.

Theoretical Insights: The "Half-Utility" Bridge

A significant contribution of the paper is the "Half-Utility" bridge (Proposition 2.4). The authors demonstrate that any contiguous allocation of items can be transformed into a "valid" allocation (one respecting the closest assignment rule) while preserving at least half of the utility for every facility. This insight provides a vital link between general fair division and the more geometrically constrained facility location setting, suggesting that the "cost" of the closest assignment rule is bounded.

Results: Fairness Guarantees and the Price of Fairness

The research quantifies the trade-offs between fairness and efficiency through the lens of the Price of Fairness (PoF). The PoF measures the ratio of the maximum possible social welfare to the maximum welfare achievable under a fairness constraint.

Price of Fairness bounds for Utilitarian and Egalitarian welfare.

As shown in the table above, the PoF for egalitarian welfare (maximizing the minimum utility) is exactly $m$. For utilitarian welfare, the price is bounded between $m-1 + 1/m$ and $m$. These high bounds indicate that enforcing strict fairness can significantly impact overall system efficiency.

Furthermore, the authors provide additive approximation bounds for Proportionality and Envy-Freeness. These results are compared against standard Fair Division with Contiguous bundles (FDC) to highlight the impact of the closest assignment constraint.

Comparison of fairness bounds between the proposed setting and standard Fair Division with Contiguous bundles (FDC).

Key findings from the fairness analysis include:

  • Proportionality Guarantees: In the proposed setting, there always exists a valid allocation that is roughly $\frac{n}{2m} \cdot u_{max}$ away from perfect proportionality.
  • Envy-Freeness Guarantees: The authors establish an additive bound of approximately $(\frac{3n}{5} + \frac{8}{5})u_{max}$ for envy-freeness.
  • Comparison to FDC: The bounds in the facility location setting are generally looser than those in FDC, reflecting the additional constraints imposed by the closest assignment rule.

Conclusion and Future Directions

This work establishes a foundational theory for fair facility location on a 1D line, highlighting the complex interplay between geography and fairness. However, the study's limitation to a 1D environment leaves several open questions. Extending the model to 2D planes or complex networks would introduce Voronoi diagram complexities where boundaries are no longer simple points. Additionally, exploring multiplicative fairness approximations (like EF1) and non-additive utility functions (such as submodular preferences) remains an important next step for developing more robust facility allocation systems.

Summary updated

BibTeX
@inproceedings{wang2021facility,
  author = {Chenhao Wang and Xiaoying Wu and Minming Li and Hau Chan},
  title = {{Facility's Perspective to Fair Facility Location Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16719},
}
Figure