Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees
Characterizing Output Locations of GSP Mechanisms to Obnoxious Facility Game in Trees
复制标题
DOI：
10.1587/transinf.2015fcp0008
复制
发表时间：
2016-03
期刊：
影响因子：
--
通讯作者：
Morito Oomine;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Morito Oomine;H. Nagamochi
在显而易见的设施游戏中，总结一个带有一个空间中的代理商的代理商，我们希望设计一种机制，一种决策程序，该程序根据代理商报告的位置确定不良设施的位置，我们不知道该位置是否知道代理报告的位置是该设施的位置中的代理，每个代理的益处都定义为距设施的位置到存在机构的位置的距离。代理商被告知该机制如何利用代理商报告的位置，以便在某些代理商报告其位置之前，可以通过策略性地将其位置作为公平的决策来操纵该设施的决定。 ，应设计机制，以便没有特定的代理可以通过误导其位置来获得更大的好处通过与给定机构的其余部分共同报告她的位置，如果可以通过机械设备作为设施的某些位置，则称其为候选人论文，我们考虑了给定空间是树准的情况，并且在树准中所有候选者的分布方面表征了群体策略机制。当且仅当树具有每个候选人具有相同距离的点时。
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.