• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Chen, Xujin (Chen, Xujin.) | Li, Minming (Li, Minming.) | Wang, Changjun (Wang, Changjun.) | Wang, Chenhao (Wang, Chenhao.) | Zhao, Yingchao (Zhao, Yingchao.)

收录:

EI Scopus

摘要:

This paper is devoted to the facility location games with payments, where every agent plays a dual role of facility and customer. In this game, each selfish agent is located on a publicly known location in a metric space, and can allow a facility to be opened at his place. But the opening cost is his private information and lie may strategically report this opening cost. Besides, each agent also bears a scrvice cost equal to the distance to his nearest open facility. We are concerned with designing truthful mechanisms for the game, which, given agents' reports, output a set of agents whose facilities could be opened, and a payment to each of these agents who opens a facility. The objective is to minimize (exactly or approximately) the social cost (the total opening and service costs) or the maximum agent cost of the outcome. We characterize the normalized truthful mechanisms for this game. Concerning the minimum social-cost objective, we give an optimal truthful mechanism without regard to time complexity, and show a small gap between the best known approximation ratio of polynomial-time truthful mechanisms for the game and that of polynomial-time approximation algorithms for the counterpart of pure optimization. For the minimum maximum-cost objective, we provide an optimal truthful mechanism which runs in polynomial time. We also investigate mechanism design for the game under a budget on the total payment. © 2019 International Foundation for Autonomous Agents and Multiagent Systems. All rights reserved.

关键词:

Approximation algorithms Autonomous agents Budget control Game theory Location Machine design Multi agent systems Polynomial approximation

作者机构:

  • [ 1 ] [Chen, Xujin]Acad. Math. and Syst. Sci. (AMSS), Chinese Acad. Sci. (CAS), China
  • [ 2 ] [Chen, Xujin]University of CAS China, China
  • [ 3 ] [Li, Minming]City University of Hong Kong, Shenzhen Research Institute China, Hong Kong
  • [ 4 ] [Wang, Changjun]Beijing University of Technology China, China
  • [ 5 ] [Wang, Chenhao]AMSS, CAS
  • [ 6 ] [Wang, Chenhao]University of CAS, China
  • [ 7 ] [Wang, Chenhao]City University of Hong Kong, Hong Kong
  • [ 8 ] [Zhao, Yingchao]Caritas Institute of Higher Education, China

通讯作者信息:

  • [wang, chenhao]amss, cas;;[wang, chenhao]city university of hong kong, hong kong;;[wang, chenhao]university of cas, china

电子邮件地址:

查看成果更多字段

相关关键词:

相关文章:

来源 :

ISSN: 1548-8403

年份: 2019

卷: 3

页码: 1470-1478

语种: 英文

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 3

归属院系:

在线人数/总访问数:657/2913368
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司