Re:Why a Dutch court stopped high school students from swapp...
by throwaway1982x on Saturday May 19, 2018 @05:42PM
(#17109878)
I found this example exceptionally difficult to read and comprehend.
I recognise that this is known as the "Stable Marriage Problem", yet I still feel an aversion to marriage being defined as between a man and a woman (and further, than a man must propose to a woman). So, this scenario cranked my unhappiness up to 11. I was not able to follow it at all beyond "male unhappiness".
Surely it is possible to write this example in a way which recognises diversity of sexuality and does not need to play up to sexist stereotypes - employees looking for work and employers should work fine.
Re:Why a Dutch court stopped high school students from swapp...
by jacquesm on Saturday May 19, 2018 @07:01PM
(#17110190)
It's just an example, not a political manifesto. Feel free to copy the comment and replace the words you object to.
Re:Why a Dutch court stopped high school students from swapp...
by throwaway1982x on Tuesday May 22, 2018 @08:17AM
(#17125349)
If it's an example and not a political manifesto, then perhaps it could be written without misogynist and heteronormative (i.e. political) undertones.
It's not an illustrative example because we have to assume an unrealistic misogynist take before it even starts to make sense.
Define a person's unhappiness as one less than the position in their ranking of the person they paired with. If someone is not paired, define their unhappiness as N, where N is the number of men and the number of women being paired.
For example, in a set of 10 men and 10 women, a women paired with her 1st choice man has unhappiness 0. A man in that set not yet paired has unhappiness 10.
The key to understanding Gale-Shapley is female unhappiness (in the version where the men propose to the women...if you do it with women proposing to men, then male unhappiness is the key).
When the algorithm runs a man through the gauntlet and his proposal is tentatively accepted by a women, her unhappiness decreases (and no other woman's happiness changes). Hence total female unhappiness decreases every round. Total female unhappiness is a non-negative integer, and it is bounded by N^2 where N is the number of females. This shows that the algorithm must terminate, and must do so in at most N^2 rounds. It is also easy to see that the algorithm only terminates when all men are paired. Thus, we can conclude that the algorithm will produce a final pairing in which everyone is paired, and it will do this in at most O(N^2).
Consider any man, M1, paired by this algorithm with woman W1. Because men propose in order of their rankings, M1 has already proposed to every woman he prefers over W1. Either they were rejected (meaning those women were already paired with men they prefer over M1) or they were tentatively accepted but then later he was jilted when someone better came along. From this, we see that the pairings produced by the algorithm (including the partial pairings after each round) are such that no man is willing to cheat on his currently assigned partner. Hence, they are stable.