SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location

Nodoka Okada, Taiki Todo, Makoto Yokoo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)


In the literature of mechanism design, market mechanisms have been developed by professionals based on their experience. The concept of automated mechanism design (AMD), initiated by Sandholm (2002), is a ground-breaking computer-aided framework to develop market mechanisms. In this paper, we apply a very recent AMD approach based on Boolean Satisfiability (SAT) to the mechanism design of false-name-proof facility location. We first provide a general theoretical characteristic of false-name-proof mechanisms, which enables a quite compact representation of target mechanisms. Our approach successfully reproduces several known results in the literature on false-name-proof facility locations over discrete structures. Furthermore, some unknown mechanisms are discovered for locating a public good on a 2-by-2 grid, and an impossibility result is revealed for locating a public bad, with an additional mild assumption, on a 2-by-3 grid. Finally, we demonstrate the extendability of our approach, by providing a new false-name-proof mechanism for a slightly modified problem of locating a public good.

Original languageEnglish
Title of host publicationPRIMA 2019
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 22nd International Conference, Proceedings
EditorsMatteo Baldoni, Mehdi Dastani, Beishui Liao, Yuko Sakurai, Rym Zalila Wenkstern
Number of pages17
ISBN (Print)9783030337919
Publication statusPublished - 2019
Event22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019 - Turin, Italy
Duration: Oct 28 2019Oct 31 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11873 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location'. Together they form a unique fingerprint.

Cite this