0 Replies - 7585 Views - Last Post: 10 January 2016 - 10:32 PM Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12135
  • View blog
  • Posts: 45,120
  • Joined: 27-December 08

Algorithmic Game Theory- College Admissions Problem

Posted 10 January 2016 - 10:32 PM

I. Introduction
This tutorial introduces the College Admissions problem, as well as several algorithmic solutions. The College Admissions problem extends the Stable Marriage problem by allowing for a many-to-one matching. The Stable-Marriage problem is a one-to-one matching problem in which each proposer may be matched with at most single acceptor, and vice-versa: e.g., one man and one woman, one firm and one employee, or one student and one school. More realistically, a firm hires many desirable employees, and a college admits many students. To this end, we extend the notion of a one-to-one matching to allow for a many-to-one matching. The College Admissions problem provides a model allowing for a college to be matched with multiple students, but students may only be matched with one college. This is also more realistic of how firms hire workers. I assume familiarity with the Stable Marriage Problem and the Gale-Shapley algorithm.

I have included a LaTeX typeset version of this tutorial for reference.
Attached File  College_Admissions.pdf (182.58K)
Number of downloads: 172

II. Introduction
The College Admissions problem starts with two disjoint sets: a set S of students and a set C of colleges. Each student i \in S has a strict, transitive preference relation \succ^{i} over the set C U \{ \emptyset \}. By convention, if an agent x prefers \emptyset to another agent y, then x prefers being unmatched than to being matched with y. Each college c \in C also has a strict, transitive preference relation \succ^{c} over S U \{\emptyset\}. Additionally, each college c \in C has a capacity qc \in Z+ of students it can admit. The solution is a matching between colleges and students, which is formalized as follows:

Definition 2.1 (Many-to-One Matching). Let S and C be sets. A many-to-one matching from C to S is a function \phi : C \to 2S such that for any distinct c1 and c2 in C, we have \phi(c1) \cap \phi(c2) = \emptyset. Furthermore, if ci \in C has capacity qi, then |\phi(ci)| <= qi.

Applying this definition to the College Admissions Problem, a Many-to-One matching function \phi relates a college c to a subset of students it admits. The matching \phi is further constrained to prohibit a student from being matched with multiple colleges. Lastly, \phi does not allow college c to admit more than qc students.

The definition of a Many-to-One Matching does not account for the actors’ preferences. To this end, the notion of stability will be introduced. Stability in the College Admissions problem is analogous to that in the Stable Marriage problem. First, define the mate function to return a student’s enrolled college: \mu : S \to (C U \{\emptyset\}) by: \mu(s) = c if s is in \phi©, and \mu(s) = \emptyset otherwise.

Definition 2.2 (Stable Matching). A Many-to-One Matching of colleges and students \phi : C \to 2S is stable if and only if the following conditions hold:
  • For any college c and student s such that s \in \phi©, s and c prefer being matched with each other to being unmatched.

  • There does not exist a student s and college c such that s \not \in \phi©, but c \succ^{s} \mu(s), s \succ^{c} \emptyset if |\phi©| < qc, and s \succ^{c} s' for some s' \in \phi© if |\phi©| = q_{c}.


Intuitively, a stable matching satisfies everyone. So no student-college pair should want to deviate and improve their outcomes. The definition of a stable matching prohibits any condition in which a student-college pair would want to match with each other over their current mates in a given matching. Consider a many-to-one matching \phi. The first condition describes when it is preferable for a student and college not to be matched. The second condition describes then prohibits a student-college s \in S and c \in C pair not matched by \phi to prefer matching with each other over their mates in \phi. Clearly, s must prefer c over its mate in \phi to deviate. The analysis of the college takes a little more work due to the fact that it can admit multiple students. If the college c has room for s (i.e., |\phi©| \leq qc), it can and should admit s. If c has fulfilled its capacity, it must check if s is a better choice than one of its already admitted students. If so, c replaces its least preferred admitted student with s.

Let’s consider an example.

Example 1: Suppose we have five student S = \{ s1, ..., s5\} and three colleges C = \{ c1, c2, c3\}. Each student i has the preference relation \succ^{i} := (c1, c2, c3) (that is, c1 is the most preferred and c3 is the least preferred). The colleges have the following preferences and capacities:
  • College c1 has the preference relation \succ := (s1, s2, s3, s4, s5) with capacity qc1 = 2.
  • College c2 has the preference relation \succ := (s5, s4, s3, s2, s1) with capacity qc2 = 1.
  • College c3 has the preference relation \succ := (s1, s2) with capacity qc3 = 1.


Consider the matching \phi : C \to 2S given by \phi(c1) = \{ s1, s2\}, \phi(c2) = \{ s5 \}, and \phi(c3) = \emptyset. Observe that c1 is matched with its top two choices, and s1 and s2 are matched with their top choices. Since \phi(c1) has reached its capacity of two students, it cannot deviate and improve its outcome.

Now consider c2. Observe that \phi gives c2 its top choice, s5. The only college s5 prefers to c2 is c1. However, c1 prefers both of its admitted students over s5 and has no room for s5. Thus, s5 cannot match with another college c1 or c3 which will improve both s5‘s outcome and the college’s outcome.

Next, consider c3. According to c3‘s preference relation, it will only match with s1 and s2. Since s1 and s2 are already matched with c1, which they prefer to c3, it follows that c3 will not admit any students in a stable matching.

Finally, consider s3 and s4. By the above analysis of c3, s4 and s5 can only match with c1 or c2. However, both c1 and c2 have filled their admittance capacities. So s4 and s5 cannot be admitted to any college. So there exists no student-college pair which can mutually deviate and match with each other over their mates in \phi. Additionally, any student-college pair that are matched under \phi prefer each other to being unmatched. Thus, \phi is a stable matching.

The definition of the core will be recalled, but I direct readers to my previous blog entry on the Stable Marriage Problem for further exposition on the core.

Definition 2.3 (Core). Let x = (x1, ..., xn) be an allocation. The allocation y = (y1, ..., yn) is said to dominate or block x if there exists a coalition S \subset N such that for every agent i \in S, yi \succeq^{i} xi; and for at least one j \in S, yj \succ^{j} xj. The Core contains the set of allocations x such that no other allocation y dominates x.

Recall from the Stable Marriage Problem that the unique stable one-to-one matching constitutes the core. The result extends to the College Assignment Problem in the case of many-to-one matchings, which is shown below.

Theorem 2.1: Let S be the set of students, and let C be the set of colleges. Let:

\mathcal{M} = \{ \phi : C \to 2S : \phi is a stable matching \}

And let \mathcal{C} be the core of the College Admissions problem. We have \mathcal{M} = \mathcal{C}.

Proof: Let \phi : C \to 2S be a stable matching. Suppose to the contrary \phi is not in the core. Then there exists a blocking coalition. By the definition of stability, no agent prefers being unmatched to its mate in \phi. So no individual will form a blocking coalition. Note that students only match with colleges, and colleges only match with students. It follows that no coalition consisting solely of students or solely of colleges will form a blocking coalition. Let \{x1, ..., xn\} be a coaliion blocking \phi consisting of both students and colleges. From the definition of a blocking coalition, at least one agent xi in the coalition strictly improves its outcome. As each agent’s preferences are strict, agent xi‘s new mate in the blocking coalition must also strictly improve its outcome over \phi, contradicting the definition of stability. It follows that \mathcal{M} \subset \mathcal{C}.

Now let x be a core allocation. As no coalition exists blocking x, no individual prefers being unmatched to its mate in x. So condition (1) of the stable matching is satisfied. Suppose x is not a stable matching. Then there exists a student-college pair that would strictly benefit from matching with each other over their mates in x. This student-college pair would form a coalition blocking x, contradicting the fact that x is a core allocation. So \mathcal{C} \subset \mathcal{M}. Thus, \mathcal{M} = \mathcal{C}. QED.


In order to find a stable matching in the College Admissions problem, the Gale-Shapley algorithm is adapted to derive two new algorithms: the Student-Optimal Deferred Acceptance (SODA) and College-Optimal Deferred Acceptance (CODA) algorithms. Recall the Gale-Shapley algorithm favors the proposers. The SODA algorithm is the analogue of the Gale-Shapley algorithm when the students propose, and the CODA algorithm is the analogue of the Gale-Shapley algorithm when the colleges propose. We begin by introducing the SODA algorithm.


III. Student-Optimal Deferred Acceptance
The Student-Optimal Deferred Acceptance algorithm works quite similarly to the Gale-Shapley algorithm. Each student takes a turn proposing to a college. If the college has not fulfilled its quota, it admits the student only if it is preferable to being unmatched. If the college has fulfilled its quota and the student is more preferable than an already admitted candidate, the college admits the student applicant and revokes acceptance to its least preferred admittant. Let’s work through an example using the SODA algorithm.

Example 2: Suppose we have six students and three colleges, with each college having a capacity of 2. The preferences are as given below:
  • Students 1 and 4 with preferences: \succ := (Y, X, Z).
  • Students 2 and 5 with preferences: \succ := (X, Z, Y).
  • Students 3 and 6 with preferences \succ := (X, Z, Y).
  • Colleges X and Y with preferences \succ := (2, 5, 3, 6, 1, 4).
  • College Z with preferences \succ := (1, 4, 2, 5, 3, 6).


The SODA algorithm proceeds as follows:
  • Student 1 proposed to College Y. College Y accepted the proposal from Student 1.
  • Student 2 proposed to College X. College X accepted the proposal from Student 2.
  • Student 3 proposed to College X. College X accepted the proposal from Student 3.
  • Student 4 proposed to College Y. College Y accepted the proposal from Student 4.
  • Student 5 proposed to College X. College X accepted the proposal from Student 5 and unmatched from Student 3.
  • Student 6 proposed to College X. College X rejected the proposal from Student 6.
  • Student 6 proposed to College Z. College Z accepted the proposal from Student 6.
  • Student 3 proposed to College Z. College Z accepted the proposal from Student 3.


The final matching is \{ (X, \{2, 5\}), (Y, \{1, 4\}), (Z, \{3, 6\}) \}.

Let’s examine an implementation.

The Student class models a Student in the College-Admissions Problem. The makeProposals() method is the workhorse of the Student class in the SODA algorithm. The makeProposals() method allows the Student to propose to Colleges in preference order until it makes a match or runs out of Students to which it can propose.

package collegeadmissions;

import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * This class models a Student in the College-Admissions Problem.
 * The Student class is designed to allow instances to propose in the
 * Student-Optimal Deferred Acceptance algorithm, or respond to College 
 * proposals in the College-Optimal Deferred Acceptance algorithm.
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
public class Student {

    private ArrayList<College> preferences;
    private College match;
    private String name;
   
    /**
     * @param name The name of this Student
     */
    public Student(String name){
        this.name = name;
        this.preferences = new ArrayList<College>();
    }
    
    /**
     * 
     * @param c The College to insert 
     * @return true if c was successfully inserted, false if c was present in the preference List
     */
    public boolean insertLeastPreferredCollege(College c){
        if(c == null || this.preferences.contains(c)){
            return false;
        }
        
        return this.preferences.add(c);
    }
    
    /**
     * 
     * @param c The College to insert
     * @param preferenceRanking The position in the preference List to insert c
     * @return true if c was successfully inserted, false if c was already present in the preference List
     */
    public boolean insertCollege(College c, int preferenceRanking){
        if(c == null || this.preferences.contains(c)){
            return false;
        }
        
        if(preferenceRanking > this.preferences.size()){
            return this.preferences.add(c);
        }
        
        this.preferences.add(preferenceRanking, c); 
        return true;
    }
    
    /**
     * Determines whether this Student is unmatched and has Colleges to which
     * it has not proposed and with which it is willing to match.
     * 
     * @return true if this Student can make proposals, false otherwise.
     */
    public boolean canMakeProposal(){
        return this.match == null && this.preferences.size() > 0;
    }
    
    /**
     * This method is used in the Student-Optimal Deferred Acceptance algorithm.
     * The Student proceeds by selecting its most preferred College
     * to which it has not already proposed, and makes a proposal.
     * The method terminates when the Student is either matched or
     * runs out of Colleges to which it can propose.
     * 
     * @return true if a College accepts a proposal from this Student, false otherwise
     */
    public boolean makeProposals(){
        College temp = null;
        
        do{
            temp = this.preferences.remove(0);
            System.out.println(this + " proposed to " + temp);
            if(temp.acceptProposal(this)){
                this.match = temp;
                System.out.println(temp + " accepted the proposal from " + this);
                return true;
            }
            
            System.out.println(temp + " rejected the proposal from " + this);
            
        }while(temp != null && this.preferences.size() > 0);
            
        return false;
    }
    
    /**
     * This method unmatches this Student from its current mate.
     * We use this method in the College-Optimal Deferred Acceptance algorithm.
     */
    public void unmatch(){
        this.match = null;
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm,
     * allowing the Student to process a College's proposal. The Student can
     * accept the College's proposal, unmatching its current mate if necessary;
     * or reject c's proposal.
     * 
     * @param c The College proposing to this Student
     * @return true if this Student accepts c's proposal, false otherwise
     */
    public boolean acceptProposal(College c){
        if(!this.preferences.contains(c)){
            return false;
        }
        
        if(this.match == null){
            this.match = c; 
            return true;
        }
        
        int index = this.preferences.indexOf(c);
        int matchIndex = this.preferences.indexOf((this.match));
        
        if(index < matchIndex){
           this.match.unmatchStudent(this);
           this.match = c;
           return true;
        }
        
        return false;
    }
            
    /**
     * @return College this Student's current mate
     */
    public College getMatch(){
        return this.match;
    }
    
    /**
     * @return String A String representation of this Student
     */
    public String toString(){
        return "Student " + this.name;
    }
}   




The College class models a College in the College-Admissions problem. The relevant method for the SODA algorithm is the acceptProposal() method, which checks several conditions. First, it checks if the College is willing to match with the Student. If not, the College outright rejects the proposal. If the College is willing to match with the student over being unmatched, the acceptProposal() method checks if the College has room; and if so, which (if any) existing Student should be replaced by the proposer.

package collegeadmissions;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * This class models a College in the College-Admissions Problem.
 * The College class is designed to allow instances to propose in the
 * College-Optimal Deferred Acceptance algorithm, or respond to Student 
 * proposals in the Student-Optimal Deferred Acceptance algorithm.
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
public class College {
   
    private PriorityQueue<Student> matches;
    private ArrayList<Student> preferences;
    private String name;
    private int capacity;
    
    /**
     * @param name The name of this College
     * @param capacity The number of Students this College can admit
     */
    public College(String name, int capacity){
        this.name = name;
        this.preferences = new ArrayList<Student>();
        this.capacity = capacity;

        //ranks Students based on their positions in the preferences List
        //this Comparator ensures that the PriorityQueue is stores Students
        //in order of increasing preference
        Comparator<Student> ranking = new Comparator<Student>(){
            
            public int compare(Student s1, Student s2){
                int indexOne = College.this.preferences.indexOf(s1);
                int indexTwo = College.this.preferences.indexOf(s2);
                
                return indexTwo - indexOne;
            }
        };
        
        this.matches = new PriorityQueue(capacity, ranking);
        
    }
    
    /**
     * 
     * @param s The Student to insert 
     * @return true if s was successfully inserted, false if s was present in the preference List
     */
    public boolean insertLeastPreferredStudent(Student s){
        if(s == null || this.preferences.contains(s)){
            return false;
        }
        
        return this.preferences.add(s);
    }
    
    /**
     * 
     * @param s The Student to insert
     * @param preferenceRanking The order in the preferences List to insert s
     * @return true if s was successfully inserted, false if s was present in the preference List
     */
    public boolean insertStudent(Student s, int preferenceRanking){
        if(s == null || this.preferences.contains(s)){
            return false;
        }
        
        if(preferenceRanking >= this.preferences.size()){
            return this.preferences.add(s);
        }
        
        this.preferences.add(preferenceRanking, s);
        return true;
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm.
     * A College can make proposals if it has not reached its quota of admitted Students
     * and it has Students to which it has not proposed (and with which it is willing to match).
     * 
     * @return true if this College can make proposals, false otherwise
     */
    public boolean canMakeProposal(){
        return this.matches.size() < this.capacity && this.preferences.size() > 0;
    }
    
    /**
     * @param s The Student to remove from this College's admitted students
     */
    public void unmatchStudent(Student s){
        System.out.println(this + " unmatched from " + s);
        this.matches.remove(s);
    }
    
    /**
     * This method is used in the College-Optimal Deferred Acceptance algorithm.
     * This College proposes to Students in preference order until it has fulfilled
     * its quota or runs out of Students to which it can propose.
     * 
     * @return true if this College added a Student to its matches, false otherwise
     */
    public boolean makeProposals(){
        boolean madeMatch = false;
        
        while(this.preferences.size() > 0 && this.matches.size() < this.capacity){
            Student temp = this.preferences.remove(0);
            System.out.println(this + " proposed to " + temp);
            
            if(temp.acceptProposal(this)){
                this.matches.add(temp);
                madeMatch = true;
                System.out.println(temp + " accepted proposal from " + temp);
                continue;
            }
            
            System.out.println(temp + " rejected proposal from " + temp);
                    
        }
        
        return true;
    }
    
    /**
     * This method is used in the Student-Optimal Deferred Acceptance algorithm,
     * allowing the College to process a Student's proposal. The College may accept
     * the proposal, unmatching its current mate if necessary; or reject the proposal.
     * 
     * @param other The Student proposing to this College
     * @return true iff this College accepted the proposal
     */
    public boolean acceptProposal(Student other){
        int index = this.preferences.indexOf(other);
        if(index == -1){
            return false;
        }
        
        if(this.matches.size() == this.capacity){
            int indexOther = this.preferences.indexOf(this.matches.peek());
            if(index < indexOther){
                Student revoked = this.matches.poll();
                System.out.println(this + " unmatched from " + revoked);
                revoked.unmatch();
                this.matches.add(other);
                return true;
            }
            
            return false;
        }
        
        this.matches.add(other);
        return true;
    }
    
    /**
     * @return PriorityQueue<Student> The admitted Students for this College
     */
    public PriorityQueue<Student> getMatches(){ 
        return this.matches;
    }
    
    /**
     * @return A String representation of this College
     */
    public String toString(){
        return "College " + this.name;
    }
}




For completeness, the MatchMaker and CollegeAdmsisions classes allow executing the algorithms.

MatchMaker.java
package collegeadmissions;

/**
 * This class accepts a List<Student> and List<College>, and allows
 * for the Student-Optimal Deferred Acceptance and College-Optimal 
 * Deferred Acceptance algorithms to be executed on the inputs
 * 
 * @author Michael Levet
 * @date 01/10/2016
 */
import java.util.List;

public class MatchMaker {
    
    private List<Student> students;
    private List<College> colleges;
    
    public MatchMaker(List<Student> students, List<College> colleges){
        this.students = students;
        this.colleges = colleges;
    }
    
    public void sodaMakeMatches(){
        boolean newProposalMade = false;
        
        do{
            newProposalMade = false;
            for(Student s : students){
                if(s.canMakeProposal()){
                   newProposalMade = s.makeProposals();
                }
            }
        }while(newProposalMade);
    }
    
    public void codaMakeMatches(){
        boolean madeMatch = false;
        
        do{
            madeMatch = false;
            
            for(College c : colleges){
                if(c.canMakeProposal()){
                    madeMatch = c.makeProposals();
                }
            }
        }while(madeMatch);
    }
}




CollegeAdmissions.java
package collegeadmissions;

/**
 *
 * @author Michael Levet
 * @date 01/10/2016
 */
import java.util.*;
public class CollegeAdmissions {

    
    public static void main(String[] args) {
        System.out.println("Executing the SODA Algorithm:");
        sodaMakeMatches();
        
        System.out.println("\n\nExecuting the CODA Algorithm:");
        codaMakeMatches();
    }
    
    public static void codaMakeMatches() {
        List<Student> students = new ArrayList<Student>();
        List<College> colleges = new ArrayList<College>();
        
        College c0 = new College("X", 2);
        College c1 = new College("Y", 2);
        College c2 = new College("Z", 2);
        colleges.add(c0);
        colleges.add(c1);
        colleges.add(c2);
        
        for(int i = 0; i < 6; i++){
            Student s = new Student((i+1) + "");
            students.add(s);
            
            if(i != 0 && i != 3){
                s.insertLeastPreferredCollege(c0);
                s.insertLeastPreferredCollege(c2);
                s.insertLeastPreferredCollege(c1);
            }
        }
        
        Student s0 = students.get(0);
        Student s3 = students.get(3);
        
        s0.insertLeastPreferredCollege(c1);
        s0.insertLeastPreferredCollege(c0);
        s0.insertLeastPreferredCollege(c2);
        s3.insertLeastPreferredCollege(c1);
        s3.insertLeastPreferredCollege(c0);
        s3.insertLeastPreferredCollege(c2);
        
        int[] prefs1 = new int[]{1, 4, 2, 5, 0, 3};
        int[] prefs2 = new int[]{0, 3, 1, 4, 2, 5};
        
        for(int i:prefs1){
            c0.insertLeastPreferredStudent(students.get(i));
            c1.insertLeastPreferredStudent(students.get(i));
        }
        
        for(int i:prefs2){
            c2.insertLeastPreferredStudent(students.get(i));
        }
        
        MatchMaker matchMaker = new MatchMaker(students, colleges);
        matchMaker.codaMakeMatches();
        
        for(Student s : students){
            System.out.println(s + " is matched with " + s.getMatch());
        }
        
        for(College c : colleges){
            System.out.println(c + " is matched with " + c.getMatches());
        }
    }

    public static void sodaMakeMatches(){
        List<Student> students = new ArrayList<Student>();
        List<College> colleges = new ArrayList<College>();
        
        College c0 = new College("A", 2);
        College c1 = new College("B", 1);
        College c2 = new College("C", 1);
        colleges.add(c0);
        colleges.add(c1);
        colleges.add(c2);
        
        for(int i = 0; i < 5; i++){
            Student s = new Student((i+1) + "");
            students.add(s);
            c0.insertLeastPreferredStudent(s);
            c1.insertStudent(s, 0);
            for(College c:colleges){
                s.insertLeastPreferredCollege(c);
            }
        }
        
        c2.insertLeastPreferredStudent(students.get(0));
        c2.insertLeastPreferredStudent(students.get(1));
        
        MatchMaker matchMaker = new MatchMaker(students, colleges);
        matchMaker.sodaMakeMatches();
        
        for(Student s : students){
            System.out.println(s + " is matched with " + s.getMatch());
        }
        
        for(College c : colleges){
            System.out.println(c + " is matched with " + c.getMatches());
        }
    }
    
}




A proof of algorithm correctness will be provided.

Theorem 3.1: The SODA algorithm terminates, resulting in a stable matching that is student-optimal.

Claim 3.1.1: The SODA algorithm terminates.

Proof: Suppose that some student s is unmatched after iteration k > |C|. It follows that each college in C to which s has proposed has either rejected s outright, or accepted s‘s proposal and later unmatched from s. If a college c outright rejected s, then s need not propose to c again. If s accepted s‘s initial proposal and later unmatched from s, then s is matched with a second student t such that t \succ^{c} s. Furthermore, for any x \not \in \{s, t\} that c was matched with, it is necessary that x \succ^{c} s (otherwise, as c is rational, it would not have unmatched from x). Agent s prefers to be unmatched than to match with any college to which it did not propose prior to iteration k (otherwise, s would have proposed to one of these colleges prior to iteration k). Thus, s need not be considered again by the algorithm. By consideration of all students, the algorithm must terminate. QED.


Claim 3.1.2: The SODA algorithm produces a stable matching.

Proof: Let \phi be the matching returned by the SODA algorithm. Suppose to the contrary that it is not stable. By the algorithm, no student will propose to a college with which it would not match. Similarly, any college will reject the proposal from a student if it would prefer to remain unmatched over matching with the student. Thus, there exists a student s and college c such that s \not \in \phi©, but c \succ^{s} \mu(s), s \succ^{c} \emptyset if |\phi©| < q_{c}, and s \succ^{c} s^{\prime} for some s^{\prime} \in \phi© if |\phi©| = q_{c}.

By the SODA algorithm, s would have proposed to c prior to its current mate in the matching. If |\phi©| < q_{c} after the algorithm terminates, then c would would have accepted s's proposal, a contradiction. If |\phi©| = q_{c} after the algorithm terminates; then by the algorithm, c would unmatch from its least preferred mate in \phi and mate with s, a contradiction. It follows that the matching must be stable. QED.


Claim 3.1.3: The matching produced from the SODA algorithm is student-optimal.

Proof: Let \phi be the matching returned by the SODA algorithm. Suppose to the contrary that \phi is not student-optimal. Let \phi' be a second stable matching which weakly improves the students’ outcomes, and let s be a student such that \mu'(s) \succ^{s} \mu(s). Then s would have proposed to \mu'(s) prior to \mu(s) under the SODA algorithm. Since s \in \phi'(\mu'(s)), \mu'(s) prefers to match with s over being unmatched. However, \mu'(s) unmatched from s or outright rejected s in the algorithm, implying that \mu'(s) prefers \phi(\mu'(s)) to \phi'(\mu'(s)). Without loss of generality, suppose this was the first instance of a rejection or unmatching in the SODA algorithm. As this is the first instance of rejection or unmatching, there exists a student t \in \phi(\mu'(s)) \setminus \phi'(\mu'(s)). Furthermore, as this is the first instance of rejection or unmatching, each student in \phi(\mu'(s)) can have no stable partner better than \mu'(s). It follows that t prefers \mu'(s) to \mu'(t), and so \{ \mu'(s), \phi(\mu'(s))\} form a coalition blocking \phi', contradicting the stability of \phi'. It follows that \phi is student-optimal. QED.

Claims 3.1.1, 3.1.2, and 3.1.3 together imply Theorem 1. Claim 3.1.3 also yields an important corollary.

Corollary 3.1.3: The SODA algorithm returns the same matching regardless of the order in which the students propose to the colleges.

Remark: When each college has capacity 1, this is exactly the Stable-Marriage problem. Recall the definition of a strategy proof mechanism is one in which truthfully revealing one’s preferences is a weakly dominant strategy. The Stable-Marriage problem has no strategy-proof mechanism, which was shown in my previous blog entry. Therefore, the result extends to the many-to-one matching case. So while in the SODA algorithm, it is optimal for students to truthfully reveal their preferences, this is not the case for the colleges as demonstrated in the example from my previous blog entry. Furthermore, the colleges receive their worst core allocations under the SODA algorithm. This generalizes the result of the Gale-Shapely algorithm, which will be proven next.


Theorem 3.1.2: Under the SODA algorithm, each college receives its least preferred core allocation.

Proof: Let \phi be the stable matching returned by the SODA algorithm. Suppose to the contrary that there exists a second stable matching \phi' that grants each college its least preferred core allocation. Let c be a college such that c prefers strictly \phi© to \phi^{\prime}©. If |\phi'©| > |\phi©|, then any student in \phi'© \setminus \phi© would have proposed to c under the SODA algorithm. As |\phi©| < |\phi'©| \leq qc, c would have admitted at least one of these students. Thus, |\phi©| \geq |\phi'©| necessarily. As c strictly prefers its allocation in \phi over that in \phi', there exists a student in s \in \phi© \setminus \phi'©. As \phi is student-optimal, \{c, \phi©\} forms a coalition blocking \phi', contradicting the stability of \phi'. QED.


IV. College-Optimal Deferred Acceptance
The College-Optimal Deferred Acceptance (CODA) algorithm is the analogue of the Gale-Shapley algorithm in which the colleges do the proposing rather than the students. The algorithm proceeds similarly as the SODA algorithm. It begins by selecting a college c with open slots. If there exist students with whom c will match, c proposes to them in order of preference. A student may accept a proposal or reject it. If a student is matched with a different college than the one proposing, the student must unmatch from its present mate before accepting a proposal from a new mate. Let’s work through an example of the CODA algorithm.

Example 3: Recall the six students and three colleges from Example 2. The CODA algorithm proceeds as follows:
  • College X proposed to Student 2. Student 2 accepted proposal from Student 2.
  • College X proposed to Student 5. Student 5 accepted proposal from Student 5.
  • College Y proposed to Student 2. Student 2 rejected proposal from Student 2.
  • College Y proposed to Student 5. Student 5 rejected proposal from Student 5.
  • College Y proposed to Student 3. Student 3 accepted proposal from Student 3.
  • College Y proposed to Student 6. Student 6 accepted proposal from Student 6.
  • College Z proposed to Student 1. Student 1 accepted proposal from Student 1.
  • College Z proposed to Student 4. Student 4 accepted proposal from Student 4.


The final matching is \{ (X, \{2, 5\}), (Y, \{3, 6\}), (Z, \{1, 4\})\}.

Recall the sample code in Section III. The makeProposals() method in the College class is the workhorse of this algorithm. A given College proposes to Students one at a time in preference order until it has either filled its quota or runs out of Students to which it can propose. Each Student can either outright reject a College’s proposal, or accept the proposal. If the Student is already matched with another College, it must unmatch from its current mate to accept a new proposal. The acceptProposal() method in the Student class handles this logic by checking if the Student is willing to match with the proposing College, and whether the proposing College is more preferable to the Student’s current mate. A College that is unmatched may propose again to any remaining Students in its preference list.

We now examine a proof of algorithm correctness for the CODA algorithm, which is analogous to that of the SODA algorithm.

Theorem 4.1: The CODA algorithm terminates, resulting in a stable matching that is college-optimal.

Claim 4.1.1: The CODA algorithm terminates.

Proof: Suppose there exists an unmatched college c at iteration k > |S|. By the CODA algorithm, each student to which c has proposed either outright rejected the proposal, or accepted the proposal then later unmatched from c. And so each student to which c has already proposed is matched with a college more preferable than c or unmatched. Therefore, c will be rejected if it proposes to these students again. Since k > |S|, c has proposed to all the students with whom it is willing to match. Therefore, c has no available options. By considering all such colleges, it follows that the CODA algorithm terminates. QED.

Claim 4.1.2: The CODA algorithm produces a stable matching.

Proof: Let \phi be the matching returned by the CODA algorithm. Suppose to the contrary that \phi is not stable. Colleges will only propose with whom they are willing to match, and students will only accept proposals from colleges with which they are willing to match. So no individual agent will form a blocking coalition by itself. So there must exist a student s and college c such that s \not \in \phi© but s and c prefer each other to their current mates in \phi. Under the CODA algorithm, c would have proposed to s. If |\phi©| < q_{c}, then s would have been added to \phi© under the CODA algorithm. But since s was not added to \phi©, it follows that |\phi©| = q_{c}. Let t \in \phi© be c's least preferred match. Since \{c, \phi©\} blocks \phi, s \succ^{c} t. Under the CODA algorithm, c would have proposed to s prior to t and s would have accepted, contradicting the fact that t \in \phi©. It follows that \phi must be stable. QED.

Claim 4.1.3: The matching produced by the CODA algorithm is college-optimal.

Proof: Let \phi be the matching returned by the CODA algorithm. Suppose to the contrary that there exists a second stable matching \phi' which weakly improves upon the colleges’ outcomes. Let c \in C such that \phi'© \succ^{c} \phi©. Then there exists a student s \in \phi'© \setminus \phi© such that c prefers s to its least preferred mate t \in \phi©. Then under the CODA algorithm, c would have proposed to s prior to t. However, s must have rejected c. Without loss of generality, suppose this is the first instance of rejection. As \phi' is stable, s prefers being matched with c over being single. So s must be matched with another college x under \phi. Since this is the first instance of rejection, it follows that x can have no better set of mates than \phi(x). So \{x, \phi(x)\} forms a blocking coalition of \phi', contradicting the stability of \phi'. QED.


Remark: Just as the SODA algorithm is not strategy proof, neither is the CODA algorithm. Furthermore, the CODA algorithm grants the students their worst stable matching, analogously to the SODA algorithm with respect to the colleges. This final result will now be proven.

Theorem 4.1.2: Under the CODA algorithm, each student receives its least preferred core allocation.

Proof: Let \phi be the stable matching returned by the CODA algorithm. Suppose to the contrary that there exists a second stable matching \phi' granting each student its least preferred core allocation. Let s be a student such that s strictly prefers its mate in \phi over its mate in \phi'. As \phi is college-optimal, \{\mu(s), \phi(\mu(s))\} blocks \phi', contradicting the stability of \phi'. QED.


V. Conclusion
In this blog entry, the notion of a one-to-one matching was extended to a many-to-one matching. Two extensions of the Gale-Shapley algorithm were explored, including the Student-Optimal Deferred Acceptance and College-Optimal Deferred Acceptance algorithms. We examined sample implementations, as well as proofs of correctness for these algorithms. The College-Admissions problem has an important extension, where Students signal their viabilities to colleges through the use of test scores. In certain approaches, Students may benefit by under-performing on certain tests. So the matching problem can be extended to design a mechanism rewarding students for doing their best on tests. Additionally, the natural question arises of how to extend the many-to-one matching problem to the case of many-to-many matchings.

Is This A Good Question/Topic? 1
  • +

Page 1 of 1