0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – rus9384
    Commented Aug 26 at 15:04
  • $\begingroup$ 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. $\endgroup$
    – Spartacus
    Commented Aug 26 at 15:33
  • $\begingroup$ Consider a graph $K_{1,3}$ $\endgroup$
    – rus9384
    Commented Aug 27 at 7:37

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.