The search functionality is under construction.

IEICE TRANSACTIONS on Information

Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees

Morito OOMINE, Hiroshi NAGAMOCHI

  • Full Text Views

    0

  • Cite this

Summary :

In the obnoxious facility game with a set of agents in a space, we wish to design a mechanism, a decision-making procedure that determines a location of an undesirable facility based on locations reported by the agents, where we do not know whether the location reported by an agent is where exactly the agent exists in the space. For a location of the facility, the benefit of each agent is defined to be the distance from the location of the facility to where the agent exists. Given a mechanism, all agents are informed of how the mechanism utilizes locations reported by the agents to determine a location of the facility before they report their locations. Some agent may try to manipulate the decision of the facility location by strategically misreporting her location. As a fair decision-making, mechanisms should be designed so that no particular group of agents can get a larger benefit by misreporting their locations. A mechanism is called group strategy-proof if no subset of agents can form a group such that every member of the group can increase her benefit by misreporting her location jointly with the rest of the group. For a given mechanism, a point in the space is called a candidate if it can be output as the location of the facility by the mechanism for some set of locations reported by agents. In this paper, we consider the case where a given space is a tree metric, and characterize the group strategy-proof mechanisms in terms of distribution of all candidates in the tree metric. We prove that there exists a group strategy-proof mechanism in the tree metric if and only if the tree has a point to which every candidate has the same distance.

Publication
IEICE TRANSACTIONS on Information Vol.E99-D No.3 pp.615-623
Publication Date
2016/03/01
Publicized
2015/12/16
Online ISSN
1745-1361
DOI
10.1587/transinf.2015FCP0008
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
Category

Authors

Morito OOMINE
  Kyoto University
Hiroshi NAGAMOCHI
  Kyoto University

Keyword