📈 economics

Pseudo-Substitutability: A Maximal Domain for Pairwise Stability in Matching Markets with Contracts

This paper introduces the concept of pseudo-substitutable preferences as a maximal domain that strictly extends classical substitutability to accommodate limited complementarities while guaranteeing the existence of pairwise stable allocations in matching markets with contracts.

Original authors: Nadia Guiñazú, Noelia Juarez, Paola Manasero, Pablo Neme, Jorge Oviedo

Published 2026-04-21

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Nadia Guiñazú, Noelia Juarez, Paola Manasero, Pablo Neme, Jorge Oviedo

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a bustling job market where doctors are looking for hospitals, and hospitals are looking for doctors. But this isn't just a simple "one doctor, one hospital" scenario. In this world, a doctor might work part-time at Hospital A, do research at Hospital B, and teach at Hospital C. Similarly, a hospital might hire five different doctors for different shifts.

The big question economists ask is: Can we always find a "stable" arrangement?

A stable arrangement means no doctor and no hospital would want to break their current deals to sign a new one with each other. If they could, the current arrangement is "unstable" and would eventually fall apart.

The Old Rule: "Substitutability"

For decades, economists believed that for a stable arrangement to always exist, everyone had to follow a strict rule called Substitutability.

Think of Substitutability like a picky eater at a buffet.

If you offer a picky eater a burger, they take it.
If you then add a side of fries to the table, they still take the burger.
The presence of fries doesn't make the burger less desirable.
The Rule: Adding more options never makes you reject an option you previously liked.

In the job market, this means a hospital would never say, "I only want to hire Dr. Smith if I also hire Dr. Jones." If they hire Dr. Smith alone, they must be happy with that. If they hire both, they must still be happy with Smith. This "no-complementarity" rule guarantees stability, but it's very restrictive. It assumes people never want things in bundles.

The New Discovery: "Pseudo-Substitutability"

The authors of this paper realized that real life is messier. Sometimes, you do want things in bundles.

Example: A hospital might say, "I don't want Dr. Smith alone (he's too expensive for just one shift), and I don't want Dr. Jones alone (she needs a team). But if I hire both together, they are perfect for each other!"

This "bundle" desire breaks the old "Substitutability" rule. Under the old rules, if a hospital wants both, it's considered "unstable" because the preferences are too complicated.

The authors introduce a new concept called Pseudo-Substitutability.

The Analogy: The "Safe Subset"

Imagine you are a chef (the hospital) with a very complex recipe book (your preferences). Some recipes require specific ingredients to work together (complementarity).

The authors say: "You don't need to throw away your complex recipe book. You just need to find a Safe Subset of recipes inside it."

The Core: Even if your full preference list is messy and full of "I only want A if I have B" rules, there is a hidden, smaller list of preferences inside your head that is simple and follows the old "Substitutability" rules.
The Magic: As long as this "Safe Subset" exists, you can find a stable match.
The Result: The market can handle the messy "bundle" desires, as long as there is a logical, simple core underneath them.

They call this Pseudo-Substitutability. It's "pseudo" (fake) because it looks like the messy real world, but it's actually built on a solid, stable foundation.

Why is this a Big Deal? (The "Maximal" Claim)

The authors didn't just find a new rule; they found the largest possible rule that works.

The Boundary: Imagine a map of all possible preferences.
- The "Substitutable" zone is a small island in the middle.
- The "Pseudo-Substitutable" zone is a huge continent surrounding that island.
- The authors proved that if you step anywhere outside this continent, you can construct a scenario where no stable match exists. The market would collapse into chaos.

So, they found the absolute limit. You can be as messy as you want, as long as you stay within this "Pseudo" boundary.

Real-World Impact: The "Non-Binding" Market

The paper also touches on a very practical problem: What happens when people change their minds?

In many real-world markets (like medical residency), a match isn't legally binding. A doctor can accept a job offer and then later say, "Actually, I'm not coming."

Old Stability: If a doctor leaves a "Corewise Stable" match (the super-strict kind), the whole system might collapse because the remaining pieces don't fit together anymore.
Pseudo Stability: Because "Pseudo-Substitutable" preferences are built on that "Safe Subset" (the simple, substitutable core), if one person leaves, the remaining matches are still logical and stable. The system is robust. It doesn't fall apart just because one person walked away.

Summary

The Problem: Real people like bundles (e.g., "I only want this job if I get that one too"), which breaks the old math rules for stability.
The Solution: The authors found a new rule called Pseudo-Substitutability. It allows for bundles, provided there is a hidden, simple "core" of preferences that follows the old rules.
The Guarantee: As long as everyone's preferences fit this new rule, a stable match is guaranteed to exist.
The Limit: This is the biggest possible rule. Go any further, and stability is impossible.
The Benefit: These matches are tougher. If one person quits, the rest of the system stays stable, making it perfect for real-world markets where people can change their minds.

In short, the paper says: "You don't have to be perfectly simple to find a stable match. You just need to have a simple heart underneath the complex desires."

1. Problem Statement

The paper addresses the fundamental problem of existence in many-to-many matching markets with contracts. Specifically, it investigates the conditions under which pairwise stable allocations are guaranteed to exist.

Context: In markets where agents (doctors and hospitals) can sign multiple contracts, stability is often defined by the absence of "blocking" pairs (a doctor and hospital who prefer to sign a new contract outside the current allocation).
The Challenge: In general environments, pairwise stable allocations may not exist. The classical literature (Kelso & Crawford, 1982; Hatfield & Milgrom, 2005) established that substitutability of preferences is a sufficient condition for existence. However, substitutability is a restrictive condition that rules out all complementarities (where the value of one contract depends positively on the presence of another).
The Gap: While various relaxations of substitutability have been proposed (e.g., weak substitutes, bilateral substitutes), the literature has struggled to identify a maximal domain of preferences that:
1. Strictly contains the classical substitutable domain.
2. Guarantees the existence of pairwise stable allocations.
3. Is defined structurally rather than relying on specific contractual representations or mechanism-based conditions.

2. Methodology and Key Concepts

The authors introduce a new domain restriction called Pseudo-Substitutability, defined through the structural concept of a sub-preference.

A. Sub-Preference ( $P' \sqsubseteq P$ )

A preference relation $P'$ is a sub-preference of $P$ if it satisfies two conditions:

Individual Rationality Preservation: If a set of contracts is chosen under $P'$ , it must also be chosen under $P$ .
Blocking Preservation: If a contract is chosen under $P$ when added to a set chosen by $P'$ , it must also be chosen under $P'$ when added to that same set.

Intuition: A sub-preference is a "simplified" version of the original preference that retains the core stability properties. If an allocation is stable under the sub-preference, it remains stable under the original preference.

B. Pseudo-Substitutability

A preference relation is pseudo-substitutable if it admits at least one sub-preference that is substitutable.

This allows the original preference to exhibit complementarities, provided there exists a "core" substitutable structure within it that can support stability.
The authors prove that among all substitutable sub-preferences of a pseudo-substitutable preference, there is a minimal one (in terms of the set of acceptable contract sets) that is unique in its structure (preserving Blair's partial order).

C. Analytical Approach

The proof strategy relies on a decomposition technique:

Identify a substitutable sub-preference profile $P'$ within the pseudo-substitutable profile $P$ .
Invoke the classical result that $S(P') \neq \emptyset$ (a stable allocation exists for $P'$ ).
Use the property that $S(P') \subseteq S(P)$ to conclude that a stable allocation exists for the original profile $P$ .

3. Key Contributions

Definition of a New Domain: The paper defines pseudo-substitutability, a domain that strictly extends the classical substitutable domain. It accommodates limited complementarities while retaining the structural guarantees of substitutability.
Existence Theorem: The authors prove that if all agents have pseudo-substitutable preferences, the set of pairwise stable allocations is non-empty (Theorem 1).
Maximality Result: The paper establishes that pseudo-substitutability is maximal. If even one agent's preferences fall outside this domain, it is possible to construct a market (with other agents having pseudo-substitutable preferences) where no pairwise stable allocation exists (Theorem 2).
Contract-Independence: Unlike many existing relaxations (e.g., Weak Observable Substitutability across Doctors - WOSAD) which rely on the specific structure of contracts or offer paths, pseudo-substitutability is defined directly on preferences. This makes the domain applicable even in contract-free matching models, where it remains a strict superdomain of substitutability.

4. Main Results

Theorem 1 (Existence): For any market with a pseudo-substitutable preference profile, the set of pairwise stable allocations $S(P)$ $S (P)$ is non-empty.
- Proof Logic: Since $P$ is pseudo-substitutable, there exists a substitutable sub-profile $P' \sqsubseteq P$ . Since $P'$ is substitutable, $S(P') \neq \emptyset$ . By Proposition 1, $S(P') \subseteq S(P)$ , implying $S(P) \neq \emptyset$ .
Theorem 2 (Maximality): If a hospital's preference is not pseudo-substitutable, there exists a market configuration (with pseudo-substitutable doctors and another hospital) such that $S(P) = \emptyset$ $S (P) = \emptyset$ .
- Proof Logic: The proof constructs specific counterexamples based on types of complementarities (unidirectional and bi-directional) that violate the pseudo-substitutable condition, demonstrating that stability breaks down.
Structural Properties:
- Pseudo-substitutable preferences satisfy consistency but generally fail path-independence (a hallmark of strict substitutability).
- All substitutable sub-preferences of a pseudo-substitutable preference share the same collection of acceptable sets and preserve Blair's partial order.

5. Significance and Implications

Resolution of an Open Question: The paper addresses the open question left by Hatfield and Kojima (2008) regarding the existence of a maximal domain for stability. While their work focused on corewise stability in many-to-one markets, this paper provides the analogous structural answer for pairwise stability in many-to-many markets.
Distinction from Literature:
- Vs. Weak/Bilateral Substitutability: These are behavioral restrictions on choice functions. Pseudo-substitutability is a structural decomposition of preferences. The domains are independent (neither implies the other).
- Vs. Substitutable Completability: While completability extends a market to a larger space to find stability, pseudo-substitutability finds stability directly within the original preference space.
- Vs. WOSAD: WOSAD is mechanism-dependent (tied to the cumulative offer algorithm). Pseudo-substitutability is mechanism-independent.
Robustness in Non-Binding Markets: The authors highlight a practical economic implication. In non-binding markets (where agents can unilaterally reject matches), pairwise stable allocations derived from pseudo-substitutable preferences offer a form of robustness. If an agent rejects a match, the remaining allocation often remains individually rational, whereas corewise stable allocations in non-substitutable environments might unravel completely.

Conclusion

The paper successfully identifies pseudo-substitutability as the largest possible domain of preferences that guarantees the existence of pairwise stable allocations in many-to-many matching markets with contracts. By shifting the focus from global substitutability to the existence of a substitutable "core" (sub-preference), the authors provide a more flexible and realistic framework for analyzing stability in complex labor and matching markets.