TY - GEN
T1 - SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location
AU - Okada, Nodoka
AU - Todo, Taiki
AU - Yokoo, Makoto
N1 - Funding Information:
Acknowledgments. This work is partially supported by JSPS KAKENHI Grants JP17H00761 and JP17H04695, and JST SICORP JPMJSC1607. The authors thank Ilan Nehama and Yuho Wada for their helpful comments and discussions. All errors are our own.
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85076402663&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85076402663&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-33792-6_20
DO - 10.1007/978-3-030-33792-6_20
M3 - Conference contribution
AN - SCOPUS:85076402663
SN - 9783030337919
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 321
EP - 337
BT - PRIMA 2019
A2 - Baldoni, Matteo
A2 - Dastani, Mehdi
A2 - Liao, Beishui
A2 - Sakurai, Yuko
A2 - Zalila Wenkstern, Rym
PB - Springer
T2 - 22nd International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2019
Y2 - 28 October 2019 through 31 October 2019
ER -