| paper | Achieving Proportionality up to the Maximin Item with Indivisible Goods |
| authors | A. Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin |
| venue | AAAI 2021 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 11
statement extracted from the paper’s text layer
Given rational additive values \(v_t(j)\ge 0\) for five valuation types \(t\in T\), masses \(\mu_t=1/5\), and recurring indivisible good types \(j\in M\) with per-capita supplies \(\rho_j=1/5\), choose masses \(y_{t,B}\ge 0\) for integral bundles \(B\subseteq M\) satisfying \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B\ni j}y_{t,B}=\rho_j\). With \(y(B)=\sum_t y_{t,B}\) and \(\delta_t(y)=\max_{B:y(B)>0}\min_{j\in B}v_t(j)\), find a feasible allocation such that \(v_t(B)+\delta_t(y)\ge\sum_j\rho_jv_t(j)\) for every \(t,B\) with \(y_{t,B}>0\), taking the minimum of an empty bundle as \(0\).
A high-multiplicity fair-division model with finitely many complete valuation types, mass assigned to integral configurations \(B\subseteq M\), per-capita good capacities \(\rho_j\), and a feasibility objective enforcing \(\mathrm{PROPm}\) through the support-based maximin witness \(\delta_t(y)\).
The support maximum is discontinuous: a bundle carried by arbitrarily small positive mass can witness every type, so the prover must justify this support semantics and its relation to finite replication.
fatal: False
The mirror covers the constructive \(\mathrm{PROPm}\) allocation result for five-agent additive valuations and leaves the other existence theorems, average-EFx proposal, Pareto-efficiency question, and non-polynomial subset-sum bottleneck untreated.
The strongest honest positive case is a qualified one, centred on Theorem 11, proved in this paper.
The paper’s theorem says: every instance with five agents and additive valuations has a \(\mathrm{PROPm}\) allocation. After normalizing \(v_i(M)=1\), this means there is a partition \(X=(X_1,\ldots,X_5)\) such that every agent \(i\) satisfies \(v_i(X_i)+\max_{k\ne i}\min_{j\in X_k}v_i(j)\ge 1/5\). The proof is constructive: it recursively builds the bundles \(D,C,B,A,E\) from close-to-proportional sets and resolves the possible valuation patterns through Lemmas 13–22. This result is proved here, not cited. The paper does not claim that the resulting procedure is polynomial-time.
A natural continuous mirror is the following.
Take a unit-mass population with five complete valuation types \(T=\{1,\ldots,5\}\), with \(\mu_t=1/5\). There are \(m\) recurring indivisible good types \(M\). Each agent may receive an integral bundle \(B\subseteq M\), with at most one copy of each good type. Each good type \(j\) has per-capita supply \(\rho_j=1/5\). Thus, for a finite replication with \(5K\) agents, there are \(K\) agents of each valuation type and \(K\) copies of every good type. The population and supplies both grow, while the number of valuation types remains \(\tau=5\).
Let \(y_{t,B}\) be the mass of type \(t\) receiving bundle \(B\). It must satisfy \(\sum_B y_{t,B}=\mu_t\) and \(\sum_{t,B:j\in B}y_{t,B}=\rho_j\) for every good \(j\). Every individual unit of mass still receives an indivisible bundle; only the allocation of identical agents across bundles is fractional.
For each type \(t\), define \(\delta_t(y)=\max_{B:\sum_s y_{s,B}>0}\min_{j\in B}v_t(j)\), with the minimum of an empty bundle taken as zero. The continuous problem is:
Given \(v_t(j)\), \(\mu\), and \(\rho\), find a feasible mass allocation \(y\) such that, for every \(t\) and every bundle \(B\) with \(y_{t,B}>0\),
\(v_t(B)+\delta_t(y)\ge \sum_j\rho_jv_t(j)\).
The right-hand side is the proportional share of a type-\(t\) agent. In the five-type replication above, normalizing \(\sum_jv_t(j)=1\) makes it \(1/5\), exactly matching Theorem 11. Clearing rational denominators converts a mass allocation into a finite allocation of repeated agents and repeated indivisible goods. Conversely, finite replicated allocations induce such mass vectors.
This is a credible mirror because it preserves the paper’s essential question: which integral bundles can be assigned so that each agent is proportionally satisfied up to a maximin item? It does not replace indivisible goods by divisible goods, and it does not average a type’s bundle before checking fairness. The type is a complete valuation and eligibility profile, so repeated agents are genuinely indistinguishable.
I would expect the approximate or fixed-\(\tau\) version to be a plausible Class A problem, perhaps through a configuration LP. The exact version is more delicate: the bundle-support and maximin conditions retain subset-sum-like pricing, precisely the obstacle the authors mention when discussing close-to-proportional sets. Thus the exact problem could become a useful Class C boundary rather than automatically becoming easy. It is not an obvious hardness-transfer case, because the paper proves universal existence for five agents and does not prove hardness of \(\mathrm{PROPm}\) allocation itself.
The weakest point is that Theorem 11 concerns exactly five named agents, whereas the proposed mirror concerns an arbitrarily large replicated population. Its existence does not automatically lift; proving that lift is essentially a new theorem related to the authors’ conjecture for more than five agents. Moreover, the paper has no numbered NP-hardness, polynomial-time, FPT, or approximation theorem. Its subset-sum statement appears only in the conclusion and is not a numbered anchor. Therefore, under the programme’s strict computational-anchor rule, this is a substantively strong mirror but not a fully compliant anchored case.
The proponent’s only anchor is Theorem 11, and it fails the programme’s computational-anchor test. The theorem proves existence of a \(\mathrm{PROPm}\) allocation for exactly five agents; it asserts no complexity, approximation, parameterized, or algorithmic result. The construction is explicitly not polynomial-time. The conclusion’s observation that finding a close-to-proportional set is at least as hard as subset sum concerns a subroutine of their proof, not the complexity of finding a \(\mathrm{PROPm}\) allocation. Thus there is no named computational result here to continuize.
The proposed high-multiplicity model also changes the theorem’s instance regime. With one unit of each valuation type, it is merely the five-agent allocation problem rewritten as mass notation. With \(K\) copies of each type and good, it becomes a problem with \(5K\) agents—the very arbitrary-agent extension that the paper only conjectures. Theorem 11 provides no result for that regime. This is not an objection that the answer might be easy or hard; it is that the proposed question is not a continuous version of the proved result. It is a new high-multiplicity fair-division problem.
More seriously, \(\mathrm{PROPm}\)'s defining correction is badly behaved under population continuization. In the proposed model,
\[ \delta_t(y)=\max_{B:y(B)>0}\min_{j\in B}v_t(j). \]
A bundle assigned to mass \(\varepsilon>0\) contributes exactly as much to \(\delta_t\) as a bundle assigned to substantial mass. Hence one exceptional bundle can improve every type’s fairness guarantee while being assigned to an arbitrarily small population. Formally, one may have
\[ \delta_t(y^\varepsilon)\geq \min_{j\in B}v_t(j) \]
for every \(\varepsilon>0\), while \(y^\varepsilon\) converges to \(y^0\) in mass and \(B\) disappears from the support at \(\varepsilon=0\), causing \(\delta_t\) to drop discontinuously. In the original five-agent problem, the witnessing bundle has a real owner and mass \(1/5\). In the continuum, it can be supplied by an asymptotically null class. The fairness condition is therefore controlled by support accidents rather than aggregate population behaviour.
The obvious repairs do not preserve the paper’s object. Requiring a witnessing bundle to have at least \(\kappa\) mass introduces a new granularity parameter. Replacing the maximum by an average or quantile produces a different notion, closer to the paper’s average-EFx discussion. Restricting each type to one bundle avoids the pathology only by collapsing back to a finite partition problem. Using an essential supremum does not help: every positive-measure exceptional bundle remains visible.
Nor is the configuration-LP suggestion yet persuasive. The constraints are conditional on \(y_{t,B}>0\), while \(\delta_t\) is a maximum over the support. This is a disjunctive, support-sensitive condition, not an ordinary linear configuration system with a straightforward pricing oracle. Fixing the support or the witness bundle restores linearity only after making a discrete choice; the subset-sum structure remains.
A recurring-goods/high-multiplicity fair-division problem could certainly be worth studying in its own right. That is the strongest concession to the positive case. But it would be a new problem, not a computational mirror of this paper’s only substantive theorem, and the maximin-item objective has no stable population limit without changing its meaning. Under the programme’s strict standard, the negative case therefore wins: this paper supplies no worthwhile continuous computational mirror.
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.