Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

Imagine you are organizing a massive, chaotic university course registration system, but with a twist: it's not just students picking classes; it's also professors picking students, and both sides have strict rules about how many people they must have to make the arrangement work.

This paper tackles a complex puzzle called "Many-to-Many Matching with Ties and Minimum Requirements."

Here is the breakdown of the problem and the solution, explained through the lens of a University Course Registration Crisis.

The Setup: The Chaos of Registration

Imagine a university with two groups: Students (Group A) and Courses (Group B).

The "Many-to-Many" Rule: A student can take multiple courses, and a course can have multiple students.
The "Quotas" (The Rules):
- Upper Quota: A course can only hold 30 students. A student can only take 5 courses.
- Lower Quota (The Critical Part): This is the tricky bit. Some courses must have at least 10 students to run, or the department cancels them. Some students must take at least 3 courses to graduate. If a course or student doesn't get their minimum number, they are "deficient" (in trouble).
The "Ties" (The Indifference): Students don't always have a strict "1st, 2nd, 3rd" choice. They might say, "I love Math and Physics equally; I don't care which one I get first." This is a tie.

The Goal: We need to assign students to courses such that:

Criticality: We save as many "lives" as possible. If we can't satisfy everyone's minimum requirement, we want to minimize the number of people who fail to meet their minimum.
Stability: No student and course should be able to say, "Hey, we both prefer each other over our current partners, let's switch!"

The Problem: The Impossible Dream

The authors discovered that in this messy world of "minimum requirements" and "indifferent ties," a perfect solution might not exist.

You might have a scenario where satisfying the minimum requirements (Criticality) forces you to create a situation where a student and a course hate their current matches and want to swap (Instability).
Conversely, forcing a "perfectly stable" match might leave a student with only 1 course when they need 3 to graduate.

It's like trying to seat guests at a wedding where some tables must have 6 people to stay open, but the guests are picky and some don't care who they sit with. Sometimes, you can't make everyone happy and keep all tables open simultaneously.

The Solution: "Relaxed Stability"

Since a perfect match is impossible, the authors introduce a concept called Relaxed Stability.

Think of this as a "Safety Valve" or a "Grace Period."

In a standard stable match, if a student and a course want to swap, the system says, "No, that's not allowed."
In Relaxed Stability, the system says:

"Okay, you two want to swap? That's fine, UNLESS the person you are currently matched with is already in trouble (deficient)."

The Analogy:
Imagine a student, Alice, is currently in a "Survival Mode" course (she only has 1 credit, but needs 3). She wants to swap to a "Dream Course" with Bob.

Standard Stability: "No! You can't leave your current course because it's unstable." (But this might leave her with 0 credits).
Relaxed Stability: "Wait, your current course is already struggling (it has too few students). If you leave, that course might die. So, we allow you to stay put to save the course, even if you prefer the other one."

The algorithm essentially says: "We will allow some 'unhappy' pairs to exist, but only if breaking that pair would hurt someone who is already failing to meet their minimum requirements."

The Algorithm: The "Proposal Party"

How do they find this solution? They use a clever, step-by-step game called a Proposal Algorithm (an evolution of the famous Gale-Shapley algorithm).

Imagine a dance floor where students propose to courses. But this dance has three distinct phases:

Phase 1: The "Survival" Dance (Levels 0 to $t-1$ )
- Students only propose to courses that are in "Survival Mode" (courses that desperately need students).
- The goal here is purely to fill the Minimum Quotas. We ignore preferences for a moment and just make sure no one starves.
Phase 2: The "Tie-Breaker" Dance (Level $t$ )
- Now that everyone has a fighting chance at survival, we look at the Preferences.
- This is where the "Ties" come in. Since students might be indifferent between two courses, the algorithm uses a trick called "Uncertain Proposals."
- Metaphor: Imagine a student is undecided between Course X and Course Y. They propose to both, but they tell the courses, "I'm not 100% sure yet, I might switch if a better option opens up." This flexibility allows the system to find a larger, better match without getting stuck.
Phase 3: The "Last Resort" Dance (Levels $t+1$ to end)
- If a student is still failing to meet their minimum requirements after the first two phases, they get a second chance. They keep proposing to anyone left, trying to fill their quota.

The Result: The "Good Enough" Guarantee

The paper proves two amazing things:

Existence: A solution that is both Critical (minimizes failures) and Relaxed-Stable (no "unjustified" swaps) always exists. You never have to give up; there is always a valid arrangement.
Efficiency: Finding the absolute best (largest) solution is mathematically impossible to do quickly (it's NP-hard). However, their algorithm finds a solution that is guaranteed to be at least 2/3 as good as the best possible solution.

The 2/3 Metaphor:
Imagine the "Perfect World" has 100 happy students. The "Impossible World" (NP-hard) says we can't find that 100.
This algorithm says: "Don't worry, I can guarantee you 67 happy students (2/3 of 100) in a reasonable amount of time, and I promise the arrangement is stable enough that no one has a valid reason to complain."

Why This Matters

This isn't just about math; it applies to real life:

Hospitals: Assigning residents to rural hospitals that must have a minimum number of doctors to stay open.
Schools: Assigning students to classes where some classes need a minimum enrollment to run.
Work: Assigning workers to projects where teams need a minimum size to function.

The authors built a tool that ensures we don't leave people behind (Criticality) while keeping the system fair enough that no one has a legitimate reason to revolt (Relaxed Stability), even when people are indecisive (Ties).

Here is a detailed technical summary of the paper "Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting."

1. Problem Definition

The paper addresses the Many-to-Many Bipartite Matching Problem under a complex set of constraints that generalize several existing models (Stable Marriage, Hospital/Residents, and standard Many-to-Many matching).

Input: A bipartite graph $G = (A \cup B, E)$ .
Preferences: Each vertex has a preference list over its neighbors. These lists may contain ties (indifference between neighbors).
Quotas:
- Upper Quota ( $q^+(u)$ ): The maximum number of partners a vertex can accept.
- Lower Quota ( $q^-(u)$ ): The minimum number of partners a vertex must accept. Vertices with $q^-(u) > 0$ are called lq-vertices.
Critical Matching: A matching is critical if it minimizes the total deficiency (the sum of $q^-(u) - |M(u)|$ for all vertices where the quota is not met). If a feasible matching (deficiency = 0) does not exist, the goal is to find a matching that satisfies lower quotas to the maximum possible extent.
Optimality Notions:
- Stability (Weak): A matching is stable if no pair $(a, b)$ exists such that both strictly prefer each other over their current partners (or are unmatched).
- Relaxed Stability: A relaxation introduced to handle cases where strict stability is impossible due to lower quotas. A blocking pair is "justified" (and thus ignored) if the vertex causing the block is fully subscribed and its current partners are not "surplus" (i.e., they are needed to meet lower quotas).

The Core Challenge:
The paper investigates the existence and computation of a matching that is both Critical and Relaxed-Stable (CRITICAL-RSM).

It is known that a matching that is both Critical and Weakly Stable may not exist.
Even without lower quotas, finding a maximum-size stable matching with ties is NP-hard.
The authors prove that deciding if a Critical and Weakly Stable matching exists is NP-complete in this setting.

2. Methodology

The authors propose a polynomial-time algorithm that combines two distinct frameworks:

Király's Algorithm (2013): Adapted for the Many-to-Many setting to handle ties and achieve a $2/3$-approximation for maximum-size stable matchings.
Multi-Level Proposal Framework (Nasre et al., 2024): Adapted for lower quotas to ensure criticality.

Key Algorithmic Components

The algorithm operates in a proposal-based manner where vertices in set $A$ propose to vertices in set $B$ . It utilizes a level-based structure ranging from $0 $to$ s+t $(where$ s $and$ t $are the sums of lower quotas for$ A $and$ B$, respectively).

Phase 1 (Levels $0 $to$ t-1$): Ensuring B-Criticality
- Vertices in $A$ propose only to lq-vertices in $B$ .
- This ensures that the lower quotas of $B$ are satisfied as much as possible before considering general preferences.
- Vertices in $B$ have restricted capacities ( $q^-$ ) during these levels.
Phase 2 (Level $t$ ): Handling Ties (Király's Step)
- Vertices in $A$ propose to all neighbors using their original preference lists (which may contain ties).
- Uncertain Proposals: The algorithm introduces the concept of "uncertain proposals" to handle ties. If a vertex $a$ proposes to a tied neighbor $b$ , the proposal is labeled "uncertain" if there is another tied neighbor $b'$ that is under-subscribed.
- Favorite Neighbor: A mechanism to uniquely select a neighbor among ties based on indices and subscription status.
- $\ast$ Status: If a vertex exhausts its list at level $t$ , it attains a special $\ast$ status (effectively improving its rank infinitesimally) and restarts proposing from the beginning of its list at a sub-level $t^*$ . This step resolves blocking pairs caused by ties.
Phase 3 (Levels $t+1$ to $s+t$ ): Ensuring A-Criticality
- If vertices in $A$ remain deficient (below their lower quota) after Phase 2, they raise their levels.
- They propose to all neighbors again, but with strict preference lists (ties broken by index).
- Vertices in $B$ prioritize higher-level proposers.
- This phase ensures that the lower quotas of $A$ are satisfied as much as possible.

Technical Refinements

Refined Uncertain Proposal: The authors identify and fix a technical flaw in Király's original definition of uncertain proposals (which required the proposer to be fully subscribed). They generalize this to the many-to-many setting where a vertex can be involved in multiple uncertain proposals simultaneously.
Cloned Graph Construction: To prove correctness, the authors construct a "cloned graph" $G_M$ where each vertex is replicated according to its quotas. This transforms the many-to-many problem into a one-to-one problem, allowing the use of alternating path arguments to prove criticality and relaxed stability.

3. Key Contributions

Generalization of Relaxed Stability: The paper extends the notion of relaxed stability (previously studied in one-to-one or many-to-one settings) to the Many-to-Many setting with ties on both sides and lower quotas on both sides.
Existence Proof: The authors prove that a Critical Relaxed-Stable Matching (CRITICAL-RSM) always exists in this generalized setting.
Approximation Algorithm: They present a polynomial-time algorithm that computes a CRITICAL-RSM with a size guarantee of $2/3$ of the maximum possible size of such a matching.
Hardness Results:
- Proved that finding a matching that is both Critical and Weakly Stable is NP-complete.
- Proved that computing a maximum-size CRITICAL-RSM is NP-hard.
Algorithmic Improvements: Refined the definition of "uncertain proposals" and "favorite neighbors" to handle the complexities of the many-to-many setting, correcting issues in prior work by Király.

4. Results

Theorem 1: For any bipartite graph with lower quotas and ties, a critical relaxed-stable matching exists. Furthermore, there exists a polynomial-time algorithm to compute a $2/3$-approximation to the maximum-size critical relaxed-stable matching.
Tightness: The approximation factor of $2/3 $is tight. Under the **Small Set Expansion Hypothesis**, it is impossible to achieve a$ (2/3 + \epsilon)$-approximation for the maximum-size stable matching with ties, even without lower quotas. Since the authors' setting generalizes that problem, their bound is optimal.
Running Time: The algorithm runs in $O(m^2)$ time, where $m$ is the number of edges.

5. Significance

Theoretical Advancement: This work bridges a significant gap in matching theory by unifying three difficult constraints: Many-to-Many capacity, Ties, and Lower Quotas. Previous works typically addressed only one or two of these simultaneously.
Practical Applicability: The model directly applies to real-world scenarios like:
- Student-Course Allocation: Where students need a minimum number of courses, and courses need a minimum number of students, and students may be indifferent between courses.
- Worker-Firm Assignment: Where firms need minimum staff, and workers have minimum job requirements, with potential ties in preferences.
Robustness: By introducing "Relaxed Stability," the paper provides a viable solution path for scenarios where strict stability is mathematically impossible due to conflicting lower quotas. It guarantees that the resulting matching is as stable as possible while maximizing the satisfaction of critical lower quotas.
Algorithmic Framework: The combination of the multi-level proposal framework with Király's tie-handling mechanism provides a robust template for future research in constrained matching problems.