d4-conf-aaai-2026-3491

The strongest positive case is the paper’s Theorem F.2 (Appendix F; proved in this paper, with the proof in Appendix G.3). It states that for an allocation instance with objective valuations, the paper’s greedy algorithm finds an EQ1 allocation in polynomial time \(O(m\log n)\). The underlying problem is to allocate every indivisible item so that, whenever one agent values her own bundle less than another agent values theirs, removing one item from one of those two bundles makes the first value at least the second. The result covers objective valuations, not only additive ones: each item is a good for every agent and bundle, or a chore for every agent and bundle. The paper contains no numbered hardness result to anchor a positive case on; its PPAD-completeness claim for envy-freeness is a conjecture, not an established result.

Here is a concrete continuous mirror. Consider a large relief programme allocating standardized benefits and obligations to households. A type \(t\) is a complete household valuation profile: two households of the same type value every bundle identically. Let \(K\) be a finite set of item kinds, such as benefit categories and required duties, and let \(\mu_t\) be the fraction of households of type \(t\), with \(\sum_t\mu_t=1\). There are \(\tau\) supported types, where \(\tau\ll N\) in the intended regime of \(N\) households. Copies of each item kind are interchangeable and scale with the population: \(q_k\) is the number of copies of kind \(k\) available per household. Each household still receives an integral bundle, represented by a count vector \(b\in\mathbb Z_{\ge0}^{K}\). Type \(t\)’s valuation is \(v_t(b)\), and each item kind is universally a good or universally a chore, as in the paper’s objective-valuation setting.

A solution is a finite list of rational masses \(y_{t,b}\ge0\), where \(y_{t,b}\) is the share of the population of type \(t\) receiving the integral bundle \(b\). It must satisfy
\[ \sum_b y_{t,b}=\mu_t \quad\text{for every }t, \qquad \sum_{t,b} y_{t,b}b_k=q_k \quad\text{for every }k. \]
The second condition allocates all item supply. For fairness, apply EQ1 to every pair of type–bundle classes with positive mass—not to type averages. Thus, if \(y_{t,b},y_{u,c}>0\) and \(v_t(b)<v_u(c)\), require
\[ \bigl(\exists k:b_k>0,\ v_t(b-e_k)\ge v_u(c)\bigr) \quad\text{or}\quad \bigl(\exists k:c_k>0,\ v_t(b)\ge v_u(c-e_k)\bigr), \]
where \(e_k\) removes one copy of kind \(k\). This preserves the paper’s single-item removal comparison, including when the same kind appears in both bundles: the removed copies are distinct items. Fractionality is only in the mass assigned to each class; every household gets an integral bundle. The task is to find such a mass assignment, with no extra welfare objective.

This is a high-multiplicity regime rather than a change to fractional outcomes. A finite society with \(N\) households has \(N\mu_t\) households of type \(t\) and \(Nq_k\) copies of item kind \(k\), when those quantities are integral. Repeating the same household and item profiles is a plausible fit for large-scale provision programmes. From a continuous solution with rational masses, choosing a common denominator realizes it as a finite allocation of cloned households and items. Conversely, any such finite EQ1 allocation yields a mass solution by recording the fraction of each type assigned each bundle. The households’ full valuation functions belong in their types; repeated types are the high-multiplicity assumption, not a loss of individual-specific information.

I would provisionally expect the compressed problem to be tractable (Class A). The anchor gives a constructive, general objective-valuation algorithm, and its proof maintains EQ1 through local item assignments; repeated profiles may allow those operations to be aggregated over cohorts. But Theorem F.2 alone does not give a polynomial-time algorithm in the continuous input’s bit length. If \(D\) is a common denominator for the \(\mu_t\) and \(q_k\), expanding the instance and running the paper’s algorithm takes \(O(D\sum_k q_k\log D)\) time. Since \(D\) can be exponential in its binary encoding, compressing the greedy process is a real open algorithmic question. There is no hardness anchor here, so Class B is unsupported; if cohort compression fails, continuum-specific hardness is the alternative to investigate.

The mirror covers Theorem F.2’s objective-valuation EQ1 allocation problem, not the paper’s other results on path-connected bundles, non-negative or non-positive valuations, EQXR, or envy-freeness. Further questions include whether one can find the mass assignment in time polynomial in \(K\), \(\tau\), and the binary input length; how large a support of type–bundle classes a solution needs; and whether the paper’s stronger equity guarantees admit analogous mirrors.

The weak point is the item model: it assumes many interchangeable copies whose valuations depend only on their kinds. That is a substantive, but plausible, regime restriction; distinct item identities can matter in the paper’s finite model. A second limitation is computational: the finite greedy algorithm guarantees a solution after expansion, but leaves the compressed-input running time unanswered. The case survives those limitations because the mirror keeps the exact EQ1 question, keeps bundles indivisible at the recipient level, and makes the population distribution itself the continuous object.