Minimizing Inequity in Facility Location Games

Conference: AAAI 2026
arXiv: 2602.01048
Code: None
Area: AI Safety / Algorithmic Game Theory
Keywords: Facility Location, Group Fairness, Strategyproofness, Approximation Ratio, Social Choice

TL;DR

Investigates the problem of minimizing the maximum weighted group effect (Maximum Group Effect) in facility location games on the real line. The paper proposes two strategyproof mechanisms, BALANCED and MAJOR-PHANTOM, achieving tight approximation ratios in single-facility settings, unifying classical objectives like utilitarian (social cost) and egalitarian (maximum cost) with group fairness objectives, and extending the endpoint mechanism to two-facility settings.

Background & Motivation

Background: Facility location games are classic problems in social choice theory—selecting facility locations on a line to serve multiple agents distributed at different positions. Agents may strategically misreport their locations for personal gain. Classical strategyproof mechanisms (such as the median mechanism) optimize utilitarian objectives (minimizing total distance) or egalitarian objectives (minimizing maximum distance).

Limitations of Prior Work: Traditional objective functions neglect group fairness. When agents belong to different groups (e.g., different neighborhoods, different income classes), the cost-optimal solution may lead to certain groups bearing disproportionately high costs. Although the maximum group effect framework proposed by Marsh and Schilling (1994) provides a fair objective function, a known gap exists for approximation algorithms achieving strategyproofness: Zhou, Li, and Chan (2022) pointed out a gap in the approximation bound under the group fairness objective.

Key Challenge: Designing mechanisms that simultaneously satisfy strategyproofness (truthfulness) and minimize group inequity (minimizing maximum group effect) is fundamentally challenging—strategyproofness restricts the space of feasible mechanisms, whereas fairness requires a delicate balance of interest among different groups.

Goal: Design strategyproof mechanisms to minimize maximum group effect and close the existing gaps in approximation bounds.

Key Insight: Unify various classic facility location objectives (utilitarian, egalitarian, group fairness) under the maximum group effect framework, addressing them with a unified analytical framework.

Core Idea: Propose two new mechanisms, BALANCED (based on weighted medians) and MAJOR-PHANTOM (based on phantom voters), to achieve tight approximation ratios under two forms of group effects: total group effect and maximum group effect, respectively.

Method

Overall Architecture

On the real line \(\mathbb{R}\), \(n\) agents are partitioned into \(m\) groups. Each group \(g\) is associated with a weight factor \(w_g\). The group effect is defined as the sum (or maximum) of distances from its members to the nearest facility, multiplied by the weight. The objective is to select facility location(s) \(y\) to minimize the maximum group effect \(\max_g w_g \cdot \text{effect}_g(y)\) under the constraint that the mechanism must be strategyproof (no agent can benefit from misreporting their location).

Key Designs

1. BALANCED Mechanism (Single Facility, Total Effect):

   • Function: Minimize the maximum of the weighted total distances of all groups.
   • Mechanism: Compute the weighted median location of each group, and then select a balance point among these medians—where the weighted total effects of all groups are equalized as much as possible. Specifically, BALANCED outputs the location that balances the effects of the groups to its left and right.
   • Design Motivation: A naive global median ignores the differences between groups, whereas BALANCED explicitly considers group fairness by searching for a balance point among the group medians.

2. MAJOR-PHANTOM Mechanism (Single Facility, Max Effect):

   • Function: Minimize the maximum of the maximum weighted individual distances in each group.
   • Mechanism: Inspired by the phantom voter framework, phantom agents are constructed for each group—with their phantom locations determined by the group's weight and member distribution. Then, a median mechanism is executed on the extended set of real and phantom agents. The placement of phantom voters guarantees strategyproofness.
   • Design Motivation: Standard phantom mechanisms do not consider group structures; MAJOR-PHANTOM achieves group awareness by setting different phantom voters for each group.

3. Extended Endpoint Mechanism (Two Facilities):

   • Function: Minimize the maximum group effect when two facilities need to be placed.
   • Mechanism: Extend the classic endpoint mechanism (which chooses the two endpoints of the agent distribution as facility locations) to the group-fair setting. Through a carefully designed group-aware endpoint selection strategy, tight approximation ratios are achieved under both maximum group effect objectives.
   • Design Motivation: In multi-facility scenarios, strategyproofness is much harder to guarantee, and the endpoint mechanism is one of the few known strategyproof mechanisms for two facilities.

Theoretical Analysis

The strategyproofness of all mechanisms is established via standard game-theoretic arguments (single-peaked preferences + phantom/fixed rules \(\rightarrow\) strategyproofness). The approximation ratios are derived via worst-case analysis, and matching lower bounds are constructed to prove tightness.

Key Experimental Results

Main Results: Approximation Ratios

Setting	Objective Function	Mechanism	Approximation Ratio	Lower Bound	Status
Single Facility	max total group effect	BALANCED	\(1 + \frac{w_{\max}}{w_{\min}}\)	\(1 + \frac{w_{\max}}{w_{\min}}\)	Tight
Single Facility	max-max group effect	MAJOR-PHANTOM	\(1 + 2\frac{w_{\max}}{w_{\min}}\)	\(1 + 2\frac{w_{\max}}{w_{\min}}\)	Tight
Two Facilities	max total group effect	Extended Endpoint	\(n-1\)	\(n-1\)	Tight
Two Facilities	max-max group effect	Extended Endpoint	\(\frac{n}{2}\)	\(\frac{n}{2}\)	Tight

Unification with Classical Objectives

Classic Objective	Special Case	Corresponding Weight Setting
Utilitarian (Social Cost)	\(m=1\) Group	\(w_1 = 1\)
Egalitarian (Max Cost)	\(m=n\) (One per group)	\(w_g = 1, \forall g\)
Maximum Total Group Cost	Equal Weight	$w_g = 1/
Maximum Average Group Cost	Equal Weight Normalized	\(w_g = 1, \forall g\)

Closed Approximation Gaps

Objective	Zhou et al. (2022) Upper Bound	Zhou et al. (2022) Lower Bound	Ours
max total group cost	3	2	2 (Tight)
max avg group cost	\(1+n/2\)	Unknown	\(1+n/2\) (Tight)

Key Findings

• Completely closed the open gaps from Zhou et al. (2022): The approximation ratio for max total group cost is precisely pinned down to 2 from the previous interval [2, 3].
• Unified Framework: It unifies seemingly disparate objectives, such as utilitarianism, egalitarianism, and group fairness, under the maximum group effect formulation, where different weights recover different classical objectives.
• Tight Approximation Ratios: All proposed mechanisms feature matching lower bounds, demonstrating that no further improvements are possible under the constraint of strategyproofness.
• BALANCED and MAJOR-PHANTOM unify classical mechanisms: Under specific weight configurations, they degenerate to the standard median or phantom mechanisms.

Highlights & Insights

• Elegant Unified Framework: A parameterized objective function, max group effect, unifies multiple classical objectives in social choice theory, with different weight settings recovering different objectives. This unified perspective provides a clean analytical framework for subsequent research.
• Precise Approximation Bounds: All results are tight (matching upper and lower bounds), which is of high value in mechanism design—it not only shows what is achievable but also precisely states that "no better is possible".
• Practical Significance: Highly applicable in fields like urban planning and public facility location. When different communities have different priority weights for services, the BALANCED mechanism guarantees fairness.

Limitations & Future Work

• Limited to the real line (one-dimensional) setting; high-dimensional facility location is more realistic but strategyproofness is much harder to achieve.
• The approximation ratios for the two-facility scenario are \(O(n)\), which might be less desirable when the number of agents is large.
• It assumes that group weights \(w_g\) are public knowledge and non-manipulable. The problem would be entirely different if weights could also be strategically reported.
• Only deterministic mechanisms are considered; randomized mechanisms could potentially achieve better approximation ratios.

Related Work & Insights

• vs Zhou, Li, Chan (2022): Introduced the group-fair facility location problem but left gaps in approximation bounds; this work completely closes those gaps.
• vs Procaccia & Tennenholtz (2013): A classic framework for single-facility mechanism design, which this paper generalizes to the group-fair setting.
• vs Moulin (1980): Standard phantom mechanisms do not consider group structure; MAJOR-PHANTOM extends this classic framework by incorporating group-aware phantom voters.

Rating

• Novelty: ⭐⭐⭐⭐ The unified framework perspective is novel, and the two new mechanisms provide solid contributions.
• Experimental Thoroughness: ⭐⭐⭐⭐ All theoretical results have tight lower bounds, making the theory complete.
• Writing Quality: ⭐⭐⭐⭐ Mathematically rigorous, though readability might be somewhat low for non-game-theory readers.
• Value: ⭐⭐⭐⭐ Closes open problems, unifies classical results, and offers significant theoretical contributions.

Related Papers

• [NeurIPS 2025] Learning-Augmented Facility Location Mechanisms for Envy Ratio
• [AAAI 2026] Revisiting (Un)Fairness in Recourse by Minimizing Worst-Case Social Burden
• [AAAI 2026] Alternative Fairness and Accuracy Optimization in Criminal Justice
• [AAAI 2026] Truth, Justice, and Secrecy: Cake Cutting Under Privacy Constraints
• [ICML 2025] Convex Markov Games: A New Frontier for Multi-Agent Reinforcement Learning