March 21, 2019 Thursday
Bedtime Story
Iterations of Algorithm of Stable Marriage Problem
In our bedtime story tonight we are in the
second round or iteration of men proposing to women in the village.
Now the women have the choice to make
between the proposal she is getting and the man she has kept on her string if
any.
The women then can either accept the new
proposal if it comes from a man ranking higher than the one she is holding on her
string or reject him if he falls below in the love list over the man she has.
It is assumed that the women will choose
and reject men depending on their positions in her selection list and thus will
be absolutely faithful to the list that they wrote out initially than anything
or anyone else.
You being the designated yenta are
obviously supervising all the Machiavellian love action.
After this second round the women then have
a man who is kept in suspense till the next one comes with a proposal.
Such rounds will continue as long as there
are rejected men out there who will keep on proposing to all women (except to
whom they have already proposed and been rejected either primarily or
secondarily) until they finally they will get accepted.
It must be borne in mind that the women who
will be accepting rejected men in the final rounds will obviously not be
getting men who were among their favorites in their love list.
But then they are left with little choice
since the men they would have ideally have wanted to marry would be already out
of the marriage market.
The authors concluded that these iterations
are not infinite and are bound to conclude after some definite number of
iterations which is a crucial factor for any problem to be computable.
This essentially means that for an
algorithm to be workable it must consist of finite number of steps no matter
how large that number is.
In fact the authors came up with a definite
number and said that the maximum number of iterations that would be needed to
attain the solution to the problem, that is, to have stable pairs of men and
women matched, would be less than n2 – 2n + 2.
I do not have the details as to the working
out of this number but I must tell you that this perhaps is the only formula I
came across in the entire 16 pages of the paper.
The reason that the process will come to a
conclusion is because as long as any woman has not been proposed to there will
be rejections and as long as there are rejections there would be new proposals
made.
But since no man can propose to the same
woman twice every woman is bound to get proposed sooner or later.
So when does the procedure end?
The courting is considered to terminate
when the last single and available woman is proposed to and she will be forced
to accept the proposing man no matter what her options in her love list was.
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