This paper studies the dual-role-facility location game with generalized service costs, in which every agent plays a dual role of facility and customer, and is associated with a facility opening cost as his private information. The agents strategically report their opening costs to a mechanism which maps the reports to a set of selected agents and payments to them. Each selected agent opens his facility, incurs his opening cost and receives the payment the mechanism sets for him. Each unselected agent incurs a services cost that is determined by the set of selected agents in a very general way. The mechanism is truthful if under it no agent has an incentive to misreport. We provide a necessary and sufficient condition for mechanisms of the game to be truthful. This characterization particularly requires an invariant service cost for each unselected agent, which is a remarkable difference from related work in literature. 

　　As applications of this truthfulness characterization, we focus on the classic metric-space setting, in which agents' service costs equal their distances to closest open facilities. We present truthful mechanisms that minimize or approximately minimize the maximum cost among all agents and the total cost of all agents, respectively. Moreover, when the total payment cannot exceed a given budget, we prove, for both cost-minimization objectives, lower and upper bounds on approximation ratios of truthful mechanisms that satisfy the budget constraint. 

　　Publication: 

　　Theoretical Computer Science, Volume 932, 6 October 2022, Pages 69-83 

　　Author: 

　　Xujin Chen 

　　Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China 

　　School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China 

　　Email: xchen@amss.ac.cn 

　　Minming Li 

　　Department of Computer Science, City University of Hong Kong, Hong Kong 

　　Changjun Wang 

　　Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China 

　　Chenhao Wang 

　　Advanced Institute of Natural Sciences, Beijing Normal University, Zhuhai, China 

　　BNU-HKBU United International College, Zhuhai, China 

　　Mengqi Zhang 

　　Beijing Institute of Astronautical Systems Engineering, Beijing, China 

　　Yingchao Zhao 

　　Caritas Institute of Higher Education, Hong Kong