Abstract
In the celebrated stable-matching problem, there are two sets of agents M and W, and the members of M only have preferences over the members of W and vice versa. It is usually assumed that each member of M and W is a single entity. However, there are many cases in which each member of M or W represents a team that consists of several individuals with common interests. For example, students may need to be matched to professors for their final projects, but each project is carried out by a team of students. Thus, the students first form teams, and the matching is between teams of students and professors. When a team is considered as an agent from M or W, it needs to have a preference order that represents it. A voting rule is a natural mechanism for aggregating the preferences of the team members into a single preference order. In this paper, we investigate the problem of strategic voting in the context of stable-matching of teams. Specifically, we assume that members of each team use the Borda rule for generating the preference order of the team. Then, the Gale-Shapley algorithm is used for finding a stable-matching, where the set M is the proposing side. We show that the single-voter manipulation problem can be solved in polynomial time, both when the team is from M and when it is from W. We show that the coalitional manipulation problem is computationally hard, but it can be solved approximately both when the team is from M and when it is from W.
Introduction
Stable matching is a cornerstone of economic theory and computer science, most famously implemented via the Gale-Shapley (GS) algorithm to match medical residents to hospitals or students to schools. Traditionally, these models assume agents are single entities with fixed preferences. However, many real-world scenarios involve teams acting as single agents—such as a group of students matching with a project advisor.
When a team acts as an agent, it must aggregate the diverse preferences of its members into a single ranked list. This research explores the intersection of Social Choice Theory and Matching Theory, specifically examining how individuals or groups within a team can strategically misreport their preferences (manipulation) to achieve a more desirable matching outcome for the team.
Methodology and Framework
The researchers model the problem by combining two distinct fields: voting rules and matching algorithms.
- The Mechanism: The framework assumes two sets of agents, "Men" ($M$) and "Women" ($W$). One agent is a team that uses the Borda rule (where candidates receive points based on their rank) to generate its aggregate preference list. The GS algorithm is then applied to find a stable matching.
- Side Asymmetry: Because the GS algorithm treats the proposing side ($M$) and the proposed-to side ($W$) differently, the authors analyze manipulation from both perspectives. In this model, $M$ is the proposing side.
- Algorithmic Design:
- For single manipulators, the authors developed greedy-style polynomial-time algorithms that iteratively adjust the manipulator's list to move "blocking" candidates lower in the team's aggregate ranking.
- For coalitional manipulation, the problem was proven to be NP-complete by reducing it from the Permutation Sum problem.
- To address NP-hardness, the authors designed heuristic algorithms based on Borda score "gaps," providing theoretical approximation guarantees.
Key Insights
Borda as a Social Welfare Function
While most voting research treats the Borda rule as a way to select a single winner, this paper treats it as a Social Welfare Function (SWF)—a rule that outputs a full ranked list. This is a more complex area of study because the entire order of the list, not just the top choice, influences the final matching in the GS algorithm.
The Proposer's Advantage
Manipulation is generally more direct from the proposing side ($M$). On the proposed-to side ($W$), the team must ensure their preferred candidate actually proposes to them, which requires managing the scores of multiple candidates simultaneously to influence the behavior of other agents in the market.
Results and Complexity
Single-Voter Manipulation
The study finds that single-voter manipulation is solvable in polynomial time for both the proposing and proposed-to sides. This implies that an individual team member can efficiently determine an optimal "lie" if they have access to the preferences of other team members and agents.
Coalitional Manipulation
In contrast, coordinating a group (coalition) to manipulate the outcome is NP-complete, even with only two manipulators. This suggests that while individual cheating is computationally easy, organized conspiracy within a team is significantly more difficult.
Approximation Performance
To circumvent the complexity of coalitional manipulation, the authors established "additive" approximation guarantees:
- Men’s Side (Proposers): The proposed heuristic is a 1-additive approximation. If a successful manipulation exists for a coalition of size $|R|$, the algorithm will find a successful manipulation for a coalition of size $|R|+1$.
- Women’s Side (Proposed-to): The heuristic is a 2-additive approximation, finding a successful manipulation with at most two additional members.
Limitations and Future Work
The current findings rely on the assumption of "perfect information," where manipulators know the preferences of all other participants. In practice, this information is often private or noisy. Additionally, this study is limited to the Borda rule. Future research could investigate other voting mechanisms (such as Plurality or STV) and "destructive" manipulation, where the goal is to avoid a specific undesirable match rather than securing a preferred one.
Summary updated