The Stable Marriage Problem and Sudoku
As you may know, I run PRIMES STEP, a local program where we do mathematical research with students in grades 6-9. Last academic year, we looked at the stable marriage problem and discovered its connection to Sudoku. Our paper The Stable Matching Problem and Sudoku (written jointly with Matvey Borodin, Eric Chen, Aidan Duncan, Boyan Litchev, Jiahe Liu, Veronika Moroz, Matthew Qian, Rohith Raghavan, Garima Rastogi, Michael Voigt) is now available at the arxiv.
Consider 3 men and 3 women who want to be married to each other in heterosexual couples. They rank each other without ties. The resulting 6 permutations of numbers 1, 2, and 3 that describe the six rankings are called the preference profile of this group of people. A matching is unstable if two people would be happier to run away together than to marry into the assigned couples. The two potential runaways are called a rogue couple. A matching is called stable if no rogue couple exists. The Gale-Shapley algorithm, invented by Gale and Shapley, finds a stable matching for any preference profile, implying that stable matching is always possible.
We discovered that preference profiles form a natural bijection with ways to place one digit into a Sudoku grid. So we wrote a paper describing the stable marriage, rogue couples, the Gale-Shapley algorithm, soulmates, and such in terms of Sudoku.
Oops, I forgot to explain who the soulmates are. We invented this term to describe two people who rank each other first. Though it is possible to have several stable matchings for the same preference profile if the soulmates exist, they must always be matched together.
We also invented a new Sudoku type, which I will explain next time.
Share:
Use Sudoku for your successful marriage – The nth Root:
[…] Consider 3 men and 3 women who want to be married to each other in heterosexual couples. They rank each other without ties. The resulting 6 permutations of numbers 1, 2, and 3 that describe the six rankings are called the preference profile of this group of people. A matching is unstable if two people would be happier to run away together than to marry into the assigned couples. The two potential runaways are called a rogue couple. A matching is called stable if no rogue couple exists. The Gale-Shapley algorithm, invented by Gale and Shapley, finds a stable matching for any preference profile, implying that stable matching is always possible. … (Tanya Khovanova’s Math Blog) […]
7 September 2021, 7:09 pmTanya Khovanova's Math Blog » Blog Archive » Joint-Groups Sudoku:
[…] « The Stable Marriage Problem and Sudoku […]
19 September 2021, 5:30 pm