  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 their preference values
towards their (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. Recently, it was shown that for both paths
and cycles it is NP-hard to decide whether an envy-free arrangement exists,
even for symmetric binary preferences. In contrast, we show that, if agents
come from a bounded number of classes, the problem is solvable in polynomial
time for arbitrarily-valued possibly asymmetric preferences, including
outputting an arrangement if possible. We also give simpler proofs of the
previous hardness results if preferences are allowed to be asymmetric. For
stability, it is known that deciding the existence of stable arrangements is
NP-hard for both topologies, but only if sufficiently-many numerical values are
allowed. As it turns out, even constructing unstable instances can be
challenging in certain cases, e.g., binary values. We completely characterize
the existence of stable arrangements based on the number of distinct values in
the preference matrix and the number of agent classes. We also ask the same
question for non-negative values and give an almost-complete characterization,
the most interesting outstanding case being that of paths with two-valued
non-negative preferences, for which we experimentally find that stable
arrangements always exist and prove it under the additional constraint that
agents can only swap seats when sitting at most two positions away. We moreover
give a polynomial algorithm for determining a stable arrangement assuming a
bounded number of classes.

Computer Science and Game Theory;Computational Complexity