For context, it's Thanksgiving in the US. I also had a discussion over dinner about the difficulty of finding stable Thanksgiving arrangements with a computer program. This problem is loosely inspired by that conversation, but some of the details about how exactly preferences work are different.
Suppose there are $n$ people sitting at a Thanksgiving table. Each person $n$ is next to two neighbors. Each person, internally, has preferences for which people they would prefer to sit next to. Their preferences are a strict ordering of the other table participants.
Let's also suppose that each person's preferences about the table arrangement overall are completely determined by the worst person they are sitting next to.
Call a table arrangement unstable precisely when there exists a coalition of $n$ people who would each strictly prefer to swap positions in some manner amongst themselves. One veto is enough to block a reshuffle in a coalition. Table participants always veto when they are indifferent between the new arrangement and the status quo.
If we fix an $n$ and consider each set of preferences uniformly at random, approximately what fraction of them have at least one stable seating arrangement?
Let each column denote the preferences of a participant, numbered 1 to 4.
1 2 3 4
-------
2 3 4 1
3 4 1 2
4 1 2 3
As an example, the seating arrangement 12341 is stable. Swapping across the table doesn't change anything. And, for any adjacent pair of people, one of them likes the other the least and therefore won't agree to any swap.
The seating arrangement 12431 is unstable, however, since 1 and 3 are both sitting apart from the person they like the least and have incentive to change places.