Answer: Both unrestricted and globally ranked preferences give \(\mathrm{NP}\)-complete existence problems, even with uniform dyadic masses. An exact algorithm runs in \(O(\tau L^2+m^\tau\tau^3mL)\), where \(m=\tau\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDeciding whether a roommate instance admits an r-EF matching is NP-complete even under globally-ranked preferences.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), strict rankings \(\succ_t\) of partner types, and, in the restricted version, a global order on unordered type pairs inducing those rankings, does there exist a symmetric nonnegative matrix \(x\) with \(\sum_u x_{tu}=\mu_t\) such that for every \(x_{tu}>0\) and \(x_{sv}>0\), \(v\succ_t u\) implies \(R_s(v)\leq R_t(v)\), where \(R_t(v)=\sum_{w\succ_t v}\mu_w+\mu_v/2\)?
A society is atomless and given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible preference types; the number of partner types is \(m=\tau\). Let \(L\) be the total input bit length.
Each type \(t\) has a strict complete ranking \(\succ_t\) of \(T\), including its own type: distinct individuals of the same type may be partners, but an individual cannot partner with herself. In the globally ranked restriction, the input also supplies a strict global order \(\triangleright\) on unordered type pairs, including repeated-type pairs, satisfying \(u\succ_t v\iff\{t,u\}\triangleright\{t,v\}\).
Define \(R_t(v)=\sum_{w\succ_t v}\mu_w+\mu_v/2\). A matching is a real matrix \(x\in\mathbb R_{\geq0}^{T\times T}\) satisfying \(x_{tu}=x_{ut}\) and \(\sum_{u\in T}x_{tu}=\mu_t\); diagonal entries count the mass of individuals paired within their own type.
The matching is rank-envy-free if, for every \(t,u,s,v\in T\) with \(x_{tu}>0\) and \(x_{sv}>0\), \(v\succ_t u\) implies \(R_s(v)\leq R_t(v)\). Equality of ranks permits no justified envy.
Is deciding whether such a rank-envy-free matching exists in \(\mathrm P\) or \(\mathrm{NP}\)-hard, for unrestricted preferences and separately for globally ranked preferences? State running times in \(m,\tau,L\).
For finite societies of an even number of distinct agents, paired in a perfect matching, rank-envy-free matching existence is NP-complete even under globally ranked preferences ([Coutance, Maddila and Wilczynski, 2023](https://anaellewilczynski.pages.centralesupelec.fr/website/articles/ecai23rankenvyfreeness.pdf)).
No result settling this exact atomless mass formulation was located in the literature search.
Both decision problems are \(\mathrm{NP}\)-complete: unrestricted preferences and globally ranked preferences. Hardness holds even when all masses are equal dyadic rationals.
An exact deterministic algorithm runs in
\(\displaystyle O\!\left(\tau L^2+m^\tau\tau^3mL\right).\)
Since \(m=\tau\), this is \(\displaystyle O\!\left(\tau L^2+\tau^{\tau+4}L\right)\). The proof below establishes both hardness and the algorithm.
We use the following finite result: rank-envy-free perfect matching existence is \(\mathrm{NP}\)-hard in the marriage setting, with two equally sized sides, strict complete preferences over the opposite side, and globally ranked pairs.
This is the marriage version of Theorem 2 in Coutance, Maddila and Wilczynski. Footnote 1 on page 496 explicitly states that their reduction also applies to marriage by separating the uppercase and lowercase agents. Global rankedness is preserved by restricting the original pair order to cross-side pairs. [Coutance, Maddila and Wilczynski, 2023](https://anaellewilczynski.pages.centralesupelec.fr/website/articles/ecai23rankenvyfreeness.pdf)
Write the sides as \(A,B\), with \(|A|=|B|=n\). Let \(\rho_t(v)\in\{1,\ldots,n\}\) denote the ordinal position of an opposite-side agent \(v\) in \(t\)'s preferences. A finite perfect matching \(\sigma\) is rank-envy-free precisely when, for agents \(t,s\) on the same side,
\(\displaystyle \sigma(s)\succ_t\sigma(t)\ \Longrightarrow\ \rho_s(\sigma(s))\leq\rho_t(\sigma(s)).\)
If the global pair order is not explicitly supplied, it can be recovered in polynomial time. Make each cross-side pair a vertex of a directed graph, and add precedence edges between consecutive pairs in every agent’s ranking. The promised global rankedness makes this graph acyclic; a topological ordering supplies the required pair order.
The finite hardness result remains valid when the side size is a power of two.
Indeed, let \(q\) be the least power of two satisfying \(q\geq n\). Add \(q-n\) dummy pairs \((a_i,b_i)\). Construct the global cross-side pair order by placing:
Every dummy agent ranks its designated partner first. Moreover, \(a_i\) is the only agent on its side ranking \(b_i\) first: original agents rank original partners ahead of dummies, and other dummy agents rank their own designated partners first.
Consequently, every finite rank-envy-free matching must match \(a_i\) with \(b_i\). Otherwise \(a_i\) prefers \(b_i\) to its assigned partner and ranks \(b_i\) strictly better than the agent receiving \(b_i\), creating rank envy.
After deleting these forced pairs, the original rankings and their ordinal positions are unchanged. Conversely, adjoining the dummy pairs to an original rank-envy-free matching creates no envy: dummy agents receive their first choices, and original agents prefer their assigned original partners to every dummy.
Thus padding preserves existence and global rankedness. Below, assume \(n\) is a power of two.
Create one positive-mass type for each finite agent. Set
\(\displaystyle T=A\cup B,\qquad \tau=m=2n,\qquad \mu_t=c:=\frac{1}{2n}\quad(t\in T).\)
These masses are positive dyadic rationals and sum to \(1\).
Extend the finite global pair order by placing all within-side pairs, including repeated-type pairs, after all cross-side pairs, in any strict order. Define each complete type ranking from this extended order.
This construction has the following properties:
For every opposite-side pair \(t,v\), uniformity of masses gives
\(\displaystyle R_t(v)=c\left(\rho_t(v)-\frac12\right).\)
Hence comparisons of these mass ranks agree exactly with comparisons of finite ordinal positions, including equality.
The construction has polynomial size: \(\tau=2n\), and its complete rankings and global pair order require \(O(n^2\log n)\) bits.
Lemma. Every atomless rank-envy-free matching in the constructed instance has zero mass on all within-side pairs, including diagonal pairs.
Proof. For a matching \(x\), define
\(\displaystyle D_A=\sum_{a,a'\in A}x_{aa'},\qquad D_B=\sum_{b,b'\in B}x_{bb'},\qquad C=\sum_{a\in A,\ b\in B}x_{ab}.\)
Summing the matching equations over each side, and using symmetry, gives
\(\displaystyle D_A+C=\frac12,\qquad D_B+C=\frac12.\)
Therefore \(D_A=D_B\).
Suppose \(D_A>0\). Nonnegativity supplies \(t,u\in A\) with \(x_{tu}>0\). Since \(D_B>0\), there are also \(s,v\in B\) with \(x_{sv}>0\).
Type \(t\) prefers the opposite-side type \(v\) to the same-side type \(u\). Furthermore, \(v\) occupies one of the first \(n\) positions for \(t\), whereas it occupies a position after the first \(n\) for \(s\). Thus
\(\displaystyle R_t(v)\leq c\left(n-\frac12\right)<c\left(n+\frac12\right)\leq R_s(v).\)
Together with the two positive entries, this violates rank-envy-freeness. Hence \(D_A=D_B=0\). Nonnegativity then forces every within-side entry to vanish. \(\square\)
This argument explicitly rules out the additional diagonal matching possibilities allowed by atomlessness.
First observe a general property.
Support heredity. If \(x\) is rank-envy-free and another matching \(\widehat{x}\), for the same input, satisfies
\(\displaystyle \operatorname{supp}(\widehat{x})\subseteq\operatorname{supp}(x),\)
then \(\widehat{x}\) is rank-envy-free.
Indeed, every pair of positive entries tested in \(\widehat{x}\) was already tested in \(x\); the preferences and ranks are unchanged.
Now suppose the constructed atomless instance admits a rank-envy-free matching \(x\). By the preceding lemma, its support is bipartite. Define
\(\displaystyle y_{ab}=\frac{x_{ab}}{c}\qquad(a\in A,\ b\in B).\)
The matching equations imply that every row and column of \(y\) sums to \(1\).
Let \(G\) be the bipartite graph containing precisely the edges with \(y_{ab}>0\). For any \(U\subseteq A\), let \(N(U)\subseteq B\) denote its neighbors. Then
\(\displaystyle |U|=\sum_{a\in U}\sum_{b\in N(U)}y_{ab}\leq\sum_{b\in N(U)}\sum_{a\in A}y_{ab}=|N(U)|.\)
Thus \(G\) satisfies Hall’s condition. Hall’s theorem supplies a finite perfect matching \(\sigma\) whose edges all belong to \(G\).
Define the atomless matching associated with \(\sigma\) by
\(\displaystyle \widehat{x}_{t,\sigma(t)}=c,\)
with every other entry zero. Its support is contained in that of \(x\), so support heredity makes it rank-envy-free. The identity
\(\displaystyle R_t(v)=c\left(\rho_t(v)-\frac12\right)\)
then implies that \(\sigma\) is rank-envy-free in the finite marriage instance.
Conversely, any finite rank-envy-free perfect matching produces a feasible atomless matching by assigning mass \(c\) to each of its pairs. To verify envy-freeness, consider any positive entries \(x_{tu},x_{sv}\) with \(v\succ_t u\). Since \(u\) is an opposite-side partner and all same-side types are ranked below it, \(v\) must also lie on the opposite side from \(t\). Consequently, \(s\) lies on the same side as \(t\), and the required mass-rank inequality is exactly the finite rank inequality.
We have proved the equivalence
\(\displaystyle \text{finite rank-envy-free perfect matching exists}\quad\Longleftrightarrow\quad\text{constructed atomless rank-envy-free matching exists}.\)
The reduction proves \(\mathrm{NP}\)-hardness for globally ranked preferences, even with uniform dyadic masses. It therefore also proves unrestricted hardness.
The following characterization applies to arbitrary preferences and arbitrary input masses.
Let \(\succeq_t\) denote the reflexive closure of \(\succ_t\). Choose a vector \(w=(w_t)_{t\in T}\), interpreted as a lower bound on each type’s partner quality. For every \(v\), define
\(\displaystyle p_v(w)=\min\{R_t(v):v\succ_t w_t\},\)
where the minimum of the empty set is \(+\infty\).
Construct an undirected graph \(G_w\), allowing loops. Include the pair \(\{s,v\}\) precisely when all four conditions hold:
\(\displaystyle v\succeq_s w_s,\qquad s\succeq_v w_v,\qquad R_s(v)\leq p_v(w),\qquad R_v(s)\leq p_s(w).\)
Characterization. A rank-envy-free matching exists if and only if, for some \(w\), a matching satisfying the mass equations exists with support contained in \(G_w\).
Proof of necessity. Given a rank-envy-free matching \(x\), choose \(w_t\) as the least preferred type receiving positive mass from row \(t\). Such a type exists because \(\mu_t>0\).
Every positive pair satisfies the two partner-quality conditions. If \(x_{sv}>0\) and \(v\succ_t w_t\), then \(x_{t,w_t}>0\), so rank-envy-freeness gives \(R_s(v)\leq R_t(v)\). Taking the minimum over all such \(t\) gives \(R_s(v)\leq p_v(w)\). Applying the same argument to the reversed positive entry gives \(R_v(s)\leq p_s(w)\). Thus the support lies in \(G_w\).
Proof of sufficiency. Suppose \(x\) is supported on \(G_w\). Consider positive entries \(x_{tu},x_{sv}\) with \(v\succ_t u\). The allowed-pair conditions give \(u\succeq_t w_t\), so \(v\succ_t w_t\). Therefore \(t\) occurs in the minimum defining \(p_v(w)\), and
\(\displaystyle R_s(v)\leq p_v(w)\leq R_t(v).\)
This is the required rank-envy-free inequality. \(\square\)
Create left and right copies of \(T\), together with a source and sink.
A flow of value \(1\) yields a nonnegative matrix \(y\) with both row and column sums equal to the prescribed masses. Because the allowed relation is symmetric,
\(\displaystyle x=\frac{y+y^{\mathsf T}}{2}\)
is supported on \(G_w\), is symmetric, and has the prescribed row sums. Conversely, a matching supported on \(G_w\) immediately supplies a flow of value \(1\).
Thus maximum flow decides feasibility for a chosen vector. This argument also handles loops, which correspond to arcs between the two copies of the same type.
The vector \(w\) requires only \(O(\tau\log m)\) bits. Guessing it and performing this polynomial-time check proves membership in \(\mathrm{NP}\), despite the original formulation permitting real matching entries.
Write each mass as \(\mu_t=a_t/b_t\), and take the common denominator
\(\displaystyle D=\prod_{t\in T}b_t.\)
Its bit length is \(O(L)\). Computing \(D\), the scaled masses \(M_t=D\mu_t\), and all rank numerators takes \(O(\tau L^2+\tau mL)\) bit operations using elementary arithmetic. Rank comparisons are exact integer comparisons because
\(\displaystyle 2D R_t(v)=2\sum_{z\succ_t v}M_z+M_v.\)
For a fixed \(w\), computing its thresholds and allowed graph takes \(O(\tau mL)\) bit operations.
Scale flow capacities by \(D\). The resulting network has \(O(\tau)\) vertices, \(O(\tau m)\) arcs, and capacities with \(O(L)\) bits. Dinic’s maximum-flow algorithm uses \(O(V^2E)\) arithmetic operations, giving \(O(\tau^3mL)\) bit operations here. [Dinitz’s account of the algorithm](https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf)
Consequently:
These bounds apply to both preference classes. Together with the reduction, they establish \(\mathrm{NP}\)-completeness for both; polynomial-time solvability would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves both requested complexity questions. The argument establishes NP-completeness for unrestricted preferences and for globally ranked preferences, including instances with equal dyadic masses. I found no major or minor mathematical issues.
The prover needs hardness for marriage instances with strict complete opposite-side preferences and globally ranked pairs, rather than merely hardness for roommate instances.
The cited paper supports this use: Theorem 2 establishes hardness under globally ranked preferences, and footnote 1 on printed page 496 explicitly states that the reduction also holds in the marriage setting by separating lowercase and uppercase agents. The paper’s concluding discussion repeats the marriage extension. Thus the marriage restriction is supported by the citation. [Coutance, Maddila and Wilczynski](https://anaellewilczynski.pages.centralesupelec.fr/website/articles/ecai23rankenvyfreeness.pdf)
The finite envy condition is stated with the correct inequality direction. When \(t\) prefers the partner assigned to \(s\), justified envy occurs precisely when \(t\) ranks that partner strictly better than \(s\) does. Equality therefore permits no justified envy, consistently with USER_TASK.
Recovering a supplied global order by topological sorting is valid. Consecutive-ranking precedence edges enforce each entire ranking by transitivity, and the existence of a consistent global order guarantees acyclicity.
The constructed order places each designated dummy pair ahead of every other pair incident to either member. Consequently, both dummy agents rank their designated partners first.
The uniqueness assertion used to force a dummy pair is also correct: original agents have original partners above every dummy, and other dummy agents rank their own designated partners first. If \(a_i\) does not receive \(b_i\), the agent receiving \(b_i\) therefore ranks \(b_i\) below first place. This creates the stated strict rank envy.
Once the forced dummy pairs are removed, original agents’ ordinal positions among original partners are unchanged. Conversely, adjoining those pairs creates no new envy: dummy agents receive first choices, and original agents prefer their assigned original partners to all dummy partners.
Taking the least power of two at least as large as the original side size adds only linearly many agents. Padding therefore remains polynomial. The case where no padding is needed is covered.
There are \(2n\) positive-mass types, each with mass \(c=1/(2n)\). Their masses sum to one and are dyadic because the padded \(n\) is a power of two.
Appending all within-side pairs, including repeated-type pairs, to the cross-side global order produces a strict order on every required unordered type pair. Defining rankings from that order ensures the required consistency condition.
Every opposite-side type precedes every same-side type. Hence an opposite-side partner in finite ordinal position \(\rho_t(v)\) has exactly \(\rho_t(v)-1\) types preceding it. The claimed identity
\(R_t(v)=c(\rho_t(v)-1/2)\)
is correct and preserves both strict comparisons and equality.
The stated polynomial construction size is valid.
The quantities \(D_A\) and \(D_B\) sum matrix entries over their respective sides. This agrees with the row-mass convention: off-diagonal within-side entries appear twice across the side’s rows, while diagonal entries appear once.
Symmetry makes the total cross-side contribution equal on both sides. Summing the row equations therefore gives
\(D_A+C=1/2\) and \(D_B+C=1/2\),
so \(D_A=D_B\).
If either is positive, nonnegativity supplies the two positive entries used in the proof. The desired type \(v\) is among the first \(n\) positions for \(t\), but after those positions for \(s\). Thus the bounds
\(R_t(v)\leq c(n-1/2)<c(n+1/2)\leq R_s(v)\)
are correct.
These entries violate exactly the quantified condition in USER_TASK. The argument remains valid if either positive entry is diagonal. Consequently, every within-side entry vanishes.
After within-side mass is excluded, dividing cross-side entries by \(c\) gives a nonnegative matrix with every row and column summing to one.
For each subset \(U\subseteq A\), all mass leaving its rows goes to \(N(U)\). The displayed calculation consequently proves \(|U|\leq |N(U)|\). The support graph is finite and bipartite with equally sized sides, so the stated application of Hall’s theorem is justified.
Support heredity is correct because the envy condition depends only on which entries are positive, together with the fixed rankings and masses. Selecting a perfect matching contained in the original support therefore preserves rank-envy-freeness when its edges are assigned mass \(c\).
The finite-to-atomless direction also checks all possible envy tests. A desired partner preferred to an assigned opposite-side partner must itself be opposite-side. Its recipient is therefore on the same side as the potentially envious type, and the mass-rank comparison is precisely the finite ordinal comparison.
Both directions of the reduction are established. Hardness for globally ranked inputs consequently implies hardness for unrestricted inputs.
The choices \(w_t\) are partner types in \(T\), as is implicit in the ranking comparisons and subsequent enumeration.
In necessity, positivity of \(\mu_t\) guarantees a positive entry in every row, so a least preferred supported partner exists. Every positive pair satisfies both quality conditions.
Whenever \(v\succ_t w_t\), the entry \(x_{t,w_t}\) is positive. Applying rank-envy-freeness against a positive entry \(x_{sv}\) gives the required bound against \(R_t(v)\). Taking the minimum proves the threshold condition. Symmetry supplies the reversed positive entry needed for the other threshold condition.
In sufficiency, \(v\succ_t u\) and \(u\succeq_t w_t\) imply \(v\succ_t w_t\). Thus \(t\) belongs to the threshold’s minimizing set, and the displayed inequality proves the required envy condition.
Empty minimizing sets, equality of ranks, and loops are handled correctly. No equality-versus-strictness error occurs.
The source capacities sum to one, as do the sink capacities. A flow of value one therefore saturates every such arc and gives exactly the prescribed row and column sums.
The allowed relation is symmetric by its definition. Hence transposing the flow matrix preserves allowed support, and averaging it with its transpose produces a symmetric matrix with the required row sums. Conversely, a feasible symmetric matrix supplies the stated flow.
Loops correspond to ordinary arcs between the two copies of the same type; their capacity and mass conventions are correct.
The guessed vector has polynomial encoding length, and its feasibility is checked by exact rational maximum flow. No certificate containing arbitrary real numbers is needed. This establishes membership in NP for both preference classes.
The product denominator \(D\) has \(O(L)\) bits. Every scaled mass is integral, and the stated formula for \(2DR_t(v)\) is exact. Scaled masses, rank numerators, and relevant sums have \(O(L)\) bits.
The elementary-arithmetic preprocessing bound \(O(\tau L^2+\tau mL)\) is sufficient. For a fixed vector, threshold and graph construction take \(O(\tau mL)\) bit operations.
The flow network has \(O(\tau)\) vertices and \(O(\tau m)\) arcs. Applying the cited general Dinic bound \(O(V^2E)\), with \(O(L)\)-bit capacity arithmetic, gives the claimed \(O(\tau^3mL)\) bit bound. The network satisfies the finite directed capacitated-network requirements. [Dinitz’s account](https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf)
There are \(m^\tau\) vectors. The resulting deterministic bound
\(O(\tau L^2+m^\tau\tau^3mL)\)
follows, and substituting \(m=\tau\) correctly yields
\(O(\tau L^2+\tau^{\tau+4}L)\).
The singleton support case is also covered by the characterization and loop-enabled flow construction.
No additional lemma, correction, or clarification is needed to make the argument verifiable.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.