Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously (aaai25-33477)

Given finitely many complete additive valuation types with rational masses \(\mu\), rational per-capita supplies \(b\) of indivisible good kinds, and fixed \(\epsilon, \delta > 0\), compute a mass assignment \(\lambda_{t,B}\) over integral whole-bundle configurations \(B\), respecting type masses and item capacities, such that every occupied bundle gives type \(t\) at least \((2/3 - \epsilon)\) times its asymptotic MMS density and every occupied pair satisfies \((1 - \delta)\)-EFX; determine the complexity and finite-replica rounding behavior.

A society is given by its support: \(\tau\) complete additive valuation types with values \(v_{tj}\in\mathbb{Q}_{\geq0}\) for \(m\) good kinds and positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Supplies \(b_j\in\mathbb{Q}_{\geq0}\) are per capita; copies of each kind are identical. Fix \(0<\varepsilon<2/3\) and \(0<\delta<1\).
An admissible replica size \(N\) has integral \(N\mu_t\) and \(Nb_j\). Let \(M_N\) contain \(Nb_j\) copies of kind \(j\), and define the asymptotic MMS benchmark \(s_t=\limsup_{N\to\infty,\ N\text{ admissible}}\operatorname{MMS}^{N}_{v_t}(M_N)\), without further division by \(N\).
A configuration is \(B\in\mathbb{Z}_{\geq0}^{m}\), with \(v_t(B)=\sum_jv_{tj}B_j\). Seek a finitely supported binary-rational assignment \(\lambda_{t,B}\geq0\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B}\lambda_{t,B}B_j\leq b_j\); unallocated goods and empty configurations are allowed.
Whenever \(\lambda_{t,B}>0\), require \(v_t(B)\geq(2/3-\varepsilon)s_t\). For every ordered pair of occupied configurations \((t,B),(u,C)\), require \(v_t(B)\geq(1-\delta)v_t(C-e_j)\) for every \(j\) with \(C_j>0\), including kinds worth zero to \(t\); \(e_j\) is the unit vector.

Is finding such an assignment, or deciding that none exists, polynomial-time in \(m,\tau,L\), or NP-hard, for fixed \(\varepsilon,\delta\)?
Does every feasible rational assignment admit partial allocations in all sufficiently large admissible replicas whose normalized configuration counts converge to it, preserving \((1-\delta)\)-EFX and \((2/3-\varepsilon)\)-MMS relative to each replica's MMS?
For rounding, use convergence in \(\ell_1\) over type–configuration pairs and compressed integer configuration counts; state running times in \(m,\tau,L,\log N\), where \(L\) is the total binary input length, including the supplied assignment when rounding.

For explicitly listed finite agents and goods, partial allocations simultaneously satisfying \((1-\delta)\)-EFX and \((2/3-\varepsilon)\)-MMS are computable in polynomial time for fixed positive constants [Akrami–Rathi](https://arxiv.org/html/2409.01963v2). No result settling exactly this support-encoded mass-assignment and replica-rounding problem was located.

1. Proven results and remaining question

Write
$$ \alpha=\frac23-\varepsilon,\qquad \beta=1-\delta. $$
Thus $0<\alpha<2/3$ and $0<\beta<1$. As in the notes, rational numbers are represented by binary numerators and denominators.

The following results are proved below:

• Existence decision: every valid instance admits a feasible rational assignment. Consequently, deciding existence is polynomial-time.
• General construction: an assignment of polynomial encoding length can be constructed in time $2^{\operatorname{poly}(m,\tau,L)}$. Whether construction is polynomial-time, or admits an appropriate search-hardness result, remains unresolved here.
• Universal rounding is false: for every fixed $\varepsilon,\delta$ in the stated ranges, there is a counterexample with $m=6$ and $\tau=3$. Every type has a positive asymptotic MMS benchmark, every kind is valued positively by some type, and the supplied assignment satisfies all required EFX inequalities strictly. Nevertheless, on infinitely many admissible replicas, every $\beta$-EFX allocation stays a fixed positive $\ell_1$ distance from that assignment.
• Compressed rounding remains polynomial-time on denominator-clearing replicas, and under the resource-slack or coordinatewise-chain hypotheses stated below.

The overall classification is therefore partial: the general search complexity remains open.

2. Benchmark attainment and universal rational existence

For an admissible $N$, let
$$ z_t(N)=\operatorname{MMS}^{N}_{v_t}(M_N), \qquad A_t=\sum_j v_{tj}b_j. $$
Every complete partition into $N$ bundles has average value $A_t$ to type $t$. Hence
$$ 0\leq z_t(N)\leq A_t. $$

Choose a positive integer $q_t$ clearing the denominators of all $v_{tj}$. Every bundle value, and therefore every $z_t(N)$, belongs to
$$ \left\{\frac{k}{q_t}:0\leq k\leq \lfloor q_tA_t\rfloor\right\}. $$
This is a finite set. The set of achieved replica MMS values is nonempty, so it has an achieved maximum, say at an admissible size $N_t$.

Repeating a witnessing partition $k$ times gives a partition at size $kN_t$ with the same minimum value. The achieved maximum therefore occurs at arbitrarily large admissible sizes. Consequently,
$$ s_t=\max_{N\text{ admissible}}z_t(N), \qquad z_t(N)\leq s_t $$
for every admissible $N$.

Let $N_*$ be a common multiple of the finitely many $N_t$. Repeating each witnessing partition shows that
$$ z_t(N_*)=s_t $$
simultaneously for every type.

We now use the following finite-agent theorem: for finitely many agents with additive nonnegative valuations, there exists a partial allocation that is exact EFX and gives every agent at least $2/3$ of her MMS. Here EFX quantifies over every removed good, including goods worth zero to the comparing agent. This is [Akrami–Rathi, Definition 2.2 and Theorem 5.2](https://arxiv.org/html/2409.01963v2).

Apply this theorem to the replica of size $N_*$. Its hypotheses hold because its agents and goods are finite and its valuations are additive and nonnegative. Let $n_{t,B}$ be the resulting configuration counts, including empty configurations when applicable, and set
$$ \lambda_{t,B}=\frac{n_{t,B}}{N_*}. $$
Then
$$ \sum_B\lambda_{t,B}=\mu_t, \qquad \sum_{t,B}\lambda_{t,B}B_j\leq b_j. $$
Every occupied pair satisfies
$$ v_t(B)\geq \frac23s_t\geq\alpha s_t. $$
Exact EFX implies $\beta$-EFX because valuations are nonnegative and $\beta<1$. Aggregation preserves every required ordered-pair comparison. Thus this is a feasible, finitely supported rational assignment.

This proves that the existence decision always answers “yes” on valid inputs. It does not by itself give a polynomial-time construction in the compressed input.

3. A counterexample to unrestricted replica rounding

3.1. Instance and supplied assignment

Fix any permitted $\alpha,\beta$. Choose integers $w,H,h$ such that
$$ w=\left\lfloor\frac{17}{\beta}\right\rfloor+1, \qquad H\geq36, \qquad \beta H>w, $$
and
$$ h\geq2, \qquad w2^{-h}\leq1. $$
These choices are possible because $\beta>0$. Moreover,
$$ 17<\beta w\leq17+\beta<18. $$

Put
$$ \rho=2^{-h}, \qquad \theta=1-2\rho. $$
There are three types, denoted $T,U,Z$, with masses
$$ \mu_T=\theta,\qquad \mu_U=\mu_Z=\rho. $$
There are six kinds, ordered as $g_1,g_2,g_3,g_4,c,d$, with valuations

| Type | $g_1$ | $g_2$ | $g_3$ | $g_4$ | $c$ | $d$ |
|---|---:|---:|---:|---:|---:|---:|
| $T$ | $4$ | $6$ | $7$ | $9$ | $w$ | $0$ |
| $U$ | $4/H$ | $6/H$ | $7/H$ | $9/H$ | $1$ | $0$ |
| $Z$ | $4/H$ | $6/H$ | $7/H$ | $9/H$ | $0$ | $1$ |

The per-capita supplies are
$$ b=\left(\theta,\theta,\frac{\theta}{2}, \frac{\theta}{2},\rho,2\rho\right). $$
All masses and supplies are positive dyadic rationals. Every kind has positive value to some type.

Define configurations
$$ \begin{aligned} P_1&=(0,0,0,2,0,0),\\ P_2&=(0,3,0,0,0,0),\\ P_3&=(1,0,2,0,0,0),\\ P_4&=(3,1,0,0,0,0),\\ C&=(0,0,0,0,1,1),\\ E&=(0,0,0,0,0,1). \end{aligned} $$
The supplied assignment is
$$ \lambda_{T,P_i}=\frac{\theta}{4}\quad(1\leq i\leq4), \qquad \lambda_{U,C}=\rho, \qquad \lambda_{Z,E}=\rho, $$
with every other entry zero.

The first four coordinates of the average of $P_1,\ldots,P_4$ are
$$ \frac14\bigl((0,0,0,2)+(0,3,0,0) +(1,0,2,0)+(3,1,0,0)\bigr) = \left(1,1,\frac12,\frac12\right). $$
Thus the assignment consumes exactly the stated supply of every kind and has the prescribed type masses.

3.2. Verification of the MMS requirements

The average-value bounds from Section 2 give
$$ \begin{aligned} s_T&\leq18\theta+w\rho\leq19,\\ s_U&\leq\frac{18\theta}{H}+\rho \leq\frac12+\frac14=\frac34,\\ s_Z&\leq\frac{18\theta}{H}+2\rho \leq\frac12+\frac12=1. \end{aligned} $$
Every supported $T$ configuration has value $18$. The supported $U$ and $Z$ configurations each have own value $1$. Therefore
$$ \alpha s_T\leq19\alpha<\frac{38}{3}<18, \qquad \alpha s_U<1, \qquad \alpha s_Z<1. $$
The MMS requirements hold.

The benchmarks are also all positive. Since $\theta\geq1/2$, every admissible replica has
$$ 2N\theta\geq N $$
copies of $g_1$ and $g_2$ combined. Give one such copy to each of $N$ bundles, then attach the remaining goods arbitrarily. Each bundle is worth at least $4$ to $T$ and at least $4/H$ to $U$ and $Z$. Hence
$$ s_T\geq4,\qquad s_U\geq\frac4H,\qquad s_Z\geq\frac4H. $$

3.3. Verification of all EFX requirements

Every supported $T$ configuration has own value $18$.

• Removing a good from a supported primary configuration leaves value at most $18$ to $T$.
• Removing $d$ from $C$ leaves value $w$ to $T$, and $\beta w<18$.
• Removing $c$ from $C$, or removing $d$ from $E$, leaves value zero to $T$.

Thus every required comparison by $T$ is strict.

Types $U$ and $Z$ each receive own value $1$. Each primary configuration has value $18/H\leq1/2$ to either type. Every one-good deletion from $C$ has value at most $1$ to either type, and deletion from $E$ leaves zero. Since $\beta<1$, every required comparison by $U$ or $Z$ is also strict.

The supplied assignment is therefore feasible and satisfies all its EFX inequalities strictly.

3.4. Infinitely many obstructed admissible replicas

Because $\rho=2^{-h}$ and $\theta/2$ has reduced denominator $2^h$, the admissible sizes are precisely
$$ N=2^h k,\qquad k\in\mathbb Z_{>0}. $$
For such an $N$, the number of copies of $g_4$ is
$$ Nb_{g_4}=\frac{N\theta}{2} =(2^{h-1}-1)k. $$
This is odd whenever $k$ is odd.

We prove that, at every such odd-$k$ size, no $\beta$-EFX partial allocation can contain a type-$U$ agent with configuration $C$. The allocation may otherwise use arbitrary configurations.

Suppose, for contradiction, that an allocation contains $(U,C)$. Define the nonnegative integer resource value
$$ p(B)=4B_1+6B_2+7B_3+9B_4+wB_c. $$
Notice that $p(B)=v_T(B)$.

For every type-$T$ agent with configuration $B$, comparison with $C$ after removing $d$ gives
$$ p(B)=v_T(B)\geq\beta v_T(C-e_d)=\beta w>17. $$
Since $p(B)$ is an integer,
$$ p(B)\geq18. $$

For every type-$U$ agent with configuration $B$, the same comparison gives
$$ v_U(B)\geq\beta v_U(C-e_d)=\beta. $$
If $B_c=0$, then $v_U(B)=p(B)/H$, so
$$ p(B)\geq\beta H>w. $$
If $B_c\geq1$, then $p(B)\geq w$. Consequently, every type-$U$ bundle has resource value at least $w$, and equality is possible only if it contains exactly one $c$ and no primary good.

The total available resource value is
$$ Np(b)=N(18\theta+w\rho). $$
Summing the preceding lower bounds over all agents yields
$$ \sum_{\text{allocated bundles }B}p(B) \geq18N\theta+wN\rho. $$
Supply feasibility gives the reverse inequality. Equality must therefore hold throughout. In particular:

• every type-$T$ bundle has resource value exactly $18$;
• every type-$U$ bundle has resource value exactly $w$, and hence exactly one $c$ and no primary good;
• every type-$Z$ bundle has resource value zero;
• every copy of every primary good and of $c$ is allocated, because all these kinds have positive resource value.

There are exactly $N\rho$ copies of $c$, and the $N\rho$ type-$U$ agents use all of them. Thus no type-$T$ bundle contains $c$. Every type-$T$ bundle consequently satisfies
$$ 4B_1+6B_2+7B_3+9B_4=18. $$

This equation forces $B_4$ to be even. Indeed, $B_4\leq2$. If $B_4=1$, the remaining goods would have to satisfy
$$ 4B_1+6B_2+7B_3=9. $$
Here $B_3$ is either zero or one. When it is zero, the left side is even; when it is one, the remaining equation is $4B_1+6B_2=2$. Both cases are impossible.

Thus every type-$T$ bundle contains an even number of $g_4$ copies. All copies of $g_4$ must be allocated to these agents, so their total number must be even. This contradicts the odd supply when $k$ is odd.

The asserted impossibility follows.

3.5. A uniform lower bound on the rounding error

For any replica allocation, include empty configurations in its integer counts and define
$$ x^{(N)}_{t,B}=\frac{n^{(N)}_{t,B}}{N}. $$
Extend both this vector and the supplied assignment by zero over all type–configuration pairs.

At every obstructed size, the preceding proof gives
$$ x^{(N)}_{U,C}=0. $$
All type-$U$ agents still have configurations, so
$$ \sum_{B\neq C}x^{(N)}_{U,B}=\rho. $$
The supplied assignment places all type-$U$ mass on $C$. Therefore
$$ \begin{aligned} \|x^{(N)}-\lambda\|_1 &\geq |x^{(N)}_{U,C}-\rho| +\sum_{B\neq C}|x^{(N)}_{U,B}-0|\\ &=2\rho. \end{aligned} $$

There are arbitrarily large obstructed admissible sizes. Hence no family of $\beta$-EFX allocations on all sufficiently large admissible replicas can converge to $\lambda$ in $\ell_1$.

This impossibility already holds without imposing the replica MMS requirements. Adding those requirements cannot restore convergence.

4. A verified exponential construction bound

For completeness, the general construction upper bound can be established without assuming polynomial-time computation of the benchmarks.

Fix a type $t$ and a candidate $z>0$ with $z\leq A_t$. A configuration minimal under deletion subject to value at least $z$ contains no zero-valued kind. For each occupied coordinate,
$$ (C_j-1)v_{tj}\leq v_t(C-e_j)<z, $$
and therefore
$$ C_j\leq\left\lceil\frac{z}{v_{tj}}\right\rceil \leq\left\lceil\frac{A_t}{v_{tj}}\right\rceil. $$

Let $\mathcal C_t(z)$ contain every configuration within these latter bounds whose value is at least $z$, with zero coordinates on kinds worth zero to $t$. Consider
$$ p_C\geq0,\qquad \sum_{C\in\mathcal C_t(z)}p_C=1,\qquad \sum_{C\in\mathcal C_t(z)}p_CC_j\leq b_j \quad\text{for every }j. $$

This rational linear system is feasible exactly when some admissible replica has MMS at least $z$:

• From a witnessing partition, delete goods until every bundle is minimal for $z$. Normalized configuration counts satisfy the system.
• Conversely, a feasible system has a rational solution. At an admissible size clearing its denominators, realize its integer configuration counts. Attach unused goods arbitrarily to obtain a complete partition; nonnegativity preserves the threshold.

For $z=0$, the empty configuration supplies a witness.

Each coordinate bound has polynomial binary length. The benchmark grid from Section 2 and all configuration boxes therefore have size at most $2^{\operatorname{poly}(m,\tau,L)}$. Enumerating them and solving the explicit rational linear programs computes all $s_t$ within this time bound.

At $z=s_t$, introduce resource slack variables. There are $m+1$ equality rows, so a basic feasible solution has at most $m+1$ positive probabilities. Its selected configuration coefficients have polynomial binary length. Clearing the rational right-hand-side denominators and applying Cramer’s rule bounds the probability encoding lengths polynomially in $m,L$. An admissible size clearing those probabilities consequently has polynomial binary length. Taking a common multiple over all types produces a simultaneous witness $N_*$ with binary length polynomial in $m,\tau,L$.

Expand this replica and use the fixed-constant polynomial-time finite-agent algorithm for simultaneous $\beta$-EFX and $\alpha$-MMS, supplied by [Akrami–Rathi, Theorem 5.4](https://arxiv.org/html/2409.01963v2). The expanded instance has size $2^{\operatorname{poly}(m,\tau,L)}$, so this construction has the same exponential upper bound.

Finally, aggregate its configurations. Restrict assignment variables to these occupied pairs and impose the type-mass equations and resource inequalities. After introducing resource slacks, this feasible system has $\tau+m$ equality rows. A basic feasible solution has at most $\tau+m$ positive assignment entries.

Every configuration coordinate is bounded by the replica supply and thus has polynomial binary length. Cramer’s rule again gives polynomial encoding length for the selected assignment entries. Changing the masses on this fixed support preserves fairness, because every retained occupied pair belonged to the original fair support.

Thus there exists—and the preceding procedure constructs—an assignment with at most $\tau+m$ occupied pairs and polynomial encoding length. This proves an exponential construction bound, not a polynomial-time search algorithm.

5. Valid compressed rounding regimes

In this section, $L$ includes the supplied assignment. Let
$$ S_t=\{B:\lambda_{t,B}>0\}, \qquad K_t=|S_t|, \qquad K=\sum_tK_t. $$
All outputs are compressed integer configuration counts.

Whenever only supplied configurations are used, their EFX inequalities persist. Their MMS guarantees also persist because Section 2 established
$$ v_t(B)\geq\alpha s_t \geq\alpha\operatorname{MMS}^{N}_{v_t}(M_N) $$
for every admissible $N$.

5.1. Denominator-clearing replicas

Let $Q$ clear the denominators of the masses, supplies, and assignment entries. For every positive multiple $N$ of $Q$, set
$$ n_{t,B}=N\lambda_{t,B}. $$
These integral counts satisfy all constraints and have zero normalized $\ell_1$ error.

Computing $Q$ and these compressed counts takes time
$$ \operatorname{poly}(m,\tau,L,\log N). $$
This establishes rounding on a cofinal subsequence.

5.2. Resource slack

Choose one $B_t^*\in S_t$ for each type. At an admissible $N$, define
$$ f_{t,B}=\lfloor N\lambda_{t,B}\rfloor, \qquad r_t=N\mu_t-\sum_{B\in S_t}f_{t,B}. $$
The residual $r_t$ is an integer and satisfies
$$ 0\leq r_t<K_t. $$
Set
$$ n_{t,B}=f_{t,B}+r_t\mathbf1_{\{B=B_t^*\}}. $$
The type counts are exact, and only supplied configurations occur. Flooring removes total count $r_t$ from type $t$; adding the residual restores that count. Consequently,
$$ \left\|\frac nN-\lambda\right\|_1 \leq\frac{2\sum_t r_t}{N} \leq\frac{2(K-\tau)}{N}. $$

Define
$$ \sigma_j=b_j-\sum_{t,B}\lambda_{t,B}B_j, \qquad R_j=\sum_t(K_t-1)B_{t,j}^*. $$
The resource use satisfies
$$ \sum_{t,B}n_{t,B}B_j \leq N(b_j-\sigma_j)+R_j. $$
Thus supplies are respected whenever $N\sigma_j\geq R_j$ for every $j$.

Suppose $\sigma_j>0$ whenever $R_j>0$. If every $R_j$ is zero, take $N_0=1$. Otherwise take
$$ N_0=\max\left( 1,\max_{j:R_j>0}\left\lceil\frac{R_j}{\sigma_j}\right\rceil \right). $$
Every admissible $N\geq N_0$ then admits this rounding.

The threshold has polynomial binary length, and the compressed computation takes time $\operatorname{poly}(m,\tau,L,\log N)$.

5.3. Coordinatewise chains

Suppose each type’s support can be ordered as
$$ B_{t,1}\leq B_{t,2}\leq\cdots\leq B_{t,K_t} $$
coordinatewise. Write
$$ N\lambda_{t,i}=f_{t,i}+x_{t,i}, \qquad 0\leq x_{t,i}<1. $$
Then
$$ r_t=\sum_i x_{t,i} $$
is an integer. Let $I_t=\{i:x_{t,i}>0\}$. Round up the $r_t$ smallest configurations within $I_t$, and round down all others.

This preserves the type count. To check a resource coordinate, write its ordered values as $a_i=B_{t,i,j}$. Let $A_t\subseteq I_t$ be the selected indices. The identity
$$ \sum_{i\in A_t}(1-x_{t,i}) = \sum_{i\in I_t\setminus A_t}x_{t,i} $$
follows from $\sum_i x_{t,i}=|A_t|$. Every selected coordinate value is no larger than every unselected eligible value. Multiplying the two sides by their respective coordinate values therefore gives
$$ \sum_{i\in A_t}(1-x_{t,i})a_i \leq \sum_{i\in I_t\setminus A_t}x_{t,i}a_i. $$
When $r_t=0$, the inequality is immediate. It follows that
$$ \sum_i n_{t,i}B_{t,i,j} \leq \sum_i N\lambda_{t,i}B_{t,i,j}. $$
The same order works for every coordinate, so all supplies are respected.

Every count differs from its fractional target by less than one. Hence
$$ \left\|\frac nN-\lambda\right\|_1\leq\frac KN. $$
This works on every admissible replica and takes time $\operatorname{poly}(m,\tau,L,\log N)$.

6. The one-kind case and the remaining open point

When $m=1$, every support is a coordinatewise chain, so every supplied feasible assignment has the preceding rounding on every admissible replica.

Construction is also polynomial-time. Put $q=\lfloor b_1\rfloor$. For every admissible $N$,
$$ \operatorname{MMS}^{N}_{v_t}(M_N)=qv_{t1}. $$
For the upper bound, some bundle has at most $q$ copies. For the lower bound, give $q$ copies to every bundle and distribute the remainder arbitrarily.

Assign configuration $q$ to every type with mass $\mu_t$. This uses $q\leq b_1$ copies per capita and gives every type its full MMS. If $q>0$, every EFX comparison follows from
$$ qv_{t1}\geq\beta(q-1)v_{t1}; $$
if $q=0$, all compared bundles are empty. Construction takes polynomial time in $\tau,L$, and compressed replica counts take polynomial time in $\tau,L,\log N$.

For general $m,\tau$, the remaining question is the complexity of finding a feasible assignment from the support-encoded input. Universal rational existence, polynomial output length, and the exponential construction above do not settle polynomial-time search or establish search hardness. The unrestricted replica-rounding question has been settled negatively by Section 3.

⟨structured verdict parsed — rendered above⟩

The output establishes substantial correct results, including a counterexample to universal replica rounding. It does not settle the general complexity of finding an assignment, so the appropriate overall status is partial. I found no false mathematical step in the results it does claim to prove.

1. Benchmark attainment

The argument in Section 2 is correct.

• For every admissible $N$, the total value to type $t$ is $NA_t$. Thus the minimum bundle value in any partition into $N$ bundles is at most $A_t$, giving

$$ 0\leq z_t(N)\leq A_t. $$

• Clearing valuation denominators makes every bundle value an integer multiple of $1/q_t$. Consequently, all replica MMS values lie in the stated finite grid.

• Admissible sizes exist because the finitely many rational masses and supplies have a common denominator. Hence the set of achieved MMS values is nonempty and has an achieved maximum.

• Repeating a witnessing partition at size $N_t$ gives a witnessing partition at every positive multiple of $N_t$. Those multiples remain admissible. Therefore the maximum occurs at arbitrarily large admissible sizes and equals the limsup defining $s_t$.

• A common multiple of the witnessing sizes attains all types’ benchmarks simultaneously. The partitions witnessing the different types’ MMS need not coincide; the argument does not require them to coincide.

These steps also justify the inequality $z_t(N)\leq s_t$ used throughout the rounding sections.

2. Universal rational existence and existence decision

The cited theorem is applicable as stated. Akrami–Rathi’s Definition 2.2 quantifies over every removed item, without excluding items of zero value to the comparing agent. Their Theorem 5.2 provides a partial allocation simultaneously satisfying exact EFX and $2/3$-MMS for finite instances with additive nonnegative valuations. [Source](https://arxiv.org/html/2409.01963v2)

The replica at $N_*$ satisfies these hypotheses. Aggregating its allocation gives:

• rational, finitely supported assignment entries;
• exact type masses;
• resource consumption bounded by the per-capita supplies;
• own values at least $(2/3)s_t$, hence at least $\alpha s_t$;
• every required ordered-pair EFX comparison.

Comparisons of an occupied pair with itself also hold by nonnegativity, whether or not that configuration occurs for multiple agents.

Thus universal rational existence is established. On the promised domain of valid inputs, the existence decision always answers affirmatively and is polynomial-time. This does not establish polynomial-time construction, as the prover correctly notes.

3. Counterexample to universal rounding

All parts of Section 3 check out.

Parameter choices. The definition of $w$ gives
$$ 17<\beta w\leq17+\beta<18. $$
The requirements on $H$ and $h$ are compatible. Moreover, $\rho>0$ and $\theta\geq1/2$, so all three masses are positive and sum to $1$.

Supply feasibility. The four primary configurations average to
$$ \left(1,1,\frac12,\frac12\right). $$
Together with $C$ and $E$, the supplied assignment consumes exactly every stated supply and has the prescribed type masses.

MMS bounds. The primary per-capita value is $18\theta$. The displayed bounds follow from $w\rho\leq1$, $H\geq36$, and $\rho\leq1/4$. Each supported primary configuration has value $18$ to $T$, while the assigned configurations have value $1$ to $U$ and $Z$. These values exceed the required $\alpha s_t$ bounds.

The positivity argument is also valid: there are at least $N$ copies of $g_1$ and $g_2$ combined, and each is positively valued by every type. Assigning one to each partition bundle establishes the stated positive lower bounds.

EFX inequalities. For comparisons by $T$, primary deletions leave value at most $18$, and deleting $d$ from $C$ leaves value $w$, with $\beta w<18$. The other relevant deletions leave zero. For comparisons by $U$ and $Z$, primary configurations have value at most $1/2$, and deletions from $C$ leave value at most $1$. Since both types receive value $1$ and $\beta<1$, all required inequalities are strict.

Admissibility and parity. The reduced denominator of $\theta/2$ is $2^h$. All other masses and supplies have denominators dividing $2^h$. Therefore admissible sizes are exactly $N=2^hk$. At odd $k$, the supply
$$ Nb_{g_4}=(2^{h-1}-1)k $$
is odd.

Resource obstruction. If an allocation contains $(U,C)$, the EFX comparison obtained by deleting $d$ forces every type-$T$ bundle to have integer resource value at least $18$.

Every type-$U$ bundle has resource value at least $w$: without $c$, its required own value forces resource value greater than $w$; with $c$, the resource value is already at least $w$. Type-$Z$ bundles have nonnegative resource value.

These lower bounds sum to the entire available resource value. Supply feasibility therefore forces equality throughout. This correctly implies that all $c$ copies go to type-$U$ agents, all primary goods go to type-$T$ agents, and every type-$T$ bundle satisfies
$$ 4B_1+6B_2+7B_3+9B_4=18. $$

The case analysis excluding $B_4=1$ is exhaustive and correct. Thus every such bundle contains an even number of $g_4$ copies, contradicting the odd total supply.

Convergence obstruction. At every obstructed size, the coordinate $(U,C)$ has normalized count zero. The full type-$U$ mass $\rho$ occurs elsewhere, giving
$$ \|x^{(N)}-\lambda\|_1\geq2\rho. $$
There are arbitrarily large obstructed sizes. This conclusively disproves convergence on all sufficiently large admissible replicas, even before imposing replica MMS requirements.

4. Exponential construction and polynomial output length

Section 4’s construction bound is justified.

• The coordinate bounds for deletion-minimal threshold configurations follow from the displayed strict deletion inequality. Zero-valued kinds can be deleted without affecting a positive threshold.

• The configuration linear system is equivalent to attaining threshold $z$ in some admissible replica. Both directions preserve the threshold, and denominator clearing can include masses and supplies.

• The valuation grid and configuration boxes have singly exponential size because their bounds have polynomial binary length. Enumerating them and solving explicit rational linear programs therefore fits the claimed exponential bound.

• After adding resource slacks, a basic feasible solution has at most $m+1$ positive variables. The selected coefficients and right-hand side have polynomial binary length, so the stated determinant bounds give probabilities of polynomial encoding length.

• The resulting simultaneous witness has polynomial binary length, although its expanded agent and good lists may be exponentially large.

• Theorem 5.4 supplies the finite-instance polynomial-time algorithm for fixed positive approximation constants. Its fairness guarantees match the application here. [Source](https://arxiv.org/html/2409.01963v2)

• The final support-reduction linear program preserves fairness because it retains only configurations from the original fair support. Its basic feasible solution gives at most $\tau+m$ occupied pairs with polynomial encoding length.

These results establish an exponential construction algorithm and polynomial output length. Neither implies polynomial-time search.

5. Compressed rounding regimes

The three restricted rounding results are correct.

• Denominator-clearing replicas: exact integer counts preserve all constraints and give zero error.
• Resource slack: the residual count satisfies $r_t<K_t$, the error bound follows from flooring and restoring type counts, and the resource bound yields the stated sufficient threshold.
• Coordinatewise chains: selecting the smallest eligible configurations gives the required resource inequality in every coordinate. Eligibility excludes zero fractional parts, so every count differs from its target by less than one.

In each case, retained configurations preserve EFX and satisfy replica MMS because $z_t(N)\leq s_t$. The compressed arithmetic uses polynomially many operations on numbers of polynomial bit length in the supplied input and $\log N$, supporting the stated running times.

6. One-kind case

The one-kind MMS formula is correct, including zero valuations and $q=0$. Assigning $q=\lfloor b_1\rfloor$ copies to every agent respects supply and satisfies both fairness requirements. The construction and compressed rounding bounds follow.

7. Issue and required feedback

Major scope issue — general search complexity remains unresolved. The task asks whether finding an assignment is polynomial-time or hard. The output proves universal existence, polynomial output length, and an exponential construction bound, but gives neither a polynomial-time general construction nor a search-hardness result.

The prover explicitly acknowledges this limitation; it is not an internal inconsistency or a false claim. To complete the task, a further argument must establish one of those general complexity conclusions. No additional clarification alone can supply the missing result.

No minor mathematical issues were identified.

⟨structured verdict parsed — rendered above⟩