Mathematics

In part 1, I introduced the Stable Marriage problem and proposed implementing it on an FPGA.

In this post, I will define the approach I am taking to define the preferences in binary form.

Series entries:

• Part 1
• Part 2 (this entry)

Note: Blog title image used without permission (pending) from numberphile.com

Since we're only dealing with eight people (four women and four men), I decided to use a 2-bit number to define the Id number of the person within their gender.

With a 2-bit number, that gives us the following Id's to work with (per gender):

• Person #1 - 00
• Person #2 - 01
• Person #3 - 10
• Person #4 - 11

To define the preferences for each person, we can take advantage of the fact that we're only using 2-bits per id and only have four preferences. That means we can use a single byte to define the preferences, with the most significant 2 bits being the first choice.

Here is a table to illustrate some sample preferences:

Proposal Table (Decimal)

So, let's take a look at our proposal cycles using this table:

First cycle

Here are the proposals:

• Woman 1: Man 2
• Woman 2: Man 2
• Woman 3: Man 2
• Woman 4: Man 4

So, Man 2 now has 3 proposals (Woman 1, Woman 2, and Woman 3). If we look at his preferences (3, 1, 2, 4), we see that he prefers Woman 3 over Women 1 and 2, so he declines them and accepts a tentative proposal from Woman 3 (since this is the first match and they both are top of each other's list, they won't be matched with another person, but that is a fact that we can deduce as humans that we can't expect the machine to know).

Woman 4 is tentatively engaged to Man 4.

Women 1 and 2 are left out because they were declined, so they'll propose to their second choice on the second cycle.

At the end of the cycle we have the following state for the Women:

• Woman 1: unmatched
• Woman 2: unmatched
• Woman 3: tentatively engaged to Man 2
• Woman 4: tentatively engaged to Man 4

Second cycle

Here are the choices

• Woman 1: Man 1
• Woman 2: Man 4
• Woman 3: N/A (tentatively engaged)
• Woman 4: N/A (tentatively engaged)

Woman 1 proposes to her 2nd choice, Man 1. Man 1 has not been proposed to yet, so he'll accept.

Woman 2 proposes to Man 4, but he is tentatively engaged to Woman 4. However, since Woman 2 is his first choice, he declines Woman 4 and "trades up" to accept the new proposal from Woman 2.

This leaves Woman 4 alone to propose in the third cycle.

At the end of the cycle we have the following state for the Women:

• Woman 1: tentatively engaged to Man 1
• Woman 2: tentatively engaged to Man 4
• Woman 3: tentatively engaged to Man 2
• Woman 4: unmatched

Third cycle

Here are the choices

• Woman 1: N/A (tentatively engaged)
• Woman 2: N/A (tentatively engaged)
• Woman 3: N/A (tentatively engaged)
• Woman 4: Man 2

So, Woman 4 proposes to Man 2, but he prefers his current fiance, so he declines her.

At the end of the cycle we have the following state for the Women:

• Woman 1: tentatively engaged to Man 1
• Woman 2: tentatively engaged to Man 4
• Woman 3: tentatively engaged to Man 2
• Woman 4: (still) unmatched

Fourth cycle

Here are the choices

• Woman 1: N/A (tentatively engaged)
• Woman 2: N/A (tentatively engaged)
• Woman 3: N/A (tentatively engaged)
• Woman 4: Man 1

Woman 4 proposes to Man 1, but he is tentatively engaged to Woman 1. However, Woman 4 is is top choice, so he declines Woman 1's proposal and "trades up" to accept Woman 4's proposal.

This leaves Woman 1 alone again, forcing her to propose in the next cycle.

At the end of the cycle we have the following state for the Women:

• Woman 1: unmatched
• Woman 2: tentatively engaged to Man 4
• Woman 3: tentatively engaged to Man 2
• Woman 4: tentatively engaged to Man 1

Fifth cycle

Here are the choices

• Woman 1: Man 4
• Woman 2: N/A (tentatively engaged)
• Woman 3: N/A (tentatively engaged)
• Woman 4: N/A (tentatively engaged)

Woman 1 proposes to Man 4, but he is already engaged to his top preference, so he declines her proposal. This leaves her alone again for the next cycle.

At the end of the cycle we have the following state for the Women:

• Woman 1: (still) unmatched
• Woman 2: tentatively engaged to Man 4
• Woman 3: tentatively engaged to Man 2
• Woman 4: tentatively engaged to Man 1

Sixth cycle

Here are the choices

• Woman 1: Man 3
• Woman 2: N/A (tentatively engaged)
• Woman 3: N/A (tentatively engaged)
• Woman 4: N/A (tentatively engaged)

Woman 1 proposes to Man 3, who is currently free, so he accepts her proposal.

At the end of the cycle we have the following state for the Women:

• Woman 1: tentatively engaged to Man 3
• Woman 2: tentatively engaged to Man 4
• Woman 3: tentatively engaged to Man 2
• Woman 4: tentatively engaged to Man 1

We now have no more unmatched Women, so our cycles are complete and we have stable marriages.

Here are the final results:

• Woman 1: engaged to Man 3
• Woman 2: engaged to Man 4
• Woman 3: engaged to Man 2
• Woman 4: engaged to Man 1

Here is the proposal table in binary (with 2-bit Id's)

So to represent the preferences of the Women, we simply create a byte containing their preferences.

Here they are for each woman:

• Woman 1 (00) - 01001110
• Woman 2 (01) - 01111000
• Woman 3 (10) - 01001110
• Woman 4 (11) - 11100100

Note: It's important to notice that I'm referring to them in 1-based decimal (Woman 1, 2, 3, 4), but 0-based binary (Woman 00, Woman 01, Woman 10, Woman 11).

So, to represent these preferences we simply need four sets of 4-bit numbers representing the matching for the women. So, our final results would look like this in binary:

0010 0111 1001 1100

I'm not considering how to scale this out, yet, so I'm making some assumptions on the feasibility of using 2-bit id's rather than full bytes. In the end, a full byte will give us more people, but I wanted to keep this simple. I hope by starting this way I don't adversely effect the overall solution.

Now that I've established the preferences and a way to represent them in binary, I need to figure out the best way to store them and run the cycles on the FPGA.

Next up, defining our finite state machines (FSMs).