Manipulation-resistant false-name-proof facility location mechanisms for complex graphs

Ilan Nehama, Taiki Todo, Makoto Yokoo

研究成果: ジャーナルへの寄稿学術誌査読

3 被引用数 (Scopus)


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. The facility location problem 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, and false-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, ZV-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 ZV-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 for all graphs of at most five vertices, discrete trees, bicliques, and clique 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.

ジャーナルAutonomous Agents and Multi-Agent Systems
出版ステータス出版済み - 4月 2022

!!!All Science Journal Classification (ASJC) codes

  • 人工知能


「Manipulation-resistant false-name-proof facility location mechanisms for complex graphs」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。