Strategyproof Mechanism for Two Heterogeneous Facilities with Constant Approximation Ratio
Authors: Minming Li, Pinyan Lu, Yuhao Yao, Jialin Zhang
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the two-facility location game with optional preference where the acceptable set of facilities for each agent could be different and an agent s cost is his distance to the closest facility within his acceptable set. The objective is to minimize the total cost of all agents while achieving strategyproofness. For general metrics, we design a deterministic strategyproof mechanism for the problem with approximation ratio of 1+2α, where α is the approximation ratio of the offline optimization version. In particular, for the setting on a line, we improve the earlier best ratio of n/2 + 1 [Yuan et al., 2016] to a ratio of 2.75. In this section, we introduce our mechanism and prove its strategyproofness. In Section 4, we will analyze its approximation ratio. |
| Researcher Affiliation | Academia | Minming Li1 , Pinyan Lu2 , Yuhao Yao3 and Jialin Zhang3,4 1City University of Hong Kong, Hong Kong, China 2ITCS, Shanghai University of Finance and Economics, Shanghai, China 3University of Chinese Academy of Sciences, Beijing, China 4Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China minming.li@cityu.edu.hk, lu.pinyan@mail.shufe.edu.cn, yaoyuhao15@mails.ucas.ac.cn, zhangjialin@ict.ac.cn |
| Pseudocode | Yes | Mechanism 1. Denote by q the preference profile {{F1, F2}, {F1, F2}, ..., {F1, F2}}, i.e. every agent prefers both facilities. Let A be the set of all available facility locations and let location pair (s1, s2) satisfy (s1, s2) = arg miny1,y2 A SCx,q(y1, y2). Finally, we output the pair (f1, f2) = arg miny1,y2 {s1,s2} SCx,p(y1, y2). We break the tie in this order: (s1, s1), (s1, s2), (s2, s1), (s2, s2). |
| Open Source Code | No | No statement about open-sourcing code or links to a code repository were found. |
| Open Datasets | No | No datasets are mentioned as the paper is theoretical. |
| Dataset Splits | No | No dataset splits are provided as the paper is theoretical and does not involve empirical validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | No specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | No experimental setup details, such as hyperparameters or training settings, are provided as the paper is theoretical. |