Facility Location Games With Fractional Preferences

Chi Kit Ken Fong, Minming Li, Pinyan Lu, Taiki Todo, Makoto Yokoo

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:

  1. Private location, public preference: Locations are hidden; preferences are known.
  2. Public location, private preference: Locations are known; preferences are hidden.
  3. 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).
Illustration of agent distribution and median-based placement on a 1D line.

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.

Summary of approximation ratios (Upper Bounds and Lower Bounds) for different objectives and information restrictions.

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

Abstract

In this paper, we propose a fractional preference model for the facility location game with two facilities that serve the similar purpose on a line where each agent has his location information as well as fractional preference to indicate how well they prefer the facilities. The preference for each facility is in the range of [0, L] such that the sum of the preference for all facilities is equal to 1. The utility is measured by subtracting the sum of the cost of both facilities from the total length L where the cost of facilities is defined as the multiplication of the fractional preference and the distance between the agent and the facilities. We first show that the lower bound for the objective of minimizing total cost is at least Ω(n^1/3). Hence, we use the utility function to analyze the agents' satification. Our objective is to place two facilities on [0, L] to maximize the social utility or the minimum utility. For each objective function, we propose deterministic strategy-proof mechanisms. For the objective of maximizing the social utility, we present an optimal deterministic strategy-proof mechanism in the case where agents can only misreport their locations. In the case where agents can only misreport their preferences, we present a 2-approximation deterministic strategy-proof mechanism. Finally, we present a 4-approximation deterministic strategy-proof mechanism and a randomized strategy-proof mechanism with an approximation ratio of 2 where agents can misreport both the preference and location information. Moreover, we also give a lower-bound of 1.06. For the objective of maximizing the minimum utility, we give a lower-bound of 1.5 and present a 2-approximation deterministic strategy-proof mechanism where agents can misreport both the preference and location.
BibTeX
@inproceedings{fong2018facility,
  author = {Chi Kit Ken Fong and Minming Li and Pinyan Lu and Taiki Todo and Makoto Yokoo},
  title = {{Facility Location Games With Fractional Preferences}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11458},
}
Figure