| paper | Approximate maximin shares for groups of agents |
| authors | Warut Suksompong |
| venue | MSS 2018 |
| filed under | fairalloc · shares |
| 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: \(\alpha=2/3\), guaranteed by an algorithm polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given indivisible goods \(G\), two groups, a distribution \(\mu\) over exactly two complete additive-utility types in group \(1\) and one type in group \(2\), and rational positive masses, define \(M_\theta=\max_{G=B_1\dot\cup B_2}\min\{u_\theta(B_1),u_\theta(B_2)\}\). Compute or approximate the maximum \(\lambda(\mu)=\max_{G_1\dot\cup G_2=G}\min_{\mu_{i,\theta}>0}u_\theta(G_i)/M_\theta\), in particular deciding whether \(\lambda(\mu)\ge 2/3\).
A high-multiplicity group-allocation model with indivisible goods, types \(t=(i,\theta)\), mass distribution \(\mu\), common bundle \(G_i\) for each group, additive utilities \(u_\theta\), and a universal maximin-share approximation objective over every positive-mass type.
Under universal fairness, the objective depends on \(\mu\) only through its positive support, so the proposed mirror may be a support quotient with little genuinely population-level computation.
fatal: False
The mirror covers the constructive approximation results in Theorems 1 and 5 and their finite-good obstructions, but not Theorems 3–4, Propositions 1–2, Theorem 6, exact maximin-partition computation, or the experiments.
My strongest case is a high-multiplicity version of the paper’s group-allocation problem in which goods remain indivisible. The population, not the goods or the outcome space, is continuous.
A type is a pair \((i,\theta)\), where \(i\) is the group to which the agent belongs and \(\theta\) is her complete additive utility vector over the goods. A society is a distribution \(\mu_{i,\theta}\) over finitely many such types. A large discrete society with \(N\mu_{i,\theta}\) copies of each type is its finite realization. The group label belongs in the type because two otherwise identical agents in different groups receive different bundles.
There are \(k\) groups and a finite set \(G\) of indivisible goods. An action is a partition \(G=G_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}G_k\), with every member of group \(i\) receiving \(G_i\). For each positive-mass type \((i,\theta)\), define
\[ M_\theta=\max_{(B_1,\ldots,B_k)}\min_{j\in[k]}u_\theta(B_j), \]
where the maximum ranges over complete partitions of \(G\) into \(k\) bundles. The continuous group-MMS objective is to find a partition maximizing
\[ \lambda(\mu)=\min_{\mu_{i,\theta}>0,\;M_\theta>0} \frac{u_\theta(G_i)}{M_\theta}. \]
Equivalently, given \(\beta\), the decision problem asks whether there is a partition satisfying \(u_\theta(G_i)\ge\beta M_\theta\) for every positive-mass type. This is a population continuization of the authors’ underlying problem: goods are still indivisible, groups still receive common bundles, utilities are still additive, and the fairness requirement is still universal over the represented agents. Only duplicate individuals have been replaced by mass.
My lead anchor is Theorem 1, proved in this paper. It states that when there are two groups with \((n_1,n_2)=(2,1)\), the best possible worst-case approximation ratio \(\alpha\) satisfies
\[ \frac23\le\alpha\le\frac34. \]
The upper bound uses four goods. The two agents in the first group have utility vectors \((3,1,2,2)\) and \((2,3,2,1)\), while the sole agent in the second group has \((3,2,2,1)\). Every agent has maximin share \(4\), but every allocation gives some agent utility at most \(3\). The lower bound is constructive. After normalizing every agent’s total utility to \(1\), if the singleton-group agent values some good at least \(1/3\), that good is assigned to her. Otherwise, the two agents in the first group take suitable goods worth at least \(1/3\) when available, and a round-robin allocation handles the remaining agents and goods. The proof guarantees every agent utility at least \(1/3\); since every maximin share is at most \(1/2\), this is a \(2/3\)-approximation. The algorithm is polynomial-time and does not require computing the exact maximin shares.
The corresponding continuous problem, which I would hand to a prover, is:
\[ \mathrm{CMMS}_{2,1}\text{-Approx} \]
Input: a finite set of indivisible goods \(G\); two groups; two positive-mass types in group \(1\), one positive-mass type in group \(2\); rational masses summing to \(1\); and nonnegative additive utilities for each type.
Output: a partition \(G=G_1\mathbin{\dot\cup}G_2\) such that every represented type \(\theta\) in group \(i\) receives \(u_\theta(G_i)\ge\frac23 M_\theta\).
The expected classification is Class A. Theorem 1’s proof lifts exactly after quotienting duplicate agents: a million copies of one utility vector create no new constraint beyond one representative of that type. The four-good upper-bound instance also lifts: assign positive mass to each of the three displayed types, and the \(3/4\) obstruction remains. Thus the continuous version preserves both the algorithmic guarantee and the substantive worst-case limitation.
This has a plausible high-multiplicity interpretation. Imagine two large university departments receiving indivisible rooms, laboratories, equipment, or research grants as department-level bundles. One department contains two recurring cohorts with different but internally homogeneous priorities; the other contains one recurring cohort. There may be hundreds of thousands of people but only three relevant complete types. The common-bundle constraint is not artificial: the institution allocates the goods to departments, not separately to every professor. The masses record the fractions of the population in those cohorts, while the fairness requirement protects every positive-mass cohort.
A second, genuinely broader anchor is Theorem 5, also proved in this paper. It says that with \(k\) groups, one group containing \(n_1\ge2\) agents and every other group containing one agent, there is always an allocation giving every agent at least
\[ \frac{2}{n_1+2k-3} \]
of her maximin share. The proof uses a threshold \(1/(n_1+2k-3)\): singleton-group agents first take sufficiently valuable goods when possible; agents in the exceptional group then take such goods; finally, a round-robin allocation is run on the remaining agents, beginning with the singleton groups.
Its continuous counterpart is:
\[ \mathrm{CMMS}_{r,1,\ldots,1}\text{-Approx} \]
Input: \(k\) groups, with \(r\ge2\) positive-mass types in group \(1\), exactly one positive-mass type in every other group, indivisible goods, rational masses, and additive utilities.
Output: a group allocation giving every positive-mass type at least
\[ \frac{2}{r+2k-3} \]
of its \(k\)-way maximin share.
This should also be Class A, in time polynomial in the number of goods, groups, distinct types, and encoding length. Again, the algorithm operates on one representative per type, so a group may contain an enormous population while \(r\) remains small. This is not merely a divisible-goods relaxation: the output is still a discrete partition, and all the combinatorial conflicts from the paper remain.
The main qualification is that the paper’s parameters \(n_i\) count named agents, whereas the mirror replaces them by numbers of distinct positive-mass types. I think this is precisely the legitimate high-multiplicity interpretation: duplicate agents impose identical constraints and are mathematically redundant. Still, the mirror becomes much less compelling if the intended application has many genuinely distinct utility vectors, or if fairness should depend on the mass of a dissatisfied cohort rather than protect every positive-mass type.
There is no numbered NP-hardness or NP-completeness theorem in the paper, so I would not manufacture a hardness anchor. The paper does state, outside a numbered theorem, that computing an exact maximin partition is NP-hard via Partition, with a PTAS but no FPTAS unless \(\mathrm{P}=\mathrm{NP}\). That hardness remains relevant because the goods stay indivisible; it is not dissolved by continuization. The positive case above therefore covers the paper’s constructive approximation results, not exact maximin computation, Theorems 3–4, or the impossibility results of Propositions 1–2 and Theorem 6.
The natural follow-up questions are whether the \(2/3\) guarantee can be improved in the continuous \(2,1\)-type regime, whether the exact worst-case ratio is \(3/4\), and how the guarantees depend on the number of distinct types rather than the number of people. Those are faithful continuations of the authors’ questions, not replacements by a different divisible-allocation problem.
The strongest objection is that both proposed mirrors make the population masses mathematically inert.
Let \(S_i(\mu)\) be the support of the types in group \(i\). The proposed objective is
\[ \lambda(\mu)= \max_{(G_1,\ldots,G_k)} \min_i\min_{\theta\in S_i(\mu)} \frac{u_\theta(G_i)}{M_\theta}. \]
It depends on \(\mu\) only through its support. Any two societies with the same positive-mass types have exactly the same feasible allocations and the same optimum, regardless of whether a type represents \(10^{-12}\) or \(99\%\) of the population. Replacing each type by a million identical agents therefore gives a lossless quotient of the original instance, not a continuous relaxation.
This defeats the proposed reading of Theorem 1. With two types in one group and one in the other, the alleged continuous instance is simply the original three-agent instance with labels renamed. The \(2/3\) algorithm never uses masses, and the \(3/4\) obstruction survives solely because the three utility vectors remain present. Allowing more types does not help: the problem is then just the original problem after deduplicating agents with identical utility vectors. With finitely many goods, duplicates impose no additional constraint.
Theorem 5 has the same defect more clearly. Its parameter \(n_1\) counts independent utility constraints, not population mass. In the proposed version, \(r\) is therefore the number of distinct types, and
\[ \frac{2}{r+2k-3} \]
is simply the paper’s bound with “agents” replaced by “distinct utility vectors.” If \(r\) instead means the total population, the theorem has no coherent limit: duplicating a type can make \(r\) arbitrarily large without changing the allocation problem at all. The round-robin proof is counting heterogeneous taste constraints, not processing population mass.
A continuous type space does not repair this. Under the paper’s universal fairness requirement, the distribution still matters only through its support. If one makes the support genuinely continuous, one obtains a robust requirement over every type in the support, not a population problem. If the mass is made relevant through an average or quantile objective, the universal maximin-share guarantee has been replaced by a different fairness notion. For example, one could require
\[ \frac{1}{\mu_i}\sum_{\theta} \mu_{i,\theta} \mathbf{1}\!\left[u_\theta(G_i)\ge \beta M_\theta\right] \ge p_i. \]
That is a legitimate weighted coverage problem over indivisible goods, but for \(p_i<1\) it no longer mirrors either theorem: a type causing the paper’s obstruction can simply have negligible mass. At \(p_i=1\), masses disappear again. The paper itself presents “a certain fraction of agents in each group” as a future relaxation, so this is best understood as a new democratic-fairness problem, not a continuization of Theorems 1 or 5.
Thus the proposed anchors do not establish a worthwhile continuous-population contribution. They are support-compressed restatements of finite fair division. But the universal negative claim is not airtight: the mass-sensitive democratic variant is natural, computationally nontrivial, preserves indivisible goods and common group bundles, and is explicitly foreshadowed by the paper. My honest verdict is therefore against these particular mirrors, not against every conceivable mirror of the paper.
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.