| paper | d4-conf-aaai-2026-4889 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
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\).
A distribution over complete household types, each assigned an integral bundle with mass \(x_{tB}\); type masses and per-capita item supplies are fixed, EF1 must hold across every positively represented type-bundle pair, and the objective maximizes the minimum group-average allocator value.
The mirror asks about Proposition 1’s CGMMS-with-EF1 objective; it does not transfer the paper’s binary-allocator algorithm or its EF1+CGEQ1 existence algorithms.
The strongest anchor is Proposition 1, proved in the paper: computing an allocation that maximizes the minimum centralized group share, subject to EF1 for agents, is strongly NP-hard. In full, its objective is to find an allocation \(\mathcal A\) attaining
\[
\max_{\mathcal A}\ \min_{G_p\in\mathcal G}
\frac{u\!\left(\bigcup_{i\in G_p} A_i\right)}{|G_p|},
\]
while every agent is EF1 toward every other agent. The paper reduces from 3-partition: it creates \(q\) agents in \(q\) singleton groups and \(3q\) items whose centralized values are the 3-partition numbers. Give the agents zero valuations, so EF1 is automatic. The optimum minimum share reaches the target \(B\) exactly when the numbers can be partitioned into \(q\) groups of sum \(B\). The paper proves this result here; it is not merely citing an external hardness theorem.
A plausible mirror is Typed-population CGMMS-EF1. Consider a city distributing standardized emergency-supply categories across a fixed set of neighborhoods. Each household gets an integral bundle: at most one indivisible item from each category. A category’s stock is specified per household and scales with the population. Households fall into a small number \(\tau\) of complete types: a type includes its neighborhood and its additive valuation for every category. The city has one additive value \(u\) for the categories. This is a high-multiplicity regime when the number of households is large while the number of neighborhoods and distinct valuation profiles stays small.
Precisely, let \(T\) be the supported types, with rational masses \(\mu_t>0\) summing to \(1\), and let \(\mu_g\) be the total mass in neighborhood \(g\). For \(d\) categories, let \(\beta_j\in[0,1]\) be the per-capita supply of category \(j\). A mass allocation is a set of nonnegative rational values \(x_{tB}\), for \(t\in T\) and \(B\subseteq[d]\), where \(x_{tB}\) is the mass of type \(t\) receiving the integral bundle \(B\). Require
\[
\sum_{B\subseteq[d]}x_{tB}=\mu_t
\quad\text{and}\quad
\sum_{t\in T}\sum_{B\ni j}x_{tB}=\beta_j
\quad\text{for each category }j.
\]
Require EF1 across the population: whenever \(x_{tB}>0\) and \(x_{t'B'}>0\), a type-\(t\) household receiving \(B\) must value \(B\) at least as much as \(B'\) after removal of some one item from \(B'\). The empty bundle is vacuous. The problem is to output a mass allocation attaining
\[
\max_x\ \min_g
\frac{\displaystyle\sum_{t:\,g(t)=g}\sum_{B\subseteq[d]}x_{tB}u(B)}
{\mu_g},
\]
subject to those supply, type-mass, and EF1 conditions. The question for a prover is its exact complexity in \(d,\tau,k\), and the binary input length \(L\).
This preserves the paper’s actual question: maximize the worst group’s average centralized value while maintaining individual EF1. A household still receives an integral bundle; only the distribution of households across type-and-bundle pairs is fractional. That fractional mass is the population continuum, while scaling stock per capita is the co-modification needed to make allocation meaningful at population scale. With rational input and allocation masses, clearing denominators realizes the allocation in a sufficiently large finite replicated instance.
My tentative expectation is Class C, for continuum-specific reasons: choosing which bundle patterns have positive mass creates pairwise EF1 compatibility constraints that remain after population counts are relaxed. That is a hypothesis, not a consequence of Proposition 1. The obvious LP over the \(x_{tB}\) handles the objective and supplies, but not the support compatibility imposed by EF1; finding structure or a pricing method for it is the central question.
The weakest point is that Proposition 1’s particular reduction uses one singleton group per agent. Since group membership is part of a complete type, its support grows with the number of agents; that is not the fixed-group, few-type regime in this mirror. So the paper’s proof does not establish that its hardness transfers. The mirror remains plausible because the objective and fairness constraint are unchanged, but whether it is tractable or continuum-specifically hard is open. The mirror covers Proposition 1 only; I would not stretch it to cover the paper’s EF1+CGEQ1 existence algorithms.
It generates two useful follow-up questions: does EF1 bundle compatibility admit an efficient structure or pricing algorithm for variable \(d,\tau\), and can the CGMMS hardness be reproduced with fixed \(k\) and small \(\tau\), or does it disappear in that regime?
The strongest case against the proposed anchor is narrow: Proposition 1’s reduction does not establish hardness in a moderate-support population regime. Its \(q\) agents each belong to a singleton group, so the type support grows with \(q\); the proof’s bin structure is encoded in the growing set of groups. It gives no evidence that the same difficulty survives when many households share a small set of complete types and groups.
That weakens the connection to the result, but it does not defeat the better mirror. The paper’s emergency-supply and housing scenarios make fixed neighborhoods, recurring valuation types, and per-capita stock plausible. Those choices yield a well-defined population problem. Keeping the paper’s finite inventory instead would make per-capita group shares vanish as the population grows; scaling stock is the co-modification the programme explicitly allows. I cannot use the loss of the original reduction as an objection: whether the resulting problem is easy or hard is itself a question the programme permits.
The bundle-support EF1 constraints may make the proposed problem a new computational challenge rather than a direct continuation of Proposition 1. That gives the negative case some force as a reason to be cautious about this particular anchor. It does not show the problem is unworthy: the objective and individual fairness requirement remain recognizable, and the output masses can be realized in sufficiently large replicated instances.
Prior work on high-multiplicity fair allocation confirms that repeated item types are a sensible regime; it studies finite-agent allocations and does not already answer this continuous CGMMS question, so it supports the mirror rather than colliding with it. [Bredereck et al., *High-Multiplicity Fair Allocation Made More Practical*](https://aamas.csc.liv.ac.uk/Proceedings/aamas2021/pdfs/p260.pdf)
I cannot make a persuasive universal case against a worthwhile mirror here. The defensible negative claim is only that Proposition 1’s particular hardness proof is a poor basis for predicting what happens at moderate support. The proposed mirror itself survives that criticism.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.