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

Morito OOMINE; Hiroshi NAGAMOCHI

doi:10.1587/transinf.2015FCP0008

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

Morito OOMINE, Hiroshi NAGAMOCHI

Full Text Views

0

Share
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

mechanisms, group strategy-proof, facility location games, trees

Cite this

Copy

Morito OOMINE, Hiroshi NAGAMOCHI, "Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees" in IEICE TRANSACTIONS on Information, vol. E99-D, no. 3, pp. 615-623, March 2016, doi: 10.1587/transinf.2015FCP0008.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015FCP0008/_p

Copy

@ARTICLE{e99-d_3_615,
author={Morito OOMINE, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees},
year={2016},
volume={E99-D},
number={3},
pages={615-623},
abstract={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.},
keywords={},
doi={10.1587/transinf.2015FCP0008},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees
T2 - IEICE TRANSACTIONS on Information
SP - 615
EP - 623
AU - Morito OOMINE
AU - Hiroshi NAGAMOCHI
PY - 2016
DO - 10.1587/transinf.2015FCP0008
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2016
AB - 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.
ER -