Optimal Seat Arrangement: What Are the Hard and Easy Cases?

1 Introduction

To designate seating for self-interested agents-seat arrangement-is a fundamental and ubiquitous task in various situations, including seating for offices and events [Lewis and Carroll, 2016; Vangerven et al., 2022], one-sided matching [Gale and Shapley, 1962; Alcalde, 1994], graphical resource allocation with preferences between the agents [Massand and Simon, 2019], project management and team sports [Guti´errez et al., 2016], and hedonic games with additive preferences [Bogomolnaia and Jackson, 2002; Aziz et al., 2013; Woeginger, 2013]. The available seats, either physical or not, can be modeled via an undirected graph, called seat graph, where each vertex corresponds to a seat and two vertices are connected through an edge if the corresponding seats are adjacent. Simple graphs can already model many real-world situations, such as paths for rows of seats in meetings, grids or graphs consisting of disjoint edges for offices, or cliques (complete subgraphs) for groups or teams in games and coalition formation. Since agents have preferences over each other, their utility for a seat may depend on who sits next to them. As such, not every seat arrangement is desired. From a social welfare perspective, one may aim for an arrangement that maximizes the total or the minimum utility of the agents. The corresponding combinatorial problems are called MAX WELFARE ARRANGEMENT (MWA) and MAXMIN UTILITY ARRANGEMENT (MUA), respectively. From a gametheoretical perspective, however, one may aim for an arrangement where no agent envies the seat of another agent or no two agents would rather want to exchange their seats. The corresponding decision problems are called ENVY-FREE ARRANGEMENT (EFA) and EXCHANGE-STABLE ARRANGEMENT (ESA), respectively. We provide an example with four agents p1, p2, p3, p4 in Figure 1. The preferences of the agents are depicted as an arc-weighted directed graph, called preference graph. An arc from agent p to agent q with weight w ̸= 0 means that p has a preference of w towards q. The missing arcs represent 0 preferences. The utility of each agent is additive, i.e., it is the sum of preferences of all the agents seated next to him. In arrangement σ1 (see Figure 1), the utilities of p1, p2, p3, and p4 are -1, 3, 0, and 2, respectively. Hence, the minimum utility is -1 and the sum of utilities, i.e., welfare, of σ1 is 4. Arrangement σ1 maximizes the welfare, but it is not exchange-stable since p1 and p3 envy each other's seat and form an exchange-blocking pair, i.e., they can increase their utility by swapping their seats. Consequently, it is not envy-free. Arrangement σ2 only maximizes the minimum utility, and is envy-free and exchange-stable.

In this work, we provide a refined complexity analysis of the four seat arrangement problems MWA, MUA, EFA, and ESA; the first three problems are known to be NP-hard even for rather restricted cases, such as when the largest component of the seat graph has constant size ℓ = 3 and the preferences are symmetric and non-negative, while ESA is NPhard even when ℓ = 2 [Bodlaender et al., 2020a] and the preferences are strict [Cechl´arov´a and Manlove, 2005], i.e., no agent has the same preferences towards two distinct agents. However, these hardness results do not necessarily transfer to the case when ℓ > 3 as all four problems become trivial if the seat graph is just a complete graph. In other words, the complexity of seat arrangement may also depend on other aspects, such as the seat graph classes and other parameters. Hence, we systematically and extensively study the algorithmic complexity through a combination of three aspects:

Aspect 1: Seat graph classes. We distinguish between path-, cycle-, clique-, stars-, and matching-graphs which means that the graphs induced by the non-isolated vertices consist of a single path, a single cycle, a complete subgraph, disjoint stars, and disjoint edges, respectively. Note that seat arrangement can also be used to model coalition formation or task management [Shehory and Kraus, 1998], so the connectivity between the seats can be more sophisticated than just simple paths and cycles. For instance, in task assignment, when communication between agents must go through a central point, a stars-graph may be needed. More concretely, in a sensor drone network one may divide drones into groups to save communication costs, and choose a center drone for each group through which other drones talk to the outside. In coalition formation, clique-graphs model the case where the task is to form a large coalition, together with singleton agents.

Aspect 2: Parameters. We specifically look at two structural parameters, namely the number k of non-isolated vertices in the seat graph and the maximum number ∆+ of agents known to an agent. Parameter k has computational motivation since all four problems would be trivial if every seat is isolated. Hence, k measures the distance from triviality. Moreover, in many scenarios, such as task assignment, there may be a limited number of tasks that should be worked on by more than one agent, but also many single-agent tasks (i.e., isolated vertices). Parameter ∆+ is motivated by the observation that each agent typically only knows a few other agents, and thus the number of non-zero preferences of an agent is bounded [Bachrach et al., 2013; Cseh et al., 2019b].

Aspect 3: Preference structures. We primarily focus on two natural restrictions: non-negative preferences which occur when no agent has enemies and symmetric preferences where each pair of agents has exactly the same preferences over each other and which can model mutual acquaintances.

Our contributions. We provide a comprehensive complexity picture (see Table 1) and summarize our key contributions as follows:

1. We obtain a number of fixed-parameter tractable (FPT) algorithms for either k or (k,∆+), i.e., the corresponding problems can be solved in time f(k) · |I|O(1) or f(k + ∆+) · |I|O(1) , where f is a computable function solely depending on the argument, and |I| denotes the input size. The FPT algorithms for k are for MWA and MUA under simple seat graphs and are based on colorcoding coupled with book keeping of either the sum of utilities or the minimum utility. The FPT algorithms for (k,∆+) apply to all four problems, mostly without any restrictions on the seat graphs. They are based on random separation or kernelization.
2. We also obtain a number of W[1]-hardness results, most-
3. ly wrt. k; these exclude any FPT algorithm for k in such cases. For MUA and MWA, these remain so for cliquegraphs and symmetric preferences, while for EFA and ESA, they hold for almost all considered seat graph classes. For EFA and ESA, the proofs are based on a novel all-or-nothing gadget (see Figure 2) which may be of independent interest.
4. We strengthen existing NP-hardness results by showing that all four problems remain NP-hard even for constant ∆+ and for severe restrictions on the seat graphs and preference structures. This is done by cleverly tweaking the preference graph with constant ∆+.

Summarizing, we show that for MUA and ESA, the combined parameter (k,∆+) (aspect 1 alone) always gives rise to an FPT algorithm, while for MWA and EFA, this is only the case for symmetric preferences. Additionally, we correct an error by Bodlaender et al. [2020b] and show that EFA remains NP-hard for matching-graphs and strict preferences (see Theorem 10).

Paper outline. In Section 2, we introduce basic concepts and the four central problems. In Sections 3 to 6, we discuss results for MWA, MUA, EFA, and ESA, respectively. In all four sections, we first consider parameter k, then ∆+, and finally the combination (k,∆+). We conclude in Section 7. Due to space constraints, proofs for results or additional material marked with (∗) are deferred to the technical report [Ceylan et al., 2023].

Related work. The solution concepts considered in the four problems are well studied in economics, social choice, and political sciences [Caragiannis et al., 2012; Shapley and Roth, 2012; Aziz et al., 2013; Brandt et al., 2016]. Bodlaender et al. [2020a] initiated the study of the four optimal seat arrangement problems (OSA) and observed that MWA and MUA generalize the NP-hard SPANNING SUBGRAPH ISOMORPHISM problem, while ESA generalizes the NP-hard EXCHANGE-STABLE ROOMMATES problem [Cechl´arov´a and Manlove, 2005]. Very recently, Chen et al. [2021] prove that EXCHANGE-STABLE ROOMMATES remains NP-hard even if each agent has positive preferences over at most three agents. Derived from this, we show the same holds for ESA under matching-graphs and with constant ∆+. OSA has been getting more attention recently. Tomi´c and Uroˇsevi´c [2021] provide heuristic approaches for solving MWA where the seat graph consists of equal-sized cliques. Vangerven et al. [2022] studied a related problem for parliament seating but the objective is different from ours.

OSA generalizes multi-dimensional matchings [Cseh et al., 2019a; Bredereck et al., 2020; Chen and Roy, 2022] and hedonic games with fixed-sized coalitions [Bil`o et al., 2022] where the seat graph consists of equal-sized cliques and cliques of fixed sizes, respectively. Bil`o et al. [2022] consider paths to exchange stability and MWA and strengthened the complexity result by Bodlaender et al. [2020a] by showing that MWA remains highly inapproximable even if the seat graph consists of cliques of constant sizes. Massand and Simon [2019] studied a generalization of OSA where the agents additionally have non-negative valuations over the seats such that the utility of an agent is the sum of his valuation of the assigned seat and his preferences over the agents in his neighborhood. Their results imply that EFA remains NP-hard even if the preference graph is a cycle with binary preferences, and that for symmetric preferences, an exchange-stable arrangement can always be obtained from a given arrangement via a finite number of swaps.

OSA can also be conceptualized as hedonic games with overlapping coalitions similar to Schelling games which has been shown to be NP-hard for simple models [Agarwal et al., 2021; Kreisel et al., 2022]. However, in Schelling games the preferences are more restricted. We refer to the work of Bodlaender et al. [2020a] for additional references.

2 Preliminaries

Given an integer t, let [t] denote the set {1, 2, . . . , t}. We recall the following graph theoretic concepts. Given an undirected graph G and a vertex v ∈ V (G), we use NG(v) to denote v's open neighborhood {w ∈ V (G) | {v, w} ∈ E(G)}. Given a directed graph F, and a vertex v ∈ V (F) we use N - F (v) and N + F (v) to denote the set of in- and outneighbors of v, respectively.

A seat arrangement instance consists of a set P of n agents, where each agent p ∈ P has cardinal preferences over the other agents, specified by the satisfaction function satp : P \ {p} → R for all p ∈ P , and an undirected graph G, called seat graph, where the number of vertices is the same as the number of agents, i.e., |V (G)| = n. We derive a weighted directed graph F = (P, A, (satp)p∈P ) from satp, called preference graph, where the vertex set is the set P of agents and A denotes the set of arcs such that an arc from agent p to q means that satp(q) ̸= 0. Note that, intuitively, negative (resp. positive) preference values model the degree of dislike (likeness) while zero values model indifference. The goal of optimal seat arrangement is to find a bijection σ: P → V (G), called arrangement, which is optimal or fair. A partial arrangement is an injective function σ which assigns only a subset of the agents to the vertices of G, i.e., σ-1 (V (G)) ⊂ P .

We look into four different criteria, namely utilitarian and egalitarian welfares, envy-freeness, and exchange stability. Given an arrangement σ, we define the utility of each agent p ∈ P as the sum of the satisfactions of p towards his neighbors in σ, i.e., utilp(σ) := ∑v∈NG(σ(p)) satp(σ-1 (v)). By convention, the utilitarian (resp. egalitarian) welfare of σ is the sum (resp. minimum) of utilities of the agents towards σ, denoted as wel(σ) := ∑p utilp(σ) (resp. egal(σ) :=minp(utilp(σ))). Additionally, for two agents p, q ∈ P we define the swap-arrangement σ[p↔q] as the arrangement where just p and q switch their seats in σ, i.e., σ[p↔q](p) := σ(q), σ[p↔q](q) := σ(p), and all other agents x ∈ P \{p, q} remain in their seats, i.e., σ[p↔q](x) := σ(x). An arrangement σ is called envy-free (resp. exchangestable) if no agent envies any other agent (resp. no two agents envy each other). An agent p ∈ P envies another agent q ∈ P \ {p} (in σ) if p finds the seat of q more attractive than his own, i.e., utilp(σ) < utilp(σ[p↔q]), and he is envy-free if he does not envy any other agents. By definition, envyfreeness implies exchange stability.

Based on the different criteria, we define four computational/decision problems.

MWA (resp. MUA)

maximumwel(σ) (resp. egal(σ)).

EFA (resp. ESA)

Input: An instance (P, (satp)p∈P ,G).

Question:Is there an arrangement σ: P → V (G)

which is envy-free (resp. exchange-stable)?

In the decision variant of MWA (resp. MUA), the input additionally has an integer L, and the question is whether there is an arrangement σ with wel(σ) ≥ L (resp. egal(σ) ≥ L). It is straightforward that EFA, ESA, and the decision variants of MWA and MUA belong to NP.

Let I = (P, (satp)p∈P , G) be an instance of our problems. We say that the preferences of the agents are

• binary if satp(q) ∈ {0, 1} holds for each {p, q} ⊆ P ,
• non-negative if satp(q) ≥ 0 holds for each {p, q} ⊆ P ,
• positive if satp(q) > 0 holds for each {p, q} ⊆ P ,
• symmetric if satp(q) = satq(p) holds for each {p, q} ⊆ P ,
• strict if satp(q1) ̸= satp(q2) holds for each three distinct

agents p, q1, q2 ∈ P .

We say that the seat graph is a

• clique-graph if it consists of a complete subgraph (aka. clique) and isolated vertices,
• stars-graph if each connected component is a star,
• path- (resp. cycle-) graph if it consists of a path (resp. cycle) and isolated vertices,
• matching-graph if it consists of disjoint edges and isolated vertices.

We use k (resp. ∆+) to denote the number of non-isolated vertices in the seat graph (resp. maximum out-degree of the vertices in the preference graph). Briefly put, k bounds the number of relevant seats that have neighbors, while ∆+ bounds the maximum number of agents that an agent likes or dislikes. We observe that all four problems are polynomial-time solvable for a constant number of non-isolated vertices by a simple brute-forcing algorithm.

Observation 1 (∗). MWA, MUA, EFA, and ESA are in XP wrt. k.

We assume basic knowledge of parameterized complexity such as fixed-parameter tractability (FPT), W[1]-hardness, and XP, and refer to the following textbooks [Niedermeier, 2006; Cygan et al., 2015] for more details.

3 MAX WELFARE ARRANGEMENT

In this section we study the (parameterized) complexity of finding an arrangement that maximizes the welfare. Using color-coding coupled with a book keeping for welfare, we get fixed-parameter tractability (FPT) for simple graphs:

Theorem 1 (∗). MWA is FPT wrt. k if the seat graph is a path-, cycle-, or stars-graph.

However, it is W[1]-hard even for restricted preferences and when the seat graph is a clique-graph since the problem generalizes the CLIQUE problem which is W[1]-hard wrt. the solution size [Downey and Fellows, 2013].

Theorem 2 (∗). For clique-graphs, MWA is W[1]-hard wrt. k, even for strict, or binary and symmetric preferences.

Surprisingly, even if each agent only knows two others, FPT algorithms (wrt. k) for MWA are unlikely:

Theorem 3. For clique graphs, MWA remains W[1]-hard wrt. k, even for binary preferences with ∆+ = 2.

Proof. We prove this via a parameterized reduction from CLIQUE, parameterized by the solution size h [Downey and Fellows, 2013]. For each vertex vi ∈ V ( ˆG) (resp. edge eℓ ∈ E( ˆG)), we create one vertex-agent pi (resp. edgeagent qℓ), and set satqℓ (pi) = 1 if vi ∈ eℓ. The nonmentioned preferences are set to zero. The seat graph G consists of a clique of size k := h+ (h2) and |V ( ˆG)|+|E( ˆG)|-k isolated vertices. Clearly, the preferences are binary. Since only edge-agents have positive preferences (towards incident vertices), we infer ∆+ = 2, as desired.

We show that ˆG admits a size-h clique if and only if there is an arrangement σ with wel(σ) ≥ h(h - 1). The forward direction is straightforward by assigning the corresponding vertex- and edge-agents contained in the h-clique to the nonisolated vertices in the clique-graph.

For the backward direction, we first observe that at least (h2) edge-agents are non-isolated; otherwise this would imply that wel(σ) < h(h-1). If (h2) +x edge-agents are assigned to non-isolated vertices with x ≥ 1, then we observe: (i) Each non-isolated edge-agent qℓ has a positive utility. Otherwise, we can exchange qℓ with a vertex-agent which is incident to some other non-isolated edge-agent. This would only increase the welfare. (ii) There are h - x vertex-agents assigned to non-isolated vertices. Hence, there can be at most (h-x 2 ) edge-agents with both endpoints in the clique. Because of (h2) + x - (h-x 2 ) ≥ 1 + x ≥ 2, we can always find two edge-agents with only one endpoint in the clique. If we exchange one edge-agent with a missing vertex-agent of the other edges, then the welfare does not decrease. Therefore, if there is an arrangement σ with wel(σ) ≥ h(h-1), we can apply these exchange-arguments until there is no more such pair. This implies that exactly (h2) edge-agents (and exactly h vertex-agents) are non-isolated. Moreover, each of these edge-agents has a utility of two, since otherwise we cannot reach the desired welfare. As there are h non-isolated vertex-agents which are incident to (h2) edge-agents, it follows that the corresponding h vertices in ˆG form a clique.

Except for matching-graphs, MWA remains intractable for constant ∆+ since it can be rephrased as finding a densest subgraph in the preference graph which remains hard for constant degree; this is also independently noted by Bil ´o et al. [2022]:

Theorem 4 (∗). For binary and symmetric preferences, MWA remains NP-hard for constant ∆+ and for each considered seat graph class except the matching-graphs.

The previous hardness results motivate us to study the combined parameters (k,∆+) for symmetric preferences. We conclude the section with another color-coding based algorithm which is more involved than the one for Theorem 1 since it works for arbitrary seat graphs.

Theorem 5 (∗). For symmetric preferences, MWA is FPT wrt. k +∆+.

4 MAXMIN UTILITY ARRANGEMENT

In this section, we focus on maximizing the minimum utility. Under non-negative preferences, FPT algorithms (wrt. k) exist since any non-trivial instance has at most k agents:

Proposition 1 (∗). For non-negative preferences, MUA is FPT wrt. k, and becomes polynomial-time solvable if the seat graph is a clique-graph.

The presence of negative preferences excludes any FPT algorithm (wrt. k) for MUA since it generalizes CLIQUE:

Theorem 6 (∗). MUA is W[1]-hard wrt. k, even for a cliquegraph and for symmetric or strict preferences.

For simple seat graphs, we can again combine color-coding with dynamic programming to obtain FPT algorithms for the single parameter k:

Theorem 7 (∗). For stars-, path-, and cycle-graphs, MUA is FPT wrt. k.

Unfortunately, MUA cannot be solved in polynomial time even if each agent knows a few other agents and the preferences are symmetric, unless P=NP.

Theorem 8 (∗). For symmetric preferences and for each of the following restrictions, MUA remains NP-hard for constant ∆+: (i) a clique-graph, (ii) a path-graph and nonnegative preferences, (iii) a cycle-graph and binary preferences, (iv) a stars-graph where each star has two leaves and binary preferences.

MUA admits a polynomial-size problem kernel for the combined parameters (k, ∆+).

Theorem 9. MUA is FPT wrt. k +∆+.

Proof. The idea is to obtain a polynomial-sized problem kernel, i.e., an equivalent instance of size (k+∆+)O(1) , or solve the problem in polynomial time. First, if the seat graph has no isolated vertices, then |P | = k and we have a linear-sized kernel. Otherwise, egal(σ) ≤ 0 holds for every arrangement σ. Further, we observe that in every directed graph with maximum out-degree ∆+, there is always a vertex with in-degree bounded by ∆+. That is, the sum of in- and out-degrees of this vertex is at most 2∆+. Hence, we iteratively select an agent p with minimum in-degree in the preference graph, put him to our solution S, and delete all in- and out-neighbors of p. If, after k steps, we can find a set S of k "independent" agents (they do not have arcs towards each other), then we can assign them arbitrarily to the non-isolated vertices. Since the preference between each two agents in S is zero, the utility of each agent in S is also zero. Hence, we found an arrangement σ with egal(σ) = 0. If we could not find k independent agents, then the instance has at most k(1+2∆+) agents since in each step we deleted at most 1+2∆+ agents. It is straightforward that the approach above runs in polynomial time.

5 ENVY-FREE ARRANGEMENT

In this section, we consider envy-freeness. First, we observe the following for non-negative preferences and we will use it extensively in designing both algorithms and reductions.

Observation 2. Let p be an agent with non-negative preferences. Then, for each envy-free arrangement it holds that if p is isolated, then every q with satp(q)>0 is isolated as well.

By Observation 2, deciding envy-freeness is easy for cliquegraphs when the preferences are additionally symmetric.

Proposition 2 (∗). For clique-graphs, and non-negative and symmetric preferences, EFA is polynomial-time solvable.

By Observation 1, EFA is polynomial-time solvable for constant k. In the next two theorems, we show that this result cannot be improved to obtain FPT algorithms by providing a parameterized reduction from either CLIQUE or INDEPENDENT SET (wrt. the solution size h). We introduce a novel all-or-nothing gadget (see Figure 2 for an example) to enforce that only f(h) many copies of the all-or-nothing gadgets can be non-isolated, which correspond to a solution of size h. In addition, Theorem 10 corrects an error by Bodlaender et al. [2020b] and shows that EFA remains NP-hard for matching-graphs and strict preferences. A crucial observation in this setting is that not every non-isolated agent needs to be matched with his most preferred agent.

Theorem 10 (∗). For each considered seat graph class, EFA is W[1]-hard wrt. k even if the preferences are binary or strict.

Theorem 11 (∗). For clique-, stars-, path-, and cycle-graphs, and for symmetric preferences, EFA is W[1]-hard wrt. k.

Proof sketch. We only show the case with path- and cyclegraphs via a parameterized reduction from CLIQUE, parameterized by the solution size [Downey and Fellows, 2013]. Let ( ˆG, h) be an instance of CLIQUE. For each vi ∈ V ( ˆG), create h(h - 1) vertex-agents p1i , . . . , ph(h-1) i . For each eℓ ∈ E( ˆG), create h4 + 1 edge-agents q0 ℓ , q1 ℓ , . . . , qh4 ℓ .

Since the preferences will be symmetric, we only specify one value for each pair of agents (see Figure 2 for the corresponding preference graph). For each (eℓ, vi) ∈ E( ˆG) × V ( ˆG), we do the following: Set satpsh+z i (psh+z+1 i ) = z for each (z, s) ∈ [h-1]×{0, . . . , h-2}, and if s ̸= h-2, then set satpsh+2 i (p(s+1)h+2 i ) = 1. For each z ∈ {0} ∪ [h4 - 1], set satqz ℓ (qz+1 ℓ ) = 1 and satq0 ℓ (q2 ℓ ) = satq3 ℓ (qh4 ℓ ) = 1. For each s ∈ {0} ∪[h - 2], set satq2 ℓ (psh+2 i )=-1 if vi ∈ eℓ. The non-mentioned preferences are set to zero. The seat graph G consists of a path (resp. cycle) with k := h2 (h-1)+h(h-1) vertices and |V ( ˆG)|h(h - 1) + |E( ˆG)|(h4 + 1) - k isolated vertices.

It remains to show that ˆG admits a size-h clique if and only if I admits an envy-free arrangement. For the "only if" part, let C be a size-h clique. For the path we begin assigning at one of the endpoints; for the cycle we can begin at any non-isolated vertex. For each edge eℓ = {vi, vj} ∈ C and some (not yet used) z, z′ ∈ [h - 1], assign agents pzh i , . . . , p(z-1)h+1 i , q0 ℓ , q1 ℓ , p(z′-1)h+1 j , . . . , pz′ h j in this order to the path (resp. cycle). Since each vertex vi ∈ C is incident to exactly h - 1 edges in C, we can find such z, z′ ∈ [h - 1]. The remaining agents are assigned to isolated vertices. This arrangement is envy-free because: (i) Every vertex-agent pzi with vi ∈ C, z ∈ [h(h-1)] has his maximum possible utility. (ii) Vertex-agents pzi with vi /∈ C, z ∈ [h(h - 1)] are envyfree since there is no non-isolated agent towards which pzi has a positive preference. (iii) All edge-agents q0 ℓ , q1 ℓ with eℓ ∈ C are envy-free since they have maximum possible utility one. (iv) The remaining edge-agents assigned to isolated vertices either have no non-isolated agent towards which they have a positive preference, or the corresponding agents q0 ℓ , q1 ℓ are assigned in such a way, that q2 ℓ does not envy his neighbors. Before we prove the "if" part, we observe the following.

Claim 11.1 (∗). Every envy-free arrangement σ satisfies:

• (i) For each edge eℓ ∈ E( ˆG), agents q2 ℓ , . . . , qh4 ℓ are always assigned to isolated vertices.
• (ii) If a vertex-agent pzi with vi ∈ V ( ˆG), z ∈ [h(h - 1)] is non-isolated, then all agents from {p1i , . . . , ph(h-1) i } are non-isolated. Moreover, if such a set of agents is non-isolated, then the seats of psh+z i and psh+z+1 i for s ∈ {0} ∪ [h - 2], z ∈ [h - 1] are adjacent.
• (iii) If q0 ℓ or q1 ℓ is non-isolated for some eℓ ∈ E( ˆG), then q0 ℓ and q1 ℓ are non-isolated and their seats are adjacent.
• (iv) If q0 ℓ and q1 ℓ are non-isolated for eℓ = {vi, vj} ∈ E( ˆG), then both q0 ℓ and q1 ℓ are adjacent in σ to vertex-agents corresponding to vi or vj. In particular, q0 ℓ and q1 ℓ are adjacent to psh+1 i or psh+1 j with s ∈ {0}∪[h-2], where the next h seats on the path (resp. cycle) are assigned to psh+1 i , . . . , p(s+1)h i or psh+1 j , . . . , p(s+1)h j .

By Claim 11.1(ii), at most h different groups of vertex-agents can be assigned to the path (resp. cycle), i.e., non-isolated. By our bound on k, at least 2(h2) many edge-agents are nonisolated. By Claim 11.1(iii), at least (h2) many pairs of edgeagents of the form {q0 ℓ , q1 ℓ } are non-isolated. Let E′ ⊆ E( ˆG) denote the set of edges that correspond to the non-isolated edge-agents. By Claim 11.1(iv), all vertex-agents that are "incident" to the edges in E′ must also be non-isolated. Since only h different groups of vertex-agents can be non-isolated, this corresponds to a clique of size h in ˆG.

The next two theorems show that achieving envy-freeness remains hard for bounded maximum out-degree and binary (resp. symmetric) preferences. The proofs are similar to the ones for Theorems 10 and 11.

Theorem 12 (∗). For each considered graph class, EFA remains NP-hard for binary preferences with ∆+ = 3.

Theorem 13 (∗). EFA remains NP-hard even for a clique-, path-, cycle-, or stars-graph and symmetric preferences with constant ∆+.

Under non-negative or symmetric preferences, we obtain an FPT algorithm for k + ∆+, which is based on random separation and dynamic programming.

Theorem 14 (∗). For non-negative or symmetric preferences, EFA is FPT wrt. k + ∆+.

Proof sketch. We only consider the case with non-negative preferences. Let I = (P, (satp)p∈P ,G) be an EFA instance with non-negative preferences. Then, no non-isolated agent in an envy-free arrangement can have any in-arcs from isolated agents by the contrapositive of Observation 2. This means that each non-isolated agent has bounded in- and outdegree. Hence, we can use random separation to separate the non-isolated agents from their isolated neighbors. The approach is as follows: Color every agent independently with r or b, each with probability 1/2. We say that a coloring χ: P → {r, b} is successful if there exists an envy-free arrangement σ such that

• (i) χ(p) = r for each p ∈ W and
• (ii) χ(p) = b for each p ∈ (P \W) ∩N + F (W ),

where W := {p ∈ P | δG(σ(p)) ≥ 1} denotes the set of nonisolated agents in σ. Note that by the above reasoning, if p ∈W, then it holds N - F (p) ⊆ W and by the first condition, all agents in N - F (p) are colored with r. Since the seat graph has k non-isolated vertices and the out-degree of each agent in the preference graph is bounded by ∆+, we infer that |W|+ |(P \ W) ∩ N + F (W)| ≤ k(1 +∆+). Hence, the probability that a random coloring is successful is at least 2-k(1+∆+) .

Let Pr be the subset of agents colored with r. We already know for each weakly connected component C of Pr that the agents in C are all assigned to either isolated or non-isolated vertices (see Observation 2). Therefore, the size of each component is bounded by k. It remains to decide which component to assign to non-isolated vertices and how to assign them.

Let the vertices of the seat graph G be denoted by {1, 2, . . . , k}. We design a simple algorithm using colorcoding as follows. We color the red agents Pr uniformly at random with colors [k]. The k colors one-to-one correspond to the k non-isolated seats in the seat graph. Let σ be a hypothetical envy-free arrangement and χ′ : Pr → [k] a coloring. We say χ′ is good (wrt. σ) if the agent at the ith vertex of G is colored i, i.e., χ′ (σ-1 (i)) = i, for each i ∈ [k]. Note that given a solution σ, the probability that the k nonisolated agents are colored with pairwise distinct colors is at least e-k [Cygan et al., 2015]. Since for each component all agents are assigned to either non-isolated or to isolated vertices, we can first check for each component, if each color appears at most once. If there are two agents p1 and p2 with χ′ (p1) = χ′ (p2), then this component will be assigned to isolated vertices in a good coloring. Since there are O(n) components, this can be done in time O(k2 · n).

For each remaining component, we check whether the given arrangement is envy-free. In this regard, we observe that the utility of an agent only depends on the agents inside the same component as all preferences between two components are zero. Hence, we compute for each agent p with χ′ (p) = i in a component C his utility utilp(ρ) = ∑q∈C\{p},χ′ (q)=j,{i,j}∈E(G) satp(q). Similarly, we can compute the utility of p in a swap-arrangement, where p and the agent assigned to seat j ̸= i swap their seats and determine whether p is envy-free. If not, we can assign this component to isolated vertices. Since each component has O(k) agents, this step can be done in time O(k2 · n).

Finally, we use dynamic programming (DP) to select from the remaining envy-free components those whose colors match the seats and sizes sum up to k. Let C1,C2, . . . ,Cm be the remaining weakly connected components. We define a DP table where an entry T[S, i] is true if there is a partial arrangement assigning the first i weakly connected components, where (i) no two non-isolated agents are colored with the same color and (ii) each color in S is used once.

We start filling our table for i = 1 as follows:

Each component Ci is either non-isolated or isolated. Therefore, the following recurrence holds:

Since S ⊆ [k], the entries of this table can be computed in time 2k · nO(1) . Summing up, the above algorithm runs in time 2k · nO(1) . The probability of a successful and good coloring is at least 2-k(1+∆+) · e-k . Hence, after repeating this algorithm 2k(1+∆+) · ek times we obtain a solution with high probability. Finally, we can de-randomize the random separation and color-coding approaches while maintaining fixedparameter tractability [Cygan et al., 2015].

For matching-graphs we also obtain fixed-parameter tractability even for arbitrary preferences.

Theorem 15 (∗). For matching-graphs, EFA is FPT wrt. k + ∆+.

The same approach for matching-graphs does not hold for other graphs as implied by the next two theorems. The proofs are once again similar to the ones for Theorems 10 and 11.

Theorem 16 (∗). EFA is W[1]-hard wrt. k, even if ∆+ = 3 and the seat graph is a clique- or stars-graph.

Theorem 17 (∗). EFA is W[1]-hard wrt. k +∆+, even for a path- or cycle-graph.

6 EXCHANGE-STABLE ARRANGEMENT

In this section we consider the last concept exchange stability. We first show that an exchange-stable arrangement always exists for clique-graphs and non-negative preferences.

Observation 3. For clique-graphs and non-negative preferences, ESA is polynomial-time solvable.

Proof. With non-negative preferences, no agent assigned to non-isolated vertices envies an isolated agent. Moreover, each agent is indifferent towards the seats in the clique. Hence, they will not form any exchange-blocking pair.

In general, the problem remains intractable, even for cliqueor matching-graphs. Particularly, it is unlikely that an FPT algorithmwrt. k exists, implied by the following.

Theorem 18 (∗). ESA is W[1]-hard wrt. k, even for a clique-, stars-, or matching-graph.

Proof sketch. We show the case with clique-graphs. We provide a parameterized reduction from INDEPENDENT SET parameterized by the solution size h [Downey and Fellows, 2013]. Given an instance ( ˆG, h) of INDEPENDENT SET, we create for each vertex vi ∈ V ( ˆG) a vertex-agent pi, and two special agents x1 and x2. For each two vi, vj ∈ V ( ˆG), the preferences are defined as follows (see Figure 3 for the corresponding preference graph): If {vi, vj} ∈ E( ˆG), set satpi (pj) = satpj (pi) = -1. Finally, set satpi (x2) = h, satx1 (x2) = -h, satx2 (x1) = h, satx1 (pi) = 1, and satx2 (pi) = -1. The non-mentioned preferences are zero. The seat graph G consists of a clique of size k := h + 1 and |V ( ˆG)| + 2 - k isolated vertices.

It remains to show that ˆG admits a size-h independent set if and only if the constructed instance admits an exchangestable arrangement. First, we observe the following.

Claim18.1. In every exchange-stable arrangement, agent x2 is assigned to an isolated vertex.

Proof of Claim 18.1. Towards a contradiction, suppose that σ is exchange-stable where x2 is non-isolated. If x1 is isolated, then utilx2 (σ) = -h < 0 and utilx1 (σ[x1↔x2]) = h > 0, implying that {x1, x2} is an exchange-blocking pair, a contradiction. If x1 is non-isolated, then utilx1 (σ) = -1. Since there is a vertex-agent pi ∈ P assigned to an isolated vertex and utilpi (σ[pi↔x1]) > 0, agents x1 and pi form an exchangeblocking pair, a contradiction. ⋄

Hence, at least h vertex-agents have to be assigned to the non-isolated vertices in an exchange-stable arrangement. If one of these non-isolated vertex-agents pi has negative utility, then pi envies every isolated agent. Depending on whether x1 is assigned to an isolated vertex, agent pi forms an exchangeblocking pair with x1 or with x2. Therefore, I admits an exchange-stable arrangement if and only if every non-isolated vertex-agent has non-negative utility. By Claim 18.1 this is equivalent to each pair of non-isolated vertex-agents is nonadjacent, i.e., ˆG admits a size-h independent set.

Even for constant values of ∆+, ESA remains intractable for each considered class of seat graphs.

Theorem 19 (∗). ESA is NP-complete for each considered seat graph class and constant ∆+.

For the combined parameters (k,∆+), ESA becomes fixedparameter tractable using the same idea as Theorem 9.

Theorem 20 (∗). ESA is FPT wrt. k +∆+.

7 Conclusion

We obtained a complete complexity picture for MWA, MUA, and EFA, and left some open questions for ESA (see Table 1). Among these open questions, it would be interesting to know whether the W[1]-hardness result for stars-graphs can be extended to the case with path/cycle-graphs. Another research direction would be to look for arrangements that maximize welfare and are also envy-free or exchange stable. In particular, is it FPT wrt. k +∆+ to find an arrangement that maximizes welfare among the exchange-stable arrangements or maximize the minimum utility among the envy-free arrangements?

Acknowledgments

This work and Jiehua Chen have been funded by the Vienna Science and Technology Fund (WWTF) [10.47379/ VRG18012].