# Stable roommate problem (Stability in Seating Arrangements)

The Seating Arrangement Problem (SOP) is a specific variant of the Stable Roommates Problem (SRP) that I have defined. In the SRP, pairs of individuals are seated at two-person tables, whereas in the SOP, individuals are arranged in a single row. An arrangement in the SOP is considered stable if there are no two individuals who mutually prefer each other over both of their current neighbors.

I have proven that any stable matching in the SRP also serves as a stable matching in the SOP. However, I am now facing a challenge: I am almost certain that a stable matching always exists in the SOP, but I am unsure how to prove it. My hypothesis is that we should first assume that the SRP has no stable matching, meaning that at least one preference list is empty in Phase 2, and then demonstrate that a stable matching can still be found in the SOP. If my assumption is incorrect, it would be helpful to have an example where no stable matching exists in both the SRP and the SOP.

• Suppose $A$ prefers $B$, $B$ prefers $A, C$. Now, let's say, they sit in this pattern: $A, C, B, D$. $A$ would prefer to sit with $B$, but $B$ has no issue with the current arrangement. Is this arrangement valid? Commented Aug 26 at 15:04
• But if A prefers B and B prefers A and C, then there is a stable matching with the SRP algorithm. I need an example where there is no stable matching with either SRP or SOP. Commented Aug 26 at 15:33
• Consider a graph $K_{1,3}$ Commented Aug 27 at 7:37