Friendly Frogs, Stable Marriage, and the Magic of Invariance

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.

About the Authors:

Maria Deijfen is a professor in Mathematical Statistics at Stockholm University. She received her PhD from Stockholm University in 2004 and held research positions at Vrije Universiteit Amsterdam, Eurandom (Eindhoven), and Chalmers University of Technology (Gothenburg) before returning to Stockholm University in 2006. Her research area is discrete probability theory, with particular emphasis on spatial structures and random graphs.

Alexander E. Holroyd received his PhD in 2000 from the University of Cambridge. Based in Seattle, he holds affiliate positions at the University of Washington and the Pacific Institute for Mathematical Sciences, and is currently visiting the University of Cambridge. Previously he was at the Theory Group of Microsoft Research, the University of California in Los Angeles and Berkeley, and the University of British Columbia. He works on discrete probability theory with emphasis on percolation, cellular automata, matching, and coupling.

James B. Martin received his PhD in 1999 from the University of Cambridge. After working in Paris for INRIA and for the CNRS, in 2005 he moved to Oxford, where he is based in the Statistics Department and at St. Hugh’s College. He works in probability theory, with particular interests including interacting particle systems, models of random growth and percolation, models of coalescence and fragmentation, and random combinatorial games. Outside mathematics, he is a keen singer, organist, and pianist, and other favorite pursuits include skiing, cricket, and a wide variety of board games and card games.