On a stable partnership problem with integer choice functions

This paper generalizes the stable roommates and non-bipartite stable allocation problems by introducing the stable partnership problem with integer choice functions (SPPIC), for which the authors establish a solvability criterion and develop an algorithm that either finds a stable partnership or canonically certifies its non-existence via a set of pairwise edge-disjoint odd cycles.

The Gist

Imagine you are the organizer of a massive, chaotic networking event. You have a group of people (let's call them "Agents") and a list of potential connections they can make. In a perfect world, everyone would find a partner they love, and no one would want to switch partners. This is the classic "Stable Marriage" problem, but usually, that only works if you have two distinct groups (like men and women, or students and schools).

The Problem: The "Roommate" Nightmare
Now, imagine the event is a free-for-all. Everyone can pair with anyone. This is the "Stable Roommates" problem. Here's the catch: Sometimes, a perfect, stable solution simply doesn't exist.

Why? Because of "odd cycles."

• The Metaphor: Imagine three friends: Alice, Bob, and Charlie.
  • Alice prefers Bob over Charlie.
  • Bob prefers Charlie over Alice.
  • Charlie prefers Alice over Bob.
  • If you pair Alice and Bob, Charlie is unhappy and wants to switch with Alice. If you pair Bob and Charlie, Alice is unhappy. If you pair Charlie and Alice, Bob is unhappy. They are stuck in a loop. In math terms, this is an "odd cycle" that prevents a stable match.

The Paper's Big Idea: The "Double-World" Trick
The author, Alexander Karzanov, tackles a much harder version of this. Instead of just "yes/no" pairings, imagine people can have multiple connections (like a company hiring several interns, or a person having several business partners), and there are limits (capacities) on how many connections they can handle. Plus, their preferences aren't just a simple list; they are complex rules (Choice Functions).

The paper asks: How do we find a stable arrangement in this messy, non-bipartite world with complex rules?

The Solution: Building a Mirror World
The author's genius move is to build a Mirror World (a mathematical trick called a "symmetric bipartite graph").

1. The Setup: For every person in the real world, he creates two clones in the Mirror World: a "Left-Hand" clone and a "Right-Hand" clone.
2. The Connection: If Alice and Bob can connect in the real world, in the Mirror World, Alice's Left-Hand connects to Bob's Right-Hand, and Bob's Left-Hand connects to Alice's Right-Hand.
3. The Magic: In this Mirror World, the rules are much nicer. We know that a stable solution always exists here. It's like turning a chaotic free-for-all into a structured dance where everyone has a partner.

The "Rotation" Dance
In the Mirror World, the author uses a concept called Rotations. Think of a rotation as a specific dance move where a group of people swap partners to get a better deal.

• The author maps out all possible dance moves (rotations) and organizes them into a hierarchy (a "poset").
• He then looks for a special kind of dance move called a Singular Rotation.
  • The Metaphor: A singular rotation is a dance move that is its own mirror image. It's a loop that looks exactly the same when you flip it.
  • The Catch: If the "weight" (the number of swaps needed) of this singular dance move is odd, it creates a problem. It's the mathematical equivalent of that Alice-Bob-Charlie loop.

The Final Verdict: The "Half-Partnership"
The paper provides an algorithm that does two things:

1. If there are no "Odd Singular Rotations": Great! The Mirror World's solution translates perfectly back to the real world. Everyone gets a stable set of partners.
2. If there ARE "Odd Singular Rotations": A perfect stable solution is impossible. The odd cycles are the "obstacles."
   • The Creative Solution: Instead of giving up, the author constructs a "Half-Partnership."
   • The Metaphor: Imagine the people in the odd cycle can't fully agree. So, they agree to a "compromise." They form a stable arrangement everywhere else, but for the people in the odd cycle, they accept a slightly imperfect state where they are "almost" matched.
   • The algorithm identifies exactly which groups of people (the odd cycles) are causing the trouble. It tells you: "You can't fix this specific loop, but here is the best possible stable arrangement for everyone else, and here is the specific list of loops that are blocking perfection."

Why This Matters
This paper is like a master mechanic who, when a car engine (the matching problem) won't start because of a specific broken gear (the odd cycle), doesn't just say "It's broken." Instead, they:

1. Build a perfect model of the engine in a simulation (the Mirror World).
2. Find the exact broken gear in the simulation.
3. Bring the model back to reality and say, "Here is the best way to run the car with that gear broken, and here is exactly which gear is the problem."

It turns a problem that was previously thought to be a dead end into a solvable puzzle, giving us a clear map of where the stability exists and where the "odd loops" prevent it.

Technical Summary

1. Problem Definition: SPPIC

The paper addresses the Stable Partnership Problem with Integer Choice functions (SPPIC). This is a generalization of classical stable assignment problems (like Stable Marriage, Stable Roommates, and Stable Allocation) to non-bipartite graphs with integer capacities and complex preference structures.

• Input:
  • A finite, non-bipartite graph $G = (V, E)$.
  • Non-negative integer edge capacities $b(e) \in \mathbb{Z}_+$ for each edge $e \in E$.
  • For each vertex (agent) $v \in V$, a choice function $C_v$ acting on vectors in the integer box $B_v = \{z \in \mathbb{Z}^{E_v}_+ : z \le b\}$.
• Axioms: The choice functions must satisfy:
  1. Substitutability (SUB): If $z \ge z'$, then $C(z) \wedge z' \le C(z')$.
  2. Size Monotonicity (MON): If $z \ge z'$, then $|C(z)| \ge |C(z')|$.
• Goal: Find a stable partnership (a vector $x \in \mathbb{Z}^E_+$ with $x \le b$) such that no edge is "blocking." An edge is blocking if both endpoints can improve their assignments by increasing the flow on that edge.
• Challenge: Unlike bipartite cases where stable solutions always exist, non-bipartite instances may not have a stable solution (analogous to the Stable Roommates problem).

2. Methodology: Symmetric Reduction and Rotation Analysis

The core methodology involves reducing the non-bipartite problem to a symmetric bipartite problem and analyzing the structure of "rotations" (cycles of improvement) within that bipartite setting.

A. Symmetric Bipartite Reduction

The author constructs a symmetric bipartite graph $G^\diamond = (V^\diamond, E^\diamond)$:

• Vertices: Each $v \in V$ is duplicated into $v_0$ and $v_1$.
• Edges: Each edge $uv \in E$ becomes two edges: $u_0v_1$ and $v_0u_1$.
• Symmetry: Capacities and choice functions are copied naturally.
• Correspondence: A stable partnership $x$ in $G$ corresponds to a symmetric stable vector $\tilde{x}$ in $G^\diamond$ (where $\tilde{x}(u_0v_1) = \tilde{x}(v_0u_1)$).

B. Lattice of Stable Solutions and Rotations

Relying on prior work by Alkan, Gale, and the author ([14]), the set of stable solutions in the bipartite case forms a distributive lattice. The transitions between solutions are governed by rotations (edge-simple cycles).

• Rotations ($R$): Directed cycles where applying the rotation increases the flow on "positive" edges and decreases it on "negative" edges, moving from one stable solution to a "better" one (in the lattice order).
• Poset of Rotations ($\Pi, \prec$): The set of weighted rotations forms a partially ordered set (poset). Stable solutions correspond to closed functions on this poset.

C. The Symmetry Obstacle

The paper analyzes the symmetry operator $\sigma$ on $G^\diamond$ (swapping indices 0 and 1).

• Self-Symmetric (Singular) Rotations: Rotations $R$ such that $R = R^*$ (where $R^*$ is the symmetric image of $R$).
• Key Insight: For a symmetric stable solution to exist, the "weights" of these singular rotations must be even. If a singular rotation has an odd maximal weight, it acts as an obstruction.
• Algorithm QB: The author develops an algorithm to construct a Quasi-Balanced (QB) closed function. This function satisfies the balance condition $\lambda(R) + \lambda(R^*) = \tau_R$ for all non-singular rotations and handles singular rotations by taking floor/ceiling values.

3. Key Contributions and Results

A. Existence of "Half-Partnerships"

The paper proves that while a stable partnership may not exist, a Stable Half-Partnership always exists.

• Definition: A pair $(x, K)$ where:
  • $x$ is an integer vector (partnership).
  • $K$ is a set of pairwise edge-disjoint, edge-simple odd cycles in $G$.
• Properties:
  • If $K = \emptyset$, then $x$ is a stable partnership.
  • If $K \neq \emptyset$, no stable partnership exists.
  • The set $K$ is canonical (unique) for a given instance.
  • The vector $x$ satisfies specific "half-stability" conditions relative to the cycles in $K$ (e.g., agents on the cycle are stable if they consider the cycle edges as "internal" or "external" in specific ways).

B. Structural Theorem (Theorem 5.1)

• Existence: A stable half-partnership $(x, K)$ always exists for any SPPIC instance.
• Uniqueness of Obstacles: The set of odd cycles $K$ is invariant across all stable half-partnerships. This generalizes the concept of "stable partitions" from the boolean Stable Roommates problem to the integer choice function setting.

C. Algorithmic Complexity

• Solvability Criterion: A stable partnership exists if and only if the set of singular rotations with odd weights in the symmetric bipartite reduction is empty.
• Complexity: The algorithm to find $(x, K)$ runs in pseudo-polynomial time (polynomial in $|V|$, $|E|$, and $b_{max}$).
  • It constructs the poset of rotations and the QB-function.
  • If the input choice functions satisfy a "gapless" condition, the complexity improves to weakly polynomial time.
  • If the problem is a relaxation to real-valued assignments (Mixed Type), it can be solved in strongly polynomial time.

4. Significance and Impact

1. Unification of Models: The paper unifies several known stability models (Stable Marriage, Stable Roommates, Stable Allocation, and Alkan-Gale's general model) under a single framework of integer choice functions on non-bipartite graphs.
2. Generalization of Stable Partitions: It extends the famous result by Tan (1991) regarding stable partitions in the Stable Roommates problem (where the "obstacle" is a set of odd cycles) to the much more complex setting of integer capacities and substitutable choice functions.
3. Canonical Obstacles: The paper establishes that the failure of stability in non-bipartite markets is not random but is structurally determined by a unique, canonical set of odd cycles. This provides a clear diagnostic tool for why a stable solution might not exist.
4. Algorithmic Framework: By leveraging the reduction to a symmetric bipartite graph and the theory of rotations, the paper provides a constructive method to either find a solution or prove its non-existence with a certificate (the set $K$).

Summary Conclusion

Alexander V. Karzanov's paper resolves the solvability of the Stable Partnership Problem with Integer Choice Functions (SPPIC) on non-bipartite graphs. By reducing the problem to a symmetric bipartite counterpart and analyzing the parity of weights in singular rotations, the author proves that a stable solution exists if and only if no "odd-weighted" singular rotations obstruct it. In cases where no stable solution exists, the paper provides a canonical structure—a stable half-partnership consisting of a vector and a unique set of odd cycles—that characterizes the instability. This work significantly advances the theory of stable matchings beyond bipartite graphs and boolean constraints.