| paper | d4-journals-mss-2023-0029 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Polynomial-time solvable in \(m,\tau,L\), with an optimal EFX allocation supported on at most \(\tau+m\) type–bundle pairs. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 8
Given \(m\) good classes with rational prices \(p_r>0\), supported types \(T\) with rational masses \(\mu_t\) summing to \(1\), and rational per-capita supplies \(q_r\), compute a finite list of bundle masses \(x_{t,z}\ge 0\), where \(z\in\mathbb Z_{\ge 0}^m\) is each person’s integral bundle and type \(t\) values classes in \(D_t\), with \(u_t(z)=\sum_{r\in D_t}p_rz_r\). Require \(\sum_z x_{t,z}=\mu_t\) and \(\sum_{t,z}z_rx_{t,z}=q_r\). For every two bundles \(z,w\) receiving positive mass and every \(r\in D_t\) with \(w_r>0\), require \(u_t(z)\ge u_t(w)-p_r\); among feasible allocations, maximize \(\sum_{t,z}x_{t,z}u_t(z)\). Is this computable in time polynomial in \(m\), \(\tau=|T|\), and the binary input length \(L\)?
A unit-mass population distributed over preference types, with per-capita supplies of repeated indivisible goods and a mass distribution over integral bundles. Optimize utilitarian welfare subject to EFX; Pareto optimality follows from welfare maximization.
The mirror targets the goods case of Theorem 8. It does not cover chores, the unrestricted-additive algorithm of Theorem 6, or the paper’s characterization and Nash-welfare results.
The strongest anchor is Theorem 8, proved in this paper: in a generalized binary utility scenario for goods or chores, the modified Algorithm 1 orders resources by decreasing maximum absolute value for goods (increasing for chores) and produces an allocation that maximizes utilitarian social welfare, is EFX and Pareto optimal, in \(O(m\log m+mn)\) time. I would use its goods case as my single anchor; it gives a stronger fairness guarantee than the paper’s EF1 result. The introduction also cites NP-completeness for finding utilitarian-welfare-maximizing EF1 allocations under unrestricted additive utilities, but that is a different valuation domain and is not a numbered result of this paper.
A plausible high-multiplicity setting is a large relief programme distributing repeated units from a small catalogue. A type records which goods a household values; households of that type have the same preferences, and value each wanted unit of good \(r\) at the common catalogue value \(p_r\), while assigning it value zero otherwise. Think tens or hundreds of thousands of households but only a few dozen supported types. The stock of each good scales with population. This keeps the paper’s utility and fairness model while making the population continuous; scaling stock per capita is the natural co-modification when the society itself is the limit object.
I would ask about Per-Capita GBU-EFX Welfare Allocation\(_\infty\). An instance has \(m\) good classes, rational values \(p_r>0\), a supported type set \(T\) of size \(\tau\), rational masses \(\mu_t\) summing to one, and rational per-capita supplies \(q_r\). Type \(t\) is specified by the set \(D_t\) of goods it values, with utility \(u_t(z)=\sum_{r\in D_t}p_rz_r\). Here \(z\in\mathbb Z_{\ge0}^m\): each person receives an integral bundle of indivisible units, though they may receive multiple copies of a class.
The requested output is a finite list of bundle masses \(x_{t,z}\ge0\), with \(\sum_zx_{t,z}=\mu_t\) and \(\sum_{t,z}z_rx_{t,z}=q_r\). Each \(x_{t,z}\) is a mass of people receiving the whole bundle \(z\), not a fractional bundle or a lottery. Require EFX: whenever \(x_{t,z}>0\), \(x_{s,w}>0\), and \(r\in D_t\) with \(w_r>0\), require \(u_t(z)\ge u_t(w)-p_r\). Among all feasible allocations, the output must maximize \(\sum_{t,z}x_{t,z}u_t(z)\), and be Pareto optimal: no reassignment of the same population and goods can weakly improve almost everyone while strictly improving a positive mass. As in the paper’s additive setting, maximum utilitarian welfare implies Pareto optimality. The central question is whether this can be solved in time polynomial in \(m,\tau\), and the binary input length \(L\).
I expect a Class A answer: the price ordering and utility-balancing idea behind Theorem 8 should have a mass-based counterpart that splits type cohorts as needed. This is a mirror the authors could recognize: it preserves their allocation problem, generalized binary utilities, utilitarian objective and EFX criterion. The extension asks for exact aggregate masses while every person still gets whole goods.
The weak point is real: Theorem 8 runs in \(n\), the number of named agents, whereas \(n\) can be exponentially large relative to binary-encoded masses. EFX also compares actual bundles, and a polynomial-size description of the necessary bundle support is not guaranteed by the discrete running time. That is the main thing a prover would need to resolve. Natural follow-ups are whether the price-ordered method yields a polynomial-size mass representation, whether EF1 is easier under the same encoding, and where the result breaks if the zero-or-\(p_r\) valuation restriction is relaxed.
This mirrors the goods branch of Theorem 8, including its EFX, maximum-welfare and PO guarantees; it does not attempt to mirror the chores branch or the paper’s other results.
The strongest case against is that the proposed mirror is not a direct high-multiplicity version of Theorem 8. The theorem assigns each of \(m\) distinct goods to one of \(n\) named agents. To obtain per-capita supplies, the mirror replaces each good with a growing stock of copies and must describe a distribution over whole, integral bundles. The theorem’s \(O(m\log m+mn)\) algorithm gives no compression guarantee in that representation: its running time can grow with the population, while the mirror’s input records only \(\tau\) preference types and rational masses. So the proposed polynomial-time result is a new question about EFX under mass allocation, not a consequence of the paper’s algorithm.
That leaves a narrow instance regime: repeated goods whose supply grows with the population, and households with identical, nonsatiating generalized-binary valuations. Many allocations of indivisible goods involve scarce, one-off objects, where scaling the stock changes the problem substantially. The repeated-goods regime is plausible, but this paper alone does not make it look broadly representative.
Those points make the mirror less immediate than the proponent suggests; they do not defeat it. The authors could reasonably recognize a large population receiving integral bundles of repeated goods as their allocation problem. Bundle masses preserve the relevant individual comparisons, and the paper supplies a named polynomial-time result with EFX, welfare maximization, and Pareto optimality. I cannot honestly argue that this anchor fails in every sensible scenario. The negative case is weak at precisely that point: the mirror may be difficult to compress, but whether it can be compressed is itself a worthwhile computational question.
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.