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.
Thanks. I don't think the result is guaranteed to be economically efficient, since it is based on only ordinal data. Adding in side payments might produce a version that is. I think that would work if payments are to the partner, harder if they can also be to rivals.
The simple algorithm to maximize economic efficiency, assuming everyone is truthful:
Select a random Alice and Bob. Ask Alice how much she would pay, or would have to be paid, to marry Bob. Ask Bob the symmetrical question. Add up the two numbers, positive for would pay, negative for have to be paid. That is the value of that pairing.
Repeat for every possible pair. Choose the allocation for which the summed values of the pairings is largest.
Until something happens, such as finding that a chosen partner has other bad habits. It's only stable in the dance realm, only for those dances danced that evening, and doesn't allow for any changes in preferences.
In other words, a typical socialist solution which solves nothing.
It is easily demonstrable that without some assumptions of preference stability there is no pairing that is stable against divorce.
In the real world there are also people entering and exiting both pools all the time, and exiting marriages by means other than divorce, such as abandonment, emigration, or death.
So what? This is a triviality.
But what you have seem to have missed about the High School Dance Algorithm is that it is the way people actually behave at a high school dance (at which mixed couples dance). Or did, when high schools allowed events as heteronormative as that.
And there is the Resident Matching Program. Alvin Roth, in collaboration with Elliott Peranson, revolutionized the National Resident Matching Program (NRMP) by designing a "stable matching" algorithm adopted in 1997 to efficiently pair medical residents with hospitals. Here is a google summary:
The Algorithm: The Roth-Peranson algorithm is a modified deferred-acceptance (DA) algorithm that prioritizes the applicants' preferences (doctor-proposing) while accommodating hospital preferences and, uniquely, couples' joint preferences.
"All-In" Policy: Following Roth's redesigns, the NRMP moved toward an "all-in" policy, ensuring that all positions are filled through the match to reduce the unreliability of, and inequalities created by, early "pre-matches".
Impact: The system brought stability to a market that previously saw chaotic last-minute scrambles and high-pressure, exploding offers.
"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."
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.
Thanks. I don't think the result is guaranteed to be economically efficient, since it is based on only ordinal data. Adding in side payments might produce a version that is. I think that would work if payments are to the partner, harder if they can also be to rivals.
The simple algorithm to maximize economic efficiency, assuming everyone is truthful:
Select a random Alice and Bob. Ask Alice how much she would pay, or would have to be paid, to marry Bob. Ask Bob the symmetrical question. Add up the two numbers, positive for would pay, negative for have to be paid. That is the value of that pairing.
Repeat for every possible pair. Choose the allocation for which the summed values of the pairings is largest.
Until something happens, such as finding that a chosen partner has other bad habits. It's only stable in the dance realm, only for those dances danced that evening, and doesn't allow for any changes in preferences.
In other words, a typical socialist solution which solves nothing.
It is easily demonstrable that without some assumptions of preference stability there is no pairing that is stable against divorce.
In the real world there are also people entering and exiting both pools all the time, and exiting marriages by means other than divorce, such as abandonment, emigration, or death.
So what? This is a triviality.
But what you have seem to have missed about the High School Dance Algorithm is that it is the way people actually behave at a high school dance (at which mixed couples dance). Or did, when high schools allowed events as heteronormative as that.
It is a pointless pairing algorithm. Of course is you limit your algorithm to such an extremely narrow sample, you can prove it works.
I could have ham and eggs for breakfast, if I had some ham and eggs. That’s just about as pointless.
Have a nice day.
And there is the Resident Matching Program. Alvin Roth, in collaboration with Elliott Peranson, revolutionized the National Resident Matching Program (NRMP) by designing a "stable matching" algorithm adopted in 1997 to efficiently pair medical residents with hospitals. Here is a google summary:
The Algorithm: The Roth-Peranson algorithm is a modified deferred-acceptance (DA) algorithm that prioritizes the applicants' preferences (doctor-proposing) while accommodating hospital preferences and, uniquely, couples' joint preferences.
"All-In" Policy: Following Roth's redesigns, the NRMP moved toward an "all-in" policy, ensuring that all positions are filled through the match to reduce the unreliability of, and inequalities created by, early "pre-matches".
Impact: The system brought stability to a market that previously saw chaotic last-minute scrambles and high-pressure, exploding offers.
"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.
Interesting ... Substack says 4 comments, but it shows only 3. (Presumably 5 and 4 once I post this comment. Yep.)
That was really interesting about ancient Babylon.
But probably not true.