Subgame perfect equilibria of sequential matching games

Yasushi Kawase, Yutaro Yamaguchi, Yu Yokoi

研究成果: ジャーナルへの寄稿学術誌査読

2 被引用数 (Scopus)


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.

ジャーナルACM Transactions on Economics and Computation
出版ステータス出版済み - 1月 27 2020

!!!All Science Journal Classification (ASJC) codes

  • コンピュータ サイエンス(その他)
  • 統計学および確率
  • 経済学、計量経済学
  • マーケティング
  • 計算数学


「Subgame perfect equilibria of sequential matching games」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。