The search functionality is under construction.
The search functionality is under construction.

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

Yuhei FUKUI, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1179-1186
Publication Date
2019/09/01
Publicized
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

Authors

Yuhei FUKUI
  Kyoto University
Aleksandar SHURBEVSKI
  Kyoto University
Hiroshi NAGAMOCHI
  Kyoto University

Keyword