## Description

## Problem 1 (Stable Marriage Problem)

Matching problems are about markets where individuals

are matched with individuals or firms or items, typically across two sides, as in employment (e.g.,

who works at which job), university admissions (e.g., which students go to which school), and

kidney donation (e.g., who receives which transplantable organ). In each problem, preferences of

individuals, firms or items are given. The aim is to identify matchings that have nice properties such

as stability. The importance of matching problems is recognized by a Nobel Prize in 2012 given to

Lloyd S. Shapley and Alvin E. Roth.

One of the matching problems described in 1962 by David Gale and Lloyd S. Shapley is Stable

Marriage Problem (SMP).

(i) Define SMP as a computational problem: What is the input? What is the output?

(ii) Give an example for SMP.

## Problem 2 (Gale-Shapley Algorithm)

In 1962, David Gale and Lloyd S. Shapley proved that, for

any equal number of men and women, it is always possible to solve SMP and make all marriages

stable. They presented an algorithm (called the Gale-Shapley algorithm) to compute a solution for

SMP.

(i) Present the Gale-Shapley algorithm with a pseudocode.1

(ii) Analyze the asymptotic time complexity of this algorithm. [Hint: Use the big-oh notation.]

## Problem 3 (BONUS)

Implement the Gale-Shapley algorithm in Python, based on your pseudocode

from Problem 2, and illustrate it with your SMP example from Problem 1.

1

Pseudocode reference by Prof. Sanjeev Arora: http://www.cs.princeton.edu/courses/

archive/spr11/cos116/handouts/Pseudocode_Reference.pdf

1