[3I1-GS-5d] エージェント：社会問題解決

[3I1-GS-5d-03] Mechanism Design for Locating a Public Bad on Grid Graphs

〇Koji Osoegawa¹, Taiki Todo¹, Makoto Yokoo¹ (1. Kyushu University)

Keywords:Mechanism Design, Facility Location, False-Name-Proofness, Pareto Efficiency

We consider the problem of locating one public bad on grid graphs. When the facility is a public bad, agents want the public bad to be located farther. In this paper, we clarify whether there exists a mechanism which is Pareto efficient and false-name-proof on grids where the size is limited to mx2. First, when m is an arbitrary odd number greater than 1, we propose a mechanism which satisfies Pareto efficiency and false-name-proofness. Second, when m is an arbitrary even number greater than 2, we prove that no such mechanism exists.