Stable matching, as a game

For a long time, I have been interested in the mathematics of elections and auctions. They are part of a broader field within economics, Social Choice Theory, which is full of interesting combinatorial problems and paradoxes.

Recently I (re-)stumbled on the subject of Stable Matching, and this subject clearly also lies within Social Choice Theory, and it has some of the same interesting aspects.

In this article, I discuss if the problem could be seen as a game.

Definition of the problem

We have a set of elements to be paired up with each other. Each element/agent has a ranked list of preferences. This matching must be done in a way such that it is stable. A matching is not stable if there are elements A and B, such that

• A and B are not currently matched with each other
• A prefers B over its current pairing
• B also prefers A over its current pairing

This condition would mean that A and B could run off with each other, ignoring other elements’ preferences. This situation is not stable.

There are two variants of the problem:

1. There are two equally-sized sets of elements, S and T, and pairs must be formed of one element from S and one from T. Thinking of men S and women T, this variant is also called the stable marriage problem.
2. There is just one group with an even number of elements. This is called stable roommates problem.

There are some key takeaways from these two variants, which I will not go into detail with here, but just summarize:

(1) For the stable marriage problem, there is always a stable match and there’s an efficient algorithm to find it: the Gale-Shapley algorithm, invented in 1962. This algorithm is presented in this YouTube video. Surprisingly, there can be multiple stable matches. The Gale-Shapley algorithm finds the matching that is optimal for all elements in the “left set”: All elements in the left set will get the best possible partner among all stable matchings. This means (to my surprise), that from the left set’s perspective, there is no trade-off. The solution is simultaneously optimal for everyone in the left set. For the right set, it is the opposite: everyone gets the worst possible outcome. Note: this does not mean that they all get their least preferred choice — but among all possible stable matchings, they get the one with their least preferred partner.

(2) For stable roommates problem, there doesn’t always exist a stable match! This problem was one of 11 hard problems about variations to Stable Marriage, put forward by D.E. Knuth. He asked for a polynomial solution, and the first to construct such an algorithm was R. W. Irving in his paper An Efficient Algorithm for the “Stable Roommates” Problem (1984). This algorithm will find a stable match if one exists. It is more complicated than Gale-Shapley, and proving correctness is also more complicated. The algorithm is explained in several YouYube videos, e.g. [1] [2].

Here is an example (video) where a stable roommates problem has no solution

No solution to stable roommate

For example, the matching AB CM is not stable, because A and C both prefer each other over their current match, which makes us switch to AC BM, which is also not stable for a similar reason, and so on. (This situation is similar to Arrow’s Paradox in social choice theory: A majority can prefer B over A, C over B, and A over C. A group’s majority preferences can form a cycle).

Realization as a game?

The fact that each element has a ranked list of preferences makes it obvious that this problem could be seen as a multi-agent game, each element being an autonomous agent seeking to maximize his selfish outcome of the game.

The criterion about a matching being stable has led me to questions:
Is stability really a goal in itself, or is instability more of a symptom? That is, if a match is unstable, it is just a sign that it is not good, that something went wrong. Conversely, just being stable, is that sufficient for having the “best” solution? How should we choose a solution when there are multiple— and what to do when there is no stable matching. Is randomization a solution, and if so, how? If there is a random aspect to the problem, should we replace rankings with numerical scores, so that we can express how to trade off different probabilities? (Example: with ranking A B C, is “100% B” better or worse than “50% A, 50% C”?)

Several questions about a possible game arise:
What are the formal rules of this game, and does optimal play of this game always lead to a stable match when one exists? Does it even lead to Pareto-optimality? If not, are there some paradoxes? Is it a turn-based game, and what happens at each turn? Could two or more agents conspire to improve their outcome of the game? To what extent does publishing of one’s ranking harm your outcome (conversely, can lying about your ranking improve your outcome)? Is randomization needed in the rules, or can we let any randomization be up to the agents?

Does the framework of Nash Equilibrium apply to this game? While Nash Equilibrium is about one player changing his strategy while the others keep theirs, in this game at least two players have to agree to change a matching. What is even a strategy in this game? Is a ranked list a strategy? Maybe, but it depends on how the game is carried out.

It is all quite confusing to me, so I have tried different approaches.

From here on, I consider only the stable roommates problem, assuming that the stable marriage problem is a simpler subproblem of this. It is not entirely clear to me that stable roommates is a proper superset, though, since for stable marriage you only rank half of the elements.

Approach 1. Distribution of outcomes

Instead of the players agreeing on one matching, maybe they could agree on a probability distribution of matchings?
This turns out to be not the case. In the counterexample from roommate matching, we could hypothesize this distribution:

Probability   Paring
x             AB, CM
y             AC, BM
1-x-y         BC, AM

But it turns out that no matter how we initialize x and y, no update can be agreed on by all four players. This means that any combination of (x, y, 1-x-y) is Pareto-optimal. This doesn’t bring us any further.

Approach 2. Turn based proposal

The game proceeds like this: In round 0 all players simultaneously publish their preference list. At every turn, a player is picked at random (uniformly). He then proposes to other players in the order of his preference list, and the first one to accept is chosen. The paired players leave the game, i.e. the chosen partner doesn’t get his turn to propose. There is no way to change one’s mind later in the game. If no proposed player accepts, the proposing player is moved to a rest group. A proposing player can propose to elements of the rest group. When only the rest group is left, these are matched at random.

Let’s play this game in the ABCM example above:
If A is picked as first proposer, he will propose to B, who will accept (Why? Because if B rejects, he knows that C will accept, and then B will end up with M). By symmetry, similar matchings will happen with B or C. If M is the first proposer, everyone will reject, and then the game proceeds as before. In summary, we will have this probability distribution of outcomes:

Prob.     Matching
1/3       AB CM
1/3       AC BM
1/3       BC AM

Questions

• Assuming that there exists a stable matching, and assuming that everyone plays optimally, will the outcome be a stable match?
• Are there circumstances where posting false preferences can help? It seems obvious that proposals should be made in order of preference, but the downside to posting true preferences is that others will see them and their strategy might depend on them.
• To what extent can players successfully conspire in order to improve their result?

I would love to hear your thoughts or ideas in the comments.