Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2015-001 (March 30, 2015)
Characterizing GSP Mechanisms to Obnoxious Facility Game in Trees via Output Locations
by Morito Oomine and Hiroshi Nagamochi
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
every two candidates have the distance.