Answer: \(\mathrm{NP\text{-}complete}\)
Theorem 3 (EFX+PO when some agent has a top-ranked good) — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven a lexicographic mixed instance where some agent’s top-ranked item is a good, an EFX+PO allocation always exists and can be com- puted in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete lexicographic agent types \(T\), rational masses \(\mu_t\), recurring item classes \(K\) with rational per-capita supplies \(\beta_k\), and type-specific good/chore classifications and importance orders, under the promise that some positive-mass type has a good as its top-ranked class, output a census \(z_{t,B}\ge 0\) over integral bundles \(B\in\mathbb{Z}_{\ge 0}^{K}\) satisfying \(\sum_B z_{t,B}=\mu_t\) and \(\sum_{t,B}z_{t,B}B_k=\beta_k\). Require that every type receiving \(B\) satisfies EFX against every supported bundle \(D\), after deleting any relevant good copy from \(D\) or any relevant chore copy from \(B\), and that no feasible census admits a type-preserving mass coupling that weakly improves every agent and strictly improves positive mass.
All kinds in \(M\) are chores. Each type \(t\in T\) has a strict importance order over \(M\). For distinct bundles \(B,B'\subseteq M\), let \(j\) be their most important differing chore for \(t\); then \(B\succ_t B'\) iff \(j\in B'\), and \(\succeq_t\) is its weak extension.
A mass allocation is numbers \(x_{t,B}\ge 0\) such that \(\sum_B x_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t,B:j\in B}x_{t,B}=s_j\) for every \(j\in M\). It is envy-free if \(x_{t,B}>0\) and \(x_{u,B'}>0\) imply \(B\succeq_t B'\).
Is deciding whether an envy-free mass allocation exists in \(P\), or is it NP-hard?
For a finite list of agents and indivisible chores with lexicographic preferences, deciding whether a complete envy-free allocation exists is NP-complete. This discrete result does not consider rational type masses or per-capita supplies.
Assume that \(T\) and \(M\) are finite, the importance orders are given explicitly, and all masses \(\mu_t\) and supplies \(s_j\) are binary-encoded rationals. Then deciding whether an envy-free mass allocation exists is \(\mathrm{NP\text{-}complete}\). In particular, it is \(\mathrm{NP\text{-}hard}\).
Types with \(\mu_t=0\) can be deleted, so below every type has positive mass.
In any envy-free mass allocation, each type \(t\) has exactly one bundle \(B_t\) with positive mass. Consequently, \(x_{t,B_t}=\mu_t\).
Lexicographic preferences induced by a strict importance order are themselves strict over distinct bundles. Indeed, for distinct \(B,C\), their most important differing chore belongs to exactly one of them, so exactly one of \(B\succ_t C\) or \(C\succ_t B\) holds. Hence the weak order \(\succeq_t\) is antisymmetric.
Suppose that \(x_{t,B}>0\) and \(x_{t,C}>0\). Applying envy-freeness with both supported bundles evaluated by type \(t\) gives \(B\succeq_t C\). Interchanging \(B\) and \(C\) gives \(C\succeq_t B\). Antisymmetry therefore implies \(B=C\).
Because \(\sum_B x_{t,B}=\mu_t>0\), exactly one such bundle exists, and its mass is \(\mu_t\). ∎
An envy-free mass allocation exists if and only if there are bundles \(B_t\subseteq M\), one for every positive-mass type, satisfying both:
Necessity follows from Lemma 1 and the supply and envy-freeness constraints.
Conversely, given such bundles, define \(x_{t,B_t}=\mu_t\) and \(x_{t,B}=0\) for \(B\ne B_t\). Condition 1 gives supply feasibility, while condition 2 gives envy-freeness. ∎
Thus the apparently fractional problem is not a fractional relaxation: strict within-type envy-freeness purifies every type onto a single bundle.
A certificate consists of the incidence vector of \(B_t\) for every type \(t\), using \(O(|T||M|)\) bits.
For every chore \(j\), one can check the rational equality \(s_j=\sum_{t:j\in B_t}\mu_t\) using exact arithmetic. For every ordered pair \(t,u\), one scans type \(t\)'s importance order until finding the first chore in \(B_t\mathbin{\triangle}B_u\). If no such chore exists, the bundles are equal. Otherwise, \(B_t\succeq_t B_u\) holds precisely when that chore belongs to \(B_u\).
These checks take polynomial time. Corollary 2 proves that this certificate characterization is exact, so the problem belongs to \(\mathrm{NP}\).
We reduce from the stated \(\mathrm{NP\text{-}complete}\) problem of deciding whether a finite collection of agents and indivisible chores admits a complete envy-free allocation under lexicographic chore preferences.
Let such an instance have agents \(N=\{1,\ldots,n\}\), chores \(M\), and importance order \(\succ_i\) for every agent \(i\). Construct a mass instance as follows:
The construction is polynomial-time, and all masses and supplies have polynomial binary encoding length.
Suppose the discrete instance has a complete envy-free allocation \((B_i)_{i\in N}\). Define \(x_{t_i,B_i}=1/n\), with every other mass variable zero.
Since the discrete allocation is complete, every chore occurs in exactly one \(B_i\). Therefore its total allocated mass is exactly \(1/n=s_j\). Moreover, discrete envy-freeness states that \(B_i\succeq_i B_k\) for all \(i,k\), which is exactly the required mass envy-freeness. Hence the mass instance is feasible.
Suppose the mass instance has an envy-free allocation. By Lemma 1, every type \(t_i\) is assigned its entire mass \(1/n\) to one bundle \(B_i\).
For any chore \(j\), the supply equality gives
\(\displaystyle \frac1n=\sum_{i:j\in B_i}\frac1n=\frac{|\{i:j\in B_i\}|}{n}\).
Therefore \(|\{i:j\in B_i\}|=1\). Thus every chore belongs to exactly one bundle, so \((B_i)_{i\in N}\) is a complete discrete allocation.
Mass envy-freeness gives \(B_i\succeq_i B_k\) for every \(i,k\). Hence this discrete allocation is envy-free.
The two instances are therefore equivalent.
If the terminology “type” requires distinct preference orders, agents with the same order can instead be aggregated. For an equivalence class containing \(k_t\) agents, set \(\mu_t=k_t/n\). In any discrete envy-free allocation, agents with the same strict preference order must receive identical bundles, because each must weakly prefer its bundle to the other's. The same forward and reverse arguments then apply.
The reduction is exact even when total type mass is normalized to \(1\) and every chore has per-capita supply \(1/n\). Together with membership in \(\mathrm{NP}\), this proves that envy-free mass-allocation existence is \(\mathrm{NP\text{-}complete}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly establishes NP-completeness under the stated finite, explicit, binary-rational input model. The reduction matches the discrete problem supplied in USER_TASK, and the membership argument is polynomial-time. No logical gaps affecting the conclusion were found.
The claim that lexicographic preferences are strict over distinct bundles is correct. For distinct \(B,C\), their highest-priority differing chore belongs to exactly one bundle, so exactly one of \(B\succ_t C\) and \(C\succ_t B\) holds.
The use of envy-freeness with \(u=t\) is legitimate. If both \(B\) and \(C\) have positive mass for type \(t\), the definition yields both \(B\succeq_t C\) and \(C\succeq_t B\). Antisymmetry then gives \(B=C\). Positive total mass consequently forces exactly one supported bundle of mass \(\mu_t\).
Corollary 2 follows in both directions:
The pairwise condition \(B_t\succeq_t B_u\) has the correct orientation for the definition of envy-freeness.
The certificate has \(|T||M|\) incidence bits.
Supply equalities between binary-encoded rationals can be checked exactly in polynomial time. Lexicographic bundle comparison is also polynomial: scanning the explicitly supplied importance order locates the most important chore in the symmetric difference. For chores, the stated direction is correct: \(B_t\) is preferred to \(B_u\) exactly when that differing chore lies in \(B_u\).
Thus the certificate is polynomially sized and polynomially verifiable.
Assigning one mass type of mass \(1/n\) to each discrete agent and setting every supply to \(1/n\) is polynomial-time. The rational \(1/n\) has polynomial binary encoding length.
The constructed preferences exactly reproduce the source agents' preferences.
A complete discrete allocation places every chore in exactly one bundle. Therefore each chore receives exactly one contribution of \(1/n\), meeting its supply.
Discrete envy-freeness is precisely the pairwise mass envy condition once each type is concentrated on its assigned bundle.
Lemma 1 correctly forces every type onto one bundle. For each chore \(j\), the equality
\[ \frac{1}{n}=\frac{|\{i:j\in B_i\}|}{n} \]
implies that exactly one bundle contains \(j\). Hence the bundles are disjoint and complete, as required by the discrete source problem.
Mass envy-freeness gives the required discrete envy inequalities for every ordered pair of agents.
The primary reduction does not require types to have distinct preference orders. The optional aggregation discussion is also substantively correct: agents with the same strict preference order must receive equal bundles in an envy-free discrete allocation. If multiple such agents form one class, disjointness forces their common bundle to be empty. Conversely, a mass type of weight \(k_t/n>1/n\) cannot contain any chore whose supply is only \(1/n\). Although this last calculation is only implicit, the aggregation paragraph is optional and not needed for the stated model or main reduction.
The argument proves membership in NP and supplies a valid many-one reduction from the NP-complete discrete problem stated in USER_TASK. The claimed NP-completeness result is therefore established.
⟨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.