Abstract
In this paper, we study a slightly different definition of popularity in bipartite graphs $G=(U,W,E)$ with two-sided preferences, when ties are present in the preference lists. This is motivated by the observation that if an agent $u$ is indifferent between his original partner $w$ in matching $M$ and his new partner $w'\ne w$ in matching $N$, then he may probably still prefer to stay with his original partner, as change requires effort, so he votes for $M$ in this case, instead of being indifferent. We show that this alternative definition of popularity, which we call weak-popularity allows us to guarantee the existence of such a matching and also to find a weakly-popular matching in polynomial-time that has size at least $\frac{3}{4}$ the size of the maximum weakly popular matching. We also show that this matching is at least $\frac{4}{5}$ times the size of the maximum (weakly) stable matching, so may provide a more desirable solution than the current best (and tight under certain assumptions) $\frac{2}{3}$-approximation for such a stable matching. We also show that unfortunately, finding a maximum size weakly popular matching is NP-hard, even with one-sided ties and that assuming some complexity theoretic assumptions, the $\frac{3}{4}$-approximation bound is tight. Then, we study a more general model than weak-popularity, where for each edge, we can specify independently for both endpoints the size of improvement the endpoint needs to vote in favor of a new matching $N$. We show that even in this more general model, a so-called $\gamma$-popular matching always exists and that the same positive results still hold. Finally, we define an other, stronger variant of popularity, called super-popularity, where even a weak improvement is enough to vote in favor of a new matching. We show that for this case, even the existence problem is NP-hard.
Introduction
Matching markets, such as assigning residents to hospitals or students to courses, typically prioritize stability—a condition where no two agents would both prefer to abandon their current assignments for each other. While stable matchings ensure fairness, they are often smaller in size than desired. Popular matchings offer a larger alternative by employing a majority-vote rule: a matching is popular if it does not lose a head-to-head majority vote against any other matching. However, when agents have ties in their preferences, popular matchings may not exist, and determining their existence becomes computationally intractable.
This paper introduces weak popularity, a new solution concept that guarantees existence even with ties and delivers significantly larger matchings than traditional stability.
Problem Statement: The Stability-Size Trade-off
In markets with ties (where an agent might be indifferent between two options), two primary challenges emerge:
- Computational Complexity of Stability: Finding the maximum-size stable matching is NP-hard, making exact solutions impractical for large-scale applications.
- Fragility of Popularity: The standard definition of popularity is often too restrictive. With ties, a majority-rule winner frequently fails to exist.
The authors address these issues by defining weak popularity. In this model, agents are assumed to have a slight bias toward the status quo; they only vote for a new matching if it offers a strict improvement over their current partner. If an alternative is only "equally good," they vote to stay. This subtle shift ensures that a weakly popular matching always exists and can be found efficiently.
Methodology
The researchers developed several algorithmic and theoretical tools:
- Edge Duplication and Gale-Shapley: To approximate the largest weakly popular matching, the authors transform the original bipartite graph by creating multiple "types" of edge copies. They then apply a modified Gale-Shapley algorithm to this expanded graph.
- $\gamma$-Popularity Generalization: The authors extend the concept to a more general model called $\gamma$-popularity, where the required "improvement threshold" for a vote can be specified independently for each agent and edge. They prove that $\gamma$-popular matchings always exist and share the same positive approximation properties as weakly popular ones.
- Approximation Bounds: The proposed algorithm achieves a $3/4$-approximation ratio for the maximum-size weakly popular matching. Furthermore, the resulting matching is guaranteed to be at least $4/5$ the size of the maximum stable matching, outperforming the current best $2/3$-approximation for stable matchings.
- Exact Computation: For scenarios requiring optimality, the authors provide an Integer Linear Programming (ILP) formulation. A refined version, MWP-MinBP, maximizes size while minimizing the number of "blocking pairs" to maintain near-stability.
Experimental Evaluation
The algorithms were tested on two main datasets:
- Synthetic Random Instances: Bipartite graphs with varying tie densities (0% to 100%) and preference list lengths were used to assess scalability and performance.
- SFAS Dataset: Real-world data from the Scottish Foundation Allocation Scheme (2005–2008), involving medical graduate assignments. This dataset is notable for its high density of ties in program preferences.
Key Results: * Increased Matching Size: In the SFAS data, weakly popular matchings were consistently larger than stable ones, matching up to 10% more agents. * Near-Optimal Performance: Although theoretically a $3/4$-approximation, the algorithm often found the absolute maximum-size matching or came within 1-2% of it in practice. * Social Acceptability: Weakly popular matchings exhibited very few blocking edges—averaging less than one per agent—suggesting they remain socially acceptable despite not being strictly stable.
Theoretical Insights and Limitations
- Hardness Results: Finding the absolute maximum-size weakly popular matching is NP-hard, even with one-sided ties. The authors also explored Super Popularity (where agents switch for any non-inferior option) and found that even determining the existence of such a matching is NP-hard.
- Tightness of Bounds: Under standard complexity-theoretic assumptions (e.g., the Unique Games Conjecture), the $3/4$ approximation bound for weak popularity is shown to be tight.
- Future Work: The current study is limited to bipartite graphs. Extending these concepts to general graphs (e.g., the "Stable Roommates" problem) and resolving the complexity of one-sided ties in super popularity remain open challenges.
Conclusion
Weak popularity provides a robust middle ground between the strictness of stability and the elusiveness of standard popularity. By accounting for the "stickiness" of current assignments, this approach guarantees the existence of a majority-rule winner that is both computationally accessible and significantly larger than traditional stable matchings.
Summary updated