Introduction
In traditional facility location games, a central planner determines the optimal placement of resources—such as libraries, hospitals, or bus stops—based on agent locations. Conventional models typically assume that facilities are identical or that agents possess binary preferences (e.g., they either require a facility or they do not). However, real-world scenarios often involve facilities that serve distinct but related purposes. For instance, a resident might visit a large supermarket weekly but a local convenience store several times a week.
This paper introduces a fractional preference model to address these nuances. In this framework, agents can report varying degrees of need for two different facilities, $F_1$ and $F_2$ (e.g., "I spend 70% of my time needing $F_1$ and 30% needing $F_2$"). The primary challenge lies in designing strategy-proof mechanisms—algorithms that ensure agents have no incentive to misreport their private locations or preferences to manipulate the outcome.
Problem Formulation
The authors model agents on a 1D line $[0, L]$. Each agent $i$ has a private location $x_i$ and a private fractional preference $w_i \in [0, 1]$ for facility $F_1$, with $1 - w_i$ being the preference for $F_2$. The "cost" to an agent is defined as the weighted distance to both facilities: $C_i = w_i \cdot d(x_i, F_1) + (1 - w_i) \cdot d(x_i, F_2)$. The "utility" is defined as $U_i = L - C_i$.
The research investigates three information scenarios based on what the planner knows:
- Private location, public preference: Locations are hidden; preferences are known.
- Public location, private preference: Locations are known; preferences are hidden.
- Both private: Both locations and preferences are hidden.
The objectives are to maximize either Social Utility (the sum of all agents' utilities) or Minimum Utility (the utility of the least-satisfied agent).
Methodology
To achieve strategy-proofness while maintaining efficiency, the authors propose several algorithmic approaches:
- Median-based mechanisms: These place facilities at the "weighted median" of agent locations. This approach is particularly effective when only locations are private.
- Extreme-point mechanisms: These determine facility locations based on the agents at the boundaries of the distribution who express a preference for a specific facility.
- Randomized mechanisms: To counter strategic misreporting in highly restrictive scenarios, the authors employ randomization (e.g., choosing between two configurations with equal probability).
Key Results
The performance of these mechanisms is measured by their approximation ratio—the ratio between the optimal theoretical utility and the utility provided by the strategy-proof mechanism. A key finding is that while minimizing total cost leads to high inefficiency (scaling with the number of agents $n$), maximizing utility allows for constant-factor approximations regardless of population size.
For Social Utility:
- Location only private: Achieves an optimal ratio of 1 (Mechanism 1).
- Preference only private: A deterministic 2-approximation (Mechanism 2).
- Both private: A deterministic 4-approximation (Mechanism 4) and a randomized 2-approximation (Mechanism 5).
For Minimum Utility:
- A deterministic 2-approximation (Mechanism 6) works even when both location and preference are private.
The authors also established lower bounds, proving that no deterministic mechanism can achieve a ratio better than 1.06 for social utility or 1.5 for minimum utility.
Conclusion
This work extends facility location games into the realm of fractional preferences, providing a more realistic model for urban planning and resource allocation. The transition from cost-minimization to utility-maximization is a critical insight that enables constant-factor efficiency.
Future research directions include extending the model to 2D planes or complex networks, scaling the number of facilities beyond two, and narrowing the gap between the current approximation ratios and the theoretical lower bounds.
Summary updated