Stable Matching

This is the marriage problem, so it must be better than insects morally. However, this is computer science, so it is quite mechanical. In this algorithm, everybody must be married. Everybody may hate you, but you are included in this circle. Therefore, everybody has the partner. This is idealistic, but it is just gaming.

They are singles. (1,2,3,4) are males. (a,b,c,d) are females. Male(1) prefers female(a) the most, and Male(2) prefers female(c) the most. This is the competition, so you downgrade your preference like (3:a,b,d,c).

You minimize it for stable matching.

min{n,k}

n is the total number of males, and k is the total number of females.

(1,a) (2,c) (3,b) (4,d)

Everybody is happy mathematically, although male(4) likes female(c) and female(a). Patience is necessary sometimes.

This is not stable. (3,d) and (4,d) are conflict. They may fight each other, although d isn't their favorite woman. They may abandon the marriage. Male(4) chooses female(b) for stable matching, but his life may be the nightmare.