News for hackers. Stuff that matters.
Re:The stable marriage problem and modern dating by likelybear on Wednesday July 08, 2020 @04:24PM (#23773855)
The difference based on which side proposes turns out to be a knife-edge result for balanced markets! For imbalanced markets, the short side gets average rank `O(log(n))` in every stable matching and the long side gets `O(n / log(n))`

Edit: reference is Ashlagi et al (2015). "Unbalanced Random Matching Markets: The Stark Effect of Competition" http://web.mit.edu/iashlagi/www/papers/UnbalancedMatchingAKL...

There are no comments on this comment yet.