Strategic Considerations for the Gale-Shapley algorithm Part 1

Abstract: In post we look at the Gale-Shapley algorithm from a strategic prospective. We start by introducing the algorithm and give an proof for that individual men can not misrepresent there intent to end up with a more desirable outcome. Then, we look at two ways to “game” the algorithm, one in which a group of men work together, and another where women are able to mispresent their intent to end up with a better outcome.

Before beginning the discussion, two quick comments. First, although this falls out of the standard game centric posts I cover in this blog, there are strategic considerations that can be made during the process, which is what we will be covering. Second, this problem is often referred to as the stable marriage problem, and most references provided will refer to it as such. Finally, my original intent was to include this as one post, but while writing, I realized it would much longer than any other post (3000+ words). As such, I have decided to break it up into two posts, with the second one picking up were the first left off.

The Gale-Shapley algorithm is an algorithmic solution to the stable matching (marriage) problem. The problem is as follows. Given students and internships, where each group has ranked all members of the opposite group in order of preference. The goal, is to then find a matching, or bijection that maps students and internships, such that there does not exists any match which both prefer each other to their current partner under the current matching. A natural question that one may ask is if such an ordering is guaranteed to exists? The answer is yes, as the Gale-Shapley algorithm will always find such an ordering. The algorithm proceeds through iterations in the following way:

• During the first iteration, each unassigned student proposes to the internship that they prefer most, with each school replying with a tentative yes to the student that is most preferred by that institution. All other students are told “no” and are left unmatched.
• We then loop the following process until all students have been matched. First, each unmatched student proposes to the most-preferred internship to which they have not yet proposed. Then if the position is not currently filled, or they prefer this candidate over the current provisional candidate, the internship will then reply with a tentative yes. It is important to note that this process may result in previously matched students becoming unmatched, at which point they reenter the unmated pool and propose next iteration.

Using this process ensures that every student finds an internship, and that all matchings are stable. We can see that this is true through the following argument, for student and internship . If prefers to their current position, before they proposed to their current position. If accepted the proposal but switched later on, then they must have received a proposal from a student they liked more. If rejected ‘s proposal, then they already had a student they liked more than . Thus, this algorithm will always produce a stable matching.

We will now look at this from the standpoint of a “game”, or look at possible strategic considerations. That is to say, is it possible for a participant to game the system and be untruthful (misrepresent their actual rankings) but achieve a better outcome?

The first case we will consider is that of the individual student, who does not list the universities in accordance with their true rank ordering. In other words, the student lies, in attempt to achieve a result that is better in terms of their “true” rank ordering. Can this student achieve a better result by engaging in fowl play? The answer is no, and for a full proof see [2]. We will however work through the proof with the critical lemma being handwaved.

We will call our student , for Machiavelli. Without loss of generality, we will assume the is the last student to propose, leaving only one internship not paired. The Theorem proved by Dubins and Freedman in [2] states that if can not get a better internship -measured by ‘s true rank ordering – than the one would get by fair play. The main way they prove this is through what they call The Scenario Lemma. To state this lemma we first need two definitions. First, we define a Scenario to be a sequence of proposals for M that function as a segment of a rank ordering. Next we define a scenario to be smaller than scenario , if all internships mentioned in occur in . As an example we could say is smaller than . From this, we can now state the Lemma:

Suppose scenario is smaller than scenario , then makes every proposal indicated in the larger scenario, and every rejection and proposal that would occur in scenario occurs in . For a full proof of this lemma see [2].

With this lemma, we can now prove that Machiavelli can do no better by falsifying his list. To do so, we use a proof by contradiction, where some scenario say gets a internship that ranks ahead , where is the internship would get under fair play. We assume , as otherwise can not do any better. In order for to get an internship at , the algorithm must terminate with another student being matched with the last internship. We now show that for all cases of the true ranking, getting matched to results in a contradiction.

Case 1: Lets assume that prefers all other internship in the scenario over . In other words is the true worst internship out of the internships in this scenario. To show the contradiction, lets look at what would happen if were to play fair. Because ends up with internship , the algorithm must terminated when is rejected by their th choice, and then applies and is accepted to their th choice. However we can use the Scenario Lemma here, as we assume that the foul play scenario is smaller than the fair play one, as ranks ahead of . As mentioned earlier, this scenario includes an application to internship which would cause the algorithm to terminate, but we know that the fair play sequence terminates with ending up at , thus we have reached a contradiction.

Case 2: Lets assume that prefers U to at least one of the other universities in our scenario. To created a contradiction here, we create a smaller foul play scenario by deleting all universities that are truly preferred over . This is equivalent to case 1, for which we have already shown that , must be rejected by (otherwise we have a contradiction). As per the Scenario Lemma, this rejection must also occur in the original sequence, which is a contradiction, as we assumed that the scenario must get , paired with internship .

Final Thoughts and Conclusion: With both cases considered, we have now shown that it is impossible for any individual student to perform better by engaging in foul play. However, this does not extend to coalitions of students. (Un)fortunately, the same result given in paper [2] extends this theorem to show that several students can not collude, with each using a false ordering, and all get a better internship. The critical word being all, as in the next post, we will go over a situation in which students can collude such that some subset of colluding students will get a better internship. We will also look at how the internships can lie to achieve a better result, and discuss truthful and non-truthful mechanisms.

[1] – By No machine-readable author provided. User A1 assumed (based on copyright claims). – No machine-readable source provided. Own work assumed (based on copyright claims)., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=10189057
[2] – Dubins, L., & Freedman, D. (1981). Machiavelli and the Gale-Shapley Algorithm. The American Mathematical Monthly, 88(7), 485-494. doi:10.2307/2321753