The search functionality is under construction.

The search functionality is under construction.

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

Yuhei FUKUI

Kyoto University

Aleksandar SHURBEVSKI

Kyoto University

Hiroshi NAGAMOCHI

Kyoto University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Yuhei FUKUI, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, "λ-Group Strategy-Proof Mechanisms for the Obnoxious Facility Game in Star Networks" in IEICE TRANSACTIONS on Fundamentals,
vol. E102-A, no. 9, pp. 1179-1186, September 2019, doi: 10.1587/transfun.E102.A.1179.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1179/_p

Copy

@ARTICLE{e102-a_9_1179,

author={Yuhei FUKUI, Aleksandar SHURBEVSKI, Hiroshi NAGAMOCHI, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={λ-Group Strategy-Proof Mechanisms for the Obnoxious Facility Game in Star Networks},

year={2019},

volume={E102-A},

number={9},

pages={1179-1186},

abstract={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.},

keywords={},

doi={10.1587/transfun.E102.A.1179},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1179

EP - 1186

AU - Yuhei FUKUI

AU - Aleksandar SHURBEVSKI

AU - Hiroshi NAGAMOCHI

PY - 2019

DO - 10.1587/transfun.E102.A.1179

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E102-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2019

AB - 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.

ER -