3 ms·
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 prop
by 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 agoTo 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!)