| paper | Groupwise Maximin Fair Allocation of Indivisible Goods |
| authors | Siddharth Barman, Arpita Biswas, Sanath Kumar Krishna Murthy, Y. Narahari |
| venue | AAAI 2018 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), additive valuations \(v_t\), an integral bundle catalogue \(2^G\), and per-capita supplies \(b_g\), find masses \(x_{t,B}\geq 0\) satisfying \(\sum_B x_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}x_{t,B}=b_g\), such that for every subpopulation \(H\) with \(0\leq h_{t,B}\leq x_{t,B}\), every type \(t\) and bundle \(B\) with \(h_{t,B}>0\) satisfy \(v_t(B)\geq \frac12\MMS_t^\infty(H)\), where \(\MMS_t^\infty(H)\) is the maximum minimum \(v_t\)-value attainable by redistributing \(H\)'s pooled goods among its mass while each individual receives an integral bundle.
A high-multiplicity configuration allocation: finitely many complete valuation types \(t\) carry population mass \(\mu_t\), individuals receive integral bundles \(B\subseteq G\), \(x_{t,B}\) is assigned mass, \(b_g\) is per-capita supply, and feasibility requires a \(1/2\)-groupwise maximin guarantee over measurable subpopulations.
The positive-mass limit loses constant-size coalitions, so the paper's \(\PMMS\Rightarrow\EFX\) consequences need not survive, and the named-agent envy graph does not automatically aggregate by type.
fatal: False
The mirror covers Theorem 1 and its \(\EFL\)-based \(1/2\)-\(\GMMS\) algorithmic architecture. It leaves the exact-existence theorems, fairness implications, empirical findings, and the discrete envy-graph proof itself unresolved.
The strongest positive case is a high-multiplicity mirror of the paper’s main algorithmic result, Theorem 1. Theorem 1 is proved in this paper: every fair-division instance with additive valuations admits a \(1/2\)-approximate \(\GMMS\) allocation, and such an allocation can be found in polynomial time. Its proof combines the polynomial-time \(\EFL\) allocation algorithm of Lemma 1 with Lemma 3, which proves that every \(\EFL\) allocation is \(1/2\)-\(\GMMS\). The paper contains no comparable named hardness theorem, so this is necessarily an algorithmic anchor.
A plausible regime is a large recurring allocation market: for example, millions of students receiving indivisible course seats. There is a finite catalogue \(G\) of course types, each with many seats, and a comparatively small set \(T\) of complete valuation types. A type includes the whole additive valuation vector \(v_t(g)\); agents with the same type are interchangeable for the problem. The population is described by masses \(\mu_t\), while \(b_g\) denotes the number of seats of course type \(g\) per unit population. For a population of size \(N\), the corresponding finite instance has approximately \(N\mu_t\) agents of type \(t\) and \(Nb_g\) individually indivisible seats of type \(g\). Thus \(N\) is very large, while \(m=|G|\) and \(\tau=|T|\) are moderate.
The seats remain indivisible. A continuous allocation is not fractional ownership of a seat by one student. Instead, let \(x_{t,B}\) be the mass of type-\(t\) students receiving the integral bundle \(B\subseteq G\). The constraints are \(\sum_B x_{t,B}=\mu_t\) for every \(t\), and \(\sum_{t,B:g\in B}x_{t,B}=b_g\) for every \(g\). Type-level averages may therefore be fractional, but almost every individual still receives an ordinary indivisible bundle.
The natural continuum version of the groupwise benchmark is also a genuine high-multiplicity limit. Take any subpopulation \(H\), represented by masses \(h_{t,B}\leq x_{t,B}\). Let its mass be \(q=\sum_{t,B}h_{t,B}\), and let \(s_g=\sum_{t,B:g\in B}h_{t,B}\) be the mass of goods pooled within \(H\). For a type \(t\) present in \(H\), define its continuum maximin share by allowing the pooled goods to be redistributed among mass \(q\) of hypothetical type-\(t\) agents, each still receiving an integral bundle: \(\MMS^\infty_t(H)\) is the maximum, over bundle-mass assignments \(y_B\) satisfying \(\sum_B y_B=q\) and \(\sum_{B:g\in B}y_B=s_g\), of \(\min_{B:y_B>0}v_t(B)\).
My lead problem is therefore:
Continuous-\(\frac12\)-\(\GMMS\). Given rational type masses \(\mu\), additive valuations \(v_t\), and per-capita indivisible-good supplies \(b\), find a mass allocation \(x\) such that, for every measurable subpopulation \(H\), every type \(t\) occurring in \(H\), and every bundle \(B\) assigned positive type-\(t\) mass inside \(H\), \(v_t(B)\geq \frac12\MMS^\infty_t(H)\).
The objective is feasibility: produce any such allocation. Equivalently, one could maximize the largest \(\alpha\) for which the allocation is \(\alpha\)-\(\GMMS^\infty\).
This is recognisably the authors’ problem rather than a softened welfare problem. It preserves additive valuations, indivisible bundles, and the defining ex-post quantification over all subgroups. Only the population has been continuized; the per-capita supply \(b\) is the necessary co-modification that keeps indivisibility meaningful when the number of agents grows. A finite group of \(qN\) agents and its pooled goods produce exactly the corresponding discrete maximin-share instance. Conversely, rational \(x\) can be replicated by a sufficiently large finite population. Thus the proposed object has the required two-way high-multiplicity dictionary.
I would expect this problem to fall in Class A, at least for a fixed or moderately sized item catalogue. The paper’s proof does not require computing every maximin share explicitly: it constructs an \(\EFL\) allocation through an envy-graph process and then derives the \(1/2\) guarantee structurally. In the high-multiplicity regime, that process should be aggregable by valuation type and bundle mass. The resulting formulation is a configuration allocation problem, precisely the setting in which column-generation or separation methods could replace the named-agent envy graph. The main algorithmic questions are whether the type-level process has a polynomial representation and whether the family of groupwise constraints admits efficient separation.
This mirror covers Theorem 1 and its \(\EFL\)-based proof architecture; it does not claim to continuize every result in the paper. It naturally generates further questions: does the \(1/2\) guarantee survive finite-population rounding, can it be improved in the continuum, and do the paper’s exact-existence results for binary or identical valuations become exact continuum results?
The weakest point is that \(\GMMS\) was originally defined using an atomic agent and an integer group size, whereas the continuum benchmark above replaces the finite partition into \(k\) bundles by a mass assignment to \(qN\) hypothetical agents. That extension is not a theorem in the paper. It is nevertheless the canonical high-multiplicity limit: discrete bundles remain integral, while only the counts of repeated agents and repeated goods become divisible. The other serious gap is that the paper’s polynomial envy graph is on named agents, so its compression to finitely many types still needs to be proved. Those are real risks, but they concern the tractability of a well-posed continuous analogue—not whether the analogue is the authors’ problem.
The strongest objection is an order-of-limits problem in \(\GMMS\), not the fact that bundles remain indivisible.
The paper’s \(\GMMS\) takes a maximum over every finite coalition \(J\), including pairs and other coalitions of constant size. Those small coalitions are essential: the paper’s fairness chain uses \(\GMMS\Rightarrow\PMMS\Rightarrow\EFX\). In a nonatomic population, however, a measurable subgroup \(H\) has positive mass \(q\). Its finite approximants contain \(qN\) agents and \(qN\)-scale supplies. As \(N\to\infty\), the integer packing effects disappear and the benchmark becomes precisely the fractional configuration problem described by the proponent’s \(y_B\).
That is a legitimate macroscopic allocation problem, but it is not the limit of the paper’s full \(\GMMS\). Coalitions with \(|J|=O(1)\) have mass \(0\) and vanish. Thus the proposed mirror drops exactly the finite-coalition constraints that make groupwise fairness distinctive. Calling the result “continuous \(\GMMS\)” hides a substantive change of fairness notion.
There are only two repairs. If one retains only positive-mass coalitions, the object is a new macroscopic packing notion; it no longer preserves the paper’s \(\GMMS\), \(\PMMS\), or \(\EFX\) content. If one restores finite coalitions by imposing conditions on every finite multiset of supported agent-and-bundle types, then the population masses largely disappear: any bundle occurring with positive mass can supply arbitrarily many hypothetical agents. The result is a support-based finite configuration problem, with a continuous allocation layer attached, rather than a genuinely population-continuous version of the paper.
The same issue undermines the claimed transfer of Theorem 1’s algorithm. Its polynomial algorithm is built around a named-agent envy graph: choose a source agent, give that individual her favourite remaining good, and rotate bundles along cycles. After aggregation, one valuation type may receive many different bundles, so “the source of a type” is undefined. EFL is a relation between an individual’s bundle and another individual’s bundle, not merely between valuation types. Enforcing it over bundle masses produces a universal, allocation-dependent family of configuration constraints; the envy-graph proof does not compress into a type-level algorithm merely because the population does.
A better course-seat model does not remove this dilemma. Scaling seats per capita gives a sensible high-multiplicity allocation market, but it yields either the macroscopic relaxation above or a hybrid model that separately retains finite coalitions. The latter may be interesting, but its decisive constraints are still the original finite fair-division problem; the continuum is not what supplies the theorem’s content.
This is a serious negative case against the proposed anchor, but not an airtight universal one. Large recurring course markets do make high multiplicity plausible, and the macroscopic configuration problem could be worth studying on its own. What cannot honestly be claimed is that Theorem 1 has a clean continuous-population mirror with the paper’s \(\GMMS\) meaning and a two-way dictionary.
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.