📈 economics

Lattice operations for the pairwise stable set in many-to-many markets via re-equilibration dynamics

This paper establishes that the set of stable matchings in many-to-many markets with path-independent choice functions forms a lattice by constructing Tarski operators based on lay-off and vacancy chain dynamics that converge to stable outcomes from quasi-stable starting points.

Original authors: Agustin G. Bonifacio, Noelia Juarez, Paola B. Manasero

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Agustin G. Bonifacio, Noelia Juarez, Paola B. Manasero

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 companies (firms) can hire multiple employees, and employees can work for multiple companies at the same time. This is a "many-to-many" market. The big question economists ask is: How do we find a "stable" arrangement where no one wants to switch jobs?

A match is "stable" if no worker and company would both prefer to work together over their current situation, even if it means dropping some of their current partners.

This paper solves a specific puzzle: How do we mathematically combine two different stable job markets to find a "best of both worlds" version, without breaking the rules of stability?

Here is the breakdown using simple analogies:

1. The Problem: The "Mix-and-Match" Trap

In a simple one-to-one world (one worker, one job), if you have two stable job markets, you can easily create a third one by giving every worker their favorite job from the two lists. It works perfectly.

But in this complex world (many-to-many), if you just take two stable lists and let every company pick its favorite workers from the combined pool, chaos ensues. The new list isn't stable. Some workers get fired, some companies get too many people, and new "blocking pairs" form (a worker and a company who really want to work together but aren't matched).

The authors say: "We can't just mix the lists and call it a day. We need a process to fix the mess."

2. The Solution: The "Quasi-Stable" Safety Net

The authors introduce a clever intermediate step called Quasi-Stability. Think of this as a "safety zone" or a "holding pattern."

Worker-Quasi-Stable: Imagine a scenario where companies are allowed to make changes and fire people, BUT the workers are protected. No worker can be fired unless they are part of a new deal that makes them happier. The workers' current happiness is the "anchor."
Firm-Quasi-Stable: The reverse. Companies are the anchor; workers can be shuffled around, but companies can't be forced to drop a worker they really want.

The paper proves that even though these "safety zones" aren't perfectly stable yet, they have a neat mathematical structure (a lattice). This means you can mathematically combine two of these "safety zone" lists to get a new one that is still in the safety zone.

3. The Engine: The "Re-Equilibration" Machine

Once you have your "safety zone" list (which is messy but safe for one side), the authors build a machine called a Tarski Operator.

Think of this operator as a decentralized game of musical chairs or a domino effect:

The Trigger: You start with a "Worker-Quasi-Stable" list. It's safe for workers, but companies might be unhappy or have empty spots.
The Round: Companies look at their current staff plus any new workers who are knocking on their door. They pick their favorite group based on their rules.
The Ripple: Because a company picked a new group, they might have to let go of some workers. Those fired workers now look for new jobs. They apply to other companies. Those companies re-evaluate and might fire their workers.
The Chain Reaction: This creates a "layoff chain" (or a "vacancy chain" if you start from the company's perspective). One firing leads to another, which leads to another.
The Stop: Eventually, the chain stops. No one wants to move anymore. The market has "re-equilibrated."

The paper proves that if you run this machine enough times, it always stops at a perfectly Stable matching.

4. The Grand Result: Finding the "Join"

The main goal of the paper is to find the "Join" (the best possible combination) of two stable markets.

Here is the recipe the authors provide:

Take two stable markets.
Create a "Worker-Quasi-Stable" mix (let companies pick their favorites from the two lists).
Run the "Re-Equilibration Machine" (the Tarski Operator) on this mix.
Let the "layoff chains" play out until the market settles.
Result: The final stable market you get is the mathematical "Join" of the original two.

5. Why This Matters

It's a Bridge: It connects the messy reality of "almost stable" markets to the perfect world of "stable" markets.
It's Economic: It explains how real markets might fix themselves after a shock (like a new company entering or a worker getting fired). It's not magic; it's a chain reaction of people finding new jobs until everyone is happy.
It's General: They did this using only the rule that "choices are consistent" (if you like a group of people, you still like them if you remove some options). They didn't need stricter, unrealistic rules.

In a nutshell: The paper shows that if you want to combine two stable job markets, you can't just mash them together. You have to let the market "shake itself out" through a series of firings and hirings (re-equilibration). If you start with a "safe" version where one side is protected, this shaking process will inevitably lead you to the perfect, stable combination.

Technical Summary: Lattice Operations for the Pairwise Stable Set in Many-to-Many Markets via Re-equilibration Dynamics

Problem Statement
The paper addresses the computation of lattice operations (join and meet) for the set of pairwise stable matchings in many-to-many markets. While the lattice structure of stable matchings is a fundamental tool in matching theory—underpinning results on conflicts of interest and the existence of side-optimal outcomes—computing these operations in many-to-many settings is non-trivial.

In one-to-one markets with strict preferences, the join and meet are constructed via simple pointwise assignments of preferred partners. However, in many-to-one and many-to-many markets with path-independent choice functions, these direct constructions fail to preserve stability. Previous approaches to resolve this have either imposed stronger conditions than path-independence (such as "separability with quota") or relied on complex theoretical constructs like "pre-matchings" (entities with difficult economic interpretations) to define Tarski operators. The authors seek to compute lattice operations under the sole requirement of path-independence, providing a method with a transparent economic interpretation that avoids pre-matchings.

Methodology
The authors propose a framework based on quasi-stable matchings and Tarski operators to bridge the gap between initial candidate matchings and stable outcomes.

Quasi-Stability Definitions: The paper introduces and formalizes two relaxed stability concepts:
- Worker-quasi-stability ( $Q_W$ ): Matchings that are individually rational and where no worker can form a blocking pair that disrupts existing worker-side relationships.
- Firm-quasi-stability ( $Q_F$ ): The symmetric definition where firm-side relationships are protected.
  The authors demonstrate that these sets form lattices under specific partial orders (Blair's orders).
Construction of Candidate Matchings: Given two stable matchings, $\mu$ and $\mu'$ , the authors construct a candidate join, $\lambda_{\mu,\mu'}$ , by assigning each firm the subset of workers selected by its choice function from the union of its partners in $\mu$ and $\mu'$ . Similarly, a candidate join for workers, $\gamma_{\mu,\mu'}$ , is constructed. The authors show that while these candidates are not necessarily stable, they are guaranteed to be quasi-stable (specifically, $\lambda_{\mu,\mu'}$ is worker-quasi-stable).
Tarski Operators and Re-equilibration: The core of the methodology involves defining Tarski operators ( $T^F$ on $Q_W$ and $T^W$ on $Q_F$ ) that map quasi-stable matchings to new quasi-stable matchings.
- Mechanism: The operator $T^F$ takes a worker-quasi-stable matching, identifies all workers who are either currently matched to a firm or form a blocking pair with it, and re-optimizes the firm's choice from this expanded pool.
- Dynamics: These operators are isotone (order-preserving) and Pareto-improving for the optimizing side. The authors interpret the iteration of these operators as re-equilibration dynamics. In a worker-quasi-stable environment, this resembles "layoff chains" where unemployed or displaced workers apply to preferred firms, triggering a cascade of adjustments. In firm-quasi-stable environments, it resembles "vacancy chain" dynamics.
Fixed Point Convergence: By Tarski's Fixed Point Theorem, iterating these operators from a quasi-stable starting point converges to a fixed point. The authors prove that the set of fixed points of these operators coincides exactly with the set of pairwise stable matchings ( $S$ ).

Key Contributions and Results

Lattice Structure of Quasi-Stable Sets: The paper proves that the sets of worker-quasi-stable and firm-quasi-stable matchings form lattices under Blair's orders. This extends previous results from many-to-one models to the many-to-many setting.
Computation of Lattice Operations: The main result (Theorem 3) establishes that the join of two stable matchings with respect to the firms' order ( $\mu \vee_F \mu'$ $μ \lor_{F} μ^{'}$ ) is obtained by iteratively applying the firm-side Tarski operator ( $T^F$ $T^{F}$ ) to the worker-quasi-stable candidate $\lambda_{\mu,\mu'}$ $λ_{μ, μ^{'}}$ until a fixed point is reached.
- $\mu \vee_F \mu' = F^F(\lambda_{\mu,\mu'})$
- $\mu \wedge_F \mu' = F^W(\gamma_{\mu,\mu'})$
- By duality, the meet for one side corresponds to the join for the other.
Economic Interpretation of Blair's Method: The authors show that Blair's (1988) method for computing lattice operations, which previously lacked a transparent economic mechanism, is equivalent to the fixed-point method applied to these quasi-stable lattices. This provides a sound economic foundation for Blair's original construct.
Counter-Examples and Necessity of Iteration: Through examples (including one adapted from Li, 2013), the paper demonstrates that the direct construction $\lambda_{\mu,\mu'}$ is not always stable, necessitating the iterative re-equilibration process. It also highlights that the lattice of stable matchings is not necessarily distributive under path-independence alone.

Significance and Claims
The paper claims to provide a unified and operational interpretation of equilibrium as the endpoint of endogenous market correction. By utilizing quasi-stable matchings instead of pre-matchings, the authors offer a method that is both theoretically rigorous (requiring only path-independence) and economically intuitive (modeled as decentralized adjustment processes like layoff or vacancy chains).

The authors note that while the lattice structure holds under path-independence, the lattice is not necessarily distributive. They further clarify that if the "law of aggregate demand" is added, the candidate matchings $\lambda_{\mu,\mu'}$ and $\gamma_{\mu,\mu'}$ become stable directly, and the lattice becomes distributive, aligning with results by Alkan (2002). However, under the sole assumption of path-independence, the iterative Tarski operator approach is required to compute the lattice operations. The paper concludes that while the join-semilattice structure of quasi-stable matchings is established, the direct computation of the meet between arbitrary quasi-stable matchings remains an open question.