| paper | Ordinal Maximin Guarantees for Group Fair Division |
| authors | Pasin Manurangsi, Warut Suksompong |
| venue | IJCAI 2024 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.4
Given \(m\) indivisible items, \(g\) groups, a finite-support rational distribution \(\mu\) over types \(t=(i,v_t)\) with additive \(v_t\in\mathbb{Q}_{\ge0}^m\), and \(p\), output an ordered partition \(A=(A_1,\ldots,A_g)\) such that every type with \(\mu_t>0\) satisfies \(v_t(A_i)\ge\theta_t(p)\), where \(\theta_t(p)=\max_{\{B_1,\ldots,B_p\}\in\Pi_p(M)}\min_j v_t(B_j)\); for \(r_i\) positive-mass types in group \(i\) and \(p=80\sum_i\lceil\log(r_i+1)\rceil\), find such an \(A\) in randomized polynomial time with success probability at least \(2/3\).
A support-compressed high-multiplicity model with additive utility types \(t=(i,v_t)\), rational masses \(\mu_t\), an integral ordered item partition \(A\) as the decision variable, and exact constraints \(v_t(A_i)\ge\theta_t(p)\) for every positive-mass type; the masses encode multiplicity but exact feasibility uses only support.
For exact \(V_p=0\), the numerical values of \(\mu_t\) are irrelevant, so the mirror is support-compressed rather than mass-sensitive and its logarithmic parameter tracks type counts \(r_i\), not represented population size.
fatal: False
It directly mirrors the constructive guarantees of Theorems 3.4 and 3.5 after replacing group populations by positive-mass support counts; it leaves the non-computational lower bounds, Lemma 5.3 as a standalone result, and the EF/MMS trade-off untouched.
The strongest honest mirror is a high-multiplicity version of the paper’s own group fair-division problem. It keeps the items indivisible and keeps the group bundle structure intact; only the population becomes a distribution over utility types.
Let \(M=[m]\) be the indivisible items and let there be \(g\) groups. A type is a complete pair \(t=(i,v_t)\), where \(i\) is the group to which the agent belongs and \(v_t\in\mathbb{Q}_{\ge 0}^m\) is the agent’s additive utility vector. The society is a distribution \(\mu=(\mu_{i,t})\), where \(\mu_{i,t}\) is the population fraction of group \(i\) having type \(t\), and \(\sum_{i,t}\mu_{i,t}=1\).
For an integer \(p\), define the type’s ordinal MMS threshold by
\[ \theta_t(p)= \max_{\{B_1,\ldots,B_p\}\in\Pi_p(M)} \min_{j\in[p]} v_t(B_j). \]
An allocation is an ordered partition \(A=(A_1,\ldots,A_g)\) of \(M\), with \(A_i\) assigned to group \(i\). Its violated population mass is
\[ V_p(A;\mu)= \sum_{i,t}\mu_{i,t}\, \mathbf{1}\!\left[v_t(A_i)<\theta_t(p)\right]. \]
My lead problem is therefore:
\[ \textsf{Continuous Ordinal-MMS Group Allocation}_\infty: \]
given \(M\), the groups, the finite-support distribution \(\mu\), the additive utilities, and \(p\), find an item partition \(A\) minimizing \(V_p(A;\mu)\). The exact mirror of the paper’s problem is the feasibility version \(V_p(A;\mu)=0\): every positive-mass type must receive its group’s bundle at least at its own \(1\)-out-of-\(p\) MMS.
This is not outcome-space continuization. Items remain indivisible, allocations remain integral, and the MMS threshold is unchanged. The only continuous object is the population.
A convincing regime is a city, university, or public agency allocating indivisible supplies, facilities, equipment, or service slots to neighbourhoods or departments. Each group contains many residents or employees, but their needs fall into a finite catalogue of recurring profiles. For example, a group may contain thousands of residents but only \(r_i=20\) distinct utility types over the available item categories. The mass \(\mu_{i,t}\) is the fraction of residents of each profile.
This is precisely the high-multiplicity regime. A finite profile with \(n_{i,t}\) agents maps to \(\mu_{i,t}=n_{i,t}/n\); conversely, rational masses can be expanded into a finite profile. If two agents have the same group and utility vector, they are indistinguishable for this problem and should be represented by one type with larger mass. That is not a distortion: it is exactly what high multiplicity means.
My strongest anchor is Theorem 3.4, proved in this paper, although its proof uses the cited Lemmas 3.1 and 3.3. The theorem says that for group sizes \(n_1,\ldots,n_g\), with
\[ p=80\left(\lceil\log(n_1+1)\rceil+\cdots+\lceil\log(n_g+1)\rceil\right), \]
an MMS allocation always exists, and a randomized polynomial-time algorithm finds one with probability at least \(2/3\).
For the continuous problem, let \(r_i\) be the number of positive-mass types in group \(i\). Run the theorem on one representative agent for each type, replacing \(n_i\) by \(r_i\). It yields an allocation satisfying every positive-mass type whenever
\[ p=80\sum_{i=1}^g\lceil\log(r_i+1)\rceil. \]
The running time is polynomial in \(m\), \(\sum_i r_i\), and the encoding length of the utilities; it is independent of the total number of agents represented by the masses. Thus this is a genuine Class A result for the promised logarithmic-\(r_i\) regime. It is also recognisably the authors’ problem: same groups, same indivisible items, same additive utilities, same ordinal MMS guarantee, and the same requirement that every member of a group be served by its group’s bundle.
The second anchor is Theorem 5.4, a result of this paper, which states that for two equal-sized groups,
\[ p_{\mathrm{MMS}}(n',n') \ge 2+\left\lfloor\frac{\log n'}{2}\right\rfloor. \]
The corresponding continuous worst-case question is:
\[ P_\infty(r)= \min\left\{ p: \begin{array}{l} \text{for every two-group society whose}\\ \text{two groups have at most r positive-mass types,}\\ \text{there exists an allocation with }V_p(A;\mu)=0 \end{array} \right\}. \]
Theorem 3.4 gives
\[ P_\infty(r)\le 160\lceil\log(r+1)\rceil, \]
while Theorem 5.4 transfers to the continuous setting by assigning positive mass to each agent type and gives
\[ P_\infty(r)\ge 2+\left\lfloor\frac{\log r}{2}\right\rfloor. \]
Hence the continuous mirror has the same \(\Theta(\log r)\) guarantee scale. This is useful evidence that the mirror is not merely a softened problem chosen because it is easy: it preserves both the upper and lower structure of the original result. I would classify the constructive upper-bound regime as Class A. For the exact optimal-\(p\) problem below the theorem’s range, I would expect Class B rather than Class C if a discrete hardness result is established, since every finite profile embeds as a rational-mass society. This paper itself does not prove NP-hardness, so I would not claim that it does.
There is also a genuinely mass-sensitive follow-up. For two groups, define the \(\varepsilon\)-version by asking for an allocation with \(V_p(A;\mu)\le\varepsilon\). Lemma 5.3, proved in this paper, says that a uniformly random subset of items satisfies one agent’s \(1\)-out-of-\(p\) MMS with probability greater than \(1-2^{-(p-1)}\). Integrating this statement over the type distribution shows that some partition has
\[ V_p(A;\mu)<2^{-(p-1)}. \]
Thus \(p\ge 1+\lceil\log(1/\varepsilon)\rceil\) suffices for an \(\varepsilon\)-mass guarantee, independently of the total population size. This is a natural continuous extension, though not an exact theorem about the paper’s unanimous “every agent” requirement. It generates questions about weighted violation minimization, deterministic derandomization, and whether the exact optimum can be computed in time polynomial in the number of types.
The scope is deliberately limited. This mirror covers the paper’s main algorithmic upper bound, Theorem 3.4, and its equal-two-group lower-bound scale, Theorem 5.4. Theorem 3.5 can be transported similarly by replacing group sizes with numbers of supported types, but it is not an independent conceptual anchor. I am not claiming that every statement in the paper has an equally natural continuous version.
The weakest point is that the exact \(V_p=0\) problem uses the masses only to identify which types are present; the numerical values of positive masses do not affect feasibility. An opposing analyst can fairly call that a type-compression result rather than a rich distributional optimization problem. The answer is that this is a real limitation, not something to conceal: unanimous fairness in the original problem is inherently insensitive to multiplicities of identical agents. The \(\varepsilon\)-mass version restores the role of population mass, but it is a principled extension rather than the paper’s exact problem. Even so, the exact support-compressed mirror is a legitimate and plausible high-multiplicity continuization, and Theorem 3.4 supplies a concrete polynomial-time result for it.
The strongest case against is that the paper’s central guarantee is intrinsically support-based, not mass-based. Let \(S_i(\mu)\) be the set of utility types with positive mass in group \(i\). For any partition \(A=(A_1,\ldots,A_g)\),
\[ V_p(A;\mu)=0 \quad\Longleftrightarrow\quad v_t(A_i)\ge \theta_t(p) \text{ for every }t\in S_i(\mu). \]
The numerical values of the masses never enter. Replacing a type’s mass by \(10^{-6}\), \(1/2\), or \(0.99\) changes nothing, provided it remains positive. Duplicating agents therefore has exactly the effect of duplicating identical constraints, which can simply be removed. The proposed “continuous society” is, for the exact problem, only a finite support list.
This directly weakens the proposed reading of Theorem 3.4. Replacing \(n_i\) by the number \(r_i\) of distinct utility types is formally valid, but it is a deduplication observation, not a continuous-population theorem. The result can be stated without distributions at all: given \(r_i\) distinct additive utility vectors for each group, an allocation exists for \(p=O(\sum_i\log(r_i+1))\). The algorithm’s randomness is over item assignments, not over the population, and its running time is polynomial in the compressed constraint system. A city with millions of residents and twenty utility profiles is indeed a sensible high-multiplicity instance, but Theorem 3.4 then says only that the same twenty constraints need not be repeated millions of times.
No better exact version repairs this. Requiring the guarantee for every positive-mass type again makes only the support relevant. Requiring it almost everywhere discards null or negligible types and therefore changes the paper’s unanimous fairness requirement. Requiring it for the entire topological support restores the support-only formulation. To make masses matter, one must replace “every agent” by a quota, expectation, quantile, or shortfall objective; that is a new fairness problem rather than a continuous mirror of the theorem.
The same objection defeats the proposed use of Theorem 5.4. Its \(\Omega(\log n')\) lower bound transfers only by representing the relevant agents as distinct utility types. The logarithm is then a function of the number of distinct constraints, not of population multiplicity. One may replicate every such type arbitrarily many times, but the continuous parameter remains \(r\), while the total number of agents can grow without bound. Thus the apparent matching \(\Theta(\log r)\) bounds demonstrate a support-compression phenomenon, not a computational phenomenon caused by continuizing the population. In the genuinely high-multiplicity regime with fixed \(r\), the lower bound ceases to grow even though the represented society becomes arbitrarily large.
The Lemma 5.3 extension is more genuinely mass-sensitive, but only because it changes the target. Integrating the lemma gives
\[ \mathbb{E}_A[V_p(A;\mu)] = \sum_t \mu_t \Pr_A[v_t(A_i)<\theta_t(p)] < 2^{-(p-1)}. \]
This is a valid averaging corollary, but it is distributionally generic: the same identity applies to any finite collection of named agents with arbitrary externally assigned weights. The bound itself does not use the structure of \(\mu\), the number of types, or high multiplicity. More importantly, \(V_p\le\varepsilon\) permits the allocation to fail every requirement of a small but possibly crucial minority. That may be a worthwhile new weighted-fairness problem, but it is no longer the paper’s ordinal MMS guarantee, whose defining content is protection of every agent in a group.
There is also no obvious way to obtain a richer mirror by continuizing the groups themselves. A group is assigned one indivisible bundle, and its identity determines which bundle it receives. Replacing many groups by a mass of group types either loses that allocation identity or requires copies/divisibility of items, moving into a different resource-allocation model. Within a fixed group, population mass disappears under the universal constraint; across groups, identity cannot be discarded.
This is not an objection based on existing high-multiplicity work, nor on the possibility that the continuous answer might be easy. The issue is more basic: for the paper’s exact computational object, the population distribution has no operative role beyond recording which utility constraints are present. The proposed mirrors are legitimate compressed formulations and may support a modest follow-up, but they do not supply the kind of continuous-population computational landscape ChoCo is meant to study.
The negative case is therefore not airtight. If ChoCo regards support compression, or an \(\varepsilon\)-mass relaxation, as sufficient, the proponent has a defensible mirror. But under a stricter standard—where the population must be a computationally meaningful continuous object—the paper offers no strong anchor.
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.