Gibbard’s Theorem vs Stable Matching

Here are two theorems from game theory, which initially seem to contradict each other. By comparing them, we can uncover some hidden nuance in the situation.

Gibbard and Roth face off!

Gibbard’s Theorem: Strategy is Inevitable

The first theorem, initially by Allan Gibbard and generalized by later work by Gibbard and others, showed that any collective decision-making process must have one of three properties:

1. There are only two possible outcomes.
2. There is a dictator, who can choose the outcome regardless of any choices made by anyone else.
3. It is strategic, meaning that the best way to get what you want depends not just on your preferred outcome but also on anticipating what others will do.

This is a pretty big deal. Think about elections, for example. Assuming we have more than two candidates and don’t have a dictatorship, strategic voting must be possible. That’s too bad, because we’d like to be able to tell people that they can always just vote for their favorite candidate. Alas, this can never be the case. It’s widely known that hopeless third parties can “spoil” the election by siphoning votes from major candidates. Clever systems like instant-runoff are supposed to fix that problem, but Gibbard showed that in general, it can never completely be fixed. (At least, not without accepting a limited two-party system or a dictatorship.)

It’s not strictly part of Gibbard’s theorem, but Gibbard and others showed later, that this remains true even if there is randomness is involved. You can wait until after the voting happens to choose the dictator, or to decide which two outcomes to allow; but ultimately the same conditions apply. That won’t be important for the rest of this article, though.

Roth’s Theorem: DA is strategy-proof!

While Gibbard’s theorem addresses any collective decision-making process, Gale and Shapley’s Deferred Acceptance (DA) algorithm is a solution for a specific kind of decision-making problem: matching. The idea is to match up some set of candidates with some set of positions. Each candidate has preferences about which position they want, and each position has preferences on which candidates they prefer. (The presentation is historically given in terms of marriage, but that presents difficulties when you consider same-sex marriage, gender identity, etc., so let’s call it candidates and positions!)

Gale and Shapley proved that there exists a matching of candidates to positions which is stable, in the sense that no candidate would prefer a position which would also prefer them. (The word “stable” perhaps comes from the fact that such a candidate could then switch to their preferred position, so an unstable matching wouldn’t last long.) They gave a specific algorithm, called DA or Deferred Acceptance, which is described in the previous link. It starts from a list of each candidate and position’s preferences, and generates a stable matching. They went on to prove that the matching it generates is the unique one that all candidates would agree is best.

You might imagine that someone very clever could find a way to get a better position by being untruthful about their preferences with this matching algorithm. For example, if someone wants a position but doesn’t think they’ll be accepted, would it be wise to instead express a more realistic preference? Surprisingly, Alvin Roth showed that this is impossible! The DA algorithm is strategy-proof, in the sense that the best way to get the position you most prefer is to provide your honest-to-goodness true list of preferences.

To strategize or not?

So now we have a dilemma. The stable matching definitely has more than two possible outcomes. It definitely doesn’t have a dictator. So it must, by Gibbard’s theorem, be strategic. But hold on… Roth showed that an honest list of preferences is always best, regardless of the preferences of others. How can both be true? The answer is subtle, and it will show that we need to be careful about exactly what words mean in each case.

Here’s the key:

• Gibbard’s theorem assumes that each participant has a set of preferences about the entire outcome of the process. In this case, the outcome of the process is the matching of all candidates to all positions.
• Roth, on the other hand, assumes that each candidate has a set of preferences about which position they individually will be assigned to. They are not entitled to a preference about which positions are given to which other candidates.

Roth’s preferences are limited enough that they only produce conflict indirectly, such as when there are more candidates who want a certain position than there are slots to accept them. And that turns out to yield just enough slack to escape the consequences of Gibbard’s theorem, and allow the decision process to be non-strategic in Roth’s sense.

But be careful! This means that if candidates do have preferences that depend on the placement of others, Roth’s result no longer applies. To take a simple example, suppose two close friends want to work together in the same position. Despite Roth’s dismissal of strategy, they will need to strategize to accomplish this. For example, they would be well-advised to favor applying for positions that are likely to be generally unpopular. They should also avoid applying to positions that wouldn’t want also want their friend. Both of these are strategic choices that involve anticipating the preferences of others.

In the end, of course, Gibbard and Roth’s results can co-exist, but one must be careful in exactly what they mean.

Some final notes

• I want to be clear that this isn’t new. In fact, Roth cited Gibbard’s result in his paper on the matching problem, and is obviously aware of this nuance.
• For this analysis, I’m considering only candidates as the participants in the decision-making process, and the employer preferences as being baked into the decision algorithm. Roth’s result does not extend to employers expressing their true preferences! In fact, Roth shows that no process can exist that also incentivizes employers to indicate their true preferences among candidates.