d4-conf-aaai-2026-4889 (d4-conf-aaai-2026-4889)

Given \(d\) item categories, a finite support \(T\) of \(\tau\) complete household types with rational masses \(\mu_t>0\), group labels \(g(t)\in[k]\), additive type valuations \(v_t\), a common additive allocator valuation \(u\), and rational per-capita supplies \(\beta_j\in[0,1]\), compute a rational mass allocation \(x_{tB}\geq 0\) over integral bundles \(B\subseteq[d]\) that attains the maximum worst-group average allocator value. Require \(\sum_{B\subseteq[d]}x_{tB}=\mu_t\), \(\sum_{t\in T}\sum_{B\ni j}x_{tB}=\beta_j\) for every category \(j\), and EF1 compatibility: whenever \(x_{tB}>0\) and \(x_{t'B'}>0\), type \(t\) must value \(B\) at least as much as \(B'\) after removal of one item, with the usual vacuous case when \(B'\) is empty. The objective is \(\max_x\min_{g\in[k]}\frac{\sum_{t:g(t)=g}\sum_{B\subseteq[d]}x_{tB}u(B)}{\mu_g}\), where \(\mu_g=\sum_{t:g(t)=g}\mu_t\). Determine the exact computational complexity in \(d,\tau,k\), and binary input length \(L\).

Let \(m=d\geq1\) be the number of item categories. A society is given by its support: a list \(T\) of \(\tau\geq1\) complete types, each specifying a group label \(g(t)\in[k]\), nonnegative binary-rational additive item values \(v_t(j)\), and a positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) counts listed positive-mass types, not possible types; every group has positive mass \(\mu_g=\sum_{t:g(t)=g}\mu_t\).
The input also specifies a common nonnegative binary-rational additive allocator valuation \(u\) and binary-rational per-capita supplies \(\beta_j\in[0,1]\); \(L\) is the total binary input length.
Each household receives an integral bundle \(B\subseteq[d]\), containing at most one item of each category. A mass allocation consists of rational \(x_{tB}\geq0\), represented by its nonzero entries, satisfying \(\sum_{B\subseteq[d]}x_{tB}=\mu_t\) and \(\sum_{t\in T}\sum_{B\ni j}x_{tB}=\beta_j\) for every category \(j\).
Require support-wise EF1: for every ordered pair \((t,B),(t',B')\) with positive allocated mass and \(B'\neq\emptyset\), some \(j\in B'\) satisfies \(v_t(B)\geq v_t(B'\setminus\{j\})\). This includes different bundles assigned to the same type; empty comparison bundles impose no condition.
Compute an allocation maximizing \(\min_{g\in[k]}\mu_g^{-1}\sum_{t:g(t)=g}\sum_{B\subseteq[d]}x_{tB}u(B)\) over these feasible allocations, or report infeasibility.

Is this exact optimization problem solvable in polynomial time in \(m=d,\tau,k,L\), or is it NP-hard?

For finite agents and indivisible items, computing a centralized group maximin allocation subject to EF1 is strongly NP-hard; the discrete problem admits a polynomial-time algorithm when allocator item values lie in \(\{0,1\}\). [Wang et al.](https://arxiv.org/html/2511.07984v1)
No result settling this precise support-wise continuous optimization problem was located in the literature search.

Partial results

I do not settle the general polynomial-time versus $\mathrm{NP}$-hardness question. I prove two additional tractability results:

• Exact optimization is polynomial-time solvable when the number of distinct household valuation vectors is fixed and household item values are nonnegative integers encoded in unary. The allocator valuation, masses, supplies, and number of groups remain unrestricted.
• A valuation-independent common bundle distribution exists under an exact, easily checked condition on the fractional supplies. This gives additional polynomial-time cases, including every instance with at most two fractional-supply categories.

I also give an exact residual-threshold formulation and reprove the polynomial certificate bound needed for membership of the threshold decision problem in $\mathrm{NP}$.

1. Residual values and the conserved objective

For any household valuation $v$ and bundle $C$, define its residual value by
$$ r_v(C)= \begin{cases} 0,&C=\emptyset,\\ v(C)-\max_{j\in C}v(j),&C\ne\emptyset. \end{cases} $$
For nonempty $C$, additivity gives
$$ r_v(C)=\min_{j\in C}v(C\setminus\{j\}). $$
Consequently, support-wise EF1 is equivalent to
$$ v_t(B)\ge r_{v_t}(C) $$
whenever $(t,B)$ has positive allocated mass and $C$ occurs anywhere in the allocation. Setting the residual of the empty bundle to zero adds no restriction, because all valuations are nonnegative.

In particular, deleting entries from a compatible support preserves EF1.

Write
$$ W=\sum_{j=1}^d\beta_j u(j). $$
Supply conservation implies that every allocation satisfies
$$ \sum_{g=1}^k\mu_g \left( \frac{1}{\mu_g} \sum_{t:g(t)=g}\sum_Bx_{tB}u(B) \right) = \sum_{t,B}x_{tB}\sum_{j\in B}u(j) = W. $$
The group masses are positive and sum to one. Thus the minimum group average is at most $W$. Any allocation giving every group average $W$ is optimal.

2. An exact formulation using one threshold per valuation vector

Let
$$ w^1,\ldots,w^q $$
be the distinct household valuation vectors appearing in the input. Thus $1\le q\le\tau$. Let $h(t)$ be the index satisfying $v_t=w^{h(t)}$, and abbreviate $r_{w^h}(B)$ to $r_h(B)$.

For a nonnegative threshold vector $a=(a_1,\ldots,a_q)$, define
$$ \mathcal C(a) = \{B\subseteq[d]:r_h(B)\le a_h\text{ for every }h\}, $$
and
$$ \mathcal A_t(a) = \{B\in\mathcal C(a):w^{h(t)}(B)\ge a_{h(t)}\}. $$

Consider the linear program that maximizes $z$, subject to
$$ \sum_{B\in\mathcal A_t(a)}x_{tB}=\mu_t \qquad(t\in T), $$
$$ \sum_t\sum_{\substack{B\in\mathcal A_t(a)\\j\in B}}x_{tB} = \beta_j \qquad(j\in[d]), $$
$$ \sum_{t:g(t)=g}\sum_{B\in\mathcal A_t(a)}x_{tB}u(B) \ge \mu_g z \qquad(g\in[k]), $$
with $x,z\ge0$.

Proposition 1. Every feasible solution of this linear program is support-wise EF1. Conversely, every support-wise EF1 allocation is feasible for one such linear program.

Proof. Suppose $x_{tB}>0$ and comparison bundle $C$ occurs in the allocation. By the permitted-bundle definitions,
$$ w^{h(t)}(B)\ge a_{h(t)} \quad\text{and}\quad r_{h(t)}(C)\le a_{h(t)}. $$
Their combination gives the required EF1 inequality.

Conversely, let $\mathcal S$ be the global bundle support of an EF1 allocation. It is nonempty because the total allocated mass is one. Set
$$ a_h=\max_{C\in\mathcal S}r_h(C). $$
Every supported bundle belongs to $\mathcal C(a)$. For each supported $(t,B)$, EF1 against every $C\in\mathcal S$ gives
$$ w^{h(t)}(B)\ge\max_{C\in\mathcal S}r_{h(t)}(C)=a_{h(t)}. $$
Thus every supported pair is permitted in the corresponding linear program. $\square$

For arbitrary rational valuations, it therefore suffices to enumerate
$$ a_h\in D_h, \qquad D_h=\{r_h(B):B\subseteq[d]\}. $$
Each set $D_h$ has at most $2^d$ elements. Enumerating bundles and these threshold vectors gives an exact algorithm with running time
$$ 2^{dq}\operatorname{poly}(2^d,\tau,k,L). $$
Every feasible linear program has $0\le z\le W$, and its allocation coordinates are bounded by the type masses. Hence its feasible region is compact. Rational linear programming supplies a rational optimum whenever it is nonempty.

This is an alternative exact enumeration bound. It does not give polynomial time when $d$ is unrestricted.

3. A pseudopolynomial algorithm for a fixed number of valuation vectors

Assume in this section that every household item value is a nonnegative integer. No integrality assumption is imposed on $u$, $\mu_t$, or $\beta_j$.

For each distinct valuation vector, put
$$ V_h=\sum_{j=1}^d w^h(j), \qquad M_h=\max_{j\in[d]}w^h(j). $$
All residual values are integers between zero and $V_h$. Proposition 1 therefore allows us to enumerate
$$ a_h\in\{0,\ldots,V_h\}. $$
The remaining issue is solving each threshold linear program without enumerating all bundles.

3.1 A finite graph representing permitted bundles

Fix a threshold vector $a$.

Construct a layered directed acyclic multigraph. Layers are indexed by $j=0,\ldots,d$. A state at layer $j$ records
$$ (s_1,\ldots,s_q,p_1,\ldots,p_q), $$
where, for the selected subset $B\subseteq[j]$,
$$ s_h=\sum_{\ell\in B}w^h(\ell), \qquad p_h= \begin{cases} \max_{\ell\in B}w^h(\ell),&B\ne\emptyset,\\ 0,&B=\emptyset. \end{cases} $$
The initial state has all coordinates zero.

From a state in layer $j-1$, there are two possible arcs:

• Exclude category $j$: leave all coordinates unchanged.
• Include category $j$: replace each pair $(s_h,p_h)$ by

$$ \left(s_h+w^h(j),\ \max\{p_h,w^h(j)\}\right). $$

The two arcs remain distinct even when their endpoints coincide, as can happen when all household valuations assign category $j$ value zero.

A bundle determines exactly one sequence of inclusion and exclusion choices. Conversely, every path through the layers determines an integral bundle.

Use one graph copy for each listed type $t$. Add a sink to that copy, and connect a layer-$d$ state to its sink precisely when
$$ s_{h(t)}\ge a_{h(t)} \quad\text{and}\quad s_h-p_h\le a_h \qquad(h=1,\ldots,q). $$
For the empty bundle, $s_h=p_h=0$, so the same test applies.

Since $s_h-p_h=r_h(B)$, the source-to-sink paths in type $t$’s graph represent exactly the bundles in $\mathcal A_t(a)$.

3.2 The flow linear program

Let $f_{te}\ge0$ be the flow on arc $e$ of type $t$’s graph. Require flow conservation at every intermediate node and source outflow $\mu_t$.

Let $E_j^+$ denote the inclusion arcs for category $j$ in the underlying graph. Impose the supply constraints
$$ \sum_t\sum_{e\in E_j^+}f_{te}=\beta_j \qquad(j\in[d]). $$
Impose the group constraints
$$ \sum_{t:g(t)=g}\sum_{j=1}^d u(j)\sum_{e\in E_j^+}f_{te} \ge\mu_g z \qquad(g\in[k]), $$
and maximize $z\ge0$.

Proposition 2. This flow linear program has exactly the same attainable group-value vectors as the threshold linear program of Section 2.

Proof. Given an allocation supported on permitted bundles, send mass $x_{tB}$ along the path for $B$ in type $t$’s graph. This gives the required source flows and conserves flow. A path traverses the inclusion arc for category $j$ exactly when $j\in B$. Thus category supplies and group allocator values are preserved.

Conversely, take any feasible rational flow. In each type’s acyclic graph, repeatedly choose a positive-flow source-to-sink path, subtract the minimum flow on that path, and assign that subtracted mass to its represented bundle.

Such a path exists whenever positive source flow remains: conservation supplies a positive outgoing arc at each reached intermediate node, and layers strictly increase until the sink is reached. Each subtraction makes at least one positive arc zero. Hence at most the number of arcs many paths are extracted.

After source flow becomes zero, no flow remains. Indeed, any remaining positive arc could be traced backwards through conservation to the source, contradicting its zero outflow.

Every extracted path reaches an allowed terminal state, so its bundle belongs to $\mathcal A_t(a)$. Path decomposition preserves type masses, inclusion-arc totals, and therefore supplies and group values. Proposition 1 then establishes EF1. $\square$

3.3 Size and complexity

Each state coordinate satisfies
$$ 0\le s_h\le V_h, \qquad 0\le p_h\le M_h. $$
Therefore each layer has at most
$$ P=\prod_{h=1}^q(V_h+1)(M_h+1) $$
states. A type’s graph has at most $(d+1)P+1$ nodes and $2dP+P$ arcs.

The flow linear program consequently has size polynomial in
$$ \tau dP,\ k,\ L. $$
Its coefficients are input rationals, together with zero and one. Standard polynomial-time rational linear programming applies. Rational path decomposition also takes polynomial time in the graph size and the encoding length of its flow.

There are
$$ A=\prod_{h=1}^q(V_h+1) $$
threshold vectors. Solving their flow programs and choosing the best solution proves the following.

Theorem 3. For integer household valuations, exact optimization can be performed in time
$$ A\operatorname{poly}(\tau dP,k,L), $$
where
$$ A=\prod_{h=1}^q(V_h+1), \qquad P=\prod_{h=1}^q(V_h+1)(M_h+1). $$

For fixed $q$, this is pseudopolynomial in the household values. In particular:

• If household values are encoded in unary and $q$ is fixed, the algorithm is polynomial in the input length.
• If household values lie in $\{0,1\}$ and $q$ is fixed, then $V_h\le d$ and $M_h\le1$, so exact optimization is polynomial in $d,\tau,k,L$.

These conclusions allow arbitrarily many listed types and groups: only the number of distinct household valuation vectors is fixed.

For rational household values, each valuation vector can independently be multiplied by a positive common denominator without changing any EF1 inequality. The resulting integer totals can, however, be exponentially large in $L$. Thus this scaling does not establish polynomial time for the original general input.

4. Exact characterization of valuation-independent common distributions

A bundle family $\mathcal S$ is universally EF1-compatible if, for every nonnegative additive valuation $v$, every ordered pair $B,C\in\mathcal S$ satisfies EF1.

Lemma 4. A family $\mathcal S$ is universally EF1-compatible if and only if
$$ |C\setminus B|\le1 \qquad(B,C\in\mathcal S). $$

Proof. If $C\setminus B$ contains one item, remove that item from $C$; the remaining bundle is contained in $B$. If $C\subseteq B$ and $C\ne\emptyset$, removing any item likewise leaves a subset of $B$. Nonnegativity then proves the inequality. Empty comparison bundles impose no condition.

Conversely, suppose $C\setminus B$ contains distinct items $i,j$. Give those two items value one and all other items value zero. Then $v(B)=0$, while removing any single item from $C$ leaves value at least one. EF1 fails. $\square$

We next classify such families.

Lemma 5. Every nonempty universally EF1-compatible family is contained in a family of one of the following forms:
$$ \{A\}\cup\{A\cup\{j\}:j\notin A\}, $$
or
$$ \{D\}\cup\{D\setminus\{j\}:j\in D\}. $$

Proof. By Lemma 4, bundle sizes differ by at most one.

First suppose both sizes $r$ and $r+1$ occur. Every size-$r$ bundle is contained in every size-$(r+1)$ bundle, because their directed difference has size at most one.

If there is exactly one smaller bundle $A$, every larger bundle is obtained by adding one item to $A$, giving the first form.

If there are two distinct smaller bundles $B_1,B_2$, their union has size $r+1$: their intersection has size $r-1$ by Lemma 4. Every larger bundle must therefore equal $D=B_1\cup B_2$. Every smaller bundle is obtained by deleting one item from $D$, giving the second form.

It remains to consider a family whose bundles all have the same size $r$. A singleton family has the first form. Otherwise choose distinct members
$$ B_1=A\cup\{b\}, \qquad B_2=A\cup\{c\}, $$
where $|A|=r-1$ and $b\ne c$.

A member containing $A$ has the form $A\cup\{e\}$. A member $B$ not containing $A$ omits some $a\in A$. The inequalities
$$ |B_1\setminus B|\le1, \qquad |B_2\setminus B|\le1 $$
force
$$ B=(A\setminus\{a\})\cup\{b,c\}. $$
If such a member exists, no member $A\cup\{e\}$ can have $e\notin\{b,c\}$: its difference from $B$ would contain both $a$ and $e$. Hence all members are size-$r$ subsets of $D=A\cup\{b,c\}$, giving the second form.

If no member omits part of $A$, all members contain $A$, giving the first form. $\square$

Let
$$ H=\{j:\beta_j=1\}, \qquad F=\{j:0<\beta_j<1\}. $$
Categories with supply zero can be omitted.

Theorem 6. A rational bundle distribution with marginals $\beta$ and universally EF1-compatible support exists if and only if
$$ \sum_{j\in F}\beta_j\le1 \quad\text{or}\quad \sum_{j\in F}(1-\beta_j)\le1. $$

Proof: necessity. By Lemma 5, its support has one of two forms.

In the first form, every supported bundle contains $A$ and at most one item outside $A$. Thus every category in $A$ has marginal one, and
$$ \sum_{j\in F}\beta_j \le \sum_{j\notin A}\beta_j = \mathbb E[|B\setminus A|] \le1. $$

In the second form, every supported bundle is contained in $D$ and omits at most one item of $D$. Every fractional category belongs to $D$, so
$$ \sum_{j\in F}(1-\beta_j) \le \sum_{j\in D}(1-\beta_j) = \mathbb E[|D\setminus B|] \le1. $$

Proof: sufficiency. If $s=\sum_{j\in F}\beta_j\le1$, use
$$ p_H=1-s, \qquad p_{H\cup\{j\}}=\beta_j \quad(j\in F). $$
These probabilities have the required marginals, and their support satisfies Lemma 4.

If $s'=\sum_{j\in F}(1-\beta_j)\le1$, put $D=H\cup F$ and use
$$ p_D=1-s', \qquad p_{D\setminus\{j\}}=1-\beta_j \quad(j\in F). $$
Again the marginals are correct, and Lemma 4 applies. Zero-probability entries are omitted. $\square$

For either distribution, assign
$$ x_{tB}=\mu_t p_B. $$
This preserves type masses and supplies. Universal compatibility establishes EF1 for all listed valuations. Every group obtains average
$$ \sum_Bp_Bu(B)=W. $$

Corollary 7. Under either condition in Theorem 6, an optimal allocation can be constructed in polynomial time. In particular, this holds whenever at most two categories have fractional supply.

For the last assertion, if $|F|\le2$ and $\sum_{j\in F}\beta_j>1$, then
$$ \sum_{j\in F}(1-\beta_j) = |F|-\sum_{j\in F}\beta_j <1. $$

5. A concrete obstruction to using one common distribution

The universal compatibility requirement above is stronger than compatibility for the particular input valuations. Nevertheless, there are valid inputs for which even input-specific EF1 rules out assigning every type the same bundle distribution.

Take four categories, each with supply $1/2$. Introduce six types, one for each two-element set $E\subseteq[4]$, each of mass $1/6$ and in its own group. Type $E$ values exactly the categories in $E$ at one. Let $u(j)=1$ for every category.

Suppose every type received the same bundle distribution with support $\mathcal S$. If $B,C\in\mathcal S$ had $|C\setminus B|\ge2$, choose a two-element set $E\subseteq C\setminus B$. Type $E$ would receive $B$ with positive mass and value it at zero, whereas removing one item from $C$ would leave value at least one. Thus
$$ |C\setminus B|\le1 $$
for all supported bundles.

By Theorem 6, such a distribution is impossible: all four supplies are fractional, and both relevant sums equal two.

This instance still attains the upper bound $W=2$. For each type $E$, distribute its mass equally over the four bundles selecting one category from $E$ and one from $[4]\setminus E$.

Every type then has each category as a marginal with probability $1/2$. Every own bundle has household value one. Every globally supported bundle has size two, so its residual value under any type’s binary valuation is at most one. Hence EF1 holds, and every group’s allocator average is two.

Therefore, extending the identical-valuation result by giving all types one common bundle distribution cannot solve the general problem.

6. Polynomial certificates and the remaining question

For completeness, the threshold decision problem belongs to $\mathrm{NP}$.

Fix any EF1-compatible typed support $S$. Its optimization linear program consists of the allocation equalities and group inequalities. Introduce nonnegative slacks $h_g$:
$$ \sum_{\substack{(t,B)\in S\\g(t)=g}}x_{tB}u(B) -\mu_gz-h_g=0. $$
Together with the type-mass and supply equations, there are $\tau+d+k$ equations.

The feasible region is bounded: allocation coordinates are bounded by type masses, $0\le z\le W$, and the displayed equations bound the slacks. Hence, if nonempty, the program has an optimal basic feasible solution. Such a solution has at most $\tau+d+k$ positive variables among $x,z,h$, and therefore at most that many positive allocation entries.

Every basis coefficient has polynomial binary length in $L$: bundle values and group masses are sums of input rationals. The basis dimension is at most $\tau+d+k$. Clearing denominators and applying determinant bounds to Cramer’s rule gives polynomial binary length for its coordinates.

There are finitely many typed supports. Thus, whenever feasible, the overall optimum is attained by a rational allocation having polynomially many entries of polynomial binary length. For a supplied rational threshold $R$, a certificate verifier checks type masses, supplies, all ordered EF1 comparisons, and every group’s average against $R$. These checks take polynomial time in $L$ and the encoding length of $R$.

The general input imposes neither a fixed number of distinct household valuation vectors nor a unary bound on their values, and it need not satisfy either supply condition of Theorem 6. The arguments above provide no polynomial-time optimizer or hardness reduction for that remaining class.

⟨structured verdict parsed — rendered above⟩

The output establishes valid partial results, but it does not resolve the general polynomial-time versus $\mathrm{NP}$-hardness question. I found no mathematical error in the stated propositions, algorithms, examples, or certificate argument. The substantive limitation is the explicitly acknowledged absence of a classification for unrestricted inputs.

Step-by-step verification

1. Residual values and the objective bound

The residual identity is correct. For nonempty $C$, additivity gives
$$ \min_{j\in C}v(C\setminus\{j\}) = v(C)-\max_{j\in C}v(j). $$
Thus the existential removal condition in EF1 is exactly the stated residual inequality.

Defining the empty bundle’s residual as zero introduces no additional restriction because household valuations are nonnegative. The formulation correctly includes comparisons between different bundles allocated to the same type.

Deleting allocated entries preserves compatibility of the remaining support. This statement concerns EF1 alone; deleting entries need not preserve masses or supplies, and the prover does not claim otherwise.

The conserved objective calculation is correct:
$$ \sum_g\mu_g\,\text{(group average)}=\sum_j\beta_j u(j)=W. $$
Since the positive group masses sum to one, the minimum group average cannot exceed $W$. An allocation giving every group average $W$ is consequently optimal.

Finding: Correct.

2. Residual-threshold formulation

Both directions of Proposition 1 are valid.

For the forward direction, every allocated bundle satisfies its recipient’s lower threshold, while every globally allocated comparison bundle satisfies every valuation’s residual upper threshold. These inequalities imply EF1 for every required ordered pair.

For the converse, the global bundle support is finite and nonempty. Consequently,
$$ a_h=\max_{C\in\mathcal S}r_h(C) $$
is defined and attained. EF1 implies the required lower threshold for every supported typed bundle, and the definition of $a_h$ supplies all residual upper bounds.

The converse also yields feasibility of the objective constraints by choosing $z=0$, since allocator values are nonnegative.

Each threshold obtained this way belongs to $D_h$. Therefore enumerating the displayed finite threshold sets covers every feasible EF1 allocation. The stated enumeration bound is valid.

For each threshold program, allocation coordinates are bounded by the type masses. Summing the group inequalities gives $z\le W$, so the feasible region is bounded and closed. Standard exact rational linear programming applies to these explicitly enumerated finite programs and produces rational optima.

Finding: Correct. This is an exponential algorithm, not a polynomial-time classification.

3. Fixed-number-of-valuations pseudopolynomial algorithm

Graph representation

The state records precisely the sums and maxima needed to evaluate the threshold conditions. For the empty bundle and for bundles consisting entirely of zero-valued items, the identity
$$ r_h(B)=s_h-p_h $$
still holds.

Keeping inclusion and exclusion arcs distinct when their endpoints coincide is necessary and correctly handled: their supply and allocator contributions differ even when their household-valuation states agree.

The terminal acceptance test is exactly membership in $\mathcal A_t(a)$. Every inclusion/exclusion sequence represents one bundle, and every bundle gives such a sequence.

Flow formulation and decomposition

Sending bundle mass along its corresponding path preserves type masses, category supplies, and group allocator values.

Conversely, flow conservation and acyclicity justify the stated path decomposition. Here the nonsink layer-$d$ nodes are intermediate nodes for purposes of conservation, including terminal states without a sink arc; conservation prevents flow from ending at a forbidden terminal state.

Each subtraction removes at least one positive arc. Thus the number of extracted paths is at most the number of arcs. A remaining positive flow after source outflow becomes zero would contradict conservation and acyclicity, as the prover states.

All extracted bundles pass the terminal test. The resulting allocation therefore satisfies the threshold program and hence EF1.

Size and arithmetic

The coordinate ranges give the stated state bound
$$ P=\prod_{h=1}^q(V_h+1)(M_h+1). $$
The node and arc bounds correctly account for all layers, inclusion/exclusion arcs, and terminal-to-sink arcs.

The number of threshold vectors is
$$ A=\prod_{h=1}^q(V_h+1). $$
The flow programs have rational coefficients of polynomial encoding length and explicitly bounded size. Exact rational linear programming and rational path decomposition therefore support the stated running-time bound.

For fixed $q$, unary household values make these quantities polynomial in the input length. Binary household values restricted to $\{0,1\}$ likewise give polynomial bounds when $q$ is fixed.

Independent positive scaling of each household valuation preserves its EF1 inequalities. The warning that denominator clearing may produce exponentially large integer totals is correct.

Finding: Correct. The restrictions on $q$ and on numerical magnitudes are essential to the polynomial-time conclusion.

4. Universally compatible bundle distributions

Lemma 4

The sufficiency argument correctly uses containment after removing the sole item of $C\setminus B$, or any item when $C\subseteq B$.

For necessity, assigning value one to two items of $C\setminus B$ and zero elsewhere makes $v(B)=0$ and leaves comparison value at least one after any single removal. This is a valid counterexample to universal compatibility.

Lemma 5

The classification proof covers all cases.

When both sizes $r$ and $r+1$ occur, the directed-difference bound forces every smaller bundle to be contained in every larger bundle. Two distinct smaller bundles have union of size $r+1$, forcing a unique larger bundle.

For equal-sized bundles, the two selected distinct members differ by one exchange. A further member omitting an element of their common part must contain both exchanged elements. Its compatibility then excludes members adding an item outside those two elements. This establishes the claimed second form; otherwise all members share the common part and lie in the first form.

Singleton families and the empty bundle are covered.

Theorem 6 and Corollary 7

Both necessary inequalities follow correctly from the classified support forms and expected numbers of added or omitted items.

Both constructions have nonnegative rational probabilities summing to one and the required marginals. Categories of supply one always appear, categories of supply zero never appear, and fractional-category marginals are as specified. Omitting zero-probability entries causes no problem, including when $F$ is empty.

Assigning $x_{tB}=\mu_t p_B$ gives each type the same conditional distribution. Universal compatibility establishes EF1, and every group receives allocator average $W$.

The constructions use at most $|F|+1$ bundles, so their explicit allocation representations have polynomial size.

For $|F|\le2$, the final complementary-sum calculation is correct and proves that at least one sufficient condition holds.

Finding: Correct. The theorem characterizes universally compatible distributions; it does not characterize feasibility for arbitrary input-specific valuations.

5. Obstruction to a common distribution

The example satisfies the input requirements: six positive-mass types, positive group masses, nonnegative binary household values, and rational supplies.

If all types share one distribution, any pair of supported bundles with at least two items in $C\setminus B$ violates EF1 for the type corresponding to a two-element subset of that difference. Thus the support must satisfy Lemma 4.

Theorem 6 then excludes such a common distribution because both relevant fractional-supply sums equal two.

The alternative allocation is valid. Each type assigns equal conditional probability to four bundles, and each category appears in exactly two of those four bundles. Hence each category has conditional marginal $1/2$, and the aggregate supplies are correct.

Every own bundle has household value one. Every comparison bundle has two items, so its residual under any listed binary valuation is at most one. EF1 follows. Every allocated bundle has allocator value two, giving every group average $W=2$.

Finding: Correct. This disproves the general common-distribution strategy, without establishing hardness.

6. Polynomial certificates

The certificate argument is valid.

For a fixed compatible typed support, introducing nonnegative group slacks gives $\tau+d+k$ equations. Allocation variables, $z$, and slacks are bounded, so every nonempty such program has an optimal basic feasible solution.

A basic feasible solution has at most the equation rank, and hence at most $\tau+d+k$, positive variables. This bounds the number of positive allocation entries.

Bundle values and group masses are sums of input rationals and have polynomial binary length. The basis dimension is polynomially bounded. Denominator clearing and determinant bounds therefore give polynomial encoding length for the resulting coordinates.

Restricting to the positive entries of this solution preserves EF1. There are finitely many typed supports, and their programs collectively cover all feasible allocations, so the overall optimum is attained and has a polynomial-size rational representation.

The listed verification operations—including all ordered EF1 comparisons—are polynomial for that representation. This proves membership of the rational-threshold decision problem in $\mathrm{NP}$.

Finding: Correct. Polynomial certificates do not themselves establish a polynomial-time optimizer or a hardness result.

Scope issue and minimum required follow-up

Major — unresolved assigned target. The general input permits unrestricted numbers of distinct valuation vectors and unrestricted binary-rational household values, and it may fail both supply conditions. None of the established results classifies that remaining class.

No clarification is needed to validate the partial results. Resolving the assigned question requires an additional general polynomial-time algorithm or a valid hardness reduction. That is new mathematical work, not an expositional repair.

⟨structured verdict parsed — rendered above⟩