Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio
文献类型：期刊论文
| 作者 | Li, Minming1; Lu, Pinyan2,3; Sha, Xingchen1,4; Yao, Yuhao5; Zhang, Jialin5,6 |
| 刊名 | GAMES AND ECONOMIC BEHAVIOR
 |
| 出版日期 | 2026-03-01 |
| 卷号 | 157页码:125-137 |
| 关键词 | Algorithmic game theory Facility location Computational social choice |
| ISSN号 | 0899-8256 |
| DOI | 10.1016/j.geb.2026.01.008 |
| 英文摘要 | In this paper, we study the two-facility location games 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 an approximation ratio of 1 + 2 alpha, where alpha is the approximation ratio of the offline optimization version. In particular, for the setting on a line, our mechanism root achieves an approximation ratio of 1 + 2, which is tight and improves the previous best upper bound of n/2 + 1 (Chen et al., 2020). |
| 资助项目 | Research Grants Council of the Hong Kong Special Administrative Region, China[11216725] ; National Natural Science Foundation of China[62272441] ; National Natural Science Foundation of China[61922052] ; Innovation Program of Shanghai Municipal Education Commission ; Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) ; Fundamental Research Funds for the Central Universities ; Science and Technology Innovation 2030-New Generation of Artificial Intelligence Major Project[2018AAA0100903] |
| WOS研究方向 | Business & Economics |
| 语种 | 英语 |
| WOS记录号 | WOS:001683156300001 |
| 出版者 | ACADEMIC PRESS INC ELSEVIER SCIENCE |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/42787]  |
| 专题 | 中国科学院计算技术研究所 |
| 通讯作者 | Sha, Xingchen |
| 作者单位 | 1.City Univ Hong Kong, Hong Kong, Peoples R China 2.Shanghai Univ Finance & Econ, Shanghai, Peoples R China 3.Minist Educ, Key Lab Interdisciplinary Res Computat & Econ SUFE, Shanghai, Peoples R China 4.Northwestern Univ, Evanston, IL 60208 USA 5.Univ Chinese Acad Sci, Beijing, Peoples R China 6.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Li, Minming,Lu, Pinyan,Sha, Xingchen,et al. Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio[J]. GAMES AND ECONOMIC BEHAVIOR,2026,157:125-137. |
| APA | Li, Minming,Lu, Pinyan,Sha, Xingchen,Yao, Yuhao,&Zhang, Jialin.(2026).Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio.GAMES AND ECONOMIC BEHAVIOR,157,125-137. |
| MLA | Li, Minming,et al."Strategyproof mechanism for two heterogeneous facilities with constant approximation ratio".GAMES AND ECONOMIC BEHAVIOR 157(2026):125-137. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。