Gale-Shapley: Prove or dissprove the following theorem In every execution of the hospitals-propose Stable Matching algorithm,...

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!

Solutions

Expert Solution

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.

milcah answered 8 months ago

Next > < Previous

Related Solutions

Is quicksort a stable sorting algorithm? If yes, prove it, if not, give an example

State a complete proof or disprove with an explicit counterexample: a) Every stable matching is also...

State a complete proof or disprove with an explicit counterexample: a) Every stable matching is also Pareto optimal. b) Every Pareto optimal matching is also stable.

Prove the following: theorem: every topological group is completely regular. Proof. Let V0 be a neighborhood...

Prove the following: theorem: every topological group is completely regular. Proof. Let V0 be a neighborhood of the identity elemetn e, in the topological group G. In general, coose Vn to be a neighborhood of e such that Vn.VncVn-1. Consider the set of all dyadic rationals p, that is all ratinal number of the form k/sn, with k and n inegers. FOr each dyadic rational p in (0,1], define an open set U(p) inductively as foloows: U(1)=V0 and

The goal of this exercise is to prove the following theorem in several steps. Theorem: Let...

The goal of this exercise is to prove the following theorem in several steps. Theorem: Let ? and ? be natural numbers. Then, there exist unique integers ? and ? such that ? = ?? + ? and 0 ≤ ? < ?. Recall: that ? is called the quotient and ? the remainder of the division of ? by ?. (a) Let ?, ? ∈ Z with 0 ≤ ? < ?. Prove that ? divides ? if and...

This question concerns the case of two input sequences. Prove that every algorithm that outputs all...

This question concerns the case of two input sequences. Prove that every algorithm that outputs all longest common subsequences of two input sequences has a worst-case running time that is exponential. To do so, show how to define, for every positive integer n, two length-n sequences Xn, Yn with lower bound (c^n) different longest common subsequences, where c>1 is a constant. You are allowed to use an alphabet of size n, i.e., the symbols in Xn, Yn can come from...

Prove by induction that it follows from Fundamental Theorem of Algebra that every f(x) ∈ C[x]

Prove by induction that it follows from Fundamental Theorem of Algebra that every f(x) ∈ C[x] can be written into a product of linear polynomials in C[x].

Using Kurosch's subgroup theorem for free proucts,prove that every finite subgroup of the free product of...

Using Kurosch's subgroup theorem for free proucts,prove that every finite subgroup of the free product of finite groups is isomorphic to a subgroup of some free factor.

Prove the following theorem: In a Pasch geometry, a quadrilateral is a convex quadrilateral if and...

Prove the following theorem: In a Pasch geometry, a quadrilateral is a convex quadrilateral if and only if the vertex of each angle is contained in the interior of the opposite angle.

Prove the following theorem. If n is a positive integer such that n ≡ 2 (mod...

Prove the following theorem. If n is a positive integer such that n ≡ 2 (mod 4) or n ≡ 3 (mod 4), then n is not a perfect square.

Prove for the following: a. Theorem: (Cantor-Schroder-Bernstein in the 1800s) For any set S, |S| <...

Prove for the following: a. Theorem: (Cantor-Schroder-Bernstein in the 1800s) For any set S, |S| < |P(S)|. b. Proposition N×N is countable. c. Theorem: (Cantor 1873) Q is countable. (Hint: Similar. Prove for positive rationals first. Then just a union.)

Subjects