In Which Matching Markets Do Costly Compatibility Inspections Lead to a Deadlock?

References

• Allon G, Bassamboo A, Cil EB (2012) Large-scale service marketplaces: The role of the moderating firm. Management Sci. 58(10):1854–1872.Link, Google Scholar
• Arnosti N (2023) Lottery design for school choice. Management Sci. 69(1):244–259.Link, Google Scholar
• Arnosti N, Johari R, Kanoria Y (2021) Managing congestion in matching markets. Manufacturing Service Oper. Management 23(3):620–636.Link, Google Scholar
• Aronson J, Frieze A, Pittel BG (1998) Maximum matchings in sparse random graphs: Karp–Sipser revisited. Random Structures Algorithms 12(2):111–177.Crossref, Google Scholar
• Ashlagi I, Nikzad A (2020) What matters in school choice tie-breaking? How competition guides design. J. Econom. Theory 190:105120.Crossref, Google Scholar
• Ashlagi I, Shi P (2014) Improving community cohesion in school choice via correlated-lottery implementation. Oper. Res. 62(6):1247–1264.Link, Google Scholar
• Ashlagi I, Kanoria Y, Leshno JD (2017) Unbalanced random matching markets: The stark effect of competition. J. Political Econom. 125(1):69–98.Crossref, Google Scholar
• Ashlagi I, Braverman M, Kanoria Y, Shi P (2020) Clearing matching markets efficiently: Informative signals and match recommendations. Management Sci. 66(5):2163–2193.Link, Google Scholar
• Athreya KB, Ney PE (2004) Branching Processes (Courier Corporation, Chelmsford, MA).Google Scholar
• Brown A (2020) Nearly Half of us Adults Say Dating Has Gotten Harder for Most People in the Last 10 Years (Pew Research Center, Washington, DC).Google Scholar
• Coles P, Kushnir A, Niederle M (2013) Preference signaling in matching markets. Amer. Econom. J.: Microeconomics 5(2):99–134.Crossref, Google Scholar
• Filippas A, Horton J, Parasurama P, Urraca D (2024) Costly capacity signaling increases matching efficiency: Evidence from a field experiment. Proc. 25th ACM Conf. Econom. Comput., 414–415.Google Scholar
• Fradkin A (2015) Search frictions and the design of online marketplaces. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Freeman WT, Pasztor EC, Carmichael OT (2000) Learning low-level vision. Internat. J. Comput. Vision 40(1):25–47.Crossref, Google Scholar
• Frey BJ, MacKay DJ (1997) A revolution: Belief propagation in graphs with cycles. Advances in Neural Information Processing Systems, 479–485.Google Scholar
• Friston KJ, Parr T, de Vries B (2017) The graphical brain: Belief propagation and active inference. Network Neurosci. 1(4):381–414.Crossref, Google Scholar
• Ghosh A, Kleinberg R (2016) Optimal contest design for simple agents. ACM Trans. Econom. Comput. 4(4):1–41.Crossref, Google Scholar
• Grossman SJ, Stiglitz JE (1980) On the impossibility of informationally efficient markets. Amer. Econom. Rev. 70(3):393–408.Google Scholar
• Halaburda H, Jan Piskorski M, Yıldırım P (2018) Competing by restricting choice: The case of matching platforms. Management Sci. 64(8):3574–3594.Link, Google Scholar
• Harris TE (1963) The Theory of Branching Processes, vol. 6 (Springer, Berlin).Crossref, Google Scholar
• Hatfield JW, Milgrom PR (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913–935.Crossref, Google Scholar
• Hatfield JW, Kojima F, Kominers SD (2026) Strategy-proofness, investment efficiency, and marginal returns: An equivalence. Eur. Econom. Rev. 105256. Google Scholar
• Horton JJ (2019) Buyer uncertainty about seller capacity: Causes, consequences, and a partial solution. Management Sci. 65(8):3518–3540.Link, Google Scholar
• Horton JJ, Johari R, Kircher P (2021) Cheap talk messages for market design: Theory and evidence from a labor market with directed search. Technical report, National Bureau of Economic Research, Cambridge, MA.Google Scholar
• Immorlica N, Leshno JD, Lo IY, Lucier BJ (2020) Information acquisition in matching markets: The role of price discovery. Preprint, submitted November 23, https://dx.doi.org/10.2139/ssrn.3705049.Google Scholar
• Immorlica N, Lucier B, Manshadi V, Wei A (2021) Designing approximately optimal search on matching platforms. Proc. 22nd ACM Conf. Econom. Comput., 632–633.Google Scholar
• Kanoria Y, Saban D (2021) Facilitating the search for partners on matching platforms. Management Sci. 67(10):5990–6029.Link, Google Scholar
• MacKay DJ, Neal RM (1996) Near shannon limit performance of low density parity check codes. Electronic Lett. 32(18):1645–1646.Crossref, Google Scholar
• Mezard M, Montanari A (2009) Information, Physics, and Computation (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Mézard M, Parisi G, Zecchina R (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297(5582):812–815.Crossref, Google Scholar
• Pakzad-Hurson B (2025) Crowdsourcing and optimal market design. Rev. Econom. Stat. 1–45. Google Scholar
• Pearl J (1986) Fusion, propagation, and structuring in belief networks. Artificial Intelligence 29(3):241–288.Crossref, Google Scholar
• Pearl J (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (Morgan Kauffmann Publishers).Google Scholar
• Peski M (2017) Large roommate problem with non-transferable random utility. J. Econom. Theory 168:432–471.Crossref, Google Scholar
• Peski M (2020) Tractable model of dynamic many-to-many matching. Amer. Econom. J.: Microeconomics. 14(2):1–43.Google Scholar
• Quint T (1994) The lattice of core (sub) matchings in a two-sided matching market. Math. Oper. Res. 19(3):603–617.Link, Google Scholar
• Richardson T, Urbanke R (2008) Modern Coding Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Roth AE, Xing X (1994) Jumping the gun: Imperfections and institutions related to the timing of market transactions. Amer. Econom. Rev. 992–1044.Google Scholar
• Roth AE, Xing X (1997) Turnaround time and bottlenecks in market clearing: Decentralized matching in the market for clinical psychologists. J. Political Econom. 105(2):284–329.Crossref, Google Scholar
• Sheremeta RM (2011) Contest design: An experimental investigation. Econom. Inquiry 49(2):573–590.Crossref, Google Scholar
• Shi P (2022) Optimal matchmaking strategy in two-sided marketplaces. Management Sci. 69(3):1323–1340.Link, Google Scholar
• Simon HA (1955) A behavioral model of rational choice. Quart. J. Econom. 69(1):99–118.Crossref, Google Scholar
• Yedidia JS, Freeman WT, Weiss Y (2005) Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. Inform. Theory 51(7):2282–2312.Crossref, Google Scholar
• Zheng H, Li D, Hou W (2011) Task design, motivation, and participation in crowdsourcing contests. Internat. J. Electronic Commerce 15(4):57–88.Crossref, Google Scholar