Matching or stable marriage problem

Stable marriage problem or stable matching problem is a popular algorithm to match two set of entities where both have preferences over the other set. Elements of a set give ratings or state their choices from the other set. The problem is to find better match (if not best). Here is a java implementation of the algorithm (in a modified form, where one set prioritizes elements from another set, but another set does not have any say on how they get prioritized).

import java.util.Collections;
import java.util.List;

public class MatchMaking {

    // See https://en.wikipedia.org/wiki/Stable_marriage_problem (1st algorithm statement)

    public void stableMatching(List<Person> people, List<Choice> choices)
    {
        // Randomize the people, so that it gives fair chance in case of clash between the choices
        Collections.shuffle(people);

        while(someChoicesAreFree(choices)) {
            for (Person person : people) {
                for (Choice choice : person.getChoicesInOrder()) {
                    if (choice.isFree()) {
                        choice.setEngaged(person);
                        break;
                    } else {
                        Person anotherPerson = choice.getEngaged();
                        if (person.getChoicesInOrder().indexOf(choice) < anotherPerson.getChoicesInOrder().indexOf(choice)) {
                            choice.setEngaged(person);
                        }
                    }
                }
            }
        }

    }

    public boolean someChoicesAreFree(List<Choice> choices) {
        return choices.stream().anyMatch(x -> x.isFree());
    }
}

import java.util.ArrayList;
import java.util.List;

public class MatchMakingTest {
    public static void main(String[] args) {
        Choice c1 = new Choice("c1");
        Choice c2 = new Choice("c2");
        Choice c3 = new Choice("c3");

        Person p1 = new Person("p1");
        p1.addChoice(c2);
        p1.addChoice(c1);
        p1.addChoice(c3);

        Person p2 = new Person("p2");
        p2.addChoice(c1);
        p2.addChoice(c2);
        p2.addChoice(c3);

        Person p3 = new Person("p3");
        p3.addChoice(c1);
        p3.addChoice(c2);
        p3.addChoice(c3);

        List<Choice> choices = new ArrayList<>();
        List<Person> people = new ArrayList<>();

        choices.add(c1);
        choices.add(c2);
        choices.add(c3);

        people.add(p1);
        people.add(p2);
        people.add(p3);

        MatchMaking matchMaking = new MatchMaking();
        matchMaking.stableMatching(people, choices);

        for (Choice choice : choices) {
            System.out.println(choice);
        }
    }
}

import java.util.ArrayList;
import java.util.List;

public class Person {
    private List<Choice> choicesInOrder;
    private String name;

    public Person(String name)
    {
        choicesInOrder = new ArrayList<>();
        this.name = name;
    }

    public void addChoice(Choice choice)
    {
        choicesInOrder.add(choice);
    }

    public List<Choice> getChoicesInOrder()
    {
        return choicesInOrder;
    }

    public String name()
    {
        return this.name;
    }
}

public class Choice {
    private String name;
    private boolean isFree;
    private Person engagedWith;

    public Choice(String name)
    {
        this.name = name;
        isFree = true;
        engagedWith = null;
    }

    public boolean isFree()
    {
        return isFree;
    }

    public void setEngaged (Person p)
    {
        engagedWith = p;
        isFree = false;
    }

    public Person getEngaged()
    {
        return engagedWith;
    }

    public String getChoiceName()
    {
        return this.name;
    }

    public String toString()
    {
        return this.name +
                (engagedWith != null ? " is engaged with " + engagedWith.name() : "");
    }
}

Here, I have tried to get a match between the worst case, where all of them select the same choices. The algorithm shuffles the person list so as to give fair chance in case of such a clash. In normal case (after shuffling) the algorithm awards the first choice to a person, if it is not already selected. If it is selected, it looks at the rating (in this case its just the index it was added as a choice by a person). If a choice was selected first, it is considered to be of higher priority.

Improving the tests

The goal would be to structure the problem of choice in such a way that the results of multiple tests could be applied to effect future decisions. E.g., If Person a’s first choice was c1 during 1st test, should a be awarded c1 during 2nd test and subsequent tests if a choose c1 again. It is a political question. It also largely depends upon the problem type. Does the algorithm have to be fair in terms of distributing the choices evenly over the course of multiple tests. However, fairness is dependent upon the problem at hand. If Person b was seeking to choose c1 from first test and was never awarded the choice should b get higher priority over a. How does it effect the fairness of his subsequent choices (i.e., his second or third choices). The complexity of the problem increases if we add grouping (Type) to the choices. E.g., If we have 5 apples, 5 oranges and 5 mangoes. We can fairly distribute these fruits to 15 people using above algorithm. However, people’s choices keep on changing over the course of multiple tests. How do we distribute the choices fairly, assuming everyone gets their better/fair choice.

References

https://en.wikipedia.org/wiki/Stable_marriage_problem

Advertisements

Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s