In: Math
Gale-Shapley: Prove or dissprove the following theorem
In every execution of the hospitals-propose Stable Matching algorithm, there is at most one hospital that makes offers to every doctor.
If anyone can help me with a long-form proof or an example that dissproves this claim!
Let the hospitals do the "selecting"
let H represent the hospitals, and S represent the students
each h in H need to fill slots, the number of slots can vary, but
the total combined number of slots (includes every hospital) is
less than the total number of students
each student s is free until he or she has accepted (at least
temporarily), an offer from a hospital, then the student is
"matched" to the hospital (but not necessarily committed; this is
like the engagement in the men/women matching problem)
Initially all h in H have no slots "taken"; they are all "free" and
all s in S are free and not "matched". When a slot in h is "taken",
the number of free slot decreases by one. It's possible for the
number of free slots in a hospital to increase if a student first
accepts an offer from h1, then gets an offer from h2 and "leaves"
h1 for h2. Now, the number of free slots h1 has has increased by
1.
Here's the algorithm:
Initially all every slot in every h in H and all s in S are
free
While there is a hospital h with at least 1 free slot and that
hasn't offered to every student S
{
Choose a hospital h with at least 1 slots
Let s be the highest-ranked student in h's preference
list to whom h has not given an offer to
If s is free, then s accepts the offer and the number
of slots h has available decreases by 1
Else s has previously accepted an offer from h'
{
If s prefers h' to h
{
s rejects h's offer
and the slot remains free
}
Else s prefers h to h'
{
s accepts h's
offer and the number of slots h has available decreases by 1
the number of
slots h' has available increases by 1 since s is no longer going to
work there
}
}
}
Returns the matches between every slot for every h in H and each
student s in S that was matched with a slot in a hospital, along
with all the free students S who were never offered slots since
there are more students than slots available.