# Friendly Frogs, Stable Marriage, and the Magic of Invariance

by Maria Deijfen, Alexander E. Holroyd, and James B. Martin

Year of Award: 2018

Publication Information: The American Mathematical Monthly, Volume 124, Number 5, May 2017, Pages 387-402.

Summary: Clever connections emerge in this article between a simple two-player game and the stable marriage problem. The authors take the readers on an enjoyable mathematical journey through an analysis of optimal strategy in the “friendly frogs game.” In this game, a pair of frogs occupy positions among a fixed set of lily-pads; the players take turns to jump one of the frogs to a new lily-pad in such a way that the distance between the frogs decreases, until no further moves are possible. Stable matching of pairs of positions arises in a natural way; given a stable matching (as found for example by the Gale-Shapley stable marriage algorithm), one player has a winning strategy in which every move leaves the positions of the two frogs matched. The exposition flows smoothly, leading from a simple start with examples of the game into deeply engaging and accessible mathematics.

Response from the Authors:

We are honored to receive this award! We are strong supporters of the MAA's mission of advancing the understanding of mathematics, and are delighted to be recognized in this way.

Stable marriage is a true gem of mathematics: elegantly simple yet subtle and incredibly useful. We strongly recommend reading the seminal (and very accessible) 1962 paper of Gale and Shapley (in the Monthly!) and the 2012 citation of Roth and Shapley for the Nobel Memorial Prize in Economic Sciences.

We were excited when we noticed an unexpected connection between stable marriage and the beautiful and instantly appealing area of combinatorial games. When we realized that the connection also provided an opportunity to showcase beautiful ideas of modern probability theory, involving translation invariance, ergodicity, and mass transport, it became clear that the Monthly would be the perfect place to share these discoveries.

We very much enjoyed this project, and it was a great pleasure to be able to share that enjoyment more widely with readers of the Monthly.