March 25, 2019 Monday
Bedtime Story
Theorems in the Stable-Marriage Problem
Tonight I shall highlight the asymmetry
that is inbuilt in this Gale-Shapley algorithm.
This is somewhat akin to the superiority a
player begets in the game of tic-tac-toe if he gets the option of making his
move first.
Among the group which proposed namely the
men landed up with preferences of their first, second and third choices whereas
as the group that was being proposed to namely the women landed up in cases
with men of their first choice but in one case with a man of last choice.
The authors point out that the group which
does the proposing (and gets rejected which initially sounded harsh and brutal)
which in our case is the men always fair better than the group which is
proposed to.
This can be stated in the form of a theorem
which would go like this:
Theorem: This algorithm assigns every man
(or any group that proposes) his best possible wife.
In other words the algorithm is
simultaneously optimal for all men.
This theorem in the original paper by Gale
and Shapley was stated in the form of college student admission problem as
Theorem 2.
“Theorem 2: Every applicant is at least as
well off under the assignment given by the procedure just described as he would
be under any other stable arrangement.”
So in summary the Gale-Shapley algorithm in
which men propose to women as was the case in ours always yields a stable
matching that is the best for all men among all possible stable matchings.
Analogously, in the case when the women do
the proposing the final matching is always the best for all women among all
possible stable matchings.
The other two theorems that the solution to
the problem generates are as follows:
Theorem: This algorithm always stops (which
is a quintessential requirement for a Turing Machine for its computation).
Theorem: This algorithm arranges stable
marriages.
The proof is evident from the fact that no
man can trade for any better woman than what this algorithm assigns to him.
This is because each woman a given man
prefers rejected him on the way.
One last rather unexpected theorem that is
a corollary of the Theorem 2 is this:
This algorithm assigns every woman her
worst possible man and thereby husband.
Fortunately things need not always be so
one sided in the real world.
In the hospitals-residents problem the
problem can be tailored to be either hospital-oriented (as was the case in the
National Residency Matching Program before 1995) or resident-oriented (which
has been the case since 1995).
Stay tuned to the voice of an
average story storytelling chimpanzee or login at http://panarrans.blogspot.com
Good night Mon Ami and my fellow cousin ape.
Advertisements
Another great educator and a teacher that I am aware of is
Professor Subhashish Chattopadhyay in Bangalore, India.
While I narrate stories, Professor Subhashish an electronic
engineer and a former professor at BARC, does and teaches real mathematics and
physics.
He started the participation of Indian students at the
International Physics Olympiad.
Do visit him here:
All his books can be downloaded for free through this link:
For edutainment and English education of your children, I
recommend this large collection of Halloween Songs for Kids:
No comments:
Post a Comment