SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location
SAT-Based Automated Mechanism Design for False-Name-Proof Facility Location
复制标题
基于SAT的防伪设施定位自动化机制设计
DOI：
10.1007/978-3-030-33792-6_20
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yokoo Makoto
中科院分区：
文献类型：
--
作者：
Okada Nodoka;Todo Taiki;Yokoo Makoto
在机制设计的文献中，市场机制是由专业人士根据他们的经验开发的。自动化机制设计（AMD）的概念，由Sandholm（2002）提出，是一个突破性的计算机辅助框架，以开发市场机制。在本文中，我们应用一个非常新的AMD方法的基础上布尔可满足性（SAT）的机制设计的假名证明设施的位置。我们首先提供了一个一般的理论特征的假名证明机制，这使得一个相当紧凑的表示目标机制。我们的方法成功地再现了几个已知的结果，在文献中的虚假名称证明设施的位置在离散结构。此外，一些未知的机制，发现在2 × 2的网格上定位一个公共产品，并揭示了一个不可能的结果，定位一个公共坏，与一个额外的温和的假设，在2 × 3的网格。最后，我们证明了我们的方法的可扩展性，通过提供一个新的假名证明机制，稍微修改的问题，定位一个公共产品。
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.
登录
查看更多内容
DOI：
10.1609/aaai.v30i1.10029
发表时间：
2016-02
期刊：
--
影响因子：
--
作者：
Akihisa Sonoda;Taiki Todo;M. Yokoo
通讯作者：
Akihisa Sonoda;Taiki Todo;M. Yokoo
DOI：
10.1016/j.mathsocsci.2016.07.001
发表时间：
2017
期刊：
Math. Soc. Sci.
影响因子：
--
作者：
Abhinaba Lahiri;H. Peters;Ton Storcken
通讯作者：
Ton Storcken
通过 SAT 求解找到策略证明的社会选择函数
DOI：
10.1613/jair.4959
发表时间：
2016
期刊：
影响因子：
--
作者：
F. Brandt;C. Geist
通讯作者：
C. Geist
稳健机构的自动化设计
DOI：
10.1609/aaai.v31i1.10574
发表时间：
2017
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Michael Albert;Vincent Conitzer;P. Stone
通讯作者：
P. Stone
通过自动化机构设计评估 Cremer-McLean 的鲁棒性
DOI：
10.1609/aaai.v29i1.9293
发表时间：
2015
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Michael Albert;Vincent Conitzer;Giuseppe Lopomo
通讯作者：
Giuseppe Lopomo