Abstract
We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algorithm can make queries to reveal information about the preferences of the agents in B. We examine three query models: comparison queries, interviews, and set queries. Using competitive analysis, our aim is to design algorithms that minimize the number of queries required to solve the problem of finding a stable matching or verifying that a given matching is stable (or stable and optimal for the agents of one side). We present various upper and lower bounds on the best possible competitive ratio as well as results regarding the complexity of the offline problem of determining the optimal query set given full information.
Introduction
The classic Stable Marriage Problem, introduced by Gale and Shapley, is a cornerstone of algorithmic mechanism design. It assumes a "God's eye view" where all preference lists are known upfront. However, in practical applications—such as matching students to mentors or residents to hospitals—eliciting these preferences is often the most significant bottleneck. Ranking a large number of candidates is cognitively demanding and time-consuming.
This research addresses the problem of one-sided uncertainty. In this model, the preferences of Group A (e.g., students) are fully known, while the preferences of Group B (e.g., mentors) are hidden and must be queried. The objective is query minimization: finding a stable matching while asking the fewest possible questions.
Query Models and Competitive Analysis
To quantify the efficiency of different approaches, the authors employ competitive analysis. This compares the number of queries an algorithm makes against an "offline optimum"—the absolute minimum number of queries a prover would need to verify a matching if they already knew the hidden preferences.
The study investigates three distinct query mechanisms:
- Comparison Queries: Asking a member of Group B to compare two specific candidates (e.g., "Mentor $b$, do you prefer student $a_1$ or $a_2$?").
- Set Queries: Asking a member of Group B to identify their favorite candidate from a specific subset.
- Interview Queries: A sequential model where an interview reveals a candidate's rank relative only to those already interviewed.
The Price of Favoritism: A-Optimality vs. B-Optimality
A central finding of the paper is the stark difference in complexity between favoring the side with known preferences versus the side with hidden preferences.
The Efficiency of A-Optimality
When the goal is to find an A-optimal matching (the stable matching most preferred by Group A), the problem is surprisingly tractable. The authors demonstrate that a modified version of the standard Gale-Shapley algorithm is 1-competitive. This means that to find and prove an A-optimal matching, the algorithm makes exactly the same number of queries as an omniscient prover would need to verify it. In essence, there is no "search penalty" when favoring the side whose preferences are already known.
The B-Optimal Bottleneck
Conversely, finding a B-optimal matching—which favors the side with hidden preferences—is significantly more expensive. In the comparison and interview query models, any algorithm is at best $\Omega(n)$-competitive.
This disparity arises because verifying B-optimality requires exploring "rotations"—cycles of potential partner swaps that could lead to a different stable matching. Without knowing Group B's preferences, an algorithm must exhaustively query to ensure no such rotations exist that would benefit Group B, leading to a linear blow-up in the competitive ratio relative to the offline optimum.
The Power of Set Queries
The research highlights that the choice of query model fundamentally changes the complexity landscape. While comparison queries are limited, Set Queries act as a powerful tool for information retrieval. By allowing an algorithm to ask for the best candidate in a group, it can perform a form of binary search over the preference lists. This reduces the competitive ratio for verifying B-optimality from $O(n)$ down to $O(\log n)$.
Computational Complexity of Verification
Beyond the competitive ratios, the paper explores the Offline Query Minimization problem: given full information, what is the smallest set of queries needed to prove a matching is stable? The authors prove that this problem is NP-hard across all three query models. This suggests that even with perfect information, finding the most efficient way to "convince" an observer of a matching's stability is computationally difficult.
Conclusion and Future Directions
This work establishes a rigorous framework for matching under uncertainty, revealing that the "price of favoritism" is a fundamental hurdle in preference elicitation. While A-optimal matchings can be found with optimal efficiency, B-optimal matchings require significantly more information exchange.
Future research directions include expanding the search algorithms to scenarios with two-sided uncertainty, closing the gap between verification and discovery in the set query model, and investigating top-k queries to bridge the gap between simple comparisons and full set queries.
Summary updated