Stable Dinner Party Seating Arrangements
share
A group of n agents with numerical preferences for each other are to be assigned to the n seats of a dining table. We study two natural topologies: circular (cycle) tables and panel (path) tables. For a given seating arrangement, an agent's utility is the sum of its preference values towards its (at most two) direct neighbors. An arrangement is envy-free if no agent strictly prefers someone else's seat, and it is stable if no two agents strictly prefer each other's seats. We show that it is NP-complete to decide whether an envy-free arrangement exists for both paths and cycles, even with binary preferences. In contrast, under the assumption that agents come from a bounded number of classes, for both topologies, we present polynomial-time algorithms computing envy-free and stable arrangements, working even for general preferences. Proving the hardness of computing stable arrangements seems more difficult, as even constructing unstable instances can be challenging. To this end, we propose a characterization of the existence of stable arrangements based on the number of distinct values in the preference matrix and the number of classes of agents. For two classes of agents, we show that stability can always be ensured, both for paths and cycles. For cycles, we moreover show that binary preferences with four classes of agents, as well as three-valued preferences with three classes of agents, are sufficient to prevent the existence of a stable arrangement. For paths, the latter still holds, while we argue that a path-stable arrangement always exists in the binary case under the additional constraint that agents can only swap seats when sitting at most two positions away. We moreover consider the swap dynamics and exhibit instances where they do not converge, despite a stable arrangement existing.
READ FULL TEXT