Subtopic Deep Dive

Matching Theory Stability
Research Guide

What is Matching Theory Stability?

Matching Theory Stability examines stable outcomes in matching markets where no pair of agents prefers each other over their current matches, primarily through game-theoretic models in bipartite and non-bipartite settings.

Research centers on the Gale-Shapley deferred acceptance algorithm and its extensions for stability in markets like hospital-resident assignments and kidney exchanges. Key works include Roth and Sotomayor's comprehensive analysis (1990, 1072 citations) and Roth's historical review of deferred acceptance (2007, 401 citations). Over 10 papers from the list address stability, strategy-proofness, and empirical designs.

Curated Papers

Key Challenges

Why It Matters

Stable matching algorithms power real-world systems including the National Resident Matching Program redesigned by Roth and Peranson, filling 20,000 physician positions annually. They enable efficient kidney exchanges and labor market assignments, reducing inefficiencies in two-sided markets (Roth and Sotomayor, 1990). Econometric applications use matching for causal evaluation, as in Heckman et al.'s kernel-based estimator (1998, 3755 citations), impacting policy design in education and organ allocation.

Key Research Challenges

Strategy-Proofness in Non-Bipartite Markets

Ensuring mechanisms prevent manipulation is harder beyond bipartite graphs, as preferences complicate stability. Roth and Sotomayor analyze game-theoretic limits in two-sided matching (1990). Empirical designs like physician markets reveal trade-offs between stability and truthfulness (Roth and Peranson).

Dynamic Stability Under Uncertainty

Markets with complementarities between applicants challenge static stability definitions. Roth and Peranson's redesign addresses position dependencies in physician matching. Kernel-matching extensions handle general conditions but require rigorous distribution theory (Heckman et al., 1998).

Fairness and Bias in Matching

Preexisting and technical biases affect stable outcomes in computerized systems. Friedman and Nissenbaum categorize biases from social institutions and technical embedding (1996, 1052 citations). Exposure fairness in rankings extends to matching visibility (Singh and Joachims, 2018).

Essential Papers

Matching As An Econometric Evaluation Estimator

James J. Heckman, Hidehiko Ichimura, Petra Todd · 1998 · The Review of Economic Studies · 3.8K citations

This paper develops the method of matching as an econometric evaluation estimator. A rigorous distribution theory for kernel-based matching is presented. The method of matching is extended to more ...

The Nucleolus of a Characteristic Function Game

David Schmeidler · 1969 · SIAM Journal on Applied Mathematics · 1.9K citations

Previous article Next article The Nucleolus of a Characteristic Function GameDavid SchmeidlerDavid Schmeidlerhttps://doi.org/10.1137/0117107PDFBibTexSections ToolsAdd to favoritesExport CitationTra...

Two-Sided Matching

Alvin E. Roth, Marilda A. Oliveira Sotomayor · 1990 · Cambridge University Press eBooks · 1.1K citations

Two-sided matching provides a model of search processes such as those between firms and workers in labor markets or between buyers and sellers in auctions. This book gives a comprehensive account o...

Bias in computer systems

Batya Friedman, Helen Nissenbaum · 1996 · ACM Transactions on Information Systems · 1.1K citations

From an analysis of actual cases, three categories of bias in computer systems have been developed: preexisting, technical, and emergent. Preexisting bias has its roots in social institutions, prac...

The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design

Alvin E. Roth, Elliott Peranson · ? · RePEc: Research Papers in Economics · 767 citations

We report on the design of the new clearinghouse adopted by the National Resident Matching Program, which annually fills approximately 20, 000 jobs for new physicians. Because the market has comple...

The Social Cost of Cheap Pseudonyms

Eric J. Friedman, Paul Resnick · 2001 · Journal of Economics & Management Strategy · 543 citations

We consider the problems of societal norms for cooperation and reputation when it is possible to obtain cheap pseudonyms, something that is becoming quite common in a wide variety of interactions o...

Fairness of Exposure in Rankings

Ashudeep Singh, Thorsten Joachims · 2018 · 532 citations

Rankings are ubiquitous in the online world today. As we have transitioned from finding books in libraries to ranking products, jobs, job applicants, opinions and potential romantic partners, there...

Reading Guide

Foundational Papers

Read Roth and Sotomayor (1990) first for two-sided theory; Schmeidler (1969) for nucleolus in cooperative stability; Heckman et al. (1998) for econometric applications.

Recent Advances

Roth (2007) on deferred acceptance history and practice; Roth and Peranson on physician market redesign; Brandt et al. (2016) handbook for computational aspects.

Core Methods

Gale-Shapley deferred acceptance; kernel-based matching estimators; nucleolus computation; stability verification in bipartite graphs.

How PapersFlow Helps You Research Matching Theory Stability

Discover & Search

Research Agent uses searchPapers and citationGraph to map stability literature from Roth and Sotomayor's 'Two-Sided Matching' (1990), revealing 1072 citations and connections to Heckman et al. (1998). exaSearch uncovers empirical extensions like kidney exchanges; findSimilarPapers links to Roth's deferred acceptance review (2007).

Analyze & Verify

Analysis Agent applies readPaperContent to extract Gale-Shapley proofs from Roth and Sotomayor (1990), then verifyResponse with CoVe checks stability claims against Schmeidler's nucleolus (1969). runPythonAnalysis simulates kernel-matching distributions from Heckman et al. (1998) using NumPy/pandas, with GRADE scoring empirical validity in Roth and Peranson's redesign.

Synthesize & Write

Synthesis Agent detects gaps in strategy-proofness across non-bipartite markets, flagging contradictions between Roth (2007) and Friedman (1996) bias categories. Writing Agent uses latexEditText and latexSyncCitations to draft proofs, latexCompile for market diagrams, and exportMermaid for stability flowcharts.

Use Cases

"Simulate stability in hospital-resident matching with incomplete preferences."

Research Agent → searchPapers('deferred acceptance') → Analysis Agent → runPythonAnalysis (Gale-Shapley NumPy sim) → matplotlib plot of stable vs unstable outcomes.

"Draft LaTeX proof of nucleolus in matching games."

Research Agent → citationGraph('Schmeidler 1969') → Synthesis Agent → gap detection → Writing Agent → latexEditText + latexSyncCitations('Roth 1990') → latexCompile PDF.

"Find code for kidney exchange stability algorithms."

Research Agent → paperExtractUrls('Roth kidney') → Code Discovery → paperFindGithubRepo → githubRepoInspect → exportCsv of repos with stable matching implementations.

Automated Workflows

Deep Research workflow conducts systematic review of 50+ stability papers, chaining searchPapers → citationGraph → structured report on deferred acceptance evolutions from Gale-Shapley to Roth (2007). DeepScan applies 7-step analysis with CoVe checkpoints to verify Heckman et al. (1998) econometric matching. Theorizer generates extensions of nucleolus stability from Schmeidler (1969) literature.

Try Doxa for Matching Theory Stability Research

Frequently Asked Questions

What defines a stable matching?

A matching is stable if no blocking pair exists where both agents prefer each other over assigned partners (Roth and Sotomayor, 1990).

What are main methods in matching stability?

Deferred acceptance (Gale-Shapley) computes stable outcomes; kernel-matching evaluates causally (Heckman et al., 1998); nucleolus imputes values in cooperative games (Schmeidler, 1969).

What are key papers?

Roth and Sotomayor (1990, 1072 citations) on two-sided theory; Heckman et al. (1998, 3755 citations) on econometrics; Roth (2007, 401 citations) on deferred acceptance practice.

What open problems exist?

Strategy-proofness in dynamic non-bipartite markets with biases; fairness in computerized redesigns (Roth and Peranson; Friedman and Nissenbaum, 1996).