betaFeedback

WorksEconomics, Econometrics and Finance

A Characterization of Quantile Stable Matchings in Many-to-Many Markets

Abstract

We study two-sided many-to-many matching markets where agents' preferences satisfy strong substitutability and the law of aggregate demand (LAD). In this framework, the set of stable matchings forms a finite distributive lattice, and quantile stable matchings exist and satisfy the polarization of interests. Building on the cycle-reduction machinery of Bonifacio et al. (2022), we provide a purely combinatorial characterization of quantile stable matchings formulated in terms of preference cycles and their induced precedence order. Specifically, we define an order-theoretic counting function on cycles and prove that each quantile stable matching corresponds to the elimination of an endogenously determined closed set of cycles starting from the firm-optimal stable matching. This characterization extends the rotation-based framework of Cheng (2008) from one-to-one markets to many-to-many markets and bypasses the need for exhaustive outcome enumeration or partner sorting across the entire stable set.

Introduction

In two-sided matching markets, the Deferred Acceptance algorithm of Gale and Shapley [10] reliably outputs stable allocations, but it does so by reaching the extreme boundaries of the stable set: the firm-optimal stable matching (which is unanimously the worst stable outcome for workers) and the worker-optimal stable matching (unanimously the worst for firms). While computationally appealing, this stark polarization of interests raises significant fairness concerns in centralized clearinghouses, where prioritizing one market side imposes maximal welfare losses on the other.

To overcome this inherent one-sided bias and provide balanced compromises, Teo and Sethuraman [15] pioneered the study of generalized median stable matchings in one-to-one markets. They established that selecting each agent’s quantile-ranked stable partner across the entire set of stable matchings yields an allocation that is itself stable. This formulation introduces a flexible spectrum of egalitarian and compromise solutions between the two market extremes. In particular, the standard median matching treats both sides symmetrically and mitigates the vulnerability of agents to strategic manipulation often observed in extremal mechanisms [13, 6] (Chen et al. 2021), although recent work highlights subtle incentive trade-offs regarding obvious manipulations in contractual settings [2].

Moving beyond the one-to-one framework, Chen et al. [6] extended this compromise paradigm to many-to-many markets under the banner of quantile stable matchings. They showed that whenever agents’ preferences satisfy the law of aggregate demand (LAD) and strong substitutability—a refinement of standard substitutability introduced by Echenique and Oviedo [9]—simultaneously assigning to each firm its ranked stable set of workers produces an allocation that is itself stable. Moreover, these compromise matchings satisfy a strict duality of interests across the distributive lattice: a favorable choice for firms corresponds precisely to the dual, symmetric outcome for workers.

Traditionally, defining or computing these quantile stable matchings requires an exhaustive global inspection of the entire stable matching set to identify each agent’s ranked stable outcomes. In the one-to-one domain, Cheng [8] overcame this limitation by showing that generalized median matchings can instead be characterized through an ideal-counting argument on a precedence order of rotations—the algorithmic terminology introduced by Irving and Leather [11] for cycles in preferences [14]. In multi-partner contexts, however, a purely structural characterization that identifies these compromise allocations without exhaustive enumeration of the stable set has remained absent. This fundamental contrast naturally raises a central question: Can quantile stable matchings in many-to-many markets be identified through an intrinsic combinatorial structure without enumerating the entire set of stable matchings?

In this note, we answer this question affirmatively by extending the combinatorial perspective to many-to-many markets using the concept of cycles in preferences introduced by Bonifacio et al. [5]. In their framework, each stable matching adjacent in Blair’s order is obtained from another by eliminating a cycle in preferences under a reduced preference profile. We show that the set of all such cycles, endowed with their natural precedence ordering, allows us to characterize every quantile stable matching directly: each compromise matching corresponds to an endogenously defined closed set of cycles, identified solely by how many stable matchings leave each cycle uneliminated.

The remainder of the note is organized as follows. § 2 introduces the model, the preference conditions, and the distributive lattice structure of stable matchings. § 3 reviews the preference reduction procedure, cycles in preferences, and their lattice-theoretic connection via Birkhoff’s representation theorem. § 4 presents our main combinatorial characterization of quantile stable matchings and its proof. § 5 concludes with a discussion on computational complexity and directions for future research.

Model and Preliminaries

Let FF and WW be disjoint, finite sets of firms and workers. Let A=F∪WA = F \cup W. Each firm f∈Ff \in F is endowed with a strict preference relation PfP_f over 2W2^W, and each worker w∈Ww \in W with a strict preference relation PwP_w over 2F2^F. A preference profile is denoted by P=(Pa)a∈AP = (P_a)_{a \in A}. For any f∈Ff \in F and S⊆WS \subseteq W, Cf(S)C_f(S) denotes ff’s chosen subset from SS according to PfP_f; similarly, Cw(S′)C_w(S') denotes ww’s chosen subset from S′⊆FS' \subseteq F.

A matching μ\mu is a mapping from F∪WF \cup W into 2F∪W2^{F \cup W} such that for all f∈Ff \in F and w∈Ww \in W: (i) μ(f)⊆W\mu(f) \subseteq W, (ii) μ(w)⊆F\mu(w) \subseteq F, and (iii) w∈μ(f)⟺f∈μ(w)w \in\mu(f) \Longleftrightarrow f \in\mu(w).

A matching μ\mu is individually rational if Ca(μ(a))=μ(a)C_a(\mu(a)) = \mu(a) for all a∈Aa \in A. A pair (f,w)∈F×W(f,w) \in F \times W blocks μ\mu if w∉μ(f)w \notin\mu(f), w∈Cf(μ(f)∪{w})w \in C_f(\mu(f) \cup\{w\}), and f∈Cw(μ(w)∪{f})f \in C_w(\mu(w) \cup\{f\}). A matching μ\mu is stable if it is individually rational and admits no blocking pair. We denote the set of stable matchings by S\mathcal{S}.

Definition 1. A preference relation PaP_a satisfies:

  1. Strong Substitutability if for any S,S′S, S' such that Ca(S′)PaCa(S)C_a(S') P_a C_a(S) and any bb,

    b∈Ca(S′∪{b})⟹b∈Ca(S∪{b}).b \in C_a(S' \cup\{b\}) \Longrightarrow b \in C_a(S \cup\{b\}).
  1. The Law of Aggregate Demand (LAD) if for all S⊆S′S \subseteq S', ∣Ca(S)∣≤∣Ca(S′)∣|C_a(S)| \leq|C_a(S')|.

Given an agent’s strict preference relation, Blair [4] defined a partial order over subsets of the opposite side of the market induced by the agent’s choice. For any firm f∈Ff \in F with preference relation PfP_f and any two subsets of workers S,S′⊆WS,S' \subseteq W, we say that SS is Blair-preferred to S′S', denoted by S≥fS′S \geq_f S', if

S=Cf(S∪S′).S = C_f(S \cup S').

That is, S≥fS′S \geq_f S' means that whenever all workers in S∪S′S \cup S' are available, the most-preferred subset of firm ff according to PfP_f is exactly SS. We write S>fS′S >_f S' if S≥fS′S \geq_f S' and S≠S′S \neq S'. Symmetrically, for each worker w∈Ww \in W and subsets F′,F′′⊆FF',F'' \subseteq F, the partial order ≥w\geq_w is defined by F′≥wF′′F' \geq_w F'' if and only if F′=Cw(F′∪F′′)F' = C_w(F' \cup F'').

At the market level, Blair’s order induces a unanimous partial ordering over matchings: for any two matchings μ\mu and μ′\mu', we write μ≥Fμ′\mu\geq_F \mu' if μ(f)≥fμ′(f)\mu(f) \geq_f \mu'(f) for all f∈Ff \in F, and μ>Fμ′\mu>_F \mu' if μ≥Fμ′\mu\geq_F \mu' with μ≠μ′\mu\neq\mu'. The unanimous order for workers, ≥W\geq_W, is defined symmetrically. Under substitutable preferences (and in particular under strongly substitutable preferences), Blair [4] established that the set of stable matchings SS forms a lattice with respect to ≥F\geq_F (and dually with respect to ≥W\geq_W).

When preferences further satisfy LAD, (S,≥F)(S,\geq_F) forms a finite distributive lattice and these lattices are dual, giving rise to the polarization of interests: μ≥Fμ′\mu\geq_F \mu' if and only if μ′≥Wμ\mu' \geq_W \mu for all μ,μ′∈S\mu,\mu' \in S (Alkan [1]). Furthermore, under strong substitutability, Blair’s order on SS coincides with the underlying strict individual preference relation PaP_a over each agent’s stable assignments.

Cycles in Preferences and Closed Sets of Cycles

In this section, we review the notion of cycles in preferences introduced by Bonifacio et al. [5]. In their framework, transitions between adjacent stable matchings in the lattice are governed by eliminating elementary cycles of worker-firm pairs under reduced preference profiles. For completeness, the formal construction of the preference reduction procedure is deferred to Appendix § 6.

For μ,μ~∈S\mu,\tilde{\mu} \in S with μ>Fμ~\mu>_F \tilde{\mu}, the reduced preference profile Pμ,μ~P^{\mu,\tilde{\mu}} eliminates partners that are strictly Blair-preferred to μ\mu or strictly less Blair-preferred than μ~\tilde{\mu}. When μ~=μW\tilde{\mu} = \mu_W, we denote this profile by PμP^\mu.

Definition 2 (Cycle in Preferences). Let μ∈S∖{μW}\mu\in S \setminus\{\mu_W\}. A cycle σ\sigma for PμP^\mu is an ordered sequence of worker-firm pairs σ={(w1,f1),(w2,f2),…,(wr,fr)}\sigma= \{(w_1,f_1),(w_2,f_2),\ldots,(w_r,f_r)\} such that for all i=1,…,ri = 1,\ldots,r:

  1. wi∈μ(fi)∖μW(fi)w_i \in\mu(f_i) \setminus\mu_W(f_i),

  1. Cfiμ(W∖{wi})=(μ(fi)∖{wi})∪{wi+1}C^{\mu}_{f_i}(W \setminus\{w_i\}) = (\mu(f_i) \setminus\{w_i\}) \cup\{w_{i+1}\}, with wr+1=w1w_{r+1} = w_1, and

  1. Cwiμ(μ(wi)∪{fi−1})=(μ(wi)∖{fi})∪{fi−1}C_{w_i}^{\mu}(\mu(w_i) \cup\{f_{i-1}\}) = (\mu(w_i) \setminus\{f_i\}) \cup\{f_{i-1}\}, with f0=frf_0 = f_r.

Eliminating a cycle σ\sigma from matching μ\mu yields the cyclic matching μσ\mu_{\sigma}, defined by μσ(f)=(μ(f)∖{wi})∪{wi+1}\mu_{\sigma}(f) = (\mu(f) \setminus\{w_i\}) \cup\{w_{i+1}\} for each f=fi∈σf = f_i \in\sigma, and μσ(f)=μ(f)\mu_{\sigma}(f) = \mu(f) otherwise. Bonifacio et al. [5] prove that μσ∈S\mu_{\sigma} \in\mathcal{S} and μ>Fμσ\mu>_F \mu_{\sigma}. In terms of the lattice (S,≥F)(\mathcal{S}, \geq_F), this cyclic transition defines an immediate covering relation: there is no stable matching μ′′∈S\mu^{\prime\prime} \in\mathcal{S} such that μ>Fμ′′>Fμσ\mu>_F \mu^{\prime\prime} >_F \mu_{\sigma}. Thus, we say that μ\mu covers μσ\mu_{\sigma}.

Let Σ\Sigma denote the set of all elementary preference cycles exposed across the lattice S\mathcal{S}.

Definition 3 (Precedence of Cycles). For two cycles σ,σ′∈Σ\sigma, \sigma' \in\Sigma, we say that σ\sigma precedes σ′\sigma' (denoted σ≤σ′\sigma\leq\sigma') if cycle σ\sigma must be eliminated before cycle σ′\sigma' can become exposed in a reduced preference profile along any path from μF\mu_F.

A subset S⊆ΣS \subseteq\Sigma is a closed set of cycles (also known in order theory as an order ideal or down-set) if whenever σ∈S\sigma\in S and σ′≤σ\sigma' \leq\sigma, then σ′∈S\sigma' \in S. We denote the family of all closed sets of cycles by C(Σ)\mathcal{C}(\Sigma).

By Birkhoff’s Representation Theorem for finite distributive lattices,4 in our setting the covering relations in (S,≥F)(\mathcal{S}, \geq_F) are characterized by the elimination of elementary preference cycles from Σ\Sigma.

Because we initialize this elimination procedure at the firm-optimal stable matching μF\mu_F (the top element of the lattice), each eliminated cycle moves the matching downward along the covering relations of Blair’s order ≥F\geq_F. Consequently, the lattice of stable matchings (S,≥F)(\mathcal{S}, \geq_F) is isomorphic to the family of closed sets of cycles (C(Σ),⊆)(\mathcal{C}(\Sigma), \subseteq) inverted. More formally, there exists a bijective correspondence between S\mathcal{S} and C(Σ)\mathcal{C}(\Sigma) such that:

  1. The firm-optimal matching μF\mu_F corresponds to the empty set of cycles, ∅\varnothing.

  1. The worker-optimal matching μW\mu_W corresponds to the full set of cycles, Σ\Sigma.

  1. For any two stable matchings μ,μ′∈S\mu, \mu' \in\mathcal{S} with corresponding closed sets Sμ,Sμ′∈C(Σ)S_{\mu}, S_{\mu'} \in\mathcal{C}(\Sigma),

μ≥Fμ′⟺Sμ⊆Sμ′.\mu\geq_F \mu' \Longleftrightarrow S_{\mu} \subseteq S_{\mu'}.

In particular, every stable matching μ∈S\mu\in\mathcal{S} is uniquely obtained by starting at μF\mu_F and eliminating all cycles belonging to its corresponding closed set SμS_{\mu}.

Characterization of Quantile Stable Matchings

Let N=∣S∣N = \lvert S\rvert denote the total number of stable matchings. For each agent a∈F∪Wa \in F \cup W, consider the collection of subsets of partners assigned to aa across all stable matchings, {μ(a):μ∈S}\{\mu(a) : \mu\in S\}. We sort these sets from most preferred to least preferred according to the strict preference relation PaP_a:

μ(1)(a)>aμ(2)(a)>a⋯>aμ(N)(a),\mu^{(1)}(a) >_a \mu^{(2)}(a) >_a \cdots>_a \mu^{(N)}(a),

where the parenthesized superscript (i)(i) indicates an order statistic: μ(i)(a)\mu^{(i)}(a) represents the ii-th most-preferred set of partners received by agent aa across the stable set SS.

We now formalize the market-wide compromise matchings introduced by Chen et al. [6], where a superscript ii (without parentheses) indexes the resulting matching.

Definition 4 (Quantile Stable Matching). For each integer i∈{1,…,N}i \in\{1,\ldots,N\}, the ii-th quantile stable matching for firms, denoted by μFi\mu_F^i, is defined by:

μFi(f)=μ(i)(f)for all f∈F.\mu_F^i(f) = \mu^{(i)}(f) \quad\text{for all } f \in F.

Symmetrically, the ii-th quantile stable matching for workers, denoted by μWi\mu_W^i, is defined by:

μWi(w)=μ(i)(w)for all w∈W.\mu_W^i(w) = \mu^{(i)}(w) \quad\text{for all } w \in W.

In particular, the extreme quantiles coincide with the lattice boundaries: μF1\mu_F^1 is the firm-optimal stable matching μF\mu_F (where each firm ff receives its first-choice stable set of workers μ(1)(f)\mu^{(1)}(f)), whereas μFN\mu_F^N is the worker-optimal stable matching μW\mu_W (the least-preferred stable outcome for every firm). Under strong substitutability and LAD, Theorem 2 in Chen et al. [6] guarantees that μFi\mu_F^i is indeed a stable matching for each i∈{1,…,N}i \in\{1,\ldots,N\}, and satisfies the polarization of interests: μFi=μWN−i+1\mu_F^i = \mu_W^{N-i+1}.

We now characterize these matchings directly through the structure of preference cycles.

Definition 5. For each preference cycle σ∈Σ\sigma\in\Sigma, let nσn_\sigma denote the number of closed sets of cycles that do not contain σ\sigma:

nσ=∣{S∈C(Σ):σ∉S}∣.n_\sigma= \left\lvert\{S \in\mathcal{C}(\Sigma) : \sigma\notin S\} \right\rvert.

Lemma 1. The function nσn_\sigma is strictly increasing in the cycle precedence order: for any σ,σ′∈Σ\sigma,\sigma' \in\Sigma, σ<σ′\sigma< \sigma' implies that nσ<nσ′n_\sigma< n_{\sigma'}.

Proof. Let S∈C(Σ)S \in\mathcal{C}(\Sigma) and let σ,σ′∈Σ\sigma,\sigma' \in\Sigma with σ<σ′\sigma< \sigma'. Since SS is closed under precedence, σ′∉S\sigma' \notin S implies σ∉S\sigma\notin S. Thus,

{S∈C(Σ):σ′∉S}⊆{S∈C(Σ):σ∉S}.\{S \in\mathcal{C}(\Sigma) : \sigma' \notin S\} \subseteq\{S \in\mathcal{C}(\Sigma) : \sigma\notin S\}.

To show that the inclusion is strict, consider the set Sσ={σ′′∈Σ:σ′′≤σ}S_\sigma= \{\sigma^{\prime\prime} \in\Sigma: \sigma^{\prime\prime} \le\sigma\}. By definition of precedence, SσS_\sigma is a closed set of cycles containing σ\sigma. Moreover, since σ<σ′\sigma< \sigma^{\prime} and the precedence order is strict, σ′∉Sσ\sigma^{\prime} \notin S_\sigma. Thus, SσS_\sigma belongs to the right-hand set but not to the left-hand set, which implies nσ<nσ′n_\sigma< n_{\sigma^{\prime}}.

Theorem 1. Assume that agents’ preferences satisfy strong substitutability and the law of aggregate demand (LAD). For each i∈{1,…,N}i \in\{1,\ldots,N\}, define:

S(i)={σ∈Σ:nσ<i}.S(i) = \{\sigma\in\Sigma: n_\sigma< i\}.

Then:

(i) S(i)S(i) is a closed set of cycles in (Σ,≤)(\Sigma, \le).

(ii) The ii-th quantile stable matching μFi\mu_F^i is precisely the stable matching obtained by eliminating all cycles in S(i)S(i) starting from μF\mu_F.

Proof. To prove (i), let σ∈S(i)\sigma\in S(i) and suppose σ′≤σ\sigma^{\prime} \le\sigma for σ′∈Σ\sigma^{\prime} \in\Sigma. By Lemma 1, nσ′≤nσ<in_{\sigma^{\prime}} \le n_\sigma< i, which implies that σ′∈S(i)\sigma^{\prime} \in S(i). Therefore, S(i)S(i) is a closed set of cycles in (Σ,≤)(\Sigma, \le).

To prove (ii), let S(μFi)S(\mu_F^i) denote the unique closed set of cycles in C(Σ)C(\Sigma) corresponding to the ii-th quantile stable matching μFi\mu_F^i. We must prove that S(μFi)=S(i)S(\mu_F^i) = S(i).

Recall that for each cycle σ∈Σ\sigma\in\Sigma, nσn_\sigma counts the number of stable matchings whose corresponding closed set does not contain σ\sigma:

nσ=∣{μ∈S:σ∉Sμ}∣.n_\sigma= \lvert\{\mu\in S : \sigma\notin S_\mu\}\rvert.

By Definition 4 (whose stability is guaranteed by Theorem 2 in Chen et al. [6]), each firm f∈Ff \in F receives under μFi\mu_F^i its ii-th preferred stable set of workers μ(f)(i)\mu(f)^{(i)}. Since preferences are strict and aligned with the lattice operations under strong substitutability, a cycle σ\sigma has been eliminated at μFi\mu_F^i (that is, σ∈S(μFi)\sigma\in S(\mu_F^i)) if and only if the number of stable matchings that dominate the execution of σ\sigma is strictly less than ii.

Indeed, if nσ<in_\sigma< i, there are fewer than ii stable matchings in which σ\sigma remains uneliminated; thus, across the sorted list of NN stable assignments, every agent involved in σ\sigma must have already traversed the transition induced by σ\sigma before or at their ii-th choice, implying σ∈S(μFi)\sigma\in S(\mu_F^i). Conversely, if nσ≥in_\sigma\ge i, there are at least ii stable matchings where σ\sigma has not yet been executed, which means that at the ii-th preferred stable outcome for firms, the cycle σ\sigma has not been eliminated, so σ∉S(μFi)\sigma\notin S(\mu_F^i).

Consequently, a cycle σ\sigma is eliminated in μFi\mu_F^i precisely when nσ<in_\sigma< i. This establishes that S(μFi)S(\mu_F^i) and S(i)S(i) contain the exact same cycles and, therefore, S(μFi)=S(i)S(\mu_F^i) = S(i).

Conclusion

In this paper, we have established a combinatorial characterization of quantile stable matchings in two-sided many-to-many matching markets where agents’ preferences satisfy strong substitutability and the law of aggregate demand. By relying exclusively on the notion of cycles in preferences and their induced precedence order, we demonstrate that each quantile stable matching is uniquely determined by the elimination of a closed set of cycles, identified via an ideal-counting condition.

This characterization extends the classic rotation-based framework of Cheng [8] from one-to-one markets to many-to-many environments without imposing artificial chain structures on individual agents. Importantly, it reveals that the compromise matchings across the entire distributive lattice are fully encoded within the poset of preference cycles, bypassing the need for exhaustive outcome enumeration or agent-by-agent partner sorting.

A remark on computational complexity is in order. In many-to-many markets, dealing with preferences over sets of partners requires access to a choice oracle, as in Bonifacio et al. [5]. Even with such an oracle, computing exact quantile stable matchings is computationally demanding, as the underlying problem of counting ideals in a poset is known to be #P-complete (Irving and Leather [11]; Cheng [8]). Whether this cycle-based framework can facilitate efficient approximations or heuristics for compromise stable matchings remains an interesting open question.

Beyond computational aspects, our combinatorial identification of quantile stable matchings also provides an operational tool for mechanism designers evaluating the balance between fairness and incentive compatibility. While quantile stable matchings offer appealing egalitarian compromises, recent findings by Arribillaga and Pepa Risma [2] demonstrate that any non-extremal quantile mechanism becomes susceptible to obvious manipulations when contractual terms are present. Understanding how our structural cycle representation interacts with strategic bidding, manipulation incentives, or constrained choice domains constitutes a natural avenue for future research.

Appendix: The Preference Reduction Procedure

Given a strongly substitutable preference profile and two Blair-comparable (for the firms) stable matchings, this reduction procedure generates a new preference profile in which the most Blair-preferred stable matching is the firm-optimal matching and the least Blair-preferred stable matching is the worker-optimal matching, for the market identified with this new preference profile (Bonifacio et al. [5]). The reduction procedure is described as follows.

Let μ\mu and μ~\tilde{\mu} be stable matchings such that μ≥Fμ~\mu\ge_F \tilde{\mu}.

Step 1: (a) For each f∈Ff \in F, each W′⊆WW' \subseteq W such that W′>fμ(f)W' >_f \mu(f), and each w~∈W′∖μ(f)\tilde{w} \in W' \setminus\mu(f), remove each W~⊆W\widetilde{W} \subseteq W such that w~∈W~\tilde{w} \in\widetilde{W} from ff’s list of acceptable sets of workers.

(b) For each w∈Ww \in W, each F′⊆FF' \subseteq F such that F′>wμ~(w)F' >_w \tilde{\mu}(w), and each f~∈F′∖μ~(w)\tilde{f} \in F' \setminus\tilde{\mu}(w), remove each F~⊆F\widetilde{F} \subseteq F such that f~∈F~\tilde{f} \in\widetilde{F} from ww’s list of acceptable sets of firms.

Step 2: (a) For each f∈Ff \in F, each W′⊆WW' \subseteq W such that μ~(f)>fW′\tilde{\mu}(f) >_f W', and each w~∈W′∖μ~(f)\tilde{w} \in W' \setminus\tilde{\mu}(f), remove each W~⊆W\widetilde{W} \subseteq W such that w~∈W~\tilde{w} \in\widetilde{W} from ff’s list of acceptable sets of workers.

(b) For each w∈Ww \in W, each F′⊆FF' \subseteq F such that μ(w)>wF′\mu(w) >_w F', and each f~∈F′∖μ(w)\tilde{f} \in F' \setminus\mu(w), remove each F~⊆F\widetilde{F} \subseteq F such that f~∈F~\tilde{f} \in\widetilde{F} from ww’s list of acceptable sets of firms.

Step 3: After Steps 1 and 2 are performed, if ff is not acceptable for ww (that is, if {f}\{f\} is not on ww’s preference list as now modified), remove each W′⊆WW' \subseteq W such that w∈W′w \in W' from ff’s list of acceptable sets of workers. If ww is not acceptable for ff (that is, if {w}\{w\} is not on ff’s preference list as now modified), remove each F′⊆FF' \subseteq F such that f∈F′f \in F' from ww’s list of acceptable sets of firms.

The profile obtained by this procedure is called the reduced preference profile with respect to μ\mu and μ~\tilde{\mu}, and is denoted by Pμμ~P^{\mu\tilde{\mu}}. When μ~=μW\tilde{\mu} = \mu_W, the profile is simply called the reduced preference profile with respect to μ\mu, and is denoted by PμP^\mu.

References

  1. [1]Alkan, A. (2002): “A class of multipartner matching markets with a strong lattice structure,” Economic Theory, 19, 737–746.DOI
  2. [2]Arribillaga, R. P. and E. Pepa Risma (2025): “A Note on Obvious Manipulations of Quantile Stable Mechanisms,” arXiv preprint arXiv:2503.11821.arxiv.org/abs/2503.11821
  3. [3]Birkhoff, G. (1940): Lattice theory, vol. 25, American Mathematical Soc.DOI
  4. [4]Blair, C. (1988): “The lattice structure of the set of stable matchings with multiple partners,” Mathematics of Operations Research, 13, 619–628.DOI
  5. [5]Bonifacio, A. G., N. Juarez, P. Neme, and J. Oviedo (2022): “Cycles to compute the full set of many-to-many stable matchings,” Mathematical Social Sciences, 117, 20–29.DOI
  6. [6]Chen, P., M. Egesdal, M. Pycia, and M. B. Yenmez (2016): “Median Stable Match-ings in Two-Sided Markets,” Games and Economic Behavior, 97, 64–69.
  7. [8]Cheng, C. T. (2008): “The Generalized Median Stable Matchings: Finding Them Is Not That Easy,” Theoretical Computer Science, 393, 184–192.DOI
  8. [9]Echenique, F. and J. Oviedo (2006): “A theory of stability in many-to-many match-ing markets,” Theoretical Economics, 1, 233–273.
  9. [10]Gale, D. and L. Shapley (1962): “College admissions and the stability of marriage,” The American Mathematical Monthly, 69, 9–15.
  10. [11]Irving, R. and P. Leather (1986): “The complexity of counting stable marriages,” SIAM Journal on Computing, 15, 655–667.DOI
  11. [12]Kelso, A. and V. Crawford (1982): “Job matching, coalition formation, and gross substitutes,” Econometrica, 50, 1483–1504.
  12. [13]Klaus, B. and F. Klijn (2006): “Median stable matching mechanisms,” International Journal of Game Theory, 34, 411–424.
  13. [14]Roth, A. and M. Sotomayor (1990): Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press.
  14. [15]Teo, C. and J. Sethuraman (1998): “The geometry of fractional stable matchings and its applications,” Mathematics of Operations Research, 23, 874–891.DOI

Paper details

vlnc:W_b7ayjkkf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Economics, Econometrics and Finance

Not recorded for this paper

View statement
Looking for related papers…
Contents