| paper | On approximately fair allocations of indivisible goods |
| authors | R. Lipton, E. Markakis, Elchanan Mossel, A. Saberi |
| venue | SIGECOM 2004 |
| 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: The continuous minimum envy-ratio problem admits a \(\mathrm{PTAS}\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given \(r\) good types with utilities \(w_j\in\mathbb{Q}_{>0}\) and per-capita supplies \(q_j\in\mathbb{Q}_{\ge0}\), consider a unit-mass population of identical agents with additive utility \(u(b)=\sum_{j=1}^r w_jb_j\) for integral bundles \(b\in\mathbb{Z}_{\ge0}^r\). Choose masses \(x_b\ge0\) satisfying \(\sum_bx_b=1\) and \(\sum_b b_jx_b=q_j\) for every \(j\), minimizing \(\rho(x)=\max_{x_b>0}u(b)/\min_{x_b>0}u(b)\), with value \(+\infty\) if a used bundle has zero utility.
A high-multiplicity configuration-scheduling model with one agent type of mass \(1\), integral bundle configurations \(b\), continuous assignment masses \(x_b\), per-capita good supplies \(q_j\), and a max/min bundle-utility objective.
Because all agents share one utility type, the proposed \(x_b\) variables may be viewed as fractional multiplicities of interchangeable machines rather than a substantively continuous population; the proponent does not fully resolve that boundary-of-scope concern.
fatal: False
The mirror covers Theorem 8's envy-ratio PTAS and fixed-player FPTAS, while leaving the bounded-envy results, cake-cutting protocol, oracle lower bound, truthfulness results, and other approximation statements unaddressed.
There is a credible continuous mirror here, and the strongest anchor is the paper’s scheduling-style special case rather than its cake-cutting section.
The lead anchor is Theorem 8, proved in this paper. It states: “There is a PTAS for the envy-ratio problem when all players have the same utility for each good. Furthermore, when the number of players is constant, there is an FPTAS.” The underlying problem is to allocate indivisible goods so as to minimize the ratio between the largest and smallest bundle utility. The paper explicitly identifies this with scheduling jobs on identical machines, where job sizes are utilities and machine loads are bundle values.
A natural continuous-population version is the following.
Call it \(\mathrm{Minimum\ Envy\mbox{-}Ratio}_\infty\). An instance consists of \(r\) good types, with utility \(w_j\in\mathbb{Q}_{>0}\) for type \(j\), and per-capita supplies \(q_j\in\mathbb{Q}_{\ge 0}\). The population has unit mass and consists of one agent type: every agent has the same additive utility \(u(b)=\sum_{j=1}^r w_jb_j\) for an integral bundle \(b=(b_1,\ldots,b_r)\in\mathbb{Z}_{\ge0}^r\).
A solution is a mass allocation \(x=(x_b)\), where \(x_b\ge0\) is the mass of agents receiving exactly bundle \(b\), satisfying \(\sum_b x_b=1\) and \(\sum_b b_jx_b=q_j\) for every good type \(j\). Thus agents receive indivisible bundles; only the population assignment is continuous. Define
\[ \rho(x)= \frac{\max\{u(b):x_b>0\}} {\min\{u(b):x_b>0\}}, \]
with value \(+\infty\) if some used bundle has zero utility. The problem is to find a feasible \(x\) minimizing \(\rho(x)\), or, in decision form, to determine whether some allocation has \(\rho(x)\le R\).
This is not fractional allocation of goods. The variables \(x_b\) say what fraction of agents receive each integral bundle. If \(q_j=a_j/N\), then \(N\) agents and \(a_j\) indivisible copies of good type \(j\) give exactly the finite realization of the instance. Conversely, any finite allocation induces \(x_b=N_b/N\). The continuous problem is therefore the high-multiplicity form of the paper’s problem, not a different divisible-goods objective.
The regime is quite plausible: a large population of interchangeable processors, service units, households, or machines receives many repeated classes of indivisible jobs or goods. The number \(N\) of agents is very large, while the number \(r\) of distinct good types and utility values is small or moderate. This is precisely the identical-machine interpretation already used by the authors, now expressed in per-capita quantities. The single population type is not an artificial loss of generality for this anchor: “all players have the same utility for each good” is exactly the hypothesis of Theorem 8.
I would expect this mirror to be Class A, probably admitting a PTAS and potentially stronger fixed-\(r\) algorithms. Let \(L=\sum_jq_jw_j\) be the average utility per unit population. The rounding argument behind Theorem 8 can be applied to the good-type values. After rounding, there are only constantly many relevant utility levels for any fixed approximation parameter, and the continuous allocation is described by a configuration LP:
\[ \sum_bx_b=1,\qquad \sum_bb_jx_b=q_j,\qquad \ell\le u(b)\le h \]
for the configurations used. The individual configurations remain integral, but their masses are continuous. Thus the high-multiplicity version removes the need to count agents one by one while retaining the combinatorial difficulty of assigning indivisible goods. Column generation or explicit enumeration after rounding should make the continuous optimization accessible.
The further questions are meaningful rather than cosmetic: whether the optimum is exactly computable in polynomial time; how the complexity depends on \(r\), the number of distinct utility levels, and the encoding of \(q_j\); whether fixed \(r\) gives an FPTAS or an exact algorithm; and how quickly finite-\(N\) allocations converge to the continuous optimum. The finite-to-continuous dictionary is especially clean: rational mass allocations can be implemented exactly whenever \(N\) clears their denominators, while continuous solutions can provide additive or asymptotic guarantees for large finite populations.
This mirror deliberately covers only Theorem 8. I would not claim that the paper’s Theorems 3 and 5 already provide the mirror: those continuize the cake or outcome space while retaining finitely many players. Nor would I use Theorem 6 as the main anchor, since its exponential value-query lower bound is driven by arbitrary non-additive utility oracles and only two players, rather than by population multiplicity.
The weakest point is that the lead mirror uses a degenerate population distribution: \(\mu\) has one agent type. An opposing reader can reasonably say that it captures high-multiplicity scheduling more clearly than heterogeneous social choice. But that is also why it is defensible. The paper itself presents identical machines as an equivalent form of its envy-ratio problem, and the proposed model preserves both parts that matter—integral bundles and the max/min fairness objective—while replacing only the large list of interchangeable agents by their mass distribution. That is a genuine continuous-population analogue of Theorem 8, even if it does not claim to continuize the paper’s full heterogeneous fair-division model.
Theorem 8 is the proponent’s strongest anchor, and the negative case against it is necessarily limited. It is a numbered computational result, and its identical-machine interpretation gives a genuinely plausible high-multiplicity scenario. I cannot honestly object that the answer might remain similar, that high-multiplicity scheduling already exists, or that the paper has only one player type.
The best objection is that the proposed formulation continuizes the allocation rather than the society. Under Theorem 8’s hypothesis, every player has exactly the same utility vector, so the population distribution is the fixed singleton \(\mu=(1)\). In a finite instance, named players are already irrelevant: an allocation can be represented by integer bundle counts \(N_b\), and the proposed variables are simply \(x_b=N_b/N\). Replacing integer counts by real masses is therefore a convexification of the assignment outcome. The input society itself has not acquired a meaningful distribution of types.
The natural repair is to introduce genuine player types \(t\), with masses \(\mu_t\) and valuations \(w_{t,j}\). But that abandons the anchor’s premise that all players have identical utilities, and hence abandons the scheduling equivalence and Theorem 8. If the added types have identical relevant utilities, they are not distinct types under the programme’s definition; if they differ, one has formulated a new heterogeneous fair-division problem rather than a continuous version of the theorem. Treating assigned bundles as “types” does not repair this: those are output classes, so the continuity remains in the outcome.
The per-capita supplies \(q_j\) make the model a perfectly coherent high-multiplicity configuration-scheduling problem. They do not, by themselves, make it a continuous-population problem in the programme’s central sense. The resulting LP is a standard convexified assignment/configuration formulation whose columns are integral bundles; for fixed resource constraints, an extreme solution uses only a small number of bundle columns. The continuum provides fractional multiplicities of interchangeable machines, not a substantive population geometry.
That is a real scope objection, but it does not defeat the anchor decisively. The programme explicitly permits singleton type spaces and co-modification of supplies, and this mirror has a clean finite-to-continuous correspondence. Thus the honest conclusion is that the negative case is weak: one can argue that this is outcome relaxation wearing a population interpretation, but a thoughtful reader can reasonably accept it as a legitimate high-multiplicity mirror of Theorem 8.
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.