Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location
Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location
复制标题
OSP机制的近似保证：以机器调度和设施选址为例
DOI：
10.1007/s00453-020-00771-x
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Ferraioli D
中科院分区：
文献类型：
--
作者：
Ferraioli D
明显的防御性(OSP)是一个有吸引力的概念，因为它允许即使在非完全理性的代理人存在的情况下也保持激励兼容性，即那些与或有推理作斗争的人(Li in Am Econ Rev 107(11)：3257-3287,2017)。然而，它已经被证明施加了一些限制，例如，没有任何OSP机制可以返回稳定的匹配(Ashlagi和Gonczarowski在J Econ Theology 177：405-425,2018)。在这里，我们通过考察OSP机制对该领域典型的基本优化问题的近似保证，即机器调度和设施选址，来深化对OSP机制局限性的研究。我们证明了OSP机制的近似保证的一些界，这些界表明OSP机制可以付出很大的代价。然而，相当令人惊讶的是，我们证明了OSP机制在使用监控时可以返回最优解决方案--这是一种新的机制设计范式，它引入了对代理声明的温和审查(Kovács等人)。在葡萄酒中：9470：398-412,2015)。
Obvious strategyproofness (OSP) is an appealing concept as it allows to maintain incentive compatibility even in the presence of agents that are not fully rational, i.e., those who struggle with contingent reasoning (Li in Am Econ Rev 107(11):3257–3287, 2017). However, it has been shown to impose some limitations, e.g., no OSP mechanism can return a stable matching (Ashlagi and Gonczarowski in J Econ Theory 177:405–425, 2018). We here deepen the study of the limitations of OSP mechanisms by looking at their approximation guarantees for basic optimization problems paradigmatic of the area, i.e., machine scheduling and facility location. We prove a number of bounds on the approximation guarantee of OSP mechanisms, which show that OSP can come at a significant cost. However, rather surprisingly, we prove that OSP mechanisms can return optimal solutions when they use monitoring—a novel mechanism design paradigm that introduces a mild level of scrutiny on agents’ declarations (Kovács et al. in WINE 9470:398–412, 2015).
登录
查看更多内容
集合系统的自动最优 OSP 机制 - 小域的情况
DOI：
--
发表时间：
2019
期刊：
Workshop on Internet and Network Economics
影响因子：
--
作者：
Diodato Ferraioli;Adrian Meier;P. Penna;Carmine Ventre
通讯作者：
Carmine Ventre
明显的优势和随机的优先级
DOI：
--
发表时间：
2019
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
M. Pycia;Peter Troyan
通讯作者：
Peter Troyan
DOI：
--
发表时间：
2018
期刊：
Games Econ. Behav.
影响因子：
--
作者：
Andrew Mackenzie
通讯作者：
Andrew Mackenzie
无需付款即可安排
影响因子：
0.5
作者：
E. Koutsoupias
通讯作者：
E. Koutsoupias
DOI：
--
发表时间：
2018
期刊：
International Joint Conference on Artificial Intelligence
影响因子：
--
作者：
Diodato Ferraioli;Carmine Ventre
通讯作者：
Carmine Ventre