4 ms·

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, bu

by bo1024 5y ago

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.

bhl 5y ago
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.
- cdsmith 5y ago
  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!)

by bo1024 5y ago

bhl 5y ago

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.

cdsmith 5y ago
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!)