| paper | Fairly Allocating Goods in Parallel |
| authors | — |
| venue | AAMAS 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6.6
statement extracted from the paper’s text layer
Given rational good-class supplies \(\rho_g\), inherent values \(w_g\), a finite type set \(\Theta\) with rational masses \(\mu_\theta\), valuation masks \(A_\theta\), and a bundle-size bound \(K\), let \(y_{\theta,b}\) be the mass of type \(\theta\) receiving integral bundle \(b \in \mathbb{Z}_{\ge 0}^q\) with \(\lVert b \rVert_1 \le K\). Require \(\sum_b y_{\theta,b}=\mu_\theta\) and \(\sum_{\theta,b} b_g y_{\theta,b}=\rho_g\). Output a finite-support law satisfying support-wise \(\mathrm{EF1}\) and population Pareto optimality, where for every supported pair either \(u_\theta(b) \ge u_\theta(b')\) or some integral good can be removed from \(b'\) to make that inequality hold, and no measure-preserving reassignment weakly improves every agent while strictly improving positive mass.
A high-multiplicity restricted-additive fair-division model with type masses \(\mu\), repeated indivisible good supplies \(\rho\), integral bundle configurations \(b\), and allocation-law variables \(y_{\theta,b}\); the task is to find support-wise \(\mathrm{EF1}\) and population \(\mathrm{PO}\).
The ranked-copy matching does not automatically compress to a capacitated formulation whose marginals can be coupled into complete bundles with support-wise mathrm{EF1}; a configuration space of size binom{q+K}{K} may be needed.
fatal: False
The primary mirror covers the allocation result in Theorem 6.6 and its binary restriction in Corollary 6.7, while leaving the fixed-order Round-Robin hardness, small-agent query results, approximation result, verification results, and most payment results outside scope.
The strongest positive case is narrow but genuine: Theorem 6.6 admits a high-multiplicity mirror in which both agents and repeated goods are represented compactly, while each microscopic allocation remains integral. I would make this the lead anchor.
The natural regime is large-scale disaster-relief or workload allocation. There may be millions of recipient agents, but only a moderate number of recurring need profiles: for example, households that value meals, water, medical kits, or tarps according to one of \(\tau\) eligibility patterns. Likewise, goods come in a finite catalogue of item classes with many repeated units. This is close to the paper’s own motivation, especially its FEMA example. The important regime is \(N\gg \tau\), with agents of the same type having identical valuation masks and all other relevant parameters.
Call the problem Mass-EF1-PO\(_\infty\) for Restricted-Additive Goods.
An instance contains:
A type-\(\theta\) agent receiving an integral bundle \(b\in\mathbb Z_{\ge0}^{q}\) has utility
\[ u_\theta(b)=\sum_{g\in A_\theta}w_g b_g. \]
The action variable is a finite-support allocation law \(y_{\theta,b}\): the mass of type-\(\theta\) agents receiving the whole, indivisible bundle \(b\). It must satisfy
\[ \sum_b y_{\theta,b}=\mu_\theta \]
and
\[ \sum_{\theta,b}b_g y_{\theta,b}=\rho_g \]
for every good class \(g\). Thus \(y\) is not fractional ownership of goods. It is a distribution over complete integral bundles. If all data are rational, clearing denominators produces a finite population with \(N\mu_\theta\) agents of type \(\theta\) and \(N\rho_g\) copies of good \(g\).
The output is an allocation law \(y\) satisfying support-wise EF1: for every two positive-mass classes \((\theta,b)\) and \((\theta',b')\), there is a whole good unit \(g\) in \(b'\) such that
\[ u_\theta(b)\ge u_\theta(b'-e_g), \]
where \(e_g\) removes one indivisible copy of \(g\). It must also be Pareto optimal in the population sense: there is no alternative allocation law \(y'\), together with a measure-preserving reassignment of agents to new whole bundles, that weakly improves every agent and strictly improves a positive mass of agents. The objective is a search objective: output such a \(y\), rather than optimize welfare.
This is a faithful mirror of Theorem 6.6, which is proved in this paper. The theorem states that Algorithm 1 returns an EF1 and Pareto-optimal allocation for restricted-additive valuations with \(t\) inherent item values, using \(O(\log^2(mn))\) parallel time and \(O(m^{5.5+t}n^{5.5})\) processors. Its binary-valuation consequence is the named Corollary 6.7, also proved here, which places the problem in RNC.
The reason the theorem appears continuizable is structural. Algorithm 1 creates ranked copies of every agent and solves a maximum-weight perfect matching. In the mass version, copies of agents with the same type become capacities: each type \(\theta\) has mass \(\mu_\theta\) in every rank slot, and each good class has supply \(\rho_g\). The matching becomes a capacitated transportation or flow problem. The exchange argument behind Lemma 6.3 is type-blind, so it should survive this replacement: if a type’s slot-\(c\) item were worse than another type’s slot-\(c+1\) item, the same local exchange would improve the matching. The resulting slot ordering gives EF1, while assigning every valued good to a type that values it gives the restricted-additive Pareto guarantee.
I would therefore expect Mass-EF1-PO\(_\infty\) to be Class A, probably solvable in time polynomial in \(q,\tau,K,t\) and the encoding length, rather than in the expanded population size \(N\). The nontrivial point is that one cannot justify this merely by clearing denominators: \(N\) may be exponentially large in the input length. The research question is whether the paper’s matching construction has a genuinely compressed capacitated implementation and a compact decomposition into whole-bundle configurations.
A useful secondary anchor is Theorem 7.2, proved by the authors in the full version [9]. It gives an NC algorithm for Constrained Payments. Its population mirror is Mass-Constrained Payments\(_\infty\):
An agent type \(\theta\) consists of a valuation \(v_\theta\), its current integral bundle \(B_\theta\), and any payment-relevant parameters; \(\mu_\theta\) is its population mass. Given an integral payment cap \(H\) and type-level implications
\[ q_\theta>x \Longrightarrow q_{\theta'}>y, \]
find integer payments \(q_\theta\in\{0,\ldots,H\}\) such that
\[ v_\theta(B_\theta)+q_\theta \ge v_\theta(B_{\theta'})+q_{\theta'} \]
for every pair of positive-mass types, while satisfying every implication. One may additionally minimize total normalized subsidy \(\sum_\theta\mu_\theta q_\theta\); the feasibility version is exactly the paper’s problem.
This is a narrower Class A candidate. The paper’s payment-rejection graph has one row per agent and one vertex per possible payment. In the mirror it has \(\tau\) rows, and reachability gives the feasible type-level payment vector. The mass does not affect feasibility—pairwise envy is multiplicity-blind—but it matters for total subsidy and for the interpretation as a common payment policy over a large population. The expected complexity is polynomial when \(H\) or the threshold grid is polynomially bounded, matching Corollary 7.3. With binary-encoded, exponentially large payment caps, the paper does not by itself provide a strongly polynomial guarantee.
I would not try to mirror Theorem 5.1 as a positive anchor. Fixed-order Round-Robin depends essentially on the identity and priority position of each agent. Making priority part of the complete type would usually make \(\tau\) grow with \(N\), destroying the high-multiplicity regime. That result is best left outside the proposed mirror.
The weakest point is the need for a repeated-inventory regime. If one insists that only the population grows while the paper’s finite set of indivisible goods remains fixed, EF1 eventually becomes dominated by empty bundles and the model loses its intended meaning. My mirror therefore scales repeated good units together with the population. This is not outcome-space continuity—no individual receives a fractional good—but it is an extension of the paper’s finite model, not a literal limit with a fixed item set. The remaining questions are whether the compressed matching proof can be made fully rigorous, whether exact finite-population rounding preserves support-wise EF1 and PO, and where tractability fails when the number \(t\) of inherent values or the number \(\tau\) of valuation types becomes large.
The strongest negative case is that the proponent has not actually produced a direct mirror of either theorem. But I cannot honestly make the universal “no worthwhile scenario” claim stick: Theorem 6.6 survives the strongest fidelity test.
For Theorem 6.6 and Corollary 6.7, a population-only limit with the paper’s fixed set of \(m\) goods degenerates. Once \(n\ge m\), one can give every good to a different agent, so every bundle is a singleton or empty. EF1 is then automatic: removing the other agent’s only good leaves value \(0\). Pareto optimality can be obtained by assigning each good to an agent who values it. Thus the literal high-multiplicity limit does not preserve the problem’s content.
The proponent’s repair is to scale the inventory with the population. That is a substantial extension, but not necessarily an illegitimate one. With repeated good classes and repeated valuation masks, clearing denominators really does recover a finite restricted-additive instance. The proposed law \(y_{\theta,b}\) retains whole indivisible bundles, and support-wise EF1 is equivalent to finite EF1 after rational cloning. This defeats the obvious objections about fractional goods, atomless agents, and loss of identity.
The remaining objection is technical rather than fundamental. Algorithm 1 matches each item to a particular agent copy in a particular rank bucket. Compressing those copies into capacities does not automatically produce a distribution over complete bundles. A capacitated matching gives marginal assignments to rank slots; it still requires a coupling theorem showing that those marginals can be assembled into bundles whose entire support satisfies EF1. If one replaces support-wise EF1 by an average condition, one has changed the fairness notion. If one retains it by enumerating bundle configurations, the configuration space can be as large as \(\binom{q+K}{K}\). Hence the claimed Class-A result does not follow from Theorem 6.6. But this is an unresolved algorithmic obligation, not a reason that the mirror cannot be worthwhile. A successful coupling or configuration argument would be a legitimate high-multiplicity extension of the theorem.
Theorem 7.2 is more vulnerable. The paper’s payment rows are indexed by named agents, and envy depends on the agent’s current bundle. A valuation type \(\theta\) that receives several different bundles cannot generally receive one common payment \(q_\theta\). The faithful type is \((\theta,b)\), including the bundle and any constraint-relevant parameters. If many agents share such a complete state, they can be compressed; if they do not, the supposed population multiplicity disappears. Likewise, arbitrary constraints such as “agent \(A\) must not be paid more than agent \(B\)” survive compression only when they are invariant across clones. Otherwise the type system must remember the identities that the mirror was supposed to remove.
There is also a quantitative gap. Theorem 7.2 is pseudo-polynomial in the payment cap \(m\Delta\), and Corollary 7.3 is polynomial in the expanded \(n,m,\Delta\), not in the bit-length of a compressed high-multiplicity instance. After cloning, \(m\Delta\) may be exponentially large in the input describing \(\rho\) and \(\mu\). If the cap \(H\) is bounded polynomially in the number of compressed types, reachability on the \(\tau H\)-vertex graph is merely an ordinary finite type quotient. If \(H\) is binary-encoded and large, the paper gives no compressed algorithm. The proposed weighted subsidy objective is also new: mass does not affect the theorem’s feasibility question at all.
Thus the negative case can reject the payment anchor as presently overstated, and can show that the fixed-inventory version of the EF1 anchor is vacuous. It cannot defeat the better repeated-agent/repeated-good formulation of Theorem 6.6. That formulation passes rational-clone equivalence and has a plausible disaster-relief interpretation. The honest verdict is therefore that the universal negative case is weak: Theorem 7.2 is not yet a convincing mirror, but Theorem 6.6 remains a worthwhile continuous-population extension.
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.