Gibbard’s Theorem vs. Stable Matching | Hacker News Reader

Gibbard’s Theorem vs. Stable Matching

cdsmithus.medium.com

67 pointsgbrown_9 comments

The final note is important, otherwise the statement of Roth's result is misleading. The X-proposing version of deferred acceptance is strategyproof for X's, but not for the other side (the Y's). For example in the national residency matching program, it's (roughly) strategyproof for doctors but not for hospitals.

When I was taught stable matching, there was a homework problem on showing that the algorithm is “proposer-optimal” and “proposee-pessimal”, meaning that a proposer always does the best they can do relative to other proposers’ preferences while proposees do the worst.

The crucial part here is how big is the gap between a proposee’s worst and best match: if the gap is null for all proposees, there isn’t any strategic incentive for one to lie about their preferences. However, that obviously is a very hard requirement.

To be clear, the algorithm is proposer-optimal only when compared to other stable matchings. It is still possible that there exists some other matching that would make all proposers happier. It just won't be stable: there will be some pair of proposer and proposee that could switch to immediately increase their happiness, BUT it would set off a chain reaction of further swaps that leave everyone less happy in the end. This was a bit surprising to me.

There's a variant where you run the deferred acceptance algorithm, but then only the proposees who never rejected anyone finalize their decision. All other proposees and their matched proposers split up, and the whole algorithm is run again with the unmatched participants. This time, you end up with a Pareto-optimal matching for the proposers, with respect to their stated preferences. That is, there's no possible way to make anyone happier without making someone else less happy. But it's not stable, and the algorithm is no longer strategy-proof. (In fact, one can prove that no strategy-proof algorithm can guarantee a Pareto-optimal matching!)

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

Doesn't this mean it's actually not very applicable to voting systems?

Voters generally only care whether their preferred candidate comes first, not about the relative ordering of the other candidates.

I suppose a voter might care how close their preferred candidate came to winning (or their margin of victory), but that's still a slightly weaker requirement than having a total ordering of all candidates relative to each other.

There are versions of Gibbard's theorem for outputting a single winner too. The famous one is Gibbard-Satterthwaite: https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_...

You can have weak inequalities in the preferences over alternatives -- e.g. you're indifferent between all rankings where your preferred candidate is number 1

Author here. No, it doesn't mean that. If the election is held to determine who wins, then the outcome is who wins, and everyone has opinions about that same outcome.

Contrast this to the matching problem, where the outcome is where ALL the candidates are assigned. You're allowed to have an opinion about where you are assigned. I'm allowed to have an opinion about where I am assigned. These opinions might conflict indirectly because of limited spots, but they don't conflict directly. This is very different from the election case, where if you and I have different opinions about who we want to win, those opinions are always contradictory.

What if an election is held to determine a set of two "finalists"? People might disagree about who the top two candidates are, but they might be satisfied as long as one of their top preferences makes it through to the second round.

Obviously once there are two candidates remaining, Gibbard's Theorem doesn't apply, so I'm guessing that any procedure which reduces the set to two outcomes must itself be subject to strategy, but it would be interesting if allowing people to cast a separate vote in a run-off election was enough to make the first round no longer require strategy.

If the result of the election is the choice of two finalists, then as long as there are more than two candidates, there are more than two possible outcomes. For example, if the candidates are A, B, and C, then the possible outcomes are: (A and B), (A and C), or (B and C), so 3 in all. In general, for n candidates, there are n * (n - 1) / 2 outcomes. By Gibbard's Theorem, then, either there is a dictator, or there is strategy.

Another way to see this: the entire process of choosing two finalists and then having a runoff to choose an ultimate winner counts as a collective decision-making process. That there are two separate votes doesn't actually matter. By Gibbard's theorem, then, if there isn't a dictator, then the entire process is strategic. Since the chance to use strategy doesn't occur in the simple-majority final runoff, by process of elimination, it must occur in choosing the candidates who qualify for the runoff.

Reply on news.ycombinator.com