
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

λGroup StrategyProof 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.E102A
No.9
pp.11791186 Publication Date: 2019/09/01
Online ISSN: 17451337
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)>>
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 strategyproof 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 kcandidate λgroup strategyproof 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 halflines 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/(k1)λ. Finally, we prove that the bound is nearly tight.

