March 17, 2019 Sunday
Bedtime Story
Stable Marriage Problem
As I said last night the problem faced by
the National Student Internship Committee was a tough and challenging one but
is now a well known problem among the mathematicians and computer scientist.
Mon ami would instantly recognize it.
Yes, that is the stable marriage problem or
sometimes also known as the stable matching problem as not all matching need to
end up in a conventional marriage.
This is a problem that is encountered and
therefore well known and studied in computer science, economics and
mathematics.
The problem is defined as finding the
perfect way to stably match two equally sized sets of elements when there
exists an ordering or preferences for each element.
Though the above definition is a fairly
complete one it may not make much of a sense to somebody who is not familiar
with the problem.
So let me simplify it by stating in the
form my usual bedtime story.
Say you live in a small village where you
are a wise and aged woman and you have to play the role of matchmaker or
sometimes known as yenta among the Yiddish or the Ashkenazi Jews.
The village has few young men and women and
it has been ordained by the village chief that it is your job to match one
eligible female with one eligible bachelor.
Since you are the old village hag you are
intimately familiar with all these young men and women and you are thoroughly
aware of their mating preferences.
It is of course easy to marry one male with
one female but it is not as simple as that since you are entrusted with the job
of stable marriages, i.e. “happy marriages” that would last and not end up in
either divorces or extra-marital affairs.
This implies that it should not make the
couples feel that they have been obviously wrongly matched.
The “stable” part of the problem is crucial
and it needs some further explanation.
This stability does NOT imply that every
individual will be happy in this marriage the way we view it conventionally
because it is still possible that in one of the pair that has been arranged by
you the wife is unhappy with her mate or the other way around.
But the marriage would still be a “successful
one” as she would be unable to dump him simply because the other men are
content with their wives leaving her no choice but to be with the man that you
have arranged.
That would still make it a stable solution
or stable configuration even though certain individuals are not wholesomely
satisfied and yet they cannot break up the arrangement simply for the lack of
options available to them.
This implies that there should not be an
unsatisfied pair of a man and a woman in any two marriages
So the problem is that given such a
situation is it always possible to arrange for stable marriages?
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