# Rank-Envy-Freeness in Roommate Matchings

Baptistin Coutance, Prasanna Maddila, Anaëlle Wilczynski

► To cite this version:

Baptistin Coutance, Prasanna Maddila, Anaëlle Wilczynski. Rank-Envy-Freeness in Roommate Matchings. 26th European Conference on Artificial Intelligence (ECAI 2023), Sep 2023, Krakow (Cracovie), Poland. 10.3233/FAIA230308. hal-04239712

HAL Id: hal-04239712

https://hal.science/hal-04239712v1

Submitted on 25 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Rank-Envy-Freeness in Roommate Matchings

Baptistin Coutanceª, Prasanna Maddilaª and Anaëlle Wilczynski a,✉

ªMICS, CentraleSupélec, Université Paris-Saclay

**Abstract.** In the roommate problem, pairs of agents must be formed, based on ordinal preferences of the agents over each other. In this article, we examine fair roommate matchings by relaxing envy-freeness to account for justified envy based on the rank in the agents' preferences. A rank-envy-free matching prevents that an agent prefers the partner of another agent whereas she has ranked it better. Although this requirement is pretty weak in house allocation [9], we show that it is more demanding in the roommate setting. We study parameterizations of rank-envy-freeness, as well as further natural relaxations of this concept. We also investigate the connections between the family of rank-based fairness criteria and known optimality or stability concepts.

## 1 Introduction

Matching under preferences is a very attractive framework that captures a large number of real-world applications. This research area has gained much attention in computer science, in particular in algorithmic game theory and computational social choice [28, 30]. The setting where pairs of agents must be formed, without distinction among the agents, is known as the *roommate setting* [22]. This is the non-bipartite version of the marriage setting, where the agents are partitioned in two types and only agents of different types can be matched. The roommate setting can be seen as a specific *hedonic game* [7], where coalitions of agents of size two must be formed.

This matching problem has been initially studied under the prism of stability [25], in the line of the seminal work of Gale and Shapley on the *stable marriage problem* [22]. Given ordinal agents' preferences, the aim is to find a matching that is stable w.r.t. blocking pairs of agents (BP) who prefer to be matched together than with their current partner in the matching. Alternative notions of stability have been introduced since then, and in particular the one of *exchange-stability* (also known as *swap-stability*) [6, 14].

Another important direction of research in matching problems concerns the search for *optimal matchings*, aiming to ensure the global satisfaction of the agents. In the context of ordinal preferences, the most prominent optimality concept is Pareto-optimality [5]. Yet, since many Pareto-optimal matchings exist, refinements have been proposed, e.g., *rank-maximality* [26] which aims to lexicographically optimize the ranks of the matched agents, and *popularity* [18], which is based on pairwise comparisons of matchings by the agents.

Alternatively to stability or optimality, we adopt another view in this article by exploring *fairness* issues in roommate matchings. Contrary to optimality, fairness does not focus on the global satisfaction but on the individual feeling of fair treatment. While an unstable matching is typically also unfair, the two notions are independent

because feeling of fair treatment does not imply that the solution is immune to local perturbations and agents may still feel frustrated in a stable solution [34]. Although fairness has been widely investigated in resource allocation [12, 32], this topic has been less explored in settings matching agents with other agents. The main development in the literature concerns *justified envy-freeness* in school choice [2], which aims to avoid that a student prefers to be matched with a given college that also prioritizes her. The analogous notion of fairness has also been studied in hedonic games [35]. Other works concern the marriage setting to counterbalance the inherent difference of treatment between the two types of agents in stable matchings [31]. In roommate matchings, we can particularly cite the rank-fairness notion [27] imposing that partners assign the same rank to each other.

In this article, we focus on another notion of fairness called *rank-envy-freeness (r-EF)*, which is a relaxation of envy-freeness [20] that requires that no agent prefers to be matched with the partner of another agent whereas she has ranked the desired agent at a better position in her preference ranking. This concept is particularly relevant in an ordinal context and is related to the notion of *justified envy*, but considers the justification for envy w.r.t. the preferences of the envious agent: Alice can legitimately feel discriminated if Bob got matched with Charlie, who is his second choice, whereas Alice has reported that Charlie was her first choice. This notion has been introduced in school choice mechanism design under the name *favoring higher ranks* [29], and has been mainly studied in random assignment (of agents to objects) [23, 33]. Rank-envy-freeness has also been recently investigated [9] in house allocation [1], a setting where each agent must be matched with a single object. This latter work proves that both rank-maximality and popularity imply r-EF, guaranteeing the existence of an r-EF allocation, while no implication relation holds with Pareto-optimality. It also generalizes the notion to *rank$_k$-envy-freeness ($r_k$-EF) and proves that popularity is equivalent to $r_1$-EF when there are as many objects as agents.

In this article, we investigate rank-envy-freeness in the particular roommate setting where agents have strict ordinal preferences over all other agents and where every agent must be matched. Preference restrictions are sometimes considered to strengthen our results. We show that, contrary to house allocation, an r-EF matching does not always exist and the previous implications with optimality do not hold anymore. We also examine $r_k$-EF matchings and show that $r_1$-EF is no longer equivalent to popularity but keeps the characterization of popularity for house allocation [3], making it decidable in polynomial time, contrary to popularity [19, 24]. We further introduce new relaxations of r-EF, namely *weak rank-envy-freeness (wr-EF)*, *BP rank-envy-freeness ($r^BP$-EF)* and *weak BP rank-envy-freeness (wr$^{BP}$-EF)*, and show that we can always construct a wr$^{BP}$-EF matching in polynomial time. This finding contrasts with the NP-completeness of

<footnote>* Corresponding Author. Email: anaelle.wilczynski@centralesupelec.fr</footnote>
the decision problems related to the existence of matchings satisfying
r-EF, wr-EF or r<sup>BP</sup>-EF. We determine the exact implication relations
between all these *rank-based envy-freeness* criteria and known opti-
mality or stability criteria; they are summarized in Figure 1. Finally,
we empirically evaluate the existence of such fair matchings.

<figure><img src="image_2.png" /><figcaption>Figure 1: Implication relations between rank-based envy-freeness criteria and optimality or stability criteria.</figcaption></figure>

## 2 Preliminaries

For an integer $k$, let $[k] := \{1, \dots, k\}$. We are given a set of agents $N = [n]$ where $n$ is even. Each agent $i \in N$ is associated with a linear order $>_{i}$ over $N \setminus \{i\}$ representing her strict ordinal preferences over the other agents. A preference profile $>_{i}$ is the set of all linear orders $>_{i}$ for all agents $i \in N$. A roommate instance is thus simply a pair $(N, >_{i})$. A matching $\sigma: N \to N$ is a bijection over $N$.

## 2.1 Preference restrictions

We sometimes consider restrictions in the preference profile, that can
capture a certain correlation in the agents’ preferences.

A preference profile $>_{i}$ is single-peaked [11] if there exists a linear order $<_{i}$ over $N$ such that for each agent $i \in N$ and each triple of agents $j, k, \ell \in N \setminus \{i\}$ with $j < k < \ell$ or $\ell < k < j$, we have $j >_{i} k$ implies $k >_{i} \ell$. A particular case is when agents consider their own position as an ideal position in the axis. A preference profile $>_{i}$ is narcissistically single-peaked [8] if $>_{i}$ is single-peaked w.r.t. axis $<_{i}$ and, for every agent, her most preferred agent is directly adjacent to her in axis $<_{i}$, either on her “left” or on her “right”.

Instead of a common axis, a global evaluation of the matches can
be considered. A preference profile $>_{i}$ is globally-ranked [4] if there
exists a global order $▷$ over all possible agent pairs such that for
every $i \in N$ and $j, k \in N \setminus \{i\}$, $j >_{i} k$ iff $\{i, j\}▷\{i, k\}$; i.e., each
agent prefers those with whom she forms an objectively better pair.

Finally, we consider a stronger restriction which satisfies both nar-
cissistic single-peakedness and global-rankedness. A preference pro-
file $>_{i}$ is 1-Euclidean [17] if there exists an embedding $E: N \to \mathbb{R}$
such that for every agent $i \in N$ and two agents $j, k \in N \setminus \{i\}$,
$j >_{i} k$ iff $|E(i) - E(j)| < |E(i) - E(k)|$. The idea is that the
agents prefer those that are closer to them on a given common scale.

## 2.2 Stable matchings

Stability is initially defined w.r.t. a *blocking pair*: agents *i* and *j* form a blocking pair in matching *σ* if they prefer to be matched together than with their partner in *σ*, i.e., *j* ><sub>*i*</sub> *σ*(*i*) and *i* ><sub>*j*</sub> *σ*(*j*). A matching *σ* is *blocking-pair (BP-)stable* if there is no blocking pair in *σ*.

Another notion of stability comes from the notion of swap. A matching $\sigma$ is *swap-stable* if there is no pair of agents $i$ and $j$ who prefer to swap their partner, i.e., $\sigma(j) >_{i} \sigma(i)$ and $\sigma(i) >_{j} \sigma(j)$.

## 2.3 Optimal matchings

One of the most classical optimality notion is Pareto-optimality. A matching $\sigma'$ Pareto-dominates a matching $\sigma$ if $\sigma'(i) \succeq_i \sigma(i)$ for every agent $i$ and there exists an agent $j$ such that $\sigma'(j) >_j \sigma(j)$. A matching $\sigma$ is *Pareto-optimal* if no matching $\sigma'$ Pareto-dominates it.

The Pareto criterion can be strengthened by considering a lexico-
graphic maximization of the agents’ satisfaction given by the rank
of their partner in the matching. The *signature* $s_\sigma$ of matching $\sigma$ is
the $(n-1)$-vector giving the number of agents $s_\sigma(k)$ assigned to
their $k^{\text{th}}$ most preferred agent in $\sigma$, for all $k \in [n-1]$. Signature
$s_\sigma$ is lexicographically strictly greater than signature $s_{\sigma'}$, denoted
by $s_\sigma >_{lex} s_{\sigma'}$, if there exists an index $i \in [n-1]$ such that
$s_\sigma(i') = s_{\sigma'}(i')$ for all $i' < i$ and $s_\sigma(i) > s_{\sigma'}(i)$. A matching
$\sigma$ is *rank-maximal* if there is no matching $\sigma'$ such that $s_{\sigma'} >_{lex} s_\sigma$.

Another direction to strengthen Pareto-optimality is by consider-
ing votes between matchings. Agent $i$ prefers matching $\sigma$ to match-
ing $\sigma'$ if $\sigma(i) >_{i} \sigma'(i)$. A matching $\sigma$ is more popular than a match-
ing $\sigma'$ if the number of agents who prefer $\sigma$ to $\sigma'$ is strictly greater
than the number of agents who prefer $\sigma'$ to $\sigma$. A matching $\sigma$ is pop-
ular if there is no matching $\sigma'$ more popular than $\sigma$.

# 3 Rank-Based Envy-Free Matchings

We study *fair* matchings w.r.t. rank-based envy-freeness notions.

## 3.1 Rank-envy-freeness

The classical notion of envy-freeness [20] is too strong in the room-
mate setting, because it requires that every agent is matched with
her most preferred agent. Therefore, we consider *rank-envy-freeness*,
a relaxation of envy-freeness which aims to prevent justified envy
based on the rank. An agent *i* rank-envies another agent *j* in match-
ing *σ* if *i* prefers the partner of *j* to her own whereas *i* ranks the
desired partner in a better position in her preference ranking than
agent *j*. Let *r*<sub>*i*</sub>: *N* → [*n* − 1] be the function giving the rank of an
agent in *>*, i.e., *r*<sub>*i*</sub>(*j*) = [*{ℓ ∈ *N*: ℓ ≥*i* *j*}]*, for agent *j* ∈ *N* \ {*i*}.

**Definition 1 (Rank-envy-freeness (r-EF)).** A matching $\sigma$ is r-EF if $\sigma(i) >_{i} \sigma(j)$ or $r_{j}(\sigma(j)) \leq r_{i}(\sigma(j))$, for every $i, j \in N$.

A generalization of r-EF can be defined by considering a parame-
terization of the concept w.r.t. rank 0 $\leq k < n - 1$. The associated
justification for envy is that the desired agent has not been ranked
good enough (among the top *k* best agents) by the envied agent.

**Definition 2 (Rank$_k$-envy-freeness (r$_k$-EF)).** A matching $\sigma$ is r$_k$-EF if $\sigma(i) >_{i} \sigma(j)$ or $r_{j}(\sigma(j)) \leq \min\{r_{i}(\sigma(j)), k\}$ for every $i, j \in N$.

Note that r<sub>k</sub>-EF implies r<sub>k'</sub>-EF for every k' > k. Moreover, r<sub>n-2</sub>-EF is equivalent to r-EF and r<sub>0</sub>-EF is equivalent to envy-freeness.
The next basic first observation can be made for r-EF matchings.

**Observation 1.** Every agent that is ranked first by some agent must be matched in an r-EF matching with an agent who ranks her first.

Contrary to house allocation where an r-EF allocation always ex-
ists [9], an r-EF matching may not exist in roommate instances, even
under 1-Euclidean preferences, as shown in Example 1.
**Example 1.** Let us consider a roommate instance with six agents who have the preferences below.

<figure><img src="image_3.png" /><figcaption>The preferences are 1-Euclidean w.r.t. the following embedding:</figcaption></figure>

<figure><img src="image_4.png" /></figure>

By Observation 1, in an r-EF matching, agent 2 must be matched with agent 1 while agent 3 must be matched with agent 2, a contradiction. Hence, there cannot exist an r-EF matching in this instance.

## 3.2 Relaxations of rank-envy-freeness

We thus propose relaxations of r-EF, which strengthen the conditions for justified envy. First, if an agent is well-ranked by her current partner, she may feel flattered and would not dare to claim for a better partner, especially if she does not rank the desired agent at a better rank than what her current partner does for her. The associated notion of envy is as follows: agent *i* strongly rank-envies agent *j* in matching $\sigma$ if $\sigma(j) \succ_i \sigma(i)$, $r_i(\sigma(j)) < r_j(\sigma(j))$, and $r_{\sigma(i)}(i) > r_i(\sigma(j))$.

**Definition 3** (Weak rank-envy-freeness (wr-EF)). A matching $\sigma$ is wr-EF if $\sigma(i) \succ_i \sigma(j)$ or $r_j(\sigma(j)) \le r_i(\sigma(j))$ or $r_{\sigma(i)}(i) \le r_i(\sigma(j))$, for every $i, j \in N$.

**Example 1** (continued). The framed matching is wr-EF. Indeed, the only rank-envious agent is agent 2 (who is rank-envious towards agent 6), but she is matched with agent 1 who ranks her first, therefore agent 2 does not complain.

Another direction for relaxing r-EF is to consider a justification of envy based on a blocking pair: the desired partner would also prefer to be matched with the envious agent. Agent *i* BP rank-envies agent *j* in matching $\sigma$ if $\sigma(j) \succ_i \sigma(i)$, $r_i(\sigma(j)) < r_j(\sigma(j))$, and $i \succ_{\sigma(j)} j$.

**Definition 4** (BP rank-envy-freeness ($r^\text{BP}$-EF)). A matching $\sigma$ is $r^\text{BP}$-EF if $\sigma(i) \succ_i \sigma(j)$ or $r_j(\sigma(j)) \le r_i(\sigma(j))$ or $j \succ_{\sigma(j)} i$, for every $i, j \in N$.

**Example 1** (continued). The framed matching is $r^\text{BP}$-EF. Indeed, even if agent 2 is rank-envious for the desired agent 3, agent 3 would not prefer to be matched with agent 2.

The next basic observation can be made for $r^\text{BP}$-EF matchings.

**Observation 2.** An $r^\text{BP}$-EF matching matches every agent ranked first by someone with an agent who ranks her first or with an agent that she ranks better than all agents who rank her first.

By definition, every BP-stable matching is $r^\text{BP}$-EF, implying that an $r^\text{BP}$-EF matching always exists under globally-ranked [4] or narsissistically single-peaked preferences [13]. Yet, in general, an $r^\text{BP}$-EF matching may not exist, as shown in the next example. Moreover, a wr-EF matching may not exist even under 1-Euclidean preferences.

**Example 2.** Let us consider a roommate instance with six agents who have the preferences below.

<figure><img src="image_5.png" /></figure>

By Observation 2, agent 2 can only be matched with agent 5 or 6, while agent 5 can only be matched with agent 6 or 2 and agent 6 can only be matched with agent 2 or 5. This cannot be achieved together, thus there cannot be an $r^\text{BP}$-EF matching in this instance.

Consequently, we further relax wr-EF and $r^\text{BP}$-EF by combining their two versions of justified envy. Agent *i* strongly BP rank-envies agent *j* in matching $\sigma$ if $\sigma(j) \succ_i \sigma(i)$, $r_i(\sigma(j)) < r_j(\sigma(j))$, $r_{\sigma(i)}(i) > r_i(\sigma(j))$ and $i \succ_{\sigma(j)} j$.

**Definition 5** (Weak BP rank-envy-freeness (wr$^\text{BP}$-EF)). A matching $\sigma$ is wr$^\text{BP}$-EF if $\sigma(i) \succ_i \sigma(j)$ or $r_j(\sigma(j)) \le r_i(\sigma(j))$ or $r_{\sigma(i)}(i) \le r_i(\sigma(j))$ or $j \succ_{\sigma(j)} i$, for every $i, j \in N$.

We prove below that a rank-maximal matching is always wr$^\text{BP}$-EF, guaranteeing the existence of a wr$^\text{BP}$-EF matching.

**Proposition 1.** Every rank-maximal matching is wr$^\text{BP}$-EF.

*Proof.* Let $\sigma$ be a rank-maximal matching that is not wr$^\text{BP}$-EF. It follows that there exist two agents *i* and *j* such that $\sigma(j) \succ_i \sigma(i)$, $r_i(\sigma(j)) < r_j(\sigma(j))$, $r_i(\sigma(j)) < r_{\sigma(i)}(i)$ and $i \succ_{\sigma(j)} j$. If we consider the matching $\sigma'$ resulting from the swap between *i* and *j* in $\sigma$, then *i* is matched with $\sigma(j)$ and *j* is matched with $\sigma(i)$ in $\sigma'$, while the rest remains unchanged. Therefore, *i* and $\sigma(j)$ are better off in $\sigma'$, while $\sigma(i)$ and *j* may be worse off. However, the rank that *i* gets for her partner in $\sigma'$ is strictly better than the one that $\sigma(i)$ and *j* get in $\sigma$. Therefore, the signature of $\sigma'$ is strictly better, lexicographically, than the signature of $\sigma$, contradicting the rank-maximality of $\sigma$. $\square$

**Corollary 1.** Every roommate instance admits a wr$^\text{BP}$-EF matching.

## 4 Characterization of Rank-Based Envy-Freeness

For a given matching $\sigma$ and a given integer $k \in [n]$, let $N_k^\sigma$ denote the subset of agents who are matched in $\sigma$ with an agent they rank at a position better than $k$ in their preferences, i.e., $N_k^\sigma := \{j \in N : r_j(\sigma(j)) < k\}$. This enables us to define, for each agent $i \in N$, the best rank $\rho^\sigma(i)$ that a “not already satisfied” agent can assign to $i$, i.e., $\rho^\sigma(i) = \min_{k \in [n-1]} \min_{j \in N_k^\sigma} r_j(i)$. Then, we can partition the agents w.r.t. these ranks in subsets $(T_1^\sigma, \dots, T_{n-1}^\sigma)$ where $T_k^\sigma := \{i \in N : \rho^\sigma(i) = k\}$ for each $k < n$. For each agent $i$, let $A_i^\sigma$ be the subset of agents that realize the best rank of $i$, i.e., $A_i^\sigma = \{j \in N : N_k^\sigma : r_j(i) = \rho^\sigma(i)\}$ (the mentions to $\sigma$ may be omitted).

We refine Observation 1 in the next characterization theorem.

**Theorem 1.** A matching $\sigma$ is r-EF iff every agent $i \in T_\ell^\sigma$ is assigned to an agent in $A_i^\sigma$, for all $\ell \in [n-1]$.

*Proof.* Suppose that a matching $\sigma$ is r-EF. We proceed by induction over $\ell \in [n-1]$. The base case $\ell = 1$ trivially follows from Observation 1. Suppose that the statement is true for all $\ell' < \ell$ for a given $\ell \in [n-1]$, and that there exists an agent $i \in T_\ell$ such that $\sigma(i) \notin A_i$. By definition of $T_\ell$, $A_i \neq \emptyset$, and we can consider an agent $j \in A_i$. Since $\sigma(i) \notin A_i$, we have $\sigma(i) \in N_\ell^\sigma$ or $r_{\sigma(i)}(i) \neq \ell$. If $\sigma(i) \in N_\ell^\sigma$, then by definition $r_{\sigma(i)}(i) < \ell$ implying that $i \in T_{\ell'}$ for some $\ell' < \ell$, a contradiction. Otherwise, we must have $r_{\sigma(i)}(i) > \ell$, implying that $j$ rank-envies $\sigma(i)$ since $r_j(i) = \ell$ and $j \notin N_\ell^\sigma$, a contradiction.
Consider now the matching $\sigma$ that assigns to each agent $i \in T_\ell$ an agent in $A_i$, for every $\ell \in [n-1]$. Suppose that $\sigma$ is not r-EF. There exist agents $i$ and $j$ such that $i$ rank-envies $j$, i.e., $r_i(\sigma(j)) < r_i(\sigma(i))$ and $r_i(\sigma(j)) < r_j(\sigma(j))$. Suppose that $\sigma(j) \in T_\ell$, i.e., $r_j(\sigma(j)) = \ell$, and thus $\ell' := r_i(\sigma(j)) < \ell$. Since $\sigma(j) \notin T_{\ell'}$, we have that $i \in N_{\ell'}^\sigma$ and thus $r_i(\sigma(i)) < \ell'$, a contradiction. $\square$

Let us now generalize this characterization by considering rank-envy-freeness parameterized by rank $k$. For a given matching $\sigma$, let us denote by $E_i$ the subset of agents that prefer $i$ to their match or are matched with $i$, i.e., $E_i := \{j \in N : \exists \ell, r_j(i) = \ell \wedge j \notin N_\ell^\sigma\}$.

**Proposition 2.** A matching $\sigma$ is $r_k$-EF iff for every agent $i \in T_\ell$ we have $\sigma(i) \in A_i$, for all $\ell \in [n-1]$, and $|E_i| = 1$ if $\ell > k$.

The previous characterization for $r_k$-EF becomes more interesting when $k=1$ since $r_1$-EF gets the same characterization as popularity in the house allocation setting [3].

**Proposition 3.** A matching is $r_1$-EF iff every agent gets matched with either her most preferred agent or her most preferred agent that is not ranked first by someone.

*Proof.* Let $\sigma$ be a matching under which one of the two conditions of the statement holds. Suppose that there exist agents $i$ and $j$ such that $i$ $r_1$-envies $j$, i.e., $\sigma(j) \succ_i \sigma(i)$ and $[r_j(\sigma(j)) > 1$ or $r_j(\sigma(j)) > r_i(\sigma(i))]$ (*). Since $i$ is envious, $\sigma(i)$ cannot be her most preferred agent, and thus $\sigma(i)$ is her most preferred agent that is not ranked first by someone. It follows that $\sigma(j)$ is ranked first by someone. It cannot be by agent $j$ because, otherwise, condition (*) would not hold. Therefore, $\sigma(j)$ is ranked first by someone else, a contradiction.

Let $\sigma$ be an $r_1$-EF matching. Consider any agent $i$. If $\sigma(i)$ is the most preferred agent of $i$, we are done. Otherwise, $i$ envies all agents $j$ such that $\sigma(j) \succ_i \sigma(i)$. Since it cannot be $r_1$-envy, $r_j(\sigma(j)) \le \min\{r_i(\sigma(j)), 1\} = 1$ holds for all such $j$. Suppose now that $\sigma(i)$ is also ranked first by some agent $j$. Therefore, $\sigma(j)$ is not the most preferred agent of $j$ and thus $j$ $r_1$-envies $i$, a contradiction. $\square$

Considering relaxations of rank-envy-freeness, we can provide some necessary conditions for $r^{\text{BP}}$-EF and wr-EF, stated below. Finding exact characterizations for these criteria is an open question.

**Proposition 4.** If a matching $\sigma$ is $r^{\text{BP}}$-EF then for every $i \in T_\ell$ either $\sigma(i) \in A_i$ or $r_i(\sigma(i)) < \min_{j \in A_i} r_j(i)$ holds, for all $\ell \in [n-1]$.

**Observation 3.** For every $i$ in $T_1$ such that for every $j \in A_i$, $j \notin T_1$ or $A_j = \{i\}$, we have $\sigma(i) \in A_i$, in every wr-EF matching.

# 5 Existence of Rank-Based Envy-Free Matchings

We have already mentioned some existence statements when introducing our criteria. This section deals with the complexity of deciding the existence of a solution satisfying a given fairness concept.

An r-EF matching does not always exist, as shown in Example 1, but we further prove below that the related decision problem is hard.

**Theorem 2.** Deciding whether a roommate instance admits an r-EF matching is NP-complete even under globally-ranked preferences.

*Proof sketch.* Membership to NP is straightforward. For hardness, we reduce from (3,B2)-SAT [10]. In an instance of (3,B2)-SAT, we are given a CNF propositional formula $\psi$ where every clause $C_j$, for $j \in [m]$, contains exactly three literals and every variable $x_i$, for $i \in [p]$, occurs exactly twice as a positive literal $x_i$ and twice as a negative literal $\bar{x}_i$ in $\psi$. From an instance of (3,B2)-SAT, we construct a roommate instance as follows.

* For each clause $C_j$, we create: three clause-agents $K_j^1$, $K_j^2$, and $K_j^3$, associated with the three literals of the clause, two agents $q_j^1$ and $q_j^2$, and two agents $G_j^1$ and $G_j^2$.

* For each variable $x_i$, we create: four literal-agents $y_i^1$, $y_i^2$, $\bar{y}_i^1$ and $\bar{y}_i^2$ and four literal-agents $Z_i^1$, $Z_i^2$, $\bar{Z}_i^1$ and $\bar{Z}_i^2$, associated with each occurrence of variable literals, two agents $a_i$ and $b_i$, and a variable-gadget composed of six agents $\Gamma_i$, $\Delta_i$, $\Theta_i$ and $\gamma_i$, $\delta_i$, $\theta_i$.

* We additionally create $\frac{m}{2}$ agents $d_k$ for $k \in [\frac{m}{2}]$, and ten dummy agents $\lambda_k$ and $\Lambda_k$ for $k \in [5]$.

The preferences of the agents are constructed as described in Table 1.<fnref n="1" /> One can observe that the preferences are globally-ranked.

<table><caption>**Table 1:** Agents' preferences for the reduction proof of Theorem 2 for every $j \in [m]$, $i \in [p]$, $k \in [m/2]$, and $r \in [5]$. Notation $t_j^\ell$ stands for the literal-agent associated with the $\ell^{\text{th}}$ literal of clause $C_j^\ell$ for $\ell \in [3]$; and $K(y_i^\ell)$ (resp., $K(\bar{y}_i^\ell)$) denotes the clause-agent $K_j^\ell$ such that $t_j^\ell = y_i^\ell$ (resp., $t_j^\ell = \bar{y}_i^\ell$). Notation $[x]_{\text{condition}}$ means that $x$ is present at the given rank only if condition is satisfied. Framed dots [...] denote an arbitrary order over the remaining agents.</caption><tbody><tr><td>K<sub>j</sub><sup>1</sup>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>λ<sub>3</sub></td><td>▷</td><td>t<sub>j</sub><sup>1</sup>▷q<sub>j</sub><sup>1</sup>▷λ<sub>4</sub>▷[...]</td></tr><tr><td>K<sub>j</sub><sup>2</sup>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>λ<sub>3</sub></td><td>▷</td><td>t<sub>j</sub><sup>2</sup>▷λ<sub>4</sub>▷q<sub>j</sub><sup>2</sup>▷[...]</td></tr><tr><td>K<sub>j</sub><sup>3</sup>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>λ<sub>3</sub></td><td>▷</td><td>t<sub>j</sub><sup>3</sup>▷q<sub>j</sub><sup>1</sup>▷q<sub>j</sub><sup>2</sup>▷[...]</td></tr><tr><td>G<sub>j</sub><sup>1</sup>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>λ<sub>3</sub></td><td>▷</td><td>λ<sub>4</sub>▷q<sub>j</sub><sup>1</sup>▷λ<sub>5</sub>▷d<sub>m</sub>▷[...]</td></tr><tr><td>G<sub>j</sub><sup>2</sup>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>λ<sub>3</sub></td><td>▷</td><td>λ<sub>4</sub>▷λ<sub>5</sub>▷q<sub>j</sub><sup>2</sup>▷d<sub>m</sub>▷[...]</td></tr><tr><td>Z<sub>j</sub><sup>1</sup>:</td><td>a<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub></td><td>▷</td><td>y<sub>i</sub><sup>1</sup></td><td>▷[...]</td><td></td></tr><tr><td>Z<sub>j</sub><sup>2</sup>:</td><td>a<sub>i</sub></td><td>▷</td><td>θ<sub>i</sub></td><td>▷</td><td>y<sub>i</sub><sup>1</sup></td><td>▷[...]</td><td></td></tr><tr><td>Z<sub>j</sub><sup>3</sup>:</td><td>b<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub></td><td>▷</td><td>y<sub>i</sub><sup>2</sup></td><td>▷[...]</td><td></td></tr><tr><td>Z<sub>j</sub><sup>4</sup>:</td><td>b<sub>i</sub></td><td>▷</td><td>θ<sub>i</sub></td><td>▷</td><td>y<sub>i</sub><sup>2</sup></td><td>▷[...]</td><td></td></tr><tr><td>Γ<sub>i</sub>:</td><td>λ<sub>1</sub></td><td>▷</td><td>λ<sub>2</sub></td><td>▷</td><td>θ<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub>▷[...]</td></tr><tr><td>Δ<sub>i</sub>:</td><td>γ<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub></td><td>▷</td><td>θ<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub>▷[...]</td></tr><tr><td>Θ<sub>i</sub>:</td><td>γ<sub>i</sub></td><td>▷</td><td>θ<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub></td><td>▷</td><td>δ<sub>i</sub>▷[...]</td></tr><tr><td>Λ<sub>r</sub>:</td><td>λ<sub>r</sub></td><td>▷[...]</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><tbody><tr><td>q<sub>j</sub><sup>1</sup>:</td><td>K<sub>j</sub><sup>1</sup></td><td>▷</td><td>K<sub>j</sub><sup>3</sup></td><td>▷</td><td>G<sub>j</sub><sup>1</sup></td><td>▷[...]</td><td></td></tr><tr><td>q<sub>j</sub><sup>2</sup>:</td><td>K<sub>j</sub><sup>2</sup></td><td>▷</td><td>K<sub>j</sub><sup>3</sup></td><td>▷</td><td>G<sub>j</sub><sup>2</sup></td><td>▷[...]</td><td></td></tr><tr><td>d<sub>k</sub>:</td><td>Λ<sub>2</sub></td><td>▷</td><td>Λ<sub>1</sub></td><td>▷</td><td>G<sub>1</sub><sup>1</sup></td><td>▷</td><td>G<sub>1</sub><sup>1</sup>▷...▷G<sub>m</sub><sup>1</sup>▷[...]</td></tr><tr><td>y<sub>i</sub><sup>1</sup>:</td><td>[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>1</sup>=t<sub>j</sub><sup>3</sup>▷K(y<sub>i</sub><sup>1</sup>)▷[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>1</sup>∈{t<sub>j</sub><sup>1</sup>,t<sub>j</sub><sup>2</sup>}▷Z<sub>i</sub><sup>1</sup>▷[...]</td></tr><tr><td>y<sub>i</sub><sup>2</sup>:</td><td>[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>1</sup>=t<sub>j</sub><sup>3</sup>▷K(\bar{y}<sub>i</sub><sup>1</sup>)▷[Λ<sub>2</sub>∃j, \bar{y}<sub>i</sub><sup>1</sup>∈{t<sub>j</sub><sup>1</sup>,t<sub>j</sub><sup>2</sup>}▷\bar{Z}<sub>i</sub><sup>1</sup>▷[...]</td></tr><tr><td>y<sub>i</sub><sup>2</sup>:</td><td>[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>2</sup>=t<sub>j</sub><sup>3</sup>▷K(y<sub>i</sub><sup>2</sup>)▷[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>2</sup>∈{t<sub>j</sub><sup>1</sup>,t<sub>j</sub><sup>2</sup>}▷Z<sub>i</sub><sup>2</sup>▷[...]</td></tr><tr><td>y<sub>i</sub><sup>2</sup>:</td><td>[Λ<sub>2</sub>∃j, y<sub>i</sub><sup>2</sup>=t<sub>j</sub><sup>3</sup>▷K(\bar{y}<sub>i</sub><sup>2</sup>)▷[Λ<sub>2</sub>∃j, \bar{y}<sub>i</sub><sup>2</sup>∈{t<sub>j</sub><sup>1</sup>,t<sub>j</sub><sup>2</sup>}▷\bar{Z}<sub>i</sub><sup>2</sup>▷[...]</td></tr><tr><td>a<sub>i</sub>:</td><td>Λ<sub>2</sub></td><td>▷</td><td>Λ<sub>3</sub></td><td>▷</td><td>Λ<sub>4</sub></td><td>▷</td><td>Z<sub>i</sub><sup>1</sup>▷\bar{Z}<sub>i</sub><sup>1</sup>▷[...]</td></tr><tr><td>b<sub>i</sub>:</td><td>Λ<sub>2</sub></td><td>▷</td><td>Λ<sub>3</sub></td><td>▷</td><td>Λ<sub>4</sub></td><td>▷</td><td>Z<sub>i</sub><sup>2</sup>▷\bar{Z}<sub>i</sub><sup>2</sup>▷[...]</td></tr><tr><td>γ<sub>i</sub>:</td><td>Γ<sub>i</sub></td><td>▷</td><td>Δ<sub>i</sub></td><td>▷</td><td>Θ<sub>i</sub></td><td>▷[...]</td><td></td></tr><tr><td>δ<sub>i</sub>:</td><td>Γ<sub>i</sub></td><td>▷</td><td>Δ<sub>i</sub></td><td>▷</td><td>Θ<sub>i</sub></td><td>▷[...]</td><td></td></tr><tr><td>θ<sub>i</sub>:</td><td>Γ<sub>i</sub></td><td>▷</td><td>Θ<sub>i</sub></td><td>▷</td><td>Δ<sub>i</sub></td><td>▷[...]</td><td></td></tr><tr><td>λ<sub>r</sub>:</td><td>λ<sub>r</sub></td><td>▷[...]</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

We claim that formula $\psi$ is satisfiable iff there exists an r-EF matching in the constructed roommate instance.

⇒: Suppose that there exists a truth assignment $\phi$ of the variables that satisfies $\psi$. We construct an r-EF matching $\sigma$ as follows:

* For every $r \in [5]$, let $\sigma(\lambda_r) = \Lambda_r$;

<footnote n="1">¹ One can show that this reduction proof also holds for the marriage setting, by distinguishing the lower and upper case agents as the two different types.</footnote>
* For every literal-agent $y_i^\ell$ (resp., $\bar{y}_i^\ell$), if the associated literal $x_i$ (resp., $\bar{x}_i$) is true in $\phi$ then $\sigma(y_i^\ell) = K(y_i^\ell)$ (resp., $\sigma(\bar{y}_i^\ell) = K(\bar{y}_i^\ell)$). Otherwise, $\sigma(y_i^\ell) = Z_i^\ell$ (resp., $\sigma(\bar{y}_i^\ell) = \bar{Z}_i^\ell$);

* For every clause-agent $K_j^\ell$ that has not been assigned yet, if $\ell \in [2]$, then $\sigma(K_j^\ell) = q_j^1$, otherwise $\sigma(K_j^3) = q_j^1$ if $q_j^1$ is still available or $\sigma(K_j^3) = q_j^2$ otherwise;

* For every agent $Z_i^\ell$ (resp., $\bar{Z}_i^\ell$) that has not been assigned yet, $\sigma(Z_i^\ell) = a_i$ if $\ell = 1$ and $\sigma(Z_i^\ell) = b_i$ if $\ell = 2$ (resp., $\sigma(\bar{Z}_i^\ell) = a_i$ if $\ell = 1$ and $\sigma(\bar{Z}_i^\ell) = b_i$ if $\ell = 2$).

* For every variable $x_i$, if $x_i$ is true in $\phi$ then let $\sigma(\Delta_i) = \gamma_i$, $\sigma(\Theta_i) = \theta_i$, and $\sigma(\Gamma_i) = \delta_i$. Otherwise, i.e., if $x_i$ is false in $\phi$, then let $\sigma(\Delta_i) = \delta_i$, $\sigma(\Theta_i) = \gamma_i$, and $\sigma(\Gamma_i) = \theta_i$.

* For every agent $q_j^\ell$ that has not been assigned yet, let $\sigma(q_j^\ell) = G_j^\ell$.

* For every remaining agents $G_j^\ell$ and $d_k$, let $\sigma(G_j^\ell) = d_k$.

`$\Leftarrow$` : The global idea is as follows. For each $i \in [p]$, the variable-gadget enforces that exactly two literal-agents among $y_i^1, y_i^2, \bar{y}_i^1$, and $\bar{y}_i^2$ are matched with their associated agents $Z_i^1, Z_i^2, \bar{Z}_i^1$, and $\bar{Z}_i^2$, and that these two chosen literal-agents mimic a truth assignment of the variables, i.e., they correspond to the same literal. The two remaining literal-agents are forced to be matched with their associated clause-agent, representing the clause to which their corresponding occurrence of literal belongs. If for a clause $C_j$, no clause-agent $K_j^\ell$ is assigned to a literal-agent, then agent $K_j^3$ will be necessarily assigned to an agent ranking her worse than second, while her associated literal-agent $t_j^3$ ranks her second and is currently matched with her third choice, creating rank-envy, a contradiction. $\square$

Whereas the characterization results of the previous section enable to derive algorithms that can be exponential, the characterization of $r_1$-EF provides a polynomial-time algorithm, as stated below.

**Proposition 5.** Deciding whether a roommate instance admits an $r_1$-EF matching can be done in polynomial time.

*Proof.* By Proposition 3, it suffices to search for a perfect matching in the undirected graph $G = (N, E)$ where $\{i, j\} \in E$ iff $j$ is either ranked first by $i$ or is her most preferred agent that is not ranked first by someone, and the reverse holds for $i$ w.r.t. $j$'s preferences. $\square$

Concerning the relaxations of rank-envy-freeness, the same construction as in the proof of Theorem 2 can be used to show that deciding about the existence of a wr-EF matching is NP-hard.

**Proposition 6.** Deciding whether a roommate instance admits a wr-EF matching is NP-complete under globally-ranked preferences.

Although an $r^{BP}$-EF matching can be efficiently computed by constructing a BP-stable matching, under globally-ranked or narcissistically single-peaked preferences [4, 13], we prove that in general the related decision problem is hard. The complexity proof is similar to the one in Theorem 2 but the agents cannot be partitioned in two types and we need gadgets that are based on odd rings [15].

**Theorem 3.** Deciding whether a roommate instance admits an $r^{BP}$-EF matching is NP-complete.

Finally, by the fact that a rank-maximal matching always exists in a roommate instance, the same guarantee holds for a wr$^{BP}$-EF matching (Corollary 1). As already discussed in the literature, a rank-maximal matching can be constructed by solving a maximum weight matching problem with weight $n^{n-r_i(j)} + n^{n-r_j(i)}$ for a pair of agents $\{i, j\}$. By using the scaling algorithm of Gabow and Tarjan [21], this problem can be solved in polynomial time.

**Corollary 2.** A wr$^{BP}$-EF matching can be found in polynomial time.

# 6 Rank-Based Envy-Freeness and Optimality

Let us analyze in this section the connections between optimal matchings and rank-based envy-free matchings, that result in the links between optimality and fairness criteria of Figure 1.

We first prove that, although rank-maximality implies our weakest criterion wr$^{BP}$-EF (Proposition 1), it is not true for popularity.

**Proposition 7.** A popular matching may not be wr$^{BP}$-EF, even under 1-Euclidean preferences.

*Proof.* Let us consider a roommate instance with eight agents who have the preferences below.

<figure><img src="image_6.png" /></figure>

The preferences are 1-Euclidean w.r.t. the following embedding:

<figure><img src="image_7.png" /></figure>

The framed matching is popular but not wr$^{BP}$-EF: agent 4 is strongly BP rank-envious towards agent 8. $\square$

Note that the implication of wr$^{BP}$-EF by rank-maximality is tight w.r.t. the hierarchy of our relaxed criteria because stronger fairness criteria are not implied by rank-maximality, as stated below.

**Proposition 8.** A rank-maximal matching may not be wr-EF or $r^{BP}$-EF, even under 1-Euclidean preferences.

Conversely, even $r_1$-EF is not a stronger requirement than rank-maximality, as proved in the next proposition.

**Proposition 9.** An $r_1$-EF matching may not be rank-maximal even under 1-Euclidean preferences.

*Proof.* Let us consider a roommate instance with six agents who have the preferences below.

<figure><img src="image_8.png" /></figure>

The preferences are 1-Euclidean w.r.t. the following embedding:

<figure><img src="image_9.png" /></figure>

The encircled matching is $r_1$-EF, but it is not rank-maximal because the unique rank-maximal matching is the framed matching. $\square$

And even $r_2$-EF is not stronger than popularity, as stated below.

**Proposition 10.** An $r_2$-EF matching may not be popular even under 1-Euclidean preferences.

The previous result is tight w.r.t. the scale of $r_k$-EF because it does not hold when $k = 1$, as proved in the next proposition.
**Proposition 11.** Every $r_1$-EF matching is popular.

*Proof.* Let $\sigma^1$ be an $r_1$-EF matching that is not popular, i.e., there exists a matching $\sigma^2$ such that $|N^2| > |N^1|$, where $N^\ell := \{i \in N : \sigma^\ell(i) \succ_i \sigma^{3-\ell}(i)\}$ for $\ell \in [2]$. Let $i$ be an agent in $N^2$, and $j$ the agent such that $\sigma^2(i) = \sigma^1(j)$. Since $\sigma^1$ is $r_1$-EF, we must have that $r_j(\sigma^1(j)) \le \min\{r_i(\sigma^1(j)), 1\} = 1$. Therefore, $\sigma^1(j) \succ_j \sigma^2(j)$, and thus $j \in N^1$. Hence, we can associate each agent in $N^2$ with a distinct agent in $N^1$, and thus $|N^1| \ge |N^2|$, a contradiction. $\square$

Finally, our weakest fairness criterion satisfies Pareto-optimality.

**Proposition 12.** Every wr$^{BP}$-EF matching is Pareto-optimal.

*Proof.* Suppose that a wr$^{BP}$-EF matching $\sigma$ is Pareto-dominated by matching $\sigma'$. Therefore, there exists an improving cycle from $\sigma$ to $\sigma'$ along the agents $(i_1, \dots, i_k)$ and $(j_1, \dots, j_k)$ such that $\sigma'(i_\ell) = \sigma(i_{\ell+1}) = j_{\ell+1}$ and $\sigma'(j_\ell) = \sigma(j_{\ell-1}) = i_{\ell-1}$ for every $\ell \in [k]$ ($k+1$ corresponds to 1 and 0 corresponds to $k$). Consider an agent $c_1 := i_1$ in the improving cycle. Since $\sigma'$ Pareto-dominates $\sigma$, we have $\sigma'(i_\ell) = j_{\ell+1} \succ_i \sigma(i_\ell) = j_\ell$ and $\sigma'(j_\ell) = i_{\ell-1} \succ_j \sigma(j_\ell) = i_\ell$ for every $\ell \in [k]$. Therefore, the agents $i_1$ and $j_2$, who are matched together in $\sigma'$, form a blocking pair in $\sigma$ and agent $i_1$ envies agent $i_2$ who is matched with agent $j_2$ in $\sigma$. Thus, for $i_1$ not being strongly BP rank-envious towards $i_2$, we need that $(1) r_{i_2}(j_2) \le r_{i_1}(j_2)$ or $(2) r_{j_1}(i_1) \le r_{i_1}(j_2)$. If (1) holds, then we have that $r_{i_2}(\sigma'(i_2)) < r_{i_2}(\sigma(i_2)) = r_{i_2}(j_2) \le r_{i_1}(j_2) = r_{i_1}(\sigma'(i_1))$. If (2) holds, then we have that $r_{j_1}(\sigma'(j_1)) < r_{j_1}(\sigma(j_1)) = r_{j_1}(i_1) \le r_{i_1}(j_2) = r_{i_1}(\sigma'(i_1))$. If (1) holds then we set $c_2 := i_2$, otherwise (2) holds and we set $c_2 := j_1$. It follows that $c_2$ is matched with a partner at a rank strictly better than $c_1$ in $\sigma'$. By repeating this argument starting from $c_2$ and so on, we get a chain of agents $c_1, c_2, \dots, c_k'$ from $\cup_{\ell \in [k]} \{i_\ell, j_\ell\}$ such that $c_\ell$ is matched with a partner at a rank strictly better than $c_{\ell-1}$ in $\sigma'$, for $\ell \in \{2, \dots, k\}$. Since $\cup_{\ell \in [k]} \{i_\ell, j_\ell\}$ is finite, there exist two agents $c_\ell$ and $c_{\ell'}$ for $\ell \ne \ell'$ such that $c_\ell = c_{\ell'}$, contradicting the iterative strict improvement of the ranks in $\sigma'$. $\square$

# 7 Rank-Based Envy-Freeness and Stability

We analyze in this section the connections between stable matchings and rank-based envy-free matchings, that result in the links between stability and fairness criteria of Figure 1. We first remark that, although BP-stability implies r$^{BP}$-EF and thus the criterion wr$^{BP}$-EF, it does not imply further rank-based envy-free criteria.

**Proposition 13.** A blocking-pair and swap-stable matching may not be wr-EF even under 1-Euclidean preferences.

*Proof.* Let us consider a roommate instance with six agents who have the preferences below.

<figure><img src="image_10.png" /></figure>

The preferences are 1-Euclidean w.r.t. the following embedding:

<figure><img src="image_11.png" /></figure>

The framed matching is BP-stable and swap-stable but it is not wr-EF: agent 6 envies agent 4 for her partner 5. $\square$

Conversely, even $r_1$-EF does not imply BP-stability.

**Proposition 14.** An $r_1$-EF matching may not be blocking-pair stable even under 1-Euclidean preferences.

*Proof.* Let us consider a roommate instance with four agents who have the preferences below (left) that are 1-Euclidean w.r.t. the embedding given below (right).

<figure><img src="image_12.png" /></figure>

The framed matching is $r_1$-EF but it is not BP-stable: agents 2 and 3 prefer to be together than with their current partner. $\square$

Every envy-free matching is trivially swap-stable because no agent prefers the partner of another agent. We show that although r-EF is a strong relaxation of envy-freeness, it still implies swap-stability.

**Proposition 15.** Every r-EF matching is swap-stable.

*Proof.* Suppose that two agents $i$ and $j$ have an incentive to swap from a matching $\sigma$ which is r-EF, i.e., $r_i(\sigma(j)) < r_i(\sigma(i))$ and $r_j(\sigma(i)) < r_j(\sigma(j))$. By rank-envy-freeness, we have $r_j(\sigma(j)) \le r_i(\sigma(j)) < r_i(\sigma(j))$. Therefore, we get that $r_j(\sigma(i)) < r_j(\sigma(j)) \le r_i(\sigma(j)) < r_i(\sigma(i))$, and thus $r_j(\sigma(i)) < r_i(\sigma(i))$, implying that agent $j$ is rank-envious towards agent $i$ in $\sigma$, a contradiction. $\square$

However, this implication does not hold for weaker versions of rank-envy-freeness, as stated below.

**Proposition 16.** A wr-EF matching may not be swap-stable even under 1-Euclidean preferences.

**Proposition 17.** An r$^{BP}$-EF matching may not be swap-stable even under globally-ranked or narcissistically single-peaked preferences.

Yet, under stronger restrictions, the implication holds for r$^{BP}$-EF.

**Proposition 18.** Every r$^{BP}$-EF matching is swap-stable under 1-Euclidean preferences.

*Proof.* Let $\sigma$ be an r$^{BP}$-EF matching that is not swap-stable. There exist two agents $i$ and $j$ such that $\sigma(j) \succ_i \sigma(i)$ and $\sigma(i) \succ_j \sigma(j)$. There must exist an agent between $i$ and $j$ who rank the partner of the other agent at a better rank, say it is the case for $j$, i.e., $r_j(\sigma(i)) < r_i(\sigma(i))$. Because $\sigma$ is r$^{BP}$-EF, we must have $i \succ_{\sigma(i)} j$. Suppose that the preferences are 1-Euclidean w.r.t. the embedding $E: N \to \mathbb{R}$ such that, w.l.o.g., $E(i) < E(j)$. To respect the preferences of the agents, only two orders are possible: $(1) E(i) < E(\sigma(j)) < E(\sigma(i)) < E(j)$, or $(2) E(\sigma(j)) < E(i) < E(\sigma(i)) < E(j)$.

If (1) holds, then $E(\sigma(i)) - E(i) < E(j) - E(\sigma(i))$ because $i \succ_{\sigma(i)} j$. Since $E(\sigma(j)) < E(\sigma(i))$, we have that $E(\sigma(j)) - E(i) < E(j) - E(\sigma(j))$, i.e., agent $\sigma(j)$ prefers $i$ to $j$. By the axis, $\sigma(j)$ also prefers $\sigma(i)$ to $j$. If $\sigma(j)$ prefers $\sigma(i)$ to $i$ (resp., $i$ to $\sigma(i)$), then the only agents that $\sigma(j)$ may prefer to $\sigma(i)$ (resp., $i$) are the agents $x \ne \sigma(j)$ such that $E(i) < E(x) < E(\sigma(i))$. In contrast, $i$ (resp., $\sigma(i)$) prefers the agents $x$ to $\sigma(i)$ (resp., $i$) such that $E(i) < E(x) < E(\sigma(i))$, including $\sigma(j)$. Therefore, $\sigma(j)$ rank-envies $i$ (resp., $\sigma(i)$), while agent $\sigma(i)$ (resp., $i$) also prefers $\sigma(j)$ to $i$ (resp., $\sigma(i)$), i.e., $\sigma(i)$ (resp., $i$) and $\sigma(j)$ form a blocking pair, a contradiction.

If (2) holds, then we have that the only agents that $i$ may prefer to $\sigma(j)$ are the agents $x \ne i$ such that $E(\sigma(j)) < E(x) < E(\sigma(i))$. In contrast, $j$ prefers the agents $x$ to $\sigma(j)$ such that $E(\sigma(j)) < E(x) \le E(\sigma(i))$ or $E(\sigma(i)) < E(x) < E(j)$. Therefore, $i$ is rank-envious towards $j$, while agent $\sigma(j)$ also prefers $i$ over $j$ (by the axis), meaning that $i$ and $\sigma(j)$ form a blocking pair, a contradiction. $\square$
<figure><img src="image_13.png" /><figcaption>(a) Proportion of instances for which a matching satisfying the given criterion exists (criteria for which existence is guaranteed are omitted)</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>(b) Number of matchings in average that satisfy the given criterion</figcaption></figure>

<caption>**Figure 2:** Existence experiments for rank-based envy-free matchings, stable matchings, or optimal matchings in roommate instances with 10 agents and various preference distributions for 10,000 runs.</caption>

# 8 Empirical Study of Rank-Based Envy-Freeness

In this section, we empirically evaluate the existence of fair match-
ings, and compare them to optimal or stable matchings, under dif-
ferent types of preferences. The generated preferences can follow:
the *impartial culture (IC)*, i.e., they are uniformly drawn from the set
of all possible linear orders; the *(narcissistically) single-peaked uni-
form peak ((nar)SP-UP) distribution* [16], i.e., an axis > over agents
is generated and then, for each agent *i*, we construct $\succ_i$ by uniformly
choosing a peak agent and then iteratively and uniformly choosing
between the left and right next available agent on > for the next pre-
ferred agent (for narcissistic preferences, the peak is one of the two
agents directly adjacent to *i* in >); the *globally-ranked uniform (GR)
distribution*, i.e., the preference profile is derived from a uniformly
drawn global order $\succ$ over all pairs of agents; or the *1-Euclidean
(1D) uniform distribution*, i.e., a preference profile is generated by
first uniformly choosing a real number for each agent and then deriv-
ing all agents' preference rankings by sorting the distances.

The existence of matchings satisfying different criteria is ana-
lyzed, for *n* = 10 agents and by sampling 10,000 instances for each
preference distribution. The criteria under consideration are rank-
based envy-freeness, where the results for *r*<sub>*k*</sub>-EF are only shown for
*k* ∈ [4], BP-stability (BP), swap-stability (SS), popularity (Pop),
rank-maximality (RM), and Pareto-optimality (PO). For each crite-
rion, we count the number of instances where a matching satisfying
it exists as well as the number of such matchings per instance and
compute its average (all possible matchings are checked).

Figure 2a shows the proportion of instances that satisfy each cri-

terion. We observe that r-EF and $r_k$-EF matchings exist with a sig-
nificant probability only for preferences that are at least narcissisti-
cally single-peaked or globally-ranked, they rarely exist for general
or single-peaked preferences. This confirms that r-EF is a very de-
manding fairness criterion. However, for 1-Euclidean preferences,
even an $r_1$-EF matching exists with a probability greater than 0.5,
so we really need a strong structure on the preferences. Interestingly,
a wr-EF matching exists with a probability greater than 0.75 for all
preference distributions (and even greater than 0.9 for narSP-UP or
GR distributions). This finding contrasts with our theoretical results
establishing the same impossibilities for r-EF and wr-EF, and shows
that wr-EF is nevertheless a useful relaxation. Finally, the probability
of existence of an $r^B$-EF matching is very close to 1 even on general
preferences for which the existence is not theoretically guaranteed.

Figure 2b indicates the average number of matchings that satisfy each criterion. As expected, the number of r-EF matchings is very low. While there are more wr-EF matchings, this number is not very large, even for instances where there exist such matchings, showing that this concept would not recommend too many solutions in practice. The same remark holds for $r^B$-EF. A larger number of matchings satisfy wr$^B$-EF, especially under weak preference restrictions. Nevertheless, this number is much smaller than the number of Pareto-optimal matchings, showing the filtering ability of wr$^B$-EF.

# 9 Conclusion

We have investigated fair roommate matchings under the prism of
rank-based envy-freeness. Our study takes inspiration from a previ-
ous work on rank-envy-freeness (r-EF) in house allocation [9]. Inter-
estingly, when matching agents to other agents instead of matching
them to objects, we observe important differences w.r.t. fairness. In-
deed, while an r-EF matching can be computed in polynomial time
in house allocation, we have shown that r-EF may not be achiev-
able in the roommate setting and that the related decision problem
is NP-complete. Additionally, whereas the stronger criterion $r_1$-EF is
equivalent to popularity in house allocation [9], we show that their
characterization in that setting [3] fails to transfer to the roommate
setting for popularity but still holds true for $r_1$-EF. We also connect r-
EF and Pareto-optimality, contrary to house allocation, because even
our strongest relaxation of r-EF, namely wr$^B$-EF, implies it, while a
wr$^B$-EF matching is computable in polynomial time. This criterion
is nevertheless not trivially satisfied since it discards many Pareto-
optimal matchings in practice. See Figure 1 for a global picture of
the interactions between stability, optimality and fairness criteria.

Several challenging open questions remain, such as the exact char-
acterization of our relaxations of r-EF. Moreover, whereas decid-
ing about the existence of a weak r-EF (wr-EF) or an r-EF match-
ing is hard even under globally-ranked preferences, we do not know
whether other restrictions would help for an efficient algorithm. Fi-
nally, although the existence of an $r_k$-EF matching can be verified in
polynomial time when $k=1$, we conjecture that it is hard for $k=2$.

Our study raises many interesting perspectives for future work. It
would for instance make sense to explore settings with indifference
or partial preference lists. However, since our results already point
out many impossibilities, there is no hope to get much more positive
results in such extensions. For instance, even in the marriage setting,
a wr-EF matching may not exist under 1-Euclidean preferences, and
the complexity proof of Theorem 2 also holds. The main difference is
that an $r^B$-EF matching can always be computed in polynomial time,
because it is the case for a BP-stable matching [22]. In contrast, the
related existence problem is NP-complete in the roommate setting.
Acknowledgements

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

References

[1] Atila Abdulkadiroğlu and Tayfun Sönmez, ‘Random serial dic-
tatorship and the core from random endowments in house allo-
cation problems’, *Econometrica*, **66**(3), 689–701, (1998).

[2] Atila Abdulkadiroğlu and Tayfun Sönmez, ‘School choice: A mechanism design approach’, *American Economic Review*, **93**(3), 729–747, (2003).

[3] David J. Abraham, Robert W. Irving, Telikepalli Kavitha, and Kurt Mehlhorn, ‘Popular matchings’, *SIAM Journal on Computing*, **37**(4), 1030–1045, (2007).

[4] David J. Abraham, Ariel Levavi, David F. Manlove, and Gregg O'Malley, ‘The stable roommates problem with globally-ranked pairs’, in *Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE-07)*, pp. 431–444, (2007).

[5] David J. Abraham and David Manlove, ‘Pareto optimality in the roommates problem’, Technical Report TR-2004-182, University of Glasgow, Department of Computing Science, (2004).

[6] José Alcalde, ‘Exchange-proofness or divorce-proofness? Stability in one-sided matching markets’, *Economic design*, 1(1), 275–287, (1994).

[7] Haris Aziz and Rahul Savani, ‘Hedonic games’, in *Handbook of Computational Social Choice*, eds., F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, 356–376, Cambridge University Press, (2016).

[8] John Bartholdi III and Michael A. Trick, ‘Stable matching with preferences derived from a psychological model’, *Operations Research Letters*, **5**(4), 165–169, (1986).

[9] Khaled Belahcène, Vincent Mousseau, and Anaëlle Wilczynski, ‘Combining fairness and optimality when selecting and allocating projects’, in *Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI-21)*, pp. 38–44, (2021).

[10] Piotr Berman, Marek Karpinski, and Alexander D. Scott, ‘Approximation hardness of short symmetric instances of MAX-3SAT’, Technical Report TR03-049, Electronic Colloquium on Computational Complexity (ECCC), (2003).

[11] Duncan Black, ‘On the rationale of group decision-making’, *Journal of Political Economy*, **56**(1), 23–34, (1948).

[12] Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet, ‘Fair allocation of indivisible goods’, in *Handbook of Computational Social Choice*, eds., F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, 284–310, Cambridge University Press, (2016).

[13] Robert Bredereck, Jiehua Chen, Ugo Paavo Finnendahl, and Rolf Niedermeier, ‘Stable roommates with narcissistic, single-peaked, and single-crossing preferences’, *Autonomous agents and multi-agent systems*, **34**(2), 1–29, (2020).

[14] Katarína Cechlárová, ‘On the complexity of exchange-stable roommates’, *Discrete Applied Mathematics*, **116**(3), 279–287, (2002).

[15] Kim-Sau Chung, ‘On the existence of stable roommate matchings’, *Games and Economic Behavior*, **33**(2), 206–230, (2000).

[16] Vincent Conitzer, ‘Eliciting single-peaked preferences using

comparison queries', *The Journal of Artificial Intelligence Research*, **35**, 161–191, (2009).

[17] Clyde H. Coombs, 'Psychological scaling without a unit of measurement', *Psychological review*, **57**(3), 145, (1950).

[18] Ágnes Cseh, 'Popular matchings', in *Trends in Computational Social Choice*, ed., U. Endriss, 105–122, AI Access, (2017).

[19] Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang, ‘Popular matchings and limits to tractability’, in *Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-19)*, pp. 2790–2809, (2019).

[20] Duncan K. Foley, 'Resource allocation and the public sector', *Yale Economic Essays*, **7**(1), 45–98, (1967).

[21] Harold N. Gabow and Robert E. Tarjan, 'Faster scaling algorithms for network problems', *SIAM Journal on Computing*, **18**(5), 1013–1036, (1989).

[22] David Gale and Lloyd S. Shapley, ‘College admissions and the stability of marriage’, *The American Mathematical Monthly*, **69**(1), 9–15, (1962).

[23] Xiaoxi Guo, Sujoy Sikdar, Lirong Xia, Yongzhi Cao, and Han-
pin Wang, ‘Favoring eagerness for remaining items: Designing
efficient, fair, and strategyproof mechanisms’, *Journal of Arti-
ficial Intelligence Research*, **7**, 287–339, (2023).

[24] Sushmita Gupta, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi, ‘Popular matching in roommates setting is NP-hard’, *ACM Transactions on Computation Theory*, **13**(2), 9:1–9:20, (2021).

[25] Robert W. Irving, ‘An efficient algorithm for the “stable roommates” problem’, *Journal of Algorithms*, **6**(4), 577–595, (1985).

[26] Robert W Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dim-
itrios Michail, and Katarzyna E. Paluch, ‘Rank-maximal
matchings’, *ACM Transactions on Algorithms*, **2**(4), 602–610,
(2006).

[27] Paula Jaramillo, Çağatay Kayı, and Flip Klijn, ‘The core of roommate problems: size and rank-fairness within matched pairs’, *International Journal of Game Theory*, **48**, 157–179, (2019).

[28] Bettina Klaus, David F. Manlove, and Francesca Rossi, ‘Matching under preferences’, in *Handbook of Computational Social Choice*, eds., F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, 333–355, Cambridge University Press, (2016).

[29] Fuhito Kojima and M Utku Ünver, ‘The “Boston” school-choice mechanism: an axiomatic approach’, *Economic Theory*, **55**, 515–544, (2014).

[30] David Manlove, *Algorithmics of matching under preferences*, volume 2, World Scientific, 2013.

[31] Eric McDermid and Robert W. Irving, ‘Sex-equal stable match-
ings: Complexity and exact algorithms’, *Algorithmica*, **68**(3),
545–570, (2014).

[32] Hervé Moulin, *Fair Division and Collective Welfare*, MIT Press, 2004.

[33] Rasoul Ramezanian and Mehdi Feizi, ‘Stepwise ordinal effi-
ciency for the random assignment problem’, *Journal of Mathe-
matical Economics*, **92**, 60–65, (2021).

[34] Assaf Romm, Alvin E. Roth, and Ran I. Shorrer, ‘Stability vs. no justified envy’, Working paper. Available at SSRN: https://ssrn.com/abstract=3550122, (2020).

[35] Suguru Ueda, ‘Envy based fairness in hedonic games’, in *Proceedings of the Genetic and Evolutionary Computation Conference Companion*, pp. 1852–1853, (2018).