JSAI2019

Presentation information

General Session

General Session » [GS] J-1 Fundamental AI, theory

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

Wed. Jun 5, 2019 9:00 AM - 10:20 AM Room E (301A Medium meeting room)

Chair:Takahisa Toda Reviewer:Yoichi Sasaki

9:40 AM - 10:00 AM

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

〇Nodoka Okada1, Yuho Wada1, Taiki Todo1, Makoto Yokoo1 (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.