Discussion about this post

User's avatar
Mr. Ala's avatar
1dEdited

As I’m sure you know, Prof. Friedman, this issue inspired a problem: given N eligible heterosexual bachelors and N eligible heterosexual spinsters, each with a preference list of the N potential spouses (spice?), (a) is there a pairing stable against divorce, that is, if A is paired to B but prefers C, then C prefers their spouse D to A (my first unironic use of the singular “their”!), (b) if there is, can it be computed in finite time? in polynomial time? and (c) if so, how—by what algorithm?

And the answers are (a) yes, (b) yes and yes, and (c) by the HIgh School Dance Algorithm, as follows.

For the first dance, each swain asks his favorite maiden. If asked by exactly one swain, a maiden chooses and dances with him. If asked by more than one, she chooses her favorite among them, dances with him, and rejects the rest. All the unchosen swains and maidens sit out the dance.

For every subsequent dance, each swain who danced the previous dance returns to his partner and asks her for this dance too; each swain who didn’t now approaches his favorite maiden who has not explicitly rejected him for some earlier dance and asks her for this dance. If asked by exactly one swain, a maiden chooses and dances with him. If asked by more than one, she chooses her favorite among them, dances with him, and rejects the rest. Her favorite need not be her partner on the previous dance. All the unchosen swains and maidens sit out the dance.

Iterate until everyone is dancing.

It is a simple exercise for the interested student to prove that this algorithm always terminates, does so in polynomial time, and produces a final pairing that is stable against divorce.

Frank's avatar

"I once estimated that the woman to whom I am still married, more than forty years after I met her, was about a one in a hundred thousand catch — for me."

Amen.

10 more comments...

No posts

Ready for more?