λ-Group Strategy-Proof Mechanisms for the Obnoxious Facility Game in Star Networks

Yuhei FUKUI  Aleksandar SHURBEVSKI  Hiroshi NAGAMOCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1179-1186
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1179
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Mechanical design
Keyword: 
mechanism design,  obnoxious facility game,  strategy proofness,  star network,  

Full Text: PDF(1015.7KB)>>
Buy this Article




Summary: 
In the obnoxious facility game, we design mechanisms that output a location of an undesirable facility based on the locations of players reported by themselves. The benefit of a player is defined to be the distance between her location and the facility. A player may try to manipulate the output of the mechanism by strategically misreporting her location. We wish to design a λ-group strategy-proof mechanism i.e., for every group of players, at least one player in the group cannot gain strictly more than λ times her primary benefit by having the entire group change their reports simultaneously. In this paper, we design a k-candidate λ-group strategy-proof mechanism for the obnoxious facility game in the metric defined by k half lines with a common endpoint such that each candidate is a point in each of the half-lines at the same distance to the common endpoint as other candidates. Then, we show that the benefit ratio of the mechanism is at most 1+2/(k-1)λ. Finally, we prove that the bound is nearly tight.