Two-facility Location Games with Minimum Distance Requirement
Authors: Xinping Xu, Bo Li, Minming Li, Lingjie Duan
JAIR 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the mechanism design problem of a social planner for locating two facilities on a line interval [0, 1], where a set of n strategic agents report their locations and a mechanism determines the locations of the two facilities. We consider the requirement of a minimum distance 0 d 1 between the two facilities. In the heterogeneous two-facility location game to minimize the social cost, we show that the optimal solution can be computed in polynomial time and prove that carefully choosing one optimal solution as output is strategyproof. We also design a strategyproof mechanism minimizing the maximum cost. In the homogeneous two-facility location game for minimizing the social cost, we show that any deterministic strategyproof mechanism has unbounded approximation ratio. Moreover, in the obnoxious heterogeneous two-facility location game for maximizing the social utility, we propose new deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound (7 d)/6 for any deterministic strategyproof mechanism. We also design a strategyproof mechanism maximizing the minimum utility. In the obnoxious homogeneous two-facility location game for maximizing the social utility, we propose deterministic group strategyproof mechanisms with provable approximation ratios and establish a lower bound 4/3. Besides, in the two-facility location game with triple-preference, where each facility may be favorable, obnoxious, indiļ¬erent for any agent, we further motivate agents to report both their locations and preferences towards the two facilities truthfully, and design a deterministic group strategyproof mechanism with an approximation ratio 4. |
| Researcher Affiliation | Academia | Xinping Xu EMAIL School of Electrical and Electronic Engineering, Nanyang Technological University, 50 Nanyang Ave, Singapore 639798 Bo Li EMAIL Department of Computing, The Hong Kong Polytechnic University, 11 Yuk Choi Rd, Hung Hom, Hong Kong SAR Minming Li EMAIL Department of Computer Science, City University of Hong Kong, 83 Tat Chee Ave, Kowloon Tong, Hong Kong SAR Lingjie Duan lingjie EMAIL Engineering System and Design Pillar, Singapore University and Design, 8 Somapah Rd, Singapore 487372 |
| Pseudocode | Yes | Mechanism 1. (y1, y2) = (y 1(d; x), y 1(d; x) + d) where y 1(d; x) = max{0, xn} = 0 if xn d xn if xn > d . Mechanism 2. If d xn x1, return y1 = min{x1, 1 d} and y2 = y1 + d; if d < xn x1, return y1 = x1 and y2 = xn. |
| Open Source Code | No | The paper does not provide any specific links to source code repositories, nor does it explicitly state that code will be made available or is included in supplementary materials. |
| Open Datasets | No | The paper is theoretical and focuses on mechanism design, proofs, and approximation ratios for facility location games. It does not use or reference any publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments on datasets, therefore, there are no dataset splits mentioned. |
| Hardware Specification | No | The paper is theoretical, focusing on mathematical proofs and mechanism design. It does not describe any computational experiments that would require specific hardware, thus no hardware specifications are provided. |
| Software Dependencies | No | The paper describes theoretical mechanisms and proofs; it does not mention any software implementations or dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and presents mathematical proofs and mechanism designs. It does not include any experimental setup details such as hyperparameters or training configurations. |