500. Popular Facility Location
Invited abstract in session MA-53: Algorithmic Game Theory and Its Applications, stream Game Theory and Mathematical Economics.
Monday, 8:30-10:00Room: Liberty Moot Court
Authors (first author is the speaker)
| 1. | Xujin Chen
|
| Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 2. | Changjun Wamg
|
| Academy of Mathematics and Systems Science, Chinese Academy of Sciences | |
| 3. | Chenhao Wang
|
| Advanced Institute of Natural Sciences, Beijing Normal University (Zhuhai) |
Abstract
Facility location problems address the strategic placement of k facilities to serve a geographically distributed set of customers. We introduce a novel "popularity" criterion for location selection: a solution (a set of k selected locations) is popular if no unselected location is preferred over any selected location by a majority of customers. For networks with continuous customer distribution, we develop efficient algorithms to compute popular solutions when k exceeds a certain threshold. We analyze the quality of popular solutions using the Price of Anarchy and Price of Stability, comparing their social cost to the optimal solution. Our analysis reveals that these price ratios are bounded by small constants and are notably lower than those of Nash equilibria in the facility location games. This suggests that popularity offers a compelling alternative to traditional solution concepts, providing both computational tractability and good-quality solutions.
Keywords
- Location
- Combinatorial Optimization
- Game Theory
Status: accepted
Back to the list of papers