9 June 2018

Author’s Note

  • DISCLAIMER: The author is relatively new to the Gale-Shapley algorithm so would appreciate suggestions and tips.
  • The Gale-Shapley algorithm is unlikely to be the most optimal solution to the problem of allocating delegates with preferences to sessions.
    • With additional time, the author wishes to explore an algorithm that maximises the group utility of delegates.
  • Credit to a Fatma Hussain, a work experience student who came up with the second algorithm, iterative preferences.

Preference Allocation

One-sided matching of delegates to sessions

  • We have a n delegates who have preferences over m sessions they wish to go to.
  • Delegates can only go to one session at any one time.
  • Each session can only hold varying numbers of people.

Or more formally…

Defining the Problem

  • Each delegate, \(d_i\) for \(i = 1, ..., n\), receives utility \(u_{d_i}(s_j)\) from being matched to session \(s_j\)
  • Each session, \(s_j\) for \(j = 1, ..., m\), receives utility \(u_{s_j}(d_i)\) = 0 from being matched to delegate \(d_i\). 1
  • Each delegate, \(d_i\), has a well defined preference ordering over all sessions.
For example, for delegate $d_i$ who has the choice of two sessions $s$ and $s'$, they prefer session $s$ over session $s'$ when $u_{d_i}(s) \ge u_{d_i}(s')$
  • Each session, \(s_j\), can hold \(p_k\) delegates where \(k \in \{1, ..., m\}\).

Note that \(i\), \(j\) and \(k\) belong to the set of natural numbers.

Approaches

To tackle this preference allocation problem, we will take two alternative approaches:

- Gale-Shapley algorithm
- Iterative Preference algorithm

Background

Nobel Prize for Economics 2012

  • The issue we will tackle in this project is popularised by the famous stable marriage problem.
  • At a high level, it asks the question of how a set of men and women should be matched whilst respecting each individual’s preferences.
  • Gale and Shapley first analysed this matching at an abstract, general level in 1962, and proved that for any equal number of men and women, it is always possible to solve the stable marriage problem and make all marriages stable.
  • The Nobel Prize in Economic Sciences 2012 was awared to Lloyd Shapely and Alvin Roth for extending this work in areas such as assigning new doctors to hospitals, students to colleges, and human organ transplants to recipients. 2

Key Assumptions

Key assumptions to our problem and the stable marriage problem are:

  • Each man (delegate) and woman (session) has a well-defined preference ordering, meaning we know their preferences.
  • Each man (delegate) and woman (session) prefers being matched over being not matched.

Our problem differs from the stable marriage problem by:

  • Sessions have no preferences over which delegates attend them. We thus have one-sided matching.
  • Stability here will be defined from the viewpoint of pareto efficiency. 3
  • Each session can hold a varying number of people.

How it Works

Gale-Shapley algorithm

The Gale-Shapley algorithm for the college admissions problem involves a number of rounds:

  1. Students sequentially make proposals to each off their most preferred available colleges.
  2. A college can hold onto at most \(s\) proposals at a time, since they have \(s\) spaces for students.
  3. A college with an open slot will provisionally accept any application it receives.
  4. A college already holding \(s\) applications will reject any student application that it values less than the current applicants they have provisionally accepted.
  5. A college already holding \(s\) applications will accept any student application that it values more than the current applicants they have provisionally accepted, and drop the least valued applicant they have currently provisionally accepted.
  6. Process continues until all students are matched to colleges.

How it Works

Iterative Preference algorithm

The Iterative Preference algorithm involves a number of rounds:

  1. Pick a delegate at random and assign them to their most preferred session.
  2. If this session is full, then assign them to their next most preferred session.
  3. Repeat the previous step until this randomly selected delegate is allocated to a free session.
  4. Pick another delegate at random and repeat the previous steps until they are allocated to a free session.
  5. Process continues until all delegates have been assigned to a free session.

Data

  • For illustrative purposes, we will use dummy data to model preferences. The table below is of delegate preferences.

  • For instance, we can see that for Person 1, they strictly prefer Session 2 over Session 1, \(u_{d_1}(2) > u_{d_1}(1)\).

  • The session preferences table is the transpose of the delegate preferences table above.

  • We have given each session a preference of \(0\) for each delegate. This is because sessions are indifferent over which delegates attend.

  • Suppose that Session 1 and Session 4 can hold two delegates, whereas Session 2 and Session 3 can only hold one delegate.
  • This means that in total, all sessions can hold 6 delegates.
  • Given we have 6 delegates to allocate to sessions, we will not get any unmatched delegates to sessions.

Analysis Approach 1 - Gale-Shapley

In the code below, we will run the college admissions variant of the Gale-Shapley algorithm.

galeShapley.collegeAdmissions(
  studentUtils = utility_delegates,
  collegeUtils = utility_sessions,
  slots = c(2, 1, 1, 2)
)

From running the algorithm we have the following allocation of delegates to sessions. 1, 4, 1, 2, 4, 3.

For instance, `Person 1` and `Person 4` are allocated to Session 1 and Session 2 respectively.

Algorithm’s Output

In the first output is the matched allocations from using the Gale-Shapley algorithm.

##                   Person 1 Person 2 Person 3 Person 4 Person 5 Person 6
## Session Allocated        1        4        1        2        4        3

In the second output is the table of delegates’ initial preferences to compare our allocations against.

Analysis Approach 2 - Iterative Preferences

In the code below, we will run Fatma’s suggested algorithm, Iterative Preferences against the initial preferences of delegates to check that our matchings are desirable.

results_iterativepreference <- func_iterative_preferences(
  x = utility_delegates, 
  limits = c(2, 1, 1, 2), 
  with_replacement = FALSE
)

From running the algorithm we have the following allocation of delegates to sessions. 4, 3, 1, 2, 4, 1.

For instance, Person 2 and Person 4 are allocated to Session 4 and Session 2 respectively.

Algorithm’s Output

In the first output is the matched allocations from using the Iterative Preferences algorithm.

##                   Person 2 Person 6 Person 3 Person 4 Person 1 Person 5
## Session Allocated        4        3        1        2        4        1

In the second output is the random order of delegates that our algorithm used.

## [1] "Person 2" "Person 6" "Person 3" "Person 4" "Person 1" "Person 5"

In the third output is the table of delegates’ initial preferences to compare our allocations against.

Hope you enjoyed the talk! :)