For Full-Text 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 Strategy-Proof Mechanisms for the Obnoxious Facility Game in Star Networks
Yuhei FUKUI Aleksandar SHURBEVSKI Hiroshi NAGAMOCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2019/09/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Mechanical design
mechanism design, obnoxious facility game, strategy proofness, star network,
Full Text: PDF(1015.7KB)>>
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.