{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:18Z","timestamp":1750220658250,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,11,30]],"date-time":"2019-11-30T00:00:00Z","timestamp":1575072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16H06931, JP16K16005, JP18K18004"],"award-info":[{"award-number":["JP16H06931, JP16K16005, JP18K18004"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR17U7, JPMJCR14D2"],"award-info":[{"award-number":["JPMJPR17U7, JPMJCR14D2"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2019,11,30]]},"abstract":"<jats:p>We study a decentralized matching market in which firms sequentially make offers to potential workers. For each offer, the worker can choose \u201caccept\u201d or \u201creject,\u201d 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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3373717","type":"journal-article","created":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T16:15:03Z","timestamp":1585930503000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Subgame Perfect Equilibria of Sequential Matching Games"],"prefix":"10.1145","volume":"7","author":[{"given":"Yasushi","family":"Kawase","sequence":"first","affiliation":[{"name":"Tokyo Institute of Technology and RIKEN AIP Center, Meguro-ku, Tokyo, Japan"}]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[{"name":"Osaka University and RIKEN AIP Center, Yamadaoka, Suita, Osaka, Japan"}]},{"given":"Yu","family":"Yokoi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Hitotsubashi, Chiyoda-ku, Tokyo, Japan"}]}],"member":"320","published-online":{"date-parts":[[2020,1,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1257\/000282803322157061"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.99.5.1954"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1997.2447"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0743"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2004.06.013"},{"volume-title":"Proceedings of the International Symposium on Algorithmic Game Theory. 153--166","author":"Avni G.","key":"e_1_2_1_6_1","unstructured":"G. Avni , T. A. Henzinger , and O. Kupferman . 2016. Dynamic resource allocation games . In Proceedings of the International Symposium on Algorithmic Game Theory. 153--166 . G. Avni, T. A. Henzinger, and O. Kupferman. 2016. Dynamic resource allocation games. In Proceedings of the International Symposium on Algorithmic Game Theory. 153--166."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.05.009"},{"volume-title":"Proceedings of the 19th ACM Conference on Economics and Computation. 251--268","author":"Dur U.","key":"e_1_2_1_8_1","unstructured":"U. Dur , T. Mennle , and S. Seuken . 2018. First choice maximizing school choice mechanisms . In Proceedings of the 19th ACM Conference on Economics and Computation. 251--268 . U. Dur, T. Mennle, and S. Seuken. 2018. First choice maximizing school choice mechanisms. In Proceedings of the 19th ACM Conference on Economics and Computation. 251--268."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1765(00)00263-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2006.03.006"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90074-5"},{"key":"e_1_2_1_13_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York New York.  M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman New York New York."},{"key":"e_1_2_1_14_1","unstructured":"D. Gusfield and R. W. Irving. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Boston.  D. Gusfield and R. W. Irving. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press Boston."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00182-009-0218-x"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Y. Kawase and K. Bando. 2019. Subgame perfect equilibria under the deferred acceptance algorithm. Available at SSRN https:\/\/ssrn.com\/abstract&equals;3235068.  Y. Kawase and K. Bando. 2019. Subgame perfect equilibria under the deferred acceptance algorithm. Available at SSRN https:\/\/ssrn.com\/abstract&equals;3235068.","DOI":"10.2139\/ssrn.3235068"},{"volume-title":"Proceedings of the 19th ACM Conference on Economics and Computation. 131--148","author":"Kawase Y.","key":"e_1_2_1_17_1","unstructured":"Y. Kawase , Y. Yamaguchi , and Y. Yokoi . 2018. Computing a subgame perfect equilibrium of a sequential matching game . In Proceedings of the 19th ACM Conference on Economics and Computation. 131--148 . Y. Kawase, Y. Yamaguchi, and Y. Yokoi. 2018. Computing a subgame perfect equilibrium of a sequential matching game. In Proceedings of the 19th ACM Conference on Economics and Computation. 131--148."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1162\/qjec.2010.125.3.1297"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"A. Kloosterman and P. Troyan. 2016. Efficient and Essentially Stable Assignments. Mimeo.  A. Kloosterman and P. Troyan. 2016. Efficient and Essentially Stable Assignments. Mimeo.","DOI":"10.2139\/ssrn.2812217"},{"volume-title":"Marriage Stables","author":"Knuth D. E.","key":"e_1_2_1_20_1","unstructured":"D. E. Knuth . 1976. Marriage Stables . Montr\u00e9al : Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al. D. E. Knuth. 1976. Marriage Stables. Montr\u00e9al: Les Presses de l\u2019Universit\u00e9 de Montr\u00e9al."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090242"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"D. F. Manlove. 2013. Algorithmics of Matching under Preferences. World Scientific.  D. F. Manlove. 2013. Algorithmics of Matching under Preferences. World Scientific.","DOI":"10.1142\/8591"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01934199"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/362619.362631"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"N. Nisan T. Roughgarden \u00c9. Tardos and V. V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press Cambridge.  N. Nisan T. Roughgarden \u00c9. Tardos and V. V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press Cambridge.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2007.12.005"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1086\/261272"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913160"},{"key":"e_1_2_1_29_1","volume-title":"Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis","author":"Roth A. E.","year":"1991","unstructured":"A. E. Roth and M. Sotomayor . 1991 . Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis . Cambridge University Press , Cambridge . A. E. Roth and M. Sotomayor. 1991. Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01210572"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0272-x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.10.002"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118785.3119249"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373717","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373717","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3373717","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:34Z","timestamp":1750197754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3373717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,30]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,11,30]]}},"alternative-id":["10.1145\/3373717"],"URL":"https:\/\/doi.org\/10.1145\/3373717","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2019,11,30]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}