Stable Matchings with Choice Correspondences Under Acyclicity

Mihir Bhattacharya; Ojasvi Khare; Varun Bansal

arxiv: 2603.23038 · v5 · pith:Z2YBKC2Nnew · submitted 2026-03-24 · 💰 econ.TH

Stable Matchings with Choice Correspondences Under Acyclicity

Varun Bansal , Mihir Bhattacharya , Ojasvi Khare This is my paper

Pith reviewed 2026-05-21 10:55 UTC · model grok-4.3

classification 💰 econ.TH

keywords choice correspondencessubstitutabilitygeneral acyclicitymany-to-many matchingmatching with contractsGrow or Discard algorithmreplacement stabilitybinary acyclicity

0 comments

The pith

Stable matchings exist when choice correspondences satisfy substitutability and general acyclicity in many-to-many markets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that stable matchings can be guaranteed in markets where agents select via choice correspondences rather than complete preference orders. It weakens the standard path-independence requirement by introducing a general acyclicity condition that, together with substitutability, ensures existence for many-to-many settings with contracts. A constructive Grow or Discard algorithm iteratively expands or drops contracts until it reaches a strongly maximal individually rational set. For one-to-one markets the authors define a replacement-based stability notion that holds under the weaker binary acyclicity property. Readers care because the result enlarges the class of admissible choice behaviors that still deliver stable outcomes.

Core claim

Stable matchings exist when choice correspondences satisfy substitutability and a new general acyclicity condition for many-to-many markets. The proof is constructive using the Grow or Discard Algorithm that iteratively expands or eliminates contracts until a strongly maximal individually rational set is reached. For one-to-one markets, replacement-based stability holds under binary acyclicity, a property weaker than path independence.

What carries the argument

The Grow or Discard Algorithm, which iteratively expands or eliminates contracts until a strongly maximal individually rational set is reached while respecting the acyclicity condition.

If this is right

Stable matchings can be found constructively without assuming path independence of choices.
Rejected contracts need not be discarded permanently during the search process.
The existence result applies directly to many-to-many matching with contracts under weaker conditions than prior work.
In one-to-one markets, a replacement-based stability concept is supported by binary acyclicity.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The general acyclicity condition may describe choice patterns observed in real housing or labor markets that violate path independence.
Empirical tests could check whether observed choice data in matching platforms satisfy the new acyclicity property.
The algorithm's flexibility in reconsidering contracts might reduce computational cost in large-scale applications.

Load-bearing premise

Choice correspondences must satisfy both substitutability and the paper's general acyclicity condition for the Grow or Discard algorithm to reach a stable matching.

What would settle it

A concrete many-to-many market instance in which choices are substitutable and generally acyclic yet the Grow or Discard algorithm fails to produce a stable matching or cycles indefinitely.

read the original abstract

We study the existence of stable matchings when agents have choice correspondences instead of preference relations. We extend the framework of \cite{chambers2017choice} by weakening the path independence assumption. For many-to-many markets, we show that stable matchings exist when choice correspondences satisfy substitutability and a new general acyclicity condition. We provide a constructive proof using a Grow or Discard Algorithm that iteratively expands or eliminates contracts until a strongly maximal individually rational set is reached. We provide an algorithm to obtain stable matchings in which rejected contracts are not permanently discarded, distinguishing our approach significantly from standard DAA-type algorithms. For one-to-one markets, we introduce a replacement-based notion of stability and provide an algorithm that constructs stable matchings when choice correspondences satisfy binary acyclicity, a property weaker than path independence. JEL classification: C62, C78, D01, D47 Keywords: choice correspondences, substitutability, general acyclicity, many-to-many matching, matching with contracts, Grow or Discard algorithm, replacement stability, binary acyclicity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Weakens path independence to general acyclicity for choice correspondences and gives a Grow or Discard algorithm that reconsiders rejected contracts.

read the letter

The main thing here is that stable matchings exist under substitutability plus a new general acyclicity condition on choice correspondences, which relaxes path independence, and the authors supply a constructive Grow or Discard algorithm that can revisit contracts instead of discarding them permanently. For one-to-one markets they add replacement-based stability under binary acyclicity. This is the core extension of the Chambers et al. 2017 setup. The paper does well by delivering explicit algorithms rather than pure existence arguments and by making the distinction from deferred acceptance methods clear. The constructive route to a strongly maximal individually rational set is a practical plus for readers who care about computation. The claims appear independent of the cited prior result rather than circular. One soft spot is that the precise strength of the new acyclicity notions depends on their formal definitions, and it is not obvious from the abstract alone whether they remain meaningfully weaker once the algorithm runs in markets with many overlapping contracts. Termination and stability verification could have edge cases that need explicit checking, though the stress test found no immediate internal gap. This paper is for specialists working on matching with contracts and choice correspondences. A reader already familiar with substitutability and acyclicity conditions will see the value in the relaxed assumptions and the non-permanent rejection feature. It deserves a serious referee because the algorithmic difference and the targeted weakening are specific enough to warrant detailed review of the proofs. I recommend sending it to peer review.

Referee Report

1 major / 3 minor

Summary. The manuscript extends Chambers et al. (2017) on choice correspondences in matching markets by relaxing path independence. For many-to-many markets with contracts, it proves existence of stable matchings when choice correspondences satisfy substitutability together with a new general acyclicity condition, via a constructive Grow or Discard algorithm that iteratively expands or eliminates contracts until reaching a strongly maximal individually rational set. For one-to-one markets, it introduces a replacement-based notion of stability and constructs stable outcomes under binary acyclicity, a condition weaker than path independence. The algorithms are distinguished from standard deferred-acceptance procedures by allowing rejected contracts to be reconsidered.

Significance. If the central claims hold, the paper makes a useful contribution by identifying weaker sufficient conditions for stability with choice correspondences and supplying explicit algorithms. The constructive proofs and the distinction between general acyclicity (many-to-many) and binary acyclicity (one-to-one) clarify the minimal structure needed beyond substitutability. The Grow or Discard procedure's feature of not permanently discarding contracts is a practical distinction from DAA-type methods and could support further algorithmic work.

major comments (1)

[§4] §4 (Grow or Discard algorithm): the termination and correctness argument relies on general acyclicity to guarantee that the process reaches a strongly maximal individually rational set without cycling; the manuscript should supply an explicit lemma showing how the acyclicity condition precludes the specific cycles that would otherwise violate convergence, as the current sketch leaves the link between the definition and the algorithm's progress implicit.

minor comments (3)

[Abstract] The abstract introduces 'replacement-based stability' for one-to-one markets without a one-sentence definition; adding a brief gloss would improve accessibility for readers unfamiliar with the variant.
[§2 and §5] Notation for choice correspondences and the acyclicity conditions should be cross-referenced more explicitly between the many-to-many and one-to-one sections to avoid confusion when comparing the two settings.
[Introduction] A short discussion of how the new acyclicity notions relate to existing weakenings in the literature (beyond Chambers et al. 2017) would help situate the contribution.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful review and constructive feedback on our manuscript. We address the major comment below and plan to incorporate the suggested clarification in the revised version.

read point-by-point responses

Referee: [§4] §4 (Grow or Discard algorithm): the termination and correctness argument relies on general acyclicity to guarantee that the process reaches a strongly maximal individually rational set without cycling; the manuscript should supply an explicit lemma showing how the acyclicity condition precludes the specific cycles that would otherwise violate convergence, as the current sketch leaves the link between the definition and the algorithm's progress implicit.

Authors: We agree with the referee that the link between the general acyclicity condition and the convergence of the Grow or Discard algorithm could be made more transparent. The current proof sketch relies on the acyclicity to prevent cycles in the iterative expansion and elimination process, but we acknowledge that an explicit lemma would strengthen the argument. In the revised manuscript, we will introduce a new lemma that formally shows how general acyclicity precludes the types of cycles that could prevent termination, by establishing a strict progress measure (such as an increase in the size of the individually rational set or a lexicographic improvement) that is guaranteed under the acyclicity assumption. This will make the connection between the definition and the algorithm's progress explicit. revision: yes

Circularity Check

0 steps flagged

Minor extension of cited framework; new acyclicity conditions and algorithm are independent

full rationale

The paper extends the Chambers et al. (2017) framework by introducing explicitly new conditions (general acyclicity for many-to-many markets and binary acyclicity for one-to-one markets) that weaken path independence while ensuring the Grow or Discard algorithm reaches a strongly maximal individually rational set or replacement-stable outcome. These conditions are defined and motivated directly in the paper rather than derived from the cited result by construction. The constructive existence proof relies on the algorithm's iterative expansion/elimination steps under the stated substitutability plus acyclicity assumptions, which do not reduce to a self-citation or fitted input. No self-definitional steps, uniqueness theorems imported from the authors, or renamings of known results appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on domain assumptions standard in matching theory plus two new acyclicity conditions introduced in the paper; no free parameters or invented entities are apparent from the abstract.

axioms (2)

domain assumption Choice correspondences satisfy substitutability
Invoked as a maintained assumption for both many-to-many and one-to-one results.
ad hoc to paper Choice correspondences satisfy general acyclicity (many-to-many) or binary acyclicity (one-to-one)
New conditions defined by the paper to replace path independence.

pith-pipeline@v0.9.0 · 5721 in / 1433 out tokens · 75215 ms · 2026-05-21T10:55:25.289004+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that stable matchings exist when choice correspondences satisfy substitutability and a new general acyclicity condition... binary acyclicity, a property weaker than path independence.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

General Acyclicity (GA) ... rules out cycles of grow or discard moves

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.