Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Facility Location Games with Optional Preferences: A Revisit
Authors: Xingchen Sha, Shuyu Bao, Hau Chan, Vincent Chau, Ken C. K. Fong, Minming Li
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the k-facility location games with optional preferences on the line. In the games, each strategic agent has a public location preference on the k facility locations and a private optional preference on the preferred/acceptable set of facilities out of the k facilities. Our goal is to design strategyproof mechanisms to elicit agents optional preferences and locate k facilities to minimize the social or maximum cost of agents based on their facility preferences and public agent locations. For the Min variant, we present two deterministic strategyproof mechanisms to minimize the maximum cost and social cost with k 3 facilities and well-separated n agents, achieving approximation ratios of 3 and 2n + 1 respectively. We complement the results by establishing lower bounds of 3 4 for the approximation ratios achievable by any deterministic strategyproof mechanisms for the maximum cost and social cost, respectively. |
| Researcher Affiliation | Academia | 1Department of Computer Science, City University of Hong Kong, HKSAR China 2Department of Computer Science and Engineering, University of Nebraska-Lincoln, USA 3School of Computer Science and Engineering, Southeast University, China 4Division of Artificial Intelligence, School of Data Science, Lingnan University, HKSAR China |
| Pseudocode | Yes | Algorithm 1: OPTMC(X) Input: Agent location profile X = (x1, . . . , xn). Without loss of generality, assume x1 xn. Parameter: Define M(i, j) to be the facility location profile that minimizes maximum cost of the first i-th agents from left to right with j facilities. Define MC(i, j) to be the maximum cost of the first i-th agents with M(i, j). Initialize M(i, 1) = { xi+x1 2 }. Initialize MC(i, j) = xi x1 2 if j = 1, otherwise. Output: M(n, k). 1: for i {2, . . . , n}, j {2, . . . , k} do 2: for m {1, . . . , i 1} do 3: if max{MC(m, j 1), xi xm+1 2 } < MC(i, j) then 4: MC(i, j) = max{MC(m, j 1), xi xm+1 5: M(i, j) = M(m, j 1).append( xi+xm+1 2 ) 6: end if 7: end for 8: end for 9: return M(n, k) |
| Open Source Code | No | The paper does not contain any explicit statement about providing open-source code or a link to a code repository. |
| Open Datasets | No | The paper describes theoretical models and algorithms for facility location games. It does not mention the use of any specific public or open datasets for experimental purposes. |
| Dataset Splits | No | The paper describes theoretical models and algorithms, and does not conduct empirical experiments with datasets. Therefore, it does not provide information on dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical contributions and does not describe any experimental setup that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental implementation that would require listing software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical in nature, focusing on mechanism design and approximation ratios, and does not include an experimental section detailing hyperparameters or training configurations. |