论文标题
最大变化成本的限制异质的两面性位置游戏
Constrained Heterogeneous Two-facility Location Games with Max-variant Cost
论文作者
论文摘要
在本文中，我们提出了一个约束的异质设施位置模型，其中一组替代位置对于建筑设施是可行的，并且在每个位置建造的设施数量受到限制。假设真实线上的一组代理可以从战略上报告其位置，并且每个代理商的成本都是她与她感兴趣的进一步设施的距离，我们研究了确定性机制设计，而无需花钱，用于有限的异质性两面性位置游戏。 根据代理是否具有可选的偏好，在两个设置中考虑了问题：强制设置和可选设置。在强制性的环境中，每个代理都由两个异质设施提供服务，我们为总和/最大成本目标提供了3个同一确定性群体防护机制，这也是相应的社会目标下的最佳确定性策略性机制。在每个代理商对两种设施之一或两者兼有感兴趣的可选环境中，我们提出了一种确定性的群体防护机制，其近似值最多为$ 2N+1 $，以达到总成本目标和确定性的组策略性机制，最多为9，以最大的成本目标为9。
In this paper, we propose a constrained heterogeneous facility location model where a set of alternative locations are feasible for building facilities and the number of facilities built at each location is limited. Supposing that a set of agents on the real line can strategically report their locations and each agent's cost is her distance to the further facility that she is interested in, we study deterministic mechanism design without money for constrained heterogeneous two-facility location games. Depending on whether agents have optional preference, the problem is considered in two settings: the compulsory setting and the optional setting. In the compulsory setting where each agent is served by the two heterogeneous facilities, we provide a 3-approximate deterministic group strategyproof mechanism for the sum/maximum cost objective respectively, which is also the best deterministic strategyproof mechanism under the corresponding social objective. In the optional setting where each agent can be interested in one of the two facilities or both, we propose a deterministic group strategyproof mechanism with approximation ratio of at most $2n+1$ for the sum cost objective and a deterministic group strategyproof mechanism with approximation ratio of at most 9 for the maximum cost objective.
