Non-uniformly Stable Common Independent Sets

Xin DuarXiv 2026 · DOI · arXiv

TL;DR

This paper provides a polynomial-time algorithm to solve a highly generalized version of the stable matching problem. By moving from simple bipartite graphs to the abstract world of matroids and allowing for ties in preferences, the author creates a unified framework for finding "non-uniformly stable" sets—a hybrid stability condition that encompasses both super-stability and strong stability.

What Problem Does This Paper Address?

The classic "Stable Matching Problem" (think: matching medical residents to hospitals) assumes everyone has a strict ranking of their choices. In the real world, people are often indifferent between options—they have ties in their preferences. Furthermore, while matching is usually visualized as a graph, many complex resource-allocation problems are better modeled using matroids, a mathematical structure that generalizes the concept of linear independence.

Previous research has tackled stability with ties in specific scenarios (like one-to-one or many-to-one matching) or under specific stability definitions (like "strong" or "super" stability). However, a gap remained: how do we handle a "non-uniform" stability condition—where different groups of agents might require different levels of stability—within the broad framework of matroid theory? This paper addresses the challenge of efficiently checking if such a stable set exists and finding it if it does.

Methods

The author proposes a novel polynomial-time algorithm (Algorithm 4) to identify a non-uniformly stable common independent set of two matroids.

Key technical components include:

  • Matroid Generalization: Instead of matching edges in a graph, the algorithm works with "common independent sets" of two matroids ($M_D$ and $M_H$).
  • Stability Definitions: The paper redefines "blocking" (the condition that breaks stability) using matroid closure operators ($\text{cl}$) and fundamental circuits. This allows the algorithm to "see" when an element outside the current set could be added to create a more preferred, stable configuration.
  • Iterative Subroutines: The main algorithm relies on three specialized subroutines (Algorithms 1, 2, and 3) that construct auxiliary matroid structures based on the preference hierarchies and the current candidate set.
  • Existence Checking: The algorithm doesn't just search; it systematically refines the set of available elements. If it hits a contradiction (a "bad element" that cannot be resolved), it correctly concludes that no such stable set exists.

Datasets

Not discussed in the paper. As a theoretical work in discrete mathematics and computer science, the paper focuses on algorithmic proofs and complexity analysis rather than empirical testing on datasets.

Key Insights and Ideas

  • The Power of Non-Uniformity: Stability isn't one-size-fits-all. By defining "non-uniform stability," the author allows for a hybrid model where some agents follow "super-stability" rules (very strict) and others follow "strong stability" rules. This makes the model much more flexible for real-world applications.
  • Matroids as a Universal Language: By proving these results for matroids, the author ensures the algorithm works for any problem that fits the matroid intersection framework, such as matching with hierarchical capacity constraints or complex scheduling.
  • Tractability of Ties: While many problems involving ties in preferences quickly become NP-hard, this paper identifies a specific, sophisticated stability condition that remains solvable in polynomial time.
  • Circuit-Based Logic: A major "aha moment" in the proof involves using the properties of matroid circuits to show that if a stable set exists, the algorithm's iterative pruning won't accidentally discard it.

Key Results

  • Theorem 1: The primary result is the proof that Algorithm 4 is correct. It will find a non-uniformly stable common independent set if one exists, and output "No" otherwise.
  • Polynomial Complexity: The algorithm is guaranteed to run in polynomial time relative to the number of elements and the time required for matroid independence oracles. This is a significant result given the complexity of the stability conditions involved.
  • Generalization: The work successfully unifies and extends several previous papers that handled super-stability, strong stability, and matroid matching as separate, isolated cases.

Limitations and Future Work

  • Two-Matroid Limit: The algorithm is designed for the intersection of two matroids. Finding common independent sets for three or more matroids is a famously NP-hard problem, so extending this to "multi-way" stable matching remains a major hurdle.
  • Structural Properties: While the paper finds a stable set, it doesn't explore the global structure of all such sets. In simpler stable matching, the solutions form a "lattice" (a specific mathematical structure); it is currently unknown if non-uniformly stable matroid sets share this property.
  • Optimization: The paper focuses on feasibility (finding any stable set). Future work could look at finding an optimal stable set (e.g., one with maximum size or minimum weight).

Summary updated

Abstract

In this paper, we consider a matroid generalization of the stable matching problem. In particular, we consider the setting where preferences may contain ties. For this generalization, we propose a polynomial-time algorithm for the problem of checking the existence of a common independent set satisfying non-uniform stability, which is a common generalization of super-stability and strong stability.
BibTeX
@misc{du2026non,
  author = {Xin Du},
  title = {{Non-uniformly Stable Common Independent Sets}},
  year = {2026},
  eprint = {2601.11153},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.11153},
}

Loading related content...

Figure