Execution of the Gale-Shapley algorithm
Although the execution of the Gale-Shapley algorithm is relatively simple, an example will prove illustrative. Consider the following preference lists:

Aladdin:
1. Jasmine
2. Belle
3. Cinderella
4. Ariel

Eric:
1. Cinderella
2. Ariel
3. Belle
4. Jasmine

Prince Charming:
1. Cinderella
2. Jasmine
3. Ariel
4. Belle

The Beast:
1. Ariel
2. Belle
3. Jasmine
4. Cinderella

Jasmine:
1. The Beast
2. Aladdin
3. Eric
4. Prince Charming

Ariel :
1. Aladdin
2. Eric
3. Prince Charming
4. The Beast

Cinderella:
1. Aladdin
2. Prince Charming
3. Eric
4. The Beast

Belle :
1. The Beast
2. Aladdin
3. Eric
4. Prince Charming

Now, let’s execute the Gale-Shapley algorithm, with men as proposers.

Aladdin proposes to Jasmine, Eric and Prince Charming propose to Cinderella, The Beast proposes to Ariel.

Jasmine provisionally accepts Aladdin, Cinderella provisionally accepts Prince Charming, and Ariel provisionally accepts The Beast.

Now Eric is free, so he proposes to Ariel. Ariel rejects The Beast, and provisionally accepts Eric.

Now The Beast is free, so he proposes to Belle. She provisionally accepts him.

No one is free, so the algorithm terminates. Everyone is married to his or her provisional partner. So Jasmine is with Aladdin, Eric is with Ariel, Cinderella is with Prince Charming, and The Beast is with Belle.

Everything is as it should be in the Magic Kingdom.

contents