Stable Tables

Abstract

We consider equilibrium one-on-one conversations between neighbors on a circular table, with the goal of assessing the likelihood of a (perhaps) familiar situation: sitting at a table where both of your neighbors are talking to someone else. When $n$ people in a circle randomly prefer their left or right neighbor, we show that the probability a given person is unmatched in equilibrium (i.e., in a stable matching) is $$\frac{1}{9}+{\left(\frac{1}{2}\right)}^n\left(\frac{2n}{3}-\frac{8}{9}+\frac{2}{n}\right)$$ for odd $n$ and $$\frac{1}{9}-{\left(\frac{1}{2}\right)}^n\left(\frac{2n}{3}-\frac{8}{9}\right)$$ for even $n$. This probability approaches $1/9$ as $n\to \infty$. We also show that the probability \textit{every} person is matched in equilibrium is $0$ for odd $n$ and $\frac{3^{n/2}-1}{2^{n-1}}$ for even $n$.