Approximation Strategy-Proof Mechanisms for Obnoxious Facility Location on a Line
文献类型：期刊论文
| 作者 | Yong Zhang; Lili Mei; Deshi Ye |
| 刊名 | Journal of Combinatorial Optimization
 |
| 出版日期 | 2017 |
| 文献子类 | 期刊论文 |
| 英文摘要 | In the facility location game on a line, there are some agents who have fixed locations on the line where an obnoxious facility will be placed. The objective is to maximize the social welfare, e.g., the sum of distances from the facility to all agents. On collecting location information, agents may misreport the locations so as to stay far away from the obnoxious facility. In this paper, strategy-proof mechanisms are designed and the approximation ratio is used to measure the performances of the strategy-proof mechanisms. Two objective functions, maximizing the sum of squares of distances (maxSOS) and maximizing the sum of distances (maxSum), have been considered. For maxSOS, a randomized 5/3-approximated strategy-proof mechanism is proposed, and the lower bound of the approximation ratio is proved to be at least 1.042. For maxSum, the lower bound of the approximation ratio of the randomized strategy-proof mechanism is proved to be 1.077. Moreover, a general model is considered that each agent may have multiple locations on the line. For the objective functions maxSum and maxSOS, both deterministic and randomized strategy-proof mechanisms are investigated, and the deterministic mechanisms are shown to be best possible. |
| URL标识 | 查看原文 |
| 语种 | 英语 |
| WOS记录号 | WOS:000435964700013 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/12477]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | Journal of Combinatorial Optimization |
| 推荐引用方式 GB/T 7714 | Yong Zhang,Lili Mei,Deshi Ye. Approximation Strategy-Proof Mechanisms for Obnoxious Facility Location on a Line[J]. Journal of Combinatorial Optimization,2017. |
| APA | Yong Zhang,Lili Mei,&Deshi Ye.(2017).Approximation Strategy-Proof Mechanisms for Obnoxious Facility Location on a Line.Journal of Combinatorial Optimization. |
| MLA | Yong Zhang,et al."Approximation Strategy-Proof Mechanisms for Obnoxious Facility Location on a Line".Journal of Combinatorial Optimization (2017). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。