[2E1-J-1] Fundamental AI, theory: quantum computing and search

[2E1-J-1-03] Mechanism Design for Facility Location via SAT Solving

〇Nodoka Okada¹, Yuho Wada¹, Taiki Todo¹, Makoto Yokoo¹ (1. Univ. of Kyushu)

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

We consider the problem of locating one facility on discrete grids with variable populations. An agent's preference is single-peaked or single-dipped, depending on whether she wants to access the facility (a public good), or be far from it (a public bad). In this paper, we clarify whether or not there exists a mechanism which satisfies both false-name-proofness and Pareto efficiency on a discrete grid by using SAT solver. Concretely, we reveal the existense about the appropreate mechanism on a grid which size is less than 3×3, further the impossibility besides those grids. Moreover, we also clarify the impossibility about ontoness on grids which size is over 2×3.