Computing a Subgame Perfect Equilibrium of a Sequential Matching Game
Computing a Subgame Perfect Equilibrium of a Sequential Matching Game
复制标题
计算顺序匹配博弈的子博弈完美均衡
DOI：
10.1145/3219166.3219200
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Yokoi Yu
中科院分区：
文献类型：
--
作者：
Kawase Yasushi;Yamaguchi Yutaro;Yokoi Yu
我们研究了一个分散的匹配市场，在这个市场中，每个公司都顺序地向潜在的工人提供工作机会。对于每一份工作，工人可以选择“接受”或“拒绝”，但这个决定是不可撤销的。接受录用保证了她在公司的工作，但这也可能会消除未来其他公司提供更好录取机会的机会。我们将这个市场描述为工人们玩的完全信息泛型博弈。这个博弈的每个实例都有一个唯一的子博弈完美均衡(SPE)，它不一定会导致稳定的匹配，并且具有一些令人困惑的性质。我们的目标是确定计算SPE的复杂性，或者更准确地说，决定SPE是否接受每个报价。我们表明，这个问题的可处理性根据与每个公司和工人相关的潜在要约的数量而发生巨大变化。如果每家公司最多向两名工人提出报价(或者每个工人最多收到两家公司的报价)，那么问题就可以通过延期接受算法的一个变体有效地解决。相比之下，问题是PSPACE-很难，即使公司和工人都与至多三份工作有关。
We study a decentralized matching market in which each firm sequentially makes 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. Our aim is to establish the complexity of computing the SPE, or more precisely, deciding whether each offer is accepted in the SPE. We show that the tractability of this problem drastically changes according to the number of potential offers related to each firm and worker. If each firm makes offers to at most two workers (or each worker receives offers from at most two firms), then the problem is efficiently solved by a variant of the deferred acceptance algorithm. In contrast, the problem is PSPACE-hard even if both firms and workers are related to at most three offers.
登录
查看更多内容
婚姻问题中稳定匹配的子博弈完美实现
影响因子：
0.9
作者：
Sang;Quan Wen
通讯作者：
Quan Wen
DOI：
10.1006/game.1999.0743
发表时间：
2000
期刊：
Games Econ. Behav.
影响因子：
--
作者：
José Alcalde;Antonio Romero
通讯作者：
Antonio Romero
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
动态资源分配博弈
DOI：
10.1007/978-3-662-53354-3_13
发表时间：
2016
期刊：
--
影响因子：
--
作者：
Guy Avni;T. Henzinger;O. Kupferman
通讯作者：
O. Kupferman