Subgame Perfect Equilibria of Sequential Matching Games
Subgame Perfect Equilibria of Sequential Matching Games
复制标题
顺序匹配博弈的子博弈完美均衡
DOI：
10.1145/3373717
复制
发表时间：
2020
影响因子：
1.2
通讯作者：
Yokoi Yu
中科院分区：
文献类型：
--
作者：
Kawase Yasushi;Yamaguchi Yutaro;Yokoi Yu
我们研究了一个分散的匹配市场中，公司顺序提供给潜在的工人。对于每个报价，工人可以选择“接受”或“拒绝”，但该决定是不可撤销的。接受一份工作保证了她在公司的工作，但这也可能使她失去将来从其他公司获得更好工作的机会。我们将这个市场描述为工人们的完全信息扩展型博弈。这个博弈的每个实例都有一个唯一的子博弈完美均衡（SPE），它不一定导致稳定的匹配，并且具有一些令人困惑的性质。如果每个公司向最多两个工人提供报价，或者每个工人从最多两个公司获得报价，则计算是容易的。相反，即使公司和工人都与最多三个报价有关，它也是PSPACE困难的。我们还研究这个匹配市场的工程方面。结果表明，对于任何偏好配置文件，我们可以设计一个公司的报价时间表，使工人最优的稳定匹配实现在SPE。
We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose “accept” or “reject,” but the decision is irrevocable. The acceptance of an offer guarantees her job at the firm, but it may also eliminate chances of better offers from other firms in the future. We formulate this market as a perfect-information extensive-form game played by the workers. Each instance of this game has a unique subgame perfect equilibrium (SPE), which does not necessarily lead to a stable matching and has some perplexing properties.We show a dichotomy result that characterizes the complexity of computing the SPE. The computation is tractable if each firm makes offers to at most two workers or each worker receives offers from at most two firms. In contrast, it is PSPACE-hard even if both firms and workers are related to at most three offers. We also study engineering aspects of this matching market. It is shown that, for any preference profile, we can design an offering schedule of firms so that the worker-optimal stable matching is realized in the SPE.
登录
查看更多内容
婚姻问题中稳定匹配的子博弈完美实现
影响因子：
0.9
作者：
Sang;Quan Wen
通讯作者：
Quan Wen
DOI：
10.1006/game.1999.0743
发表时间：
2000
期刊：
Games Econ. Behav.
影响因子：
--
作者：
José Alcalde;Antonio Romero
通讯作者：
Antonio Romero
第一选择——最大化择校机制
DOI：
--
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Timo Mennle;Sven Seuken
通讯作者：
Sven Seuken
DOI：
10.1016/j.geb.2014.05.009
发表时间：
2014-09
期刊：
Games Econ. Behav.
影响因子：
--
作者：
Keisuke Bando
通讯作者：
Keisuke Bando
去中心化随机匹配市场的激励
DOI：
10.1016/j.geb.2007.12.005
发表时间：
2008
期刊：
Games Econ. Behav.
影响因子：
--
作者：
J. Pais
通讯作者：
J. Pais