Characterizing Mechanisms in Obnoxious Facility Game
Characterizing Mechanisms in Obnoxious Facility Game
复制标题
DOI：
10.1007/978-3-642-31770-5_27
复制
发表时间：
2012-08
期刊：
影响因子：
--
通讯作者：
Ken Ibara;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Ken Ibara;H. Nagamochi
在本文中，我们研究的（组）防策略的确定性机制在讨厌的设施游戏。在这个游戏中，给定一组策略代理在一个度量，我们设计了一个机制，输出的设施的位置在度量的基础上的代理报告自己的位置。代理人的利益是她的位置和设施之间的距离，社会效益是所有代理人的总效益。智能体可能会试图通过策略性地误报她的位置来操纵该机制的输出。我们希望设计一种防策略的机制（即，没有代理可以通过错误报告获得她的利益）或组策略防护（即，不存在代理人的联盟，使得联盟中的每个成员都可以通过误报同时获益），而社会效益将最大化。在本文中，我们首先证明，在线度量，没有策略证明机制，使候选人（位置输出的机制，一些报告的位置）的数量超过两个。接下来，我们完全描述（组）策略证明机制，在一般度量中正好有两个候选人，并表明在任何度量中存在4-近似组策略证明机制。
In this paper, we study the (group) strategy-proofness of deterministic mechanisms in the obnoxious facility game. In this game, given a set of strategic agents in a metric, we design a mechanism that outputs the location of a facility in the metric based on the locations of the agents reported by themselves. The benefit of an agent is the distance between her location and the facility and the social benefit is the total benefits of all agents. An agent may try to manipulate outputs by the mechanism by misreporting strategically her location. We wish to design a mechanism that isstrategy-proof(i.e., no agent can gain her benefit by misreporting) orgroup strategy-proof(i.e., there is no coalition of agents such that each member in the coalition can simultaneously gain benefit by misreporting), while the social benefit will be maximized. In this paper, we first prove that, in the line metric, there is no strategy-proof mechanism such that the number of candidates (locations output by the mechanism for some reported locations) is more than two. We next completely characterize (group) strategy-proof mechanisms with exactly two candidates in the general metric and show that there exists a 4-approximation group strategy-proof mechanism in any metric.