| paper | d4-conf-aaai-2026-3163 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(\text{Polynomial-time solvable}\): an EF1 outcome always exists and can be found using polynomially many oracle queries and bit operations in \(m,k,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m\) indivisible goods, \(k\) groups with rational quota shares \(\alpha_i\) summing to \(1\), and a finite set \(T\) of complete utility types with rational masses \(\mu_t\) summing to \(1\), find a partition of the goods into bundles \(A_1,\ldots,A_k\) and nonnegative assignment masses \(x_{t,i}\) such that \(\sum_i x_{t,i}=\mu_t\), \(\sum_t x_{t,i}=\alpha_i\), and whenever \(x_{t,i}>0\), for every group \(j\) there is a set \(B\subseteq A_j\) with \(|B|\leq 1\) and \(u_t(A_i)\geq u_t(A_j\setminus B)\). With value-oracle access to the monotone utilities, can such an outcome be found in time polynomial in \(m\), \(k\), \(|T|\), and the input bit length \(L\)?
Each type \(t\) specifies a complete normalized monotone utility function and carries rational mass \(\mu_t\). Goods remain indivisible and are partitioned into whole bundles; the decision variables are that partition and a mass assignment \(x_{t,i}\) meeting rational group quotas \(\alpha_i\). The objective is to find any feasible EF1 outcome, with polynomial dependence on \(m\), \(k\), \(|T|\), and \(L\) as the computational question.
The mirror covers Theorem 1’s EF1 existence and computation result. It leaves the connected-bundle existence result and the random-utility asymptotic results in Theorems 2–5 aside.
The strongest mirror is \(\textsc{Variable-Group EF1}_{\mathrm{mass}}\), anchored in Theorem 1, proved in this paper. The theorem says that for every finite instance with arbitrary monotonic utilities, there is an EF1 outcome, and the paper’s envy-cycle algorithm computes one in time \(O(mn^3)\). The paper offers no comparable named hardness result, so this is an algorithmic anchor rather than a case about discrete hardness dissolving.
In the mirror, the instance has \(m\) indivisible goods, \(k\) groups with rational target mass shares \(\alpha_1,\dots,\alpha_k\) summing to \(1\), and \(\tau\) complete utility types. Each type \(t\) has a rational population mass \(\mu_t\), with \(\sum_t\mu_t=1\), and a normalized monotonic utility function \(u_t\) over bundles of goods. A type specifies everything relevant to the allocation: two people of that type value every bundle identically. Ask for a partition of the goods into whole bundles \(A_1,\dots,A_k\), and assignment masses \(x_{t,i}\geq 0\), such that
\[
\sum_i x_{t,i}=\mu_t,\qquad \sum_t x_{t,i}=\alpha_i,
\]
and whenever \(x_{t,i}>0\), type \(t\) regards group \(i\)’s bundle as at least as good as each other group’s bundle after removing some one good from that other bundle. The solution is the bundles and the mass-assignment matrix; the objective is to find any such EF1 outcome. Bundles stay indivisible. Only population and group membership become continuous.
A plausible regime is a large employer assigning equipment to teams: thousands of workers fall into a relatively small number of recurring preference classes, while each team has a target workforce share. This is exactly where the group-membership decision can sensibly be made in proportions. For a discrete instance, the dictionary is direct: set \(\mu_t=n_t/n\) and \(\alpha_i=n_i/n\). The mirror allows a type’s mass to split between groups at finer granularity than \(1/n\), so it is a relaxation; rounding a mass assignment back to individual workers while retaining EF1 is a natural follow-up question.
The existence part is already supported by Theorem 1. For rational masses and quotas, take a common denominator \(D\), make \(D\mu_t\) identical copies of each type, and set group sizes to \(D\alpha_i\). The theorem gives an EF1 outcome, which can be aggregated into the required mass assignment. That construction may take time polynomial in \(D\), which can be exponential in the binary input length. My expectation is nevertheless Class A: a compressed envy-cycle or fractional-flow version may yield an algorithm polynomial in \(m,\tau,k\), and the bit length \(L\). That is a conjecture about the mirror, not a consequence of the stated \(O(mn^3)\) bound.
The scope here is Theorem 1’s general EF1 allocation and computation result. I would leave the connected-bundle theorem and the random-utility asymptotic results outside this mirror rather than stretch the claim across different questions.
The weak point is the computation claim. Theorem 1 moves named agents and preserves integer group sizes; with mass types, only part of a type’s population may need to move, and it is not automatic that cycle elimination still terminates efficiently. The existence mirror is solid; the research question is whether its algorithm can depend on \(\tau\) and \(L\) instead of the potentially enormous represented population.
The only anchor is Theorem 1, and it is a real computational result: EF1 can be found in \(O(mn^3)\) time. The best mirror is also well specified. Give each complete utility type mass \(\mu_t\), each group a rational quota \(\alpha_i\), keep the goods indivisible, and require every type assigned positive mass to a group to satisfy EF1 there. Large organizations with recurring preferences over shared equipment are a plausible regime. Neither individual identity nor the pointwise fairness condition is lost: the type records the full valuation, and the condition applies to every positive-mass type.
The strongest objection is that the paper’s runtime does not establish a useful bound in the mirror’s parameters. Cloning rational masses into a finite population proves existence, but a common denominator can be exponential in its bit length \(L\); the \(O(mn^3)\) guarantee therefore does not give an algorithm polynomial in \(m,\tau,k,L\). Nor does the paper show that its cycle-elimination algorithm compresses when identical agents are aggregated. So the proponent’s claimed continuous computation is an open question, not a consequence of Theorem 1.
That objection narrows the payoff, but it does not defeat the mirror. Whether the dependence on population size can be replaced by dependence on type support and input length is precisely a high-multiplicity computational question. Fractional type-to-group assignments are a natural way to pose it, and existing high-multiplicity work supports the regime rather than colliding with it. Keeping goods indivisible does not remove the population from the model; population mass is the axis being continuized.
I can make the case against the programme’s priority for this paper: the proposed contribution is one compressed algorithmic version of an already universal EF1 witness theorem, and the paper gives no evidence that its bottleneck is population multiplicity. But that is a judgment about likely payoff, not a fundamental reason the question is ill-posed or uninteresting. The strongest anchor survives, and I cannot honestly support the universal claim that no worthwhile continuous mirror exists.
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.