• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

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

Indexed by:

EI Scopus

Abstract:

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.

Keyword:

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

Author Community:

  • [ 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

Reprint Author's Address:

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

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 1548-8403

Year: 2019

Volume: 3

Page: 1470-1478

Language: English

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:1436/10692608
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.