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

  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!

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?

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

  • 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.

Software engineer at Facebook, volunteer math and computer science teacher, author of the CodeWorld platform, amateur ring theorist, and Haskell enthusiast.