Manipulation-resistant false-name-proof facility location mechanisms for complex graphs
Manipulation-resistant false-name-proof facility location mechanisms for complex graphs
复制标题
复杂图的防篡改防伪名设施定位机制
DOI：
10.1007/s10458-021-09535-5
复制
发表时间：
2022
影响因子：
1.9
通讯作者：
Makoto Yokoo
中科院分区：
文献类型：
--
作者：
Ilan Nehama;Taiki Todo;Makoto Yokoo
在许多现实生活场景中，一组代理需要就共同的操作达成一致，例如，在公共设施的位置上，虽然他们的偏好之间存在一定的一致性，例如，所有偏好都是从公共度量空间导出的。设施选址问题模型这样的情况下，它是一个很好的研究问题，在社会选择。我们研究机制的设施位置上的未加权无向图，是抵抗操纵（策略证明，防御，和虚假名称证明）的个人和联盟一方面和匿名和有效的（帕累托最优）。我们定义了一个新的家庭的图，线图，并显示了这些图，满足所有这些所需的属性的一般设施定位机制。该机制也可以在多项式时间内计算，并且它可以根据某个预定义的顺序等效地被定义为第一帕累托最优位置。我们的主要结果，线图家庭和我们提出的机制，统一了所有的作品在文献中的虚假名称证明设施位置离散图，包括初步（未发表）的作品，我们知道。特别是，我们显示的机制，为所有的图，最多五个顶点，离散树，bicliques，和团树图。最后，我们讨论了一些推广和限制，我们的结果设施选址问题的其他结构：加权图，大离散圈，无限图;和设施选址问题的无限社会。
In many real-life scenarios, a group of agents needs to agree on a common action, e.g., on a location for a public facility, while there is some consistency between their preferences, e.g., all preferences are derived from a common metric space. Thefacility locationproblem models such scenarios and it is a well-studied problem in social choice. We study mechanisms for facility location on unweighted undirected graphs that are resistant to manipulations (strategy-proof,abstention-proof, andfalse-name-proof) by both individuals and coalitions on one hand and anonymous and efficient (Pareto-optimal) on the other. We define a new family of graphs,-line graphs, and show a general facility location mechanism for these graphs that satisfies all these desired properties. This mechanism can also be computed in polynomial time and it can equivalently be defined as the first Pareto-optimal location according to some predefined order. Our main result, the-line graphs family and the mechanism we present for it, unifies all works in the literature of false-name-proof facility location on discrete graphs including the preliminary (unpublished) works we are aware of. In particular, we show mechanisms forall graphs of at most five vertices,discrete trees,bicliques, andclique tree graphs. Finally, we discuss some generalizations and limitations of our result for facility location problems on other structures: Weighted graphs, large discrete cycles, infinite graphs; and for facility location problems concerning infinite societies.
登录
查看更多内容
直接选举、一致同意和幽灵选民
DOI：
10.2307/2296962
发表时间：
1983
期刊：
The Review of Economic Studies
影响因子：
--
作者：
Kim C. Border;J. Jordan
通讯作者：
J. Jordan
防假名投票的成本超过两种选择
影响因子：
0.6
作者：
Liad Wagman;Vincent Conitzer
通讯作者：
Vincent Conitzer
基于SAT的防伪设施定位自动化机制设计
DOI：
10.1007/978-3-030-33792-6_20
发表时间：
2019
期刊：
Proceedings of PRIMA-2019
影响因子：
--
作者：
Okada Nodoka;Todo Taiki;Yokoo Makoto
通讯作者：
Yokoo Makoto
加权投票游戏中的假名操纵：实证和理论分析
影响因子：
2.8
作者：
Ramoni O. Lasisi;V. Allan
通讯作者：
V. Allan
使用内存测试将用户限制为一个帐户
DOI：
10.1007/978-3-642-15237-5_5
发表时间：
2008
期刊：
ArXiv
影响因子：
--
作者：
Vincent Conitzer
通讯作者：
Vincent Conitzer