One-Way Stable Mariage Matching

Question

I have to match a list managers and their preferred schools. Each manager will write down their top 5 favorite schools (in order). There are 24 managers and 12 schools; each school gets two managers.

This is the sorting logic I used, but it doesn't seem to work:

Randomly assign 2 managers to each school. 
Calculate the initial total preference, P.
Create an array of all managers
While managers is not empty:
    Select the first manager, m
    Determine its current assigned university, u'
    Determine its top preferred university, u
    Determine the least preferred manager for u, m'
    Try to switch these two managers ( m->u, m'->u')
    Calculate the new preference, P'
    If( P' > P )
        Accept the switch
        Push the manager, m' to the manager array list
    EndIf
EndWhile

The PHP code I have written is:

// Assume $this->managers has the list of all managers, and $this->universities has the list of universities
// Managers are already assigned to the universities
$managers = $this->managers;
shuffle($managers);
while( !empty($managers) ) 
{
    // Select the Manager
    $m       = array_shift($managers);
    // Find school they are part of
    $current = $this->getCurrentUniversity($m);
    // Find their top school
    $top     = $this->getTopUniversity($m, $current);
    // Find least preferred person for $top
    $least   = $this->getLeastManager($top);
    $try     = $this->switchManagers($m, $current, $top, $least);
    // If this makes it better, then accept it!
    $tryPref = $this->preference($try);
    if( $tryPref > $preference ) {
        $this->universities = $try;
        $preference         = $tryPref;
        array_push($managers, $least);
    }  

}

Needless to say, it doesn't work. It does make the match relatively better, but it is not the best sorting. More over, if rerun the program, everytime I get a new result. So the matching is not converging and there is no unique answer.

Why?!

Answer 1

What you have is a transportation problem.

Unfortunately I can't find a complete implementation in PHP, but here's one description of the algorithm.

In essence, a transportation problem is defined as:

Having

• m sources that produce M[] units each, and
• n destinations that require N[] units each, and
• the cost to provide one unit from source i to destination j is defined by matrix A[i][j].

Find such an transportation plan (number of units to provide from each source to each destination), that the total cost is minimal.

In your case, managers provide supply (1 from each) and schools provide demand (2 for each) and the cost to assign manager A to school B is reverse of the position of B in A's preference list.