Stable Dinner Party Seating Arrangements
METADATA ONLY
Loading...
Author / Producer
Date
2023-07
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
External links
Editor
Book title
Proceedings of the 9th International Workshop on Computational Social Choice
Journal / series
Volume
Pages / Article No.
Publisher
Computational Social Choice
Event
9th International Workshop on Computational Social Choice (COMSOC 2023)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Computer Science and Game Theory (cs.GT); Computational Complexity (cs.CC); FOS: Computer and information sciences
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger
Notes
Funding
Related publications and datasets
Is new version of: 10.48550/arXiv.2305.09549Is part of: https://research.illc.uva.nl/COMSOC/proceedings/comsoc-2023/