Abstract
Recently, research has initiated work on understanding the structural relationships between the lattices of solutions of two "nearby" instances of the stable matching problem. While previous work restricted changes between instances to simple upward shifts in preference, this paper allows for any one agent to permute their preference list arbitrarily. We prove that the matchings remaining stable across both instances form a sublattice of the original stable matching lattices. This structural insight allows for a polynomial-time algorithm to identify robust stable matchings and reconstruct the partial order of the underlying sublattice, as per Birkhoff’s Representation Theorem. These results offer new perspectives on the incentive compatibility of the Gale-Shapley algorithm and the broader problem of robust matching.
Introduction
The stable matching problem—famously solved by the Gale-Shapley algorithm—is a cornerstone of algorithmic game theory, used to match doctors to hospitals, students to schools, and organ donors to recipients. Traditionally, these models assume that preference lists are fixed and accurately reported. However, in real-world scenarios, preference data may be noisy, or agents may strategically manipulate their lists to achieve better outcomes.
This paper addresses the challenge of finding "robust" stable matchings: solutions that remain stable even when an agent’s preferences are altered. While prior research focused on minor "upward shifts" in preferences, this work generalizes the problem to accommodate arbitrary permutations of an agent's preference list, seeking to characterize the structural relationship between the original and modified sets of stable matchings.
Theoretical Framework: Generalizing Birkhoff
To solve the robustness problem, the authors bridge abstract lattice theory with algorithmic matching through three key pillars:
1. Birkhoff’s Representation Theorem
Birkhoff’s Theorem states that every finite distributive lattice is isomorphic to the lattice of closed sets of a partial order (poset). In the context of stable matching, the set of all stable matchings forms a distributive lattice, where the underlying poset is composed of "rotations"—cyclic changes that move from one stable matching to another.
2. Poset Compressions
The authors introduce a novel operation called "poset compression." This operation partitions the elements of a poset into "meta-elements" and defines new precedence rules between them. The paper proves a fundamental one-to-one correspondence between these compressions and the sublattices of the original lattice. This provides a formal mechanism to describe how a subset of matchings (those that remain stable after a preference change) relates to the original set.
3. Structural Characterization
The research analyzes two specific settings. Setting I involves a lattice partitioned into two sublattices. Setting II, which is more complex and relevant to arbitrary preference permutations, occurs when a lattice is partitioned into a sublattice and a join-semi-sublattice. The authors prove that when one agent permutes their list, the matchings stable in both the old and new instances ($M_A \cap M_B$) form a sublattice, while those lost ($M_A \setminus M_B$) form a join-semi-sublattice.
The FindBouquet Algorithm
Building on these structural proofs, the authors develop the FindBouquet algorithm. This polynomial-time algorithm uses a "membership oracle" to identify the specific compression that generates the sublattice of robust matchings.
Crucially, the algorithm does more than just find a single robust matching; it identifies the entire partial order that generates the sublattice. This allows researchers to generate all matchings that remain stable across the "error" instances. While finding matchings stable across errors on both sides of the market naively leads to exponential runtimes, this structural approach maintains polynomial efficiency for the "fully robust" case involving a single agent's permutations.
Implications for Incentive Compatibility
A significant application of this work lies in the study of the Gale-Shapley Deferred Acceptance Algorithm. The results provide new tools to analyze how agents might manipulate their preference lists. For instance, a dominant firm might manipulate its list to find a matching that is stable for everyone else's true preferences but more favorable to itself. Because the resulting matching is "robustly" stable, such manipulation might remain undetected by other agents or a central clearinghouse.
Conclusion and Future Directions
This paper provides a powerful generalization of Birkhoff’s Theorem, turning an abstract algebraic property into a practical algorithmic tool for robust matching. However, several challenges remain:
- Probabilistic Robustness: The current model is binary (a matching is either stable or not). Future work could address matchings that maximize the probability of stability given a distribution of preference errors.
- Multiple Manipulators: The current study is limited to changes by a single agent. Extending these results to coalitions of agents remains an open problem.
- Broader Models: Applying these structural insights to the "Stable Roommates" problem or matchings with incomplete preference lists could further expand the utility of poset compressions in market design.
Summary updated