Answer: \(\mathrm P\): every valid instance is feasible.
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any instance with ordinal preferences, Algorithm 3 computes an allocation that is simultaneously p-EFX, p-MMS and balanced in polynomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(T\), item categories \(G\), rational type masses \(\mu\), per-capita supply \(\sigma\in\mathbb Q_{\ge0}^{G}\), and weak ordinal rankings \(\succeq_t\), find finite-support masses \(x_{t,b}\ge0\) over integer bundles \(b\in\mathbb Z_{\ge0}^{G}\) and additive witnesses \(u_t\) consistent with \(\succeq_t\) such that \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b=\sigma\), every used bundle has size \(\lfloor\bar m\rfloor\) or \(\lceil\bar m\rceil\) for \(\bar m=\sum_{g\in G}\sigma_g\), every used bundle \(b\) of type \(t\) satisfies \(u_t\cdot b\ge u_t\cdot(b-e_g)\) for every item \(g\) appearing in any used bundle \(b'\), and \(u_t\cdot b\ge\lambda_t\), where \(\lambda_t=\sup\{\min_{b'':y_{b''}>0}u_t\cdot b'':y\ge0,\sum_{b''}y_{b''}=1,\sum_{b''}y_{b''}b''=\sigma,\ y\text{ has finite support}\}\).
Let \(G\) be a nonempty set of \(m\) item categories. A society is given by its support: the list of its \(\tau\) types \(T\) with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not possible rankings. Each type has a weak order \(\succeq_t\) on \(G\). Supply is \(\sigma\in\mathbb Q_{\ge0}^{G}\) per unit society mass. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Bundles are vectors \(b\in\mathbb Z_{\ge0}^{G}\), allowing repeated items of a category. An additive witness is \(u_t\in\mathbb R_{\ge0}^{G}\) with \(u_{t,g}\ge u_{t,h}\iff g\succeq_t h\); thus ties require equal values and strict preferences require strict inequalities. The same witness must satisfy both fairness conditions below for every bundle used by its type.
An allocation consists of nonnegative real masses \(x_{t,b}\) with finite support, satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b=\sigma\). Write \(S=\{b:\sum_t x_{t,b}>0\}\) and \(\bar m=\sum_g\sigma_g\). Balancedness requires \(\sum_gb_g\in\{\lfloor\bar m\rfloor,\lceil\bar m\rceil\}\) for every \(b\in S\).
Possible EFX requires \(u_t\cdot b\ge u_t\cdot(b'-e_g)\) whenever \(x_{t,b}>0\), \(b'\in S\), and \(b'_g>0\), where \(e_g\) is the unit vector of category \(g\).
Define \(\lambda_t(u_t,\sigma)=\sup_y\min_{c:y_c>0}u_t\cdot c\), where \(y\) ranges over all finitely supported nonnegative real distributions on \(\mathbb Z_{\ge0}^{G}\) satisfying \(\sum_c y_c=1\) and \(\sum_c y_cc=\sigma\). These benchmark distributions need not be balanced. Possible MMS requires \(u_t\cdot b\ge\lambda_t(u_t,\sigma)\) whenever \(x_{t,b}>0\).
Is deciding whether a balanced allocation and common additive witnesses satisfying possible EFX and possible MMS exist in \(\mathrm P\), or is it NP-hard?
For finitely many agents and individually listed indivisible goods, balanced possible-EFX and possible-MMS allocations always exist and are computable in polynomial time, using the same valuation profile for both conditions ([Aziz, Li, Xing and Zhou](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p197.pdf)). No result settling the exact distributional problem above was identified in the literature search.
Every valid instance is feasible. Moreover, the allocation masses and the common witnesses can be chosen rational. Thus the decision problem belongs to \(\mathrm P\): on the promised input domain, reading the input and returning YES takes \(O(L)\) time.
The proof uses finite replication only to establish existence. It does not establish a polynomial-time construction of an allocation from the compressed input.
Write \(|b|=\sum_{g\in G}b_g\), \(q=\lfloor\bar m\rfloor\), and \(r=\bar m-q\), so \(0\le r<1\).
We use the following prescribed-valuation form of the finite-agent result.
Let \(H\) be a finite set of individually listed goods. For each agent \(i\), choose positive values \(v_i\), equal on each indifference class, such that
\(v_i(h)>\sum_{h':\,h\succ_i h'}v_i(h')\)
for every good \(h\). Choose \(W_i>\sum_{h\in H}v_i(h)\), and define \(U_i(h)=W_i+v_i(h)\). Then a balanced allocation exists that is simultaneously EFX and MMS for these prescribed valuations \(U_i\).
This is the form established by Lemmas 10–11 and Theorem 2 in Section 4 of [Aziz, Li, Xing and Zhou](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p197.pdf). Below, all its hypotheses are checked explicitly.
Here \(\bar m<1\). Define a distribution by
\(y_0=1-\bar m,\qquad y_{e_g}=\sigma_g.\)
It has total mass one and mean \(\sigma\). Give every type this distribution, setting \(x_{t,b}=\mu_t y_b\), and choose any rational positive witness representing its weak order.
Every used bundle is empty or a singleton, so balancedness and EFX hold.
Furthermore, every admissible benchmark distribution must give positive mass to the empty bundle. Otherwise every supported bundle would have at least one item, contradicting its expected size \(\bar m<1\). Nonnegative utilities therefore imply \(\lambda_t(u_t,\sigma)=0\). MMS holds as well.
Henceforth assume \(q\ge1\).
For type \(t\), write its indifference classes, from best to worst, as \(C_t^1,\ldots,C_t^{k_t}\). Let \(j_t(g)\) denote the class containing \(g\). Set
\(B=q+2,\qquad \varepsilon=\dfrac{1-r}{2(q+1)},\qquad u_{t,g}=1+\varepsilon B^{\,1-j_t(g)}.\)
These are positive rational witnesses representing the weak orders exactly. They satisfy
\(1<u_{t,g}\le1+\varepsilon,\qquad q\varepsilon<1.\)
Consequently,
\(u_t\cdot\sigma \le(q+r)(1+\varepsilon) <q+r+(q+1)\varepsilon =q+\dfrac{1+r}{2} <q+1.\)
Every bundle of size at most \(q-1\) has utility less than \(q\), since
\(u_t\cdot b\le(q-1)(1+\varepsilon)<q.\)
Every bundle of size at least \(q+1\) has utility at least \(q+1\).
For bundles of equal size \(q\), these witnesses compare their class-count vectors lexicographically. To verify this, suppose the first differing class is \(j\), with \(b\) having more items there than \(c\). Its advantage at that class contributes at least \(\varepsilon B^{1-j}\). The total adverse contribution from all lower classes is at most \(q\varepsilon B^{-j}\). Hence
\(u_t\cdot b-u_t\cdot c \ge\varepsilon B^{1-j}(1-q/B)>0.\)
Equal class-count vectors have equal utility.
Lemma. Suppose a finitely supported distribution \(y\) has mean \(\sigma\) and uses only bundles of size at least \(q\). It can be replaced by a distribution with the same mean, supported on bundles of sizes \(q\) and \(q+1\), whose bundles of size \(q\) all belonged to the original support.
Proof. Let \(s\) be the total probability of bundles larger than \(q\), and let \(a=1-s\). Since the expected size is \(q+r\),
\(q+r\ge q(1-s)+(q+1)s=q+s.\)
Thus \(s\le r<1\), and \(a>0\).
Replace each bundle \(c\) of size \(k\ge q+1\), with its original mass \(y_c\), by pure bundles \((q+1)e_g\), assigning mass \(y_c c_g/k\) to category \(g\). This preserves its probability mass and decreases its contribution to the mean coordinatewise. Let the total decrease be \(d\). Then
\(d=\sum_{|c|\ge q+1}y_c\left(1-\dfrac{q+1}{|c|}\right)c\ge0,\qquad |d|=r-s.\)
Write \(D=|d|=r-s\). Because \(D\le a\), replace the mass \(y_b\) of each original size-\(q\) bundle \(b\) by:
These masses sum to \(y_b\). Summing over the original size-\(q\) bundles restores exactly the missing mean vector \(d\). All resulting bundles have size \(q\) or \(q+1\), and the only size-\(q\) bundles are original ones. The support remains finite. \(\square\)
Fix a type \(t\) and its witness \(u_t\).
First, a balanced distribution with mean \(\sigma\) exists. Choose category \(g\) with probability \(\sigma_g/\bar m\), and independently choose bundle size \(q\) with probability \(1-r\), or \(q+1\) with probability \(r\); give that many copies of the chosen category. Its mean is
\(\bigl(q(1-r)+(q+1)r\bigr)\dfrac{\sigma}{\bar m}=\sigma.\)
Every bundle in this distribution has utility at least \(q\). The average-utility bound therefore gives
\(q\le\lambda_t(u_t,\sigma)\le u_t\cdot\sigma<q+1.\)
Now consider any admissible benchmark distribution whose minimum utility is at least \(q\). It cannot contain a bundle of size below \(q\). Apply the balancedization lemma. Every resulting size-\(q\) bundle was originally supported, while every resulting size-\(q+1\) bundle has utility at least \(q+1\), exceeding the original minimum, which is bounded by \(u_t\cdot\sigma<q+1\). Thus balancedization does not decrease minimum utility.
It follows that the unrestricted benchmark equals the benchmark restricted to sizes \(q\) and \(q+1\). Indeed, distributions with minimum utility below \(q\) cannot improve the supremum, and every remaining distribution can be balancedized.
There are only finitely many bundles of these two sizes. Therefore the possible minimum utilities of balanced distributions lie in a finite set, and their supremum is attained.
An optimizer can be chosen rational. To see this, take the support of an optimizer and consider the finite polytope defined by nonnegative probabilities, total probability one, and mean \(\sigma\), on that support. It is nonempty and bounded, with rational defining coefficients. A vertex has rational coordinates. Its support is contained in the original support, so its minimum utility cannot decrease; by optimality, it remains exactly the benchmark.
Choose such a rational balanced optimizer \(y^t\). Balancedness and its mean imply
\(\sum_{|c|=q}y^t_c=1-r>0.\)
Since every size-\(q+1\) bundle has utility above the benchmark, some supported size-\(q\) bundle \(b_t^\star\) satisfies
\(\lambda_t(u_t,\sigma)=u_t\cdot b_t^\star.\)
Every supported size-\(q\) bundle is consequently lexicographically at least as good as \(b_t^\star\), in type \(t\)'s class-count order.
Choose a positive integer \(n\) clearing the denominators of all \(\mu_t\), all \(\sigma_g\), and all positive probabilities in all distributions \(y^t\).
Construct a finite instance with:
There are \(n\) agents and \(M=n\bar m\) goods. Each agent ranks copies according to its type's category order, tying copies whenever their categories are tied.
For each type \(t\), the distribution \(y^t\) becomes a partition of these goods into \(n\) bundles: use exactly \(ny^t_c\) copies of bundle \(c\). These are integer numbers of bundles, and their aggregate category counts are exactly \(n\sigma\). Thus each such partition is a valid finite MMS benchmark partition.
Let \(C=M+1\). Prescribe, for every agent of type \(t\),
\(v_{t,g}=C^{\,k_t-j_t(g)},\qquad W_t=M C^{k_t-1}+1,\qquad U_{t,g}=W_t+v_{t,g}.\)
These satisfy the finite theorem's hypotheses. Values are positive and equal precisely on the prescribed indifference classes. For a good in class \(j<k_t\), the sum of values of all strictly worse goods is at most
\(M C^{k_t-j-1}<C^{k_t-j}=v_{t,g}.\)
For the last class, that sum is zero. Also,
\(\sum_{h\in H}v_t(h)\le M C^{k_t-1}<W_t.\)
Two consequences will be used:
Both compare class-count vectors lexicographically. For \(U_t\), the common term \(qW_t\) cancels, and \(C=M+1>q\), since \(M\ge q\).
For a feasible bundle \(c\), its total \(v_t\)-value is below \(W_t\). Thus a size-\(q\) bundle has utility below \((q+1)W_t\), while a size-\(q+1\) bundle has utility at least \((q+1)W_t\).
Apply the finite theorem to obtain a balanced EFX and MMS allocation for these prescribed \(U_t\). Its bundles have sizes \(q\) and \(q+1\), because the average size is \(M/n=q+r\).
Aggregate this allocation by defining
\(x_{t,b}=\dfrac{\#\{\text{type-}t\text{ agents receiving category-count vector }b\}}{n}.\)
These rational masses have finite support, satisfy the required type masses and supply equations, and are balanced. It remains to verify both fairness conditions using the fixed witnesses \(u_t\).
Fix a type \(t\). In the finite benchmark partition obtained from \(y^t\), every size-\(q\) bundle is lexicographically at least as good as \(b_t^\star\), and hence has \(U_t\)-utility at least \(U_t\cdot b_t^\star\). Every size-\(q+1\) bundle has strictly greater \(U_t\)-utility than \(b_t^\star\).
Therefore the finite MMS value for \(U_t\) is at least \(U_t\cdot b_t^\star\). Finite MMS fairness implies that every allocated bundle \(b\) of type \(t\) satisfies
\(U_t\cdot b\ge U_t\cdot b_t^\star.\)
If \(|b|=q\), the agreement of comparisons on size-\(q\) bundles yields
\(u_t\cdot b\ge u_t\cdot b_t^\star=\lambda_t(u_t,\sigma).\)
If \(|b|=q+1\), then
\(u_t\cdot b\ge q+1>\lambda_t(u_t,\sigma).\)
Thus exact distributional MMS holds.
Let \(b\) be used by type \(t\), let \(b'\) be any used bundle, and suppose \(b'_g>0\). Corresponding finite agents and a copy of category \(g\) give, by finite EFX,
\(U_t\cdot b\ge U_t\cdot(b'-e_g).\)
If \(|b|=q\) and \(|b'|=q+1\), both compared bundles have size \(q\). Agreement of comparisons therefore gives
\(u_t\cdot b\ge u_t\cdot(b'-e_g).\)
In every other case, put \(k=|b'-e_g|\). Then \(k\le q\) and \(|b|\ge k+1\). The near-equal bounds imply
\(u_t\cdot b\ge |b|\ge k+1>k(1+\varepsilon)\ge u_t\cdot(b'-e_g),\)
where the strict inequality follows from \(k\varepsilon\le q\varepsilon<1\).
Hence EFX also holds, using the very same witness \(u_t\) already used for MMS. This completes the existence proof and the decision classification.
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the stated decision problem: every valid instance is feasible, with rational allocation masses and rational common witnesses. I found no major or minor mathematical issues. The polynomial-time conclusion concerns decision on the promised input domain; the output correctly makes no polynomial-time construction claim.
This is the critical external dependency. An existence theorem allowing unspecified witnesses would not suffice for Section 6, which prescribes the valuations before obtaining the allocation.
I checked the cited paper. Section 4.1, equation (7), permits valuations consisting of a common additive constant plus positive lexicographic values satisfying the stated dominance inequality. Lemmas 10 and 11 establish EFX and MMS for those valuations, and Theorem 2 establishes balancedness of the same allocation. Thus the prescribed-valuation formulation in Section 2 is supported by the source. [Aziz, Li, Xing and Zhou, Section 4](https://www.southampton.ac.uk/~eg/AAMAS2023/pdfs/p197.pdf).
The proposed distribution has nonnegative masses totaling
\[
1-\bar m+\sum_g\sigma_g=1,
\]
and its mean is \(\sigma\). Multiplication by \(\mu_t\) gives the correct type masses and aggregate supply.
Its supported bundles are empty or singleton bundles, so balancedness holds. Removing an item from any nonempty supported bundle leaves the empty bundle, making all required EFX inequalities valid for nonnegative witnesses.
Every benchmark distribution must put positive mass on the empty bundle: otherwise its expected bundle size would be at least one. Consequently every benchmark minimum is zero, and \(\lambda_t=0\).
This also covers \(\bar m=0\), when the empty bundle is the entire support. Positive rational witnesses representing any finite weak order exist, including the all-tied order.
For \(q\ge1\), the definitions give \(B>1\) and \(\varepsilon>0\). Equal classes receive equal values, and successive strict classes receive strictly decreasing values. Hence the witnesses represent the weak orders exactly, including categories with zero supply.
The bounds \(1<u_{t,g}\le1+\varepsilon\) and \(q\varepsilon<1\) are valid. The average-utility estimate is also correct: its strict step uses \(q+r<q+1\), together with \(\varepsilon>0\).
The resulting separation by bundle size is sound:
The lexicographic comparison calculation for size-\(q\) bundles is valid. At the first differing class, the advantage is at least one class-value increment. The adverse lower-class contribution is bounded by \(q\) times the next class-value increment. Since \(B=q+2>q\), the displayed lower bound is strictly positive. Equal class-count vectors give equal utility.
The expected-size inequality correctly yields \(s\le r<1\), so \(a=1-s>0\). There is no division-by-zero issue.
Replacing a size-\(k\) bundle by the indicated pure bundles preserves its probability mass. Its new mean contribution is \((q+1)/k\) times its original contribution, so the decrease is coordinatewise nonnegative.
Summing the decreases gives
\[
|d|=\sum_{|c|\ge q+1}y_c\bigl(|c|-(q+1)\bigr)=r-s.
\]
Thus \(D=r-s\ge0\), and \(D\le a\) follows from \(r<1\).
The second replacement has nonnegative coefficients summing to the original mass. Its aggregate mean increase is exactly \(d\). Consequently the original mean is restored.
Only original size-\(q\) bundles remain at size \(q\); all other resulting bundles have size \(q+1\). Finite support is preserved. When \(r=0\), necessarily \(s=D=0\), so the lemma also handles integral average supply without introducing positive mass on size-\(q+1\) bundles.
The initial balanced distribution is well-defined because \(\bar m\ge1\). Its probabilities sum to one, and the stated mean calculation is correct. Its minimum utility is at least \(q\).
For every admissible distribution, its minimum utility is at most its average utility, which equals \(u_t\cdot\sigma\). Hence
\[
q\le\lambda_t(u_t,\sigma)\le u_t\cdot\sigma<q+1.
\]
Any benchmark distribution with minimum utility at least \(q\) excludes bundles smaller than \(q\). Balancedization retains only original size-\(q\) bundles and introduces larger bundles whose utilities exceed the original minimum. Therefore it cannot decrease that minimum.
Distributions whose minimum is below \(q\) cannot improve on the already available benchmark. This justifies equality of the unrestricted and balanced benchmark suprema; it does not assume attainment prematurely.
There are finitely many integer bundles of sizes \(q\) and \(q+1\). Every achievable balanced minimum is one of their finitely many utility values. The nonempty set of achievable values therefore has an attained maximum.
The rationality argument is valid. The probability polytope on an optimizer’s support is nonempty, bounded, and defined by rational coefficients. A vertex has rational coordinates. Restricting support cannot lower the minimum, and optimality prevents it from increasing beyond the benchmark.
Finally, balancedness implies that size-\(q\) bundles have total probability \(1-r>0\). Since larger bundles have utility above the benchmark, a supported size-\(q\) bundle attains it. The conclusions about \(b_t^\star\) and lexicographic comparisons follow.
A single denominator-clearing integer exists because there are finitely many rational masses, supply coordinates, and optimizer probabilities.
Each positive \(\mu_t\) gives a positive integer number of agents, and their total is \(n\). The goods counts are nonnegative integers.
For each type, the replicated optimizer specifies exactly \(n\) bundles with aggregate category counts \(n\sigma\). These counts permit assignment of the individually listed copies to realize the partition. Different types may use different benchmark partitions, as finite MMS allows.
In particular, every bundle in these partitions is feasible in the finite goods set. This addresses the otherwise relevant distinction between unrestricted distributional bundles and finite-instance bundles.
Here \(M\ge n\ge1\), and \(C=M+1\). The values are positive and respect the replicated weak orders.
For a good in a nonlast class, every strictly worse good has value at most \(C^{k_t-j-1}\). There are at most \(M\) such goods, giving the stated strict dominance inequality. For the last class, the required sum is zero.
The estimate
\[
\sum_{h\in H}v_t(h)\le MC^{k_t-1}<W_t
\]
verifies the remaining hypothesis.
On size-\(q\) bundles, the common \(qW_t\) term cancels, and \(C>q\) ensures the same lexicographic comparisons as \(u_t\).
Every feasible bundle has total residual value below \(W_t\). The claimed strict separation between feasible size-\(q\) and size-\(q+1\) bundles follows. It applies to \(b_t^\star\), which belongs to a replicated benchmark partition.
The finite allocation aggregates to rational masses with the correct type totals and supply. Its balanced sizes are exactly those required by the distributional problem, with only size \(q\) used when \(r=0\).
For MMS, the replicated optimizer partition establishes a finite MMS lower bound of \(U_t\cdot b_t^\star\). Finite MMS fairness then gives that lower bound for every allocated bundle of type \(t\).
For allocated size-\(q\) bundles, agreement of comparisons transfers the inequality to \(u_t\). For allocated size-\(q+1\) bundles, the direct utility bound exceeds the exact distributional benchmark. This holds for every bundle used by the type.
For EFX, each used bundle corresponds to a finite recipient, and each positive category count supplies an actual copy that can be removed. Finite EFX therefore gives the displayed \(U_t\) inequality.
The only case comparing equal sizes is \(|b|=q\), \(|b'|=q+1\); comparison agreement handles it. In all remaining cases, \(|b|\ge |b'-e_g|+1\), and the displayed near-equal-value bound is valid because \(q\varepsilon<1\).
Thus every required EFX inequality holds under the same \(u_t\) already used for MMS.
Universal feasibility makes returning YES correct on every promised valid input. Reading the input and returning YES takes \(O(L)\) time, which is a valid running-time statement in the requested parameters \(m,\tau,L\).
Replication may be large, but it is used only for existence. Neither polynomial output size nor polynomial construction time is needed for this decision conclusion.
No additional clarification or repair is needed.
⟨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.