Ordinal Hedonic Seat Arrangement under Restricted Preference Domains: Swap Stability and Popularity

1 Introduction

Coalition formation [Dr`eze and Greenberg, 1980] is a very important topic in algorithmic game theory and computational social choice for modeling the behavior of rational agents when forming groups for, e.g., clubs, activities, or alliances. It has been mainly studied under the lens of hedonic games [Aziz and Savani, 2016], where the goal is to partition agents into disjoint coalitions according to their preferences over the agents in their coalition. However, there exist many real-world situations where agents have to be put in relation with each other but not within separated groups. For example, in a residential area along a street, one may have connections with her two direct neighbors but they themselves are not directly connected. The same can happen for coworkers with adjacent offices along a hallway or adjacent desks in openplan work environments. This configuration can also occur in social events such as conference or wedding dinners, where different conversations may take place at a table depending on the position of the guests around the table. Beyond geographical configurations, it is very common that agents, e.g., workers, are involved in several tasks where they interact with different collaborators that may not be in contact themselves. Also think about workers who take their shifts in sequence, and where only consecutive shifts overlap. This implies that an employee working a given shift only meets those working the shift just before and after hers. Such a temporal allocation is sequential or even cyclic for some jobs that include day and night shifts.

In the previous examples, agents have to be assigned a resource which is not important in itself but which induces relations between owners of "adjacent" resources. This configuration can be naturally modeled by a graph. The goal is then to assign the agents to the vertices of the graph according to their preferences for the agents assigned in their neighborhood. This model is called hedonic seat arrangement and has been introduced by Bodlaender et al. (2020).

This model is closely related to several others. In Schelling games on graphs [Elkind et al., 2019], spatial segregation is modeled via positioning on a graph of agents who are defined by their type; their utility depends on the ratio of agents of their own type in their neighborhood. Closely related to Schelling games are topological distance games [Bullinger and Suksompong, 2022], where agents are placed on vertices of a graph and their utility depends on their valuations for the other agents and their distance to them in the graph. There also exist resource allocation models where both the valuation for the assigned item and the local neighborhood of the assigned itemmatter in the utility function of the agents [Elkind et al., 2020; Massand and Simon, 2019]. Hedonic games with coalitions of fixed size (see, e.g., Cseh et al. [2019]; Bil `o et al. [2022]) form a subclass of hedonic seat arrangements where the graph is a cluster, composed of disjoint cliques. Most of these models assume cardinal preferences. However, the choice of a precise value for the satisfaction of an agent can highly influence the analysis of the game, while not being always easy to elicit or accurate. In this article, we thus focus on ordinal hedonic seat arrangements, where the agents express ordinal preferences over the other single agents.

Consequently, preference extensions [Barber`a et al., 2004] are needed in order to compare subsets of agents given by different neighborhoods. We study some extensions on the basis of their properties and focus in particular on three common extensions that take into account all the agents of a subset and give different visions of a good subset of agents: Fishburn's [1972] and G¨ardenfors' [1976] extensions favor small high quality subsets, while the responsive set extension [Roth, 1985] assumes independence of the agents and favors large subsets. The first two extensions have been mainly used to study manipulation in social choice (see, e.g., Brandt and Brill [2011]), and the latter one has been introduced in the college admission setting and is especially used in resource allocation (see, e.g., Aziz et al. [2019]).

The main goal for a central authority in hedonic seat arrangement is to find a good assignment of agents to the vertices of the graph according to the preferences of the agents, so that the solution is durable (implementing another solution may be costly). We consider in this article the solution concept of swap stability, where no two agents can benefit from swapping their positions. This concept is relevant here since a swap would not require a lot of coordination for the agents. It has been primarily studied in resource allocation (see, e.g., Damamme et al. [2015]; Gourv`es et al. [2017]) but has also been explored in coalition formation, for the matching setting (called there exchange stability [Alcalde, 1994; Cechl´arov´a and Manlove, 2005; Chen et al., 2021]), in Schelling games [Agarwal et al., 2020] and hedonic games of fixed sizes [Bil`o et al., 2022]. While it has been investigated in hedonic seat arrangement for cardinal preferences [Bodlaender et al., 2020] or for graphs corresponding to matchings, swap stability has not been explored so far in more general hedonic seat arrangements for the ordinal setting.

Another perturbation that a central authority would like to avoid is the proposition of a new solution that more agents prefer to the current one and that she would be obliged to implement. The associated notion is popularity: an arrangement is popular if there is no other arrangement that is preferred by more agents. While swap stability focuses on local perturbations, popularity is an optimality concept which considers global perturbations, where the question is whether agents would vote for another arrangement. Popular partitions have been explored in hedonic games [Brandt and Bullinger, 2020; Kerkmann et al., 2020] and matchings [Cseh, 2017], but have not been investigated for hedonic seat arrangements with a graph that may not be made of disjoint cliques.

Ordinal hedonic seat arrangements inherit from negative results of roommate matchings (which correspond to arrangements in cluster graphs made of disjoint cliques of size two) for the existence of swap-stable [Cechl´arov´a, 2002] or popular [Faenza et al., 2019; Gupta et al., 2021] matchings. Therefore, in the line of the literature on restricted preference domains [Elkind et al., 2016], we analyze swap stability and popularity w.r.t. natural preference restrictions and focus on some that allow for positive results in stable matching problems [Gudmundsson, 2013]. We take the occasion to review some relevant preference restrictions and to enrich their relations. The goal is to determine which restriction can ensure the existence of an arrangement satisfying the solution concept. In the line of literature on graph assignment, we focus on natural and simple graph classes for representing realworld configurations: path graphs (e.g., hallway, street), cycle graphs (e.g., table, shifts) and cluster graphs (coalitions).

2 Model and Preliminaries

For an integer k, let [k] := {1, . . . , k}. We are given a set of agents N = [n]. Each agent i ∈ N has strict ordinal preferences over other agents which are represented by the linear order ≻i over N \ {i}. A preference profile ≻ denotes the set of all linear orders ≻i for all agents i ∈ N. In hedonic seat arrangement, the agents have to be placed on the vertices of an undirected graph H = (V,E) such that |V | = n. An arrangement is a bijection of the agents to the vertices of the graph, i.e., an assignment σ : N → V such that σ(i) ̸= σ(j) for all agents i ̸= j. Because of the hedonic flavor of the model, the agents evaluate the quality of an arrangement according to the neighborhood of their assigned position in H. The set of neighbors for agent i ∈ N in arrangement σ is N σ (i) := {j ∈ N : {σ(j), σ(i)} ∈ E}.

In this article, we will focus on the following wellinterpretable graph classes for the assignment of the agents:

• a path graph Pn := (V = {v1, v2, . . . , vn},E = {{v1, v2}, {v2, v3}, . . . , {vn-1, vn}}),
• a cycle graph Cn := (V = {v1, v2, . . . , vn},E = {{v1, v2}, {v2, v3}, . . . , {vn-1, vn}, {vn, v1}}),

· a cluster graph, which is a graph composed of disjoint cliques (a k-cluster graph refers to a cluster graph where all cliques have the same size k). Hedonic seat arrangements in cluster graphs are equivalent to hedonic games with coalitions of fixed size and, when the graph is a 2-cluster, it boils down to the roommate matching setting [Irving, 1985].

2.1 Preference Extensions

Since the agents have ordinal preferences over single agents, we need a preference extension to deduce their preferences over neighborhoods in arrangements, which are subsets of agents. A preference extension ≻ext defines the rules for extending the linear order ≻i over N \ {i} to the partial order ≻ext i over 2N\{i} \ {∅}, for every agent i ∈ N. We naturally restrict to transitive preference extensions that also satisfy the extension rule (for every i, x, y ∈ N, if x ≻i y then {x} ≻ext i {y}). We detail below several desirable properties [Barber`a et al., 2004] that can be imposed on preference extentions, and give them for any subsets of agents X and Y .

• Kelly's dominance [Kelly, 1977]: [x ≻i y, ∀x ∈ X, ∀y ∈ Y ] implies X ≻ext i Y ;
• Dominance or G¨ardenfors principle: for each a ∈ N \{i},
• [a ≻i x, ∀x ∈ X] implies X ∪ {a} ≻ext i X, and
• [x ≻i a, ∀x ∈ X] implies X ≻ext i X ∪ {a};

This can be weakened into simple dominance by considering singletons: x ≻i y implies {x} ≻ext i {x, y} ≻ext i {y};

• (Strict) independence: X ≻ext i Y implies X ∪ {z} ≻ext i Y ∪ {z}, for every z ∈ N \ (X ∪ Y ∪ {i}); This can be weakened into strict simple independence by considering singletons: x ≻i y implies that {x, z} ≻ext i {y, z}, for every z /∈ {x, y}; which can also be weakened into simple middle independence: x ≻i y ≻i z implies {x, y} ≻ext i {y, z}.
• Responsiveness: (X\{x})∪{y} ≻ext i X iff y ≻i x, ∀x ∈ X and ∀y ∈ N \ (X ∪ {i});
• Monotonicity: X ≻ext i X \ {x}, ∀x ∈ X.

We also introduce a weaker property called Best compatibility: [∃a ∈ Y s.t. a ≻i x, ∀x ∈ X] implies X ̸≻ext i Y . This axiom is implied by all dominance and independence axioms, as well as responsiveness.

We present now three concrete extensions ≻ext , where ext ∈ {F,G,RS}. For every two non-empty subsets of agents X and Y such that X ̸= Y , we consider:

• Fishburn's preference extension ≻F [1972]:

∀x ∈ X, ∀x′ ∈ X \ Y, ∀y ∈ Y, ∀y′ ∈ Y \X, i.e.,

all X's elements are preferred or equal to all Y 's elements;

• G¨ardenfors' preference extension ≻G [1976]:

i.e., the elements not in the intersection are compared w.r.t. ≻F , and a smaller (resp., larger) subset is better only if it contains its best elements (resp., it adds better elements);

• Responsive set extension ≻RS [Roth, 1985]: which minimally satisfies responsiveness and monotonicity, i.e., it is compatible with every positive additive utility function.

G¨ardenfors' extension is a refinement of Fishburn's extension (less incomparabilities), i.e., ≻Fi ⊆≻Gi or, equivalently, if one set is Fishburn-preferred to another one, then it is also G¨ardenfors-preferred. In regular graphs (e.g., cycle graphs), where all positions have the same neighborhood size, the responsive set extension is a refinement of G¨ardenfors' extension, i.e., ≻Gi ⊆≻RS i . When the two sets to compare are disjoint, Fishburn's and G¨ardenfors' extensions are equivalent.

While responsiveness and monotonicity are only satisfied by ≻RS , Kelly's dominance and best compatibility are satisfied by all extensions ≻F , ≻G, and ≻RS . G¨ardenfors principle is satisfied by ≻F and ≻G, and strict independence is satisfied by ≻RS while ≻G only satisfies its strict simple version and ≻F only satisfies its simple middle version.

2.2 Preference Restrictions

We consider several natural restrictions on the preference profile over single agents, which mainly come from the matching literature. They define different types of correlation between agents' preferences. A preference profile ≻ is:

• single-peaked (SP) [Black, 1948] if there exists a linear order < over N such that for each agent i ∈ N and each triple of agents j, k, ℓ ∈ N \ {i} with j < k < ℓ or ℓ < k < j, we have j ≻i k implies k ≻i ℓ;
• narcissistically single-peaked (narSP) [Bartholdi III and Trick, 1986; Bredereck et al., 2020] 1 if it is single-peaked w.r.t. axis < and, for every agent, her most preferred agent is directly adjacent to her, on her left or her right, in axis <;
• iteratively mutual best (IMB) [Abizada, 2019] if there exists a sequence of ⌊n/2⌋ pairs of different agents ({a11 , a12 }, . . . , {a⌊n/2⌋ 1 , a⌊n/2⌋ 2 }) such that for every t ∈ [⌊n/2⌋] and ℓ ∈ {1, 2}, we have at3-ℓ ≻atℓ y for every y ∈ N \ ⋃t′<t {at′ 1 , at′ 2 }; i.e., there exists a decomposition in a sequence of subprofiles (≻1=≻, . . . ,≻[⌊n/2⌋] , ∅) where each subprofile ≻t contains a pair of agents who prefer each other the most and ≻t+1 is obtained by removing this pair;
• globally-ranked (GR) [Abraham et al., 2007] if there exists a global order ▷ over all possible pairs of distinct agents such that for every i ∈ N and any j, k ∈ N \ {i}, we have j ≻i k iff {i, j} ▷ {i, k}; i.e., each agent prefers the agents

1 Our definition differs from the one of Bartholdi III and Trick because, in our setting, agents do not express preferences over themselves. Nevertheless, their definition is equivalent to ours when selfpreferences are omitted from their considered preference profiles.

with whom she forms an objectively better pair w.r.t. a given global comparison of all pairs;

• 1-Euclidean (1-D) [Coombs, 1950] if there exists an embedding E : N → R of the agents into the real line such that for every agent i ∈ N and two agents j, k ∈ N \ {i}, j ≻i k iff |E(i) - E(j)| < |E(i) - E(k)|; i.e., each agent prefers the agents that are closer to her w.r.t. a given common scale.

All these preference restrictions are recognizable in polynomial time (see Bartholdi III and Trick [1986]; Escoffier et al. [2008] for (narcissistic) single-peakedness, Abraham et al. [2007] for global-rankedness, and Doignon and Falmagne [1994]; Knoblauch [2010]; Elkind and Faliszewski [2014] for the 1-Euclidean property; for IMB preferences, it suffices to iteratively remove mutual best pairs as long as it is possible). Observe that there is no inclusion relation between IMB preferences and single-peakedness. Narcissistic singlepeakedness or global-rankedness implies IMB but the converse is not true. Moreover, a 1-Euclidean preference profile is globally-ranked and narcissistically single-peaked. However, a preference profile that is both narcissistically singlepeaked and globally-ranked may not be 1-Euclidean. All these relations are presented in Figure 1.

2.3 Problems: Swap Stability and Popularity

In this article, we search for arrangements that are stable according to different views: a local one based on swaps and a global one based on the optimality concept of popularity.

First, we search for arrangements that are immune to exchanges of size two, i.e., swaps, which are reasonable deviations since they do not require much coordination. A swap can be performed from an arrangement σ if there exist two agents i and j such that N σ′ (i) ≻ext i N σ (i) and N σ′ (j) ≻ext j N σ (j) for a given preference extension ≻ext and where arrangement σ′ is such that σ′ (k) = σ(k) for every agent k ∈ N \{i, j}, σ′ (i) = σ(j), and σ′ (j) = σ(i). An arrangement σ is swap-stable if no swap can be performed from σ w.r.t. extension ≻ext .

Moreover, we search for arrangements that are immune to a global switch to another arrangement that more agents prefer. Agent i prefers arrangement σ′ over arrangement σ w.r.t. extension ≻ext if N σ′ (i) ≻ext i N σ (i). Arrangement σ′ is more popular than arrangement σ if the number of agents preferring σ′ over σ is strictly greater than the number of agents preferring σ over σ′ . Arrangement σ is popular if there is no other arrangement σ′ that is more popular.

To summarize, we investigate the following problems: Given an ordinal hedonic seat arrangement instance 〈N,≻ ,H,≻ext 〉, does there exist an arrangement that is swapstable (resp., popular)? We focus on the construction of such arrangements when they exist.

3 Swap Stability

Since deciding about the existence of an exchange-stable matching is NP-complete in roommate markets [Cechl´arov´a, 2002], deciding about the existence of a swap-stable arrangement is NP-complete even in a 2-cluster graph. However, we show that a swap-stable arrangement exists in every graph when the preferences are globally-ranked. We prove an even stronger statement by showing that every sequence of swaps converges under such a preference restriction.

Theorem 1. The dynamics of swaps is guaranteed to converge for every graph under globally-ranked preferences and every preference extension for which all comparisons are based on the extension rule, Kelly's dominance, dominance, independence, responsiveness, or monotonicity.

Proof. Consider an instance on a graph H = (V,E) with globally-ranked preferences w.r.t. order ▷ over all pairs of agents, and preference extension ≻ext . We denote by ▷lex the lexicographic relation w.r.t. ▷ over vectors of agent pairs, i.e., given two vectors µ and µ′ of agent pairs, µ ▷lex µ′ iff when µ and µ′ are ordered w.r.t. ▷, there exists an index ℓ such that µℓ′ = µ′ℓ′ for all 1 ≤ ℓ′ < ℓ and [µℓ ▷ µ′ℓ or |µ| = ℓ - 1 < |µ′ |]. Note that ▷lex is transitive.

For an arrangement σ, we denote by µσ its associated |E|- vector composed of all pairs of agents that are neighbors in σ. We denote by µσ (i) the vector composed of all the pairs {i, k} where k is a neighbor of i in σ. For any swap between agents i and j from an arrangement σ which transforms σ into σ′ , we will prove that µσ′ ▷lex µσ , implying the convergence of the swap dynamics, by a potential function argument.

The swap of agents i and j from σ to σ′ implies that σ′ (k) ≻ext k σ(k) for each k ∈ {i, j}. By definition, µσ and µσ′ are the same on the pairs that are not part of µσ (i) or µσ (j). Thus, to compare µσ and µσ′ w.r.t. ▷lex, we need to compare µσ (i) and µσ (j) with µσ′ (i) and µσ′ (j). We now give axioms for subset comparison in ≻ext k for k ∈ {i, j} that guarantee ▷lex for the associated vectors of agent pairs.

• the extension rule: {x} ≻ext k {y} because x ≻k y therefore ({k, x}) ▷lex ({k, y});
• Kelly's dominance: X ≻ext k Y because x ≻k y for all x ∈ X, y ∈ Y therefore ({k, x})x∈X ▷lex ({k, y})y∈Y ;
• dominance: X ∪ {z} ≻ext k X because z ≻k x for all x ∈ X therefore ({k, z}, {k, x})x∈X ▷lex ({k, x})x∈X, or X ≻ext k X ∪ {z} because x ≻k a for all x ∈ X therefore ({k, x})x∈X ▷lex ({k, z}, {k, x})x∈X;
• independence: X∪{z} ≻ext k Y ∪{z} becauseX ≻ext k Y , therefore it suffices that X ≻ext k Y is based on a comparison that guarantees ({k, x})x∈X ▷lex ({k, y})y∈Y for ({k, z}, {k, x})x∈X ▷lex ({k, z}, {k, y})y∈Y being true;
• responsiveness: (X \ {x}) ∪ {y} ≻ext k X because y ≻k x therefore ({k, z}, {k, y})z∈X\{x,y} ▷lex ({k, z}, {k, x})z∈X\{x,y};
• monotonicity makes X ∪ {z} ≻ext k X hold for all agents k but it cannot be used by both agents i and j during a swap because σ′ (i) \ {j} = σ(j) \ {i} and vice versa.

By transitivity of ▷lex, any preference extension that is based on the previous properties for subset comparison will guarantee that µσ′ (i) ▷lex µσ (i) and µσ′ (j) ▷lex µσ (j).

However, this positive result for convergence does not hold as soon as the preferences are not globally-ranked, even under other strong preference restrictions, and for any preference extension that satisfies very weak conditions (which hold, e.g., for ≻F , ≻G, and ≻RS ), as shown below.

Proposition 1. The dynamics of swaps can cycle even under narcissistically single-peaked preferences,

1. in a 2-cluster graph for any preference extension, or
2. in a path or cycle graph for any preference extension that satisfies strict simple independence, or
3. in a path graph for any preference extension that satisfies simple dominance, or
4. in a cycle graph for any preference extension that satisfies Kelly's dominance.

Sketch of proof. We only present here cases 1 and 2. Take an instance with four agents who have the following preferences, narcissistically single-peaked w.r.t. axis 1 < 2 < 3 < 4.

1 : 2 ≻ 3 ≻ 4

2 : 3 ≻ 4 ≻ 1

3 : 2 ≻ 1 ≻ 4

4 : 3 ≻ 2 ≻ 1

A cycle in the swap dynamics is given for a 2-cluster graph in Figure 2(a), for a path (resp., cycle) graph and any extension that satisfies strict simple independence in Figure 2(b) (resp., Figure 2(c)).

This negative result on convergence does not necessarily exclude the existence of stable arrangements under the same conditions. From now on, we focus on specific graphs to determine whether preference restrictions other than globalrankedness allow for the existence of stable arrangements.

3.1 Path Graph

Firstly, a swap-stable arrangement may not exist in - the apparently very restricted class of - path graphs, even under single-peaked preferences, and extensions that satisfy weak conditions on dominance (that hold, e.g., for ≻F and ≻G).

Proposition 2. There are instances with no swap-stable arrangement even under single-peaked preferences in a path, for any preference extension that satisfies simple dominance.

Proof. Take an instance with three agents. The preferences, single-peaked w.r.t. axis 1 < 2 < 3, are depicted below (left). There is a possible swap from each possible arrangement (up to symmetries), as depicted below (right).

The preference profile in the latter counterexample is not narcissistically single-peaked. Indeed, this restriction guarantees the existence under ≻F and ≻G, and for ≻F even more generally under IMB preferences, as stated below.

Theorem 2. There always exists a polynomial-time computable swap-stable arrangement in a path graph under iteratively mutual best preferences and Fishburn's extension.

Sketch of proof. Suppose that the sequence of mutual best pairs induced by the preference profile is ({a11 , a12 }, . . . , {a⌊ n2 ⌋ 1 , a⌊ n2 ⌋ 2 }). We consider the arrangement that assigns this sequence of pairs in the same order to the path graph, except potentially at the end. The idea of the proof is that no agent atℓ , for ℓ ∈ {1, 2} and t ∈ [⌊ n2 ⌋], has an incentive to swap with agents located at later positions in the path.

Theorem 3. There always exists a polynomial-time computable swap-stable arrangement in a path under narcissistically single-peaked preferences and G¨ardenfors' extension.

Sketch of proof. Suppose that the preferences are narcissistically single-peaked w.r.t. axis 1 < · · · < n. Take the mutual best pair {i∗ , i∗ + 1} with the lowest indices. Initially, we assign on graph Pn all i∗ + 1 "smallest" agents: agent i∗ + 1 first then i∗ and then all agents from i∗ - 1 to 1. Then we iteratively complete the partial arrangement by inserting at each step the agent, among the three next available ones, who prefers the last assigned agent to the closest agents from her right in the axis. If the chosen agent is not the smallest available agent, we then insert after her the one or two missing agents by decreasing order of indices. One can prove, by induction over the first k assigned agents in the path, that the resulting arrangement is swap-stable.

The question of the existence of a swap-stable arrangement remains nevertheless open in a path graph under ≻RS .

3.2 Cycle Graph

Although path and cycle graphs seem similar, we observe significant differences on swap stability, mainly due to the chosen preference extension: while non-existence holds for dominant extensions in paths, it holds for independent extensions (such as ≻G and ≻RS ) in cycles.

Proposition 3. There are instances with no swap-stable arrangement even when the graph is a cycle, under singlepeaked and iteratively mutual best preferences for any preference extension that satisfies strict simple independence.

Proof. Take an instance with four agents. The preferences, which are single-peaked w.r.t. axis 1 < 2 < 3 < 4 and iteratively mutual best w.r.t. sequence ({2, 3}, {1, 4}), are given below (left). There is a possible swap, only based on strict simple independence, from each possible arrangement (up to symmetries), as depicted below (right).

Moreover, contrary to path graphs, a swap-stable arrangement always exists in cycle graphs under ≻F .

Theorem 4. There always exists a polynomial-time computable swap-stable arrangement in a cycle graph under Fishburn's extension.

Sketch of proof. We construct an initial arrangement σ0 , based on the idea of serial dictatorship, as follows. Consider an arbitrary initial agent a1 and assign to her the position v1 in Cn. Then, for each index ℓ ranging from ℓ = 1 to ℓ = n - 1, we select the most preferred agent for agent aℓ who is still available, i.e., she has not been assigned to a position of the graph yet. We call this agent aℓ+1 and assign to her the position vℓ+1 in Cn. At the end of the loop, by construction, all the agents have been assigned to a position in the cycle graph.

One can show that every agent ak, for k ∈ [n - 3], is stable, in the sense that no agent ak has an incentive to swap as long as the arrangement remains the same as σ0 for positions v1, . . . , vk+1. Thus, a swap in arrangement σ0 can involve only agents an, an-1, or an-2. Agent an-2 prefers agent an-1 to an whereas a swap between an-1 and an-2 would imply that an-2 prefers an to an-1, a contradiction. Hence, under ≻F , if σ0 is not swap-stable, then the only possible swaps from σ0 are between agents an and an-1 or between agents an and an-2. For each case, it is possible to construct specific arrangements that are swap-stable.

It remains open if narcissistic single-peakedness allows for the existence of stable arrangements under ≻G and ≻RS .

3.3 Cluster Graph

A swap-stable roommate matching may not exist, even under single-peaked preferences [Alcalde, 1994], but always exists under IMB preferences [Abizada, 2019]. Hence the same results hold for arrangements in 2-cluster graphs. We extend the positive result under IMB preferences to all cluster graphs that contain at most one disjoint clique of odd size. More precisely, we can iteratively assign the first pairs of agents in the sequence of mutual best pairs to all even cliques. One can prove that these agents will never swap no matter the rest of the arrangement. Thus, we can remove them from our consideration and focus only on odd cliques and remaining agents.

Corollary 1. There always exists a polynomial-time computable swap-stable arrangement in a cluster graph with at most one odd-sized (non-singleton) clique under iteratively mutual best preferences and every preference extension that satisfies best compatibility.

This positive result can be extended to any cluster graph when the preferences are slightly more restricted.

Theorem 5. There always exists a polynomial-time computable swap-stable arrangement in a cluster graph under narcissistically single-peaked preferences and every preference extension that satisfies best compatibility.

Sketch of proof. Since narcissistically single-peaked preferences are iteratively mutual best, we can proceed to the previously described preprocessing on even cliques, and assume that all cliques are of odd size greater than one (a swap cannot involve alone agents). Consider the following algorithm in order to assign the remaining agents (the agents who have not been assigned yet) to a remaining position in a clique of the cluster graph:

1. N ′ ← N \ {agents assigned in a clique entirely filled}.
2. If there are two remaining agents who prefer the most each other within N ′ :
3. If there remains a clique that has not been filled yet, then assign the two agents to this clique; Go to step 1.
4. Otherwise, if there remain at least two positions in a partially filled clique, then assign the two agents to this clique. Go to step 1.
5. If there is a remaining agent preferring the most, within N ′ , an agent assigned in a clique that is partially filled, then assign her to this clique. Go to step 1.
6. Assign an arbitrary remaining agent to the best currently open clique according to her preferences. Go to step 1.

At the end of the algorithm, all agents are assigned. One can prove that the resulting arrangement is swap-stable.

It remains open whether IMB preferences allow for the existence of a stable arrangement in general cluster graphs.

4 Popularity

By the roommate setting, it is known that popular arrangements may not exist, even under single-peaked preferences. Moreover, deciding about the existence of a popular roommate matching is NP-hard [Faenza et al., 2019; Gupta et al., 2021], thus deciding about the existence of a popular arrangement is NP-hard even in a 2-cluster graph. Hence, we investigate in this section the existence of popular arrangements on specific graphs. To construct the popularity relation, we count the agents preferring each arrangement in pair-wise comparisons. Therefore, the abstention of agents because of neighborhood incomparability may matter. Contrary to swap stability, a result on popularity for a given extension does not imply others for related extensions.

4.1 Path Graph

We show that, while narcissistic single-peakedness ensures the existence of a popular arrangement for ≻F , we also need global-rankedness for ≻RS . Surprisingly, no popular arrangement may exist for ≻G, even under 1-D preferences.

Proposition 4. There are instances with no popular arrangement even when the graph is a path and:

1. under 1-Euclidean preferences for G¨ardenfors' preference extension, or
2. under narcissistically single-peaked preferences for the responsive set extension, or
3. under single-peaked and globally-ranked preferences for Fishburn's or the responsive set extension.

Theorem 6. There always exists a polynomial-time computable popular arrangement in a path under narcissistically single-peaked preferences and Fishburn's extension.

Proof. Suppose, w.l.o.g., that the preferences are narcissistically single-peaked w.r.t. axis 1 < · · · < n. For path graph Pn, let σ be the arrangement such that σ(i) = vi for every i ∈ N. By narcissistic single-peakedness, each agent i is adjacent in Pn to her most preferred agent, who is either i - 1 or i + 1. By ≻F , the two agents 1 and n, located at leaf nodes, prefer arrangement σ over any other arrangement where their neighborhood differs, and every other agent i such that 1 < i < n can prefer another arrangement only if she is positioned at a leaf node adjacent to her most preferred agent. Hence, at most two agents can prefer another arrangement over σ but the number of these better-off agents is equal to the number of worse-off agents among the agents located at leaf nodes in σ (there are only two leaves in a path). Consequently, for any other arrangement σ′ , we cannot have more agents preferring σ′ over σ than agents preferring σ over σ′ , and thus σ is popular.

Theorem 7. There always exists a polynomial-time computable popular arrangement in a path graph under narcissistically single-peaked and globally-ranked preferences and the responsive set extension.

Sketch of proof. Suppose that the preferences are narcissistically single-peaked w.r.t. axis 1 < · · · < n. For a path graph Pn, let σ be the arrangement such that σ(i) = vi for every i ∈ N. For each other arrangement σ′ , we match each better-off agent i in σ′ with a specific worse-off agent, who is the first agent not indifferent between σ′ and σ that is reached from i by following the direction of the location of i's most preferred agent in σ′ . All the worse-off agents associated with a better-off agent are different, thus the matching is valid. It follows from this matching, perfect for the set of better-off agents in σ′ , that there cannot be more agents who prefer σ′ over σ than agents who prefer σ over σ′ , and thus σ′ is not more popular than σ. Since this is true for any other arrangement σ′ , arrangement σ is popular.

4.2 Cycle Graph

The results are similar to those concerning path graphs but this time the existence is guaranteed under ≻G and narcissistically single-peaked and globally-ranked preferences.

Proposition 5. There are instances with no popular arrangement even when the graph is a cycle and:

1. under narcissistically single-peaked preferences for G¨ardenfors' or responsive set extension, or
2. under single-peaked and globally-ranked preferences for Fishburn's, G¨ardenfors', or the responsive set extension.

Sketch of proof. Let us present case 1. Take an instance with five agents who have the following preferences, which are narcissistically single-peaked w.r.t. axis 1 < 2 < 3 < 4 < 5.

Figure 3 shows that for every arrangement there is another arrangement that is more popular w.r.t. ≻G and ≻RS .

The two statements of the next proposition are proved by following the same strategy of proof as Theorems 6 and 7.

Proposition 6. There always exists a polynomial-time computable popular arrangement in a cycle graph under:

1. narcissistically single-peaked preferences and Fishburn's extension, or
2. narcissistically single-peaked and globally-ranked preferences and G¨ardenfors' or responsive set extension.

4.3 Cluster Graph

A popular arrangement may not exist even in 2-cluster graphs under single-peaked preferences. However, a stable roommate matching w.r.t. blocking pairs, i.e., no two agents prefer to be paired than being with their current partner, is also popular [Bir´o et al., 2010]. One can remark that this implication does not hold for swap stability, even under 1-D preferences. Nevertheless, under IMB preferences, we show below that there exists a popular arrangement in 2-cluster graphs which is also swap-stable and stable w.r.t. blocking pairs.

Theorem 8. There always exists a polynomial-time computable popular arrangement in a 2-cluster graph under iteratively mutual best preferences.

Proof. Suppose that the sequence of mutual best pairs induced by the preference profile is ({a11 , a12 }, {a21 , a22 }, . . . , {a⌊ n2 ⌋ 1 , a⌊ n2 ⌋ 2 }). For a 2-cluster graph, let σ be the arrangement that assigns the agents at1 and at2 to connected vertices, for each t ∈ [⌊ n2 ⌋]. By Abizada [2019], this arrangement is swap-stable. But the associated matching is also stable w.r.t. blocking pairs. Indeed, suppose that agents i and j prefer to be together than with their current partner in σ. Say, w.l.o.g., that i = atℓ and j = at′ ℓ′ , where t < t′ , and ℓ, ℓ′ ∈ {1, 2}. By definition of mutual best pairs, agent i = atℓ prefers at3-ℓ , her current partner in σ, to agent j = at′ ℓ′ , a contradiction. Since stability w.r.t. blocking pairs implies popularity [Bir´o et al., 2010], arrangement σ is popular.

Table 1: Summary on the existence of swap-stable or popular arrangements on path, cycle, and cluster graphs w.r.t. the preference restrictions of Figure 1 and extensions ≻F , ≻G, ≻RS .

However, this positive result does not hold if the cliques may be of size greater than two [Brandt and Bullinger, 2020]. We show that this negative result can occur even when all cliques are of size three and under 1-D preferences.

Proposition 7. There are instances with no popular arrangement even in a 3-cluster, under 1-Euclidean preferences and Fishburn's, G¨ardenfors', or the responsive set extension.

5 Conclusion

We have shown that the level of preference restriction needed to guarantee the existence of swap-stable or popular arrangements depends on the chosen combination of preference extension and graph structure, see Table 1. While our results are tight for popularity w.r.t. the hierarchy of restrictions (Fig. 1), it remains some gaps to fill for swap stability (see question marks in Table 1 (a)), which are interesting open problems.

Our study also brings insights on preference restrictions. In particular, narcissistic single-peakedness is a rich structure which allows for several positive results, as well as the iterative mutual best restriction, although it is designed for matchings and not so hardly restrictive (weaker than both globalrankedness and narcissistic single-peakedness). Another very powerful restriction is global-rankedness, which allows for strong positive results on swap stability since it makes the dynamics of swaps converge for every graph. This result significantly generalizes convergence results from matchings.

The investigated existence problems are hard even in very restricted graphs. While we provide polynomial-time algorithms to construct desirable arrangements under some restrictions, it would be interesting to determine whether these restrictions enable to efficiently recognize positive instances, even when they do not guarantee the existence.

Acknowledgments

This work is supported by the ANR project APPLE-PIE (grant ANR-22-CE23-0008-01).