| paper | Guaranteeing Maximin Shares: Some Agents Left Behind |
| authors | Hadi Hosseini, Andrew Searns |
| venue | IJCAI 2021 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\mathsf P\): every valid instance admits a qualifying allocation. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite set of additive valuation types \(T\) with distribution \( \mu \), finite indivisible good classes \(G\), per-capita supplies \(b_g\), and an integer benchmark scale \(K\), define \(q_{t,K}(b)\) as the maximum minimum value over partitions of \(K b_g\) good copies into \(K\) integral bundles. Decide whether there is a mass allocation \(x_{t,a}\ge 0\) over integral bundle configurations \(a\) satisfying \( \sum_a x_{t,a}=\mu_t \) and \( \sum_{t,a} a_g x_{t,a}=b_g \), in which at least \(1-1/K\) of the population receives value at least \( \frac{K+2}{2(K-1)}q_{t,K}(b) \).
A nonatomic high-multiplicity relaxation of indivisible-goods fair division: valuation types carry mass \( \mu_t \), each unit of mass receives an integral bundle configuration \(a\), aggregate bundle usage is constrained by per-capita supplies \(b\), and the objective maximizes mass meeting the \(K\)-dependent MMS threshold.
The proposed arbitrary real mass allocation is not exactly interchangeable with a \(K\)-agent allocation: clearing denominators changes the population scale and therefore changes the MMS benchmark and approximation factor; moreover, the asymptotic benchmark may collapse toward average value.
fatal: False
The mirror covers Theorem 2's polynomial-time \( (n-1)/n \)-MMS approximation over repeated valuation types and indivisible good classes. It does not address Theorems 1, 3, or 4, the corollaries, or the empirical findings.
The strongest positive case is a single-anchor one: Theorem 2.
The paper’s named computational anchor is Theorem 2, proved in the paper, not merely cited:
Given any instance of \(n\) agents with additive valuations over indivisible goods, an allocation satisfying \(\left(\frac{n-1}{n},\frac{1}{2}\frac{n+2}{n-1}\right)\)-MMS can be computed in polynomial time.
Concretely, the output allocation gives at least \(n-1\) agents a bundle worth at least \(\frac{n+2}{2(n-1)}\operatorname{MMS}_i^n(M)\), where \(\operatorname{MMS}_i^n(M)\) is agent \(i\)’s maximin share when the goods are partitioned into \(n\) bundles. The guarantee is \(1\) for \(n=4\), \(7/8\) for \(n=5\), \(4/5\) for \(n=6\), and so on. The proof combines the paper’s normalization and reduction lemmas with an EFX-producing envy-graph algorithm.
I would mirror this with the following problem.
Call it Continuous High-Multiplicity \((K-1)/K\)-MMS. There is a finite set \(T\) of complete valuation types and a distribution \(\mu\) over \(T\). There is also a finite catalogue \(G\) of indivisible good classes. A type \(t\) has additive values \(v_t(g)\) for \(g\in G\). The population scale is \(K\), so the finite expansion would contain \(K\mu_t\) agents of type \(t\). Good class \(g\) has per-capita supply \(b_g\), meaning that the expansion contains \(K b_g\) indivisible copies of \(g\). Assume the rational data are scaled so these quantities are integral.
For each type \(t\), define \(q_{t,K}(b)\) to be the maximin share obtained by partitioning the \(K b_g\) copies into \(K\) integral bundles. Thus the MMS benchmark remains the paper’s indivisible-goods benchmark; only the population representation is continuous.
A solution is a mass allocation \(x_{t,a}\ge 0\), where \(a\in\mathbb Z_{\ge0}^{G}\) is an integral bundle and \(x_{t,a}\) is the mass of type \(t\) receiving that bundle. It must satisfy
\(\sum_a x_{t,a}=\mu_t\) for every \(t\), and \(\sum_{t,a}a_gx_{t,a}=b_g\) for every good class \(g\).
The objective is to maximize the satisfied population mass
\(\sum_{t,a:\,v_t(a)\ge \frac{K+2}{2(K-1)}q_{t,K}(b)}x_{t,a}\).
The decision version asks whether this value is at least \(1-\frac1K\). In other words: can all but a \(1/K\) fraction of the population receive the Theorem 2 approximation to their MMS?
This is genuinely a population continuization. Every agent still receives an integral bundle; goods are not fractionalized. What becomes fractional is only the mass of repeated types assigned to different integral bundles. If all masses are rational, clearing denominators converts the plan back into an ordinary finite allocation, while grouping a finite allocation by valuation type produces such a mass plan. This gives the required two-way high-multiplicity dictionary.
The intended regime is a large university or hospital system. There may be hundreds of thousands of students or tasks, but only a moderate number of exact valuation profiles: seniority, degree requirements, accessibility needs, or standardized task priorities. Course seats, treatment slots, or resource units remain indivisible, while their supplies scale with population. The relevant comparison is \(K\gg |T|,|G|\), not merely “fair division” in the abstract.
The authors should recognize this as their problem. Their paper explicitly introduces \((\alpha,\beta)\)-MMS as fairness for a fraction of society, discusses senior students as a protected fraction, and uses hospital tasks as motivation. The mirror preserves exactly that objective while replacing a long list of repeated agents by their type masses. It is not a cake-cutting or fractional-allocation reformulation.
I would expect the mirror to be Class A in the intended fixed-type regime. The mass formulation is a configuration LP: its variables are integral bundle configurations, while the population assignment is linear. Column generation, fixed-dimensional integer optimization, or proximity methods are natural tools. The paper’s normalization and envy-graph proof suggest that the \((K-1)/K\) guarantee should survive aggregation, although proving a compressed algorithm polynomial in \(|T|,|G|,\log K\) would be new work.
If the number of good classes grows with \(K\), hardness is more likely to transfer from the goods-and-valuation structure, making that unrestricted version Class B rather than continuum-specific. I would not claim that Theorem 2 automatically supplies a compressed algorithm: its finite algorithm is polynomial in the expanded number of agents, whereas the mirror asks whether repeated-agent structure can be exploited.
The further questions are whether \(q_{t,K}(b)\) can itself be computed or approximated without expanding \(K\), whether the guarantee holds for a pre-designated protected mass of each type, and whether the limit \(K\to\infty\) yields an almost-everywhere \(1/2\)-MMS guarantee.
The weakest point is that the paper’s exact MMS benchmark is intrinsically tied to a finite number \(n\) of bundles. I retain that parameter as the population scale \(K\), rather than pretending that an MMS denominator can become a real number. Consequently, this is a family of continuous high-multiplicity problems, not one parameter-free atomless theorem. Also, if the paper’s carefully constructed hard instances require almost every good and valuation to be unique, they fall outside the intended regime. The positive case therefore depends on a real but defensible scenario: many repeated valuation types and scaled supplies, with indivisible bundles preserved.
The proponent’s anchor is real: Theorem 2 is a numbered polynomial-time computational result, so the negative case cannot rest on “the paper has no algorithmic theorem.” The problem is that the proposed mirror is not actually equivalent to Theorem 2’s high-multiplicity instance.
At population scale \(K\), an exact finite expansion has \(K\mu_t\) agents of type \(t\) and \(Kb_g\) copies of good \(g\). If \(y_{t,a}\) denotes the number of type-\(t\) agents receiving integral bundle \(a\), then necessarily
\[ y_{t,a}\in\mathbb Z_{\ge 0},\qquad x_{t,a}=\frac{y_{t,a}}{K}. \]
The proponent instead permits arbitrary real \(x_{t,a}\). That is not a harmless continuum notation: it allows the omitted \(1/K\) population mass to be spread fractionally across several types and bundles, whereas Theorem 2 omits one whole agent. Clearing denominators does not repair the equivalence. It produces a finite instance with population \(K'\), not \(K\); but both the benchmark \(q_{t,K}(b)\) and the factor
\[ \beta_K=\frac{K+2}{2(K-1)} \]
depend on the population scale. The resulting allocation is therefore evaluated against the wrong MMS benchmark. The claimed two-way dictionary fails precisely because MMS is not scale-invariant.
There are only two natural repairs. If one insists on the exact \(K\)-agent MMS benchmark, then the mass variables must be quantized in multiples of \(1/K\). The allegedly continuous LP collapses back to a compressed representation of a finite allocation problem. If one permits arbitrary masses, the problem becomes a new fractional relaxation whose relation to Theorem 2 has not been proved. Column generation does not establish that relation: even after fixing the threshold, generating an integral bundle with sufficient value under resource constraints contains knapsack-type pricing, while computing \(q_{t,K}(b)\) is itself a high-multiplicity partitioning problem. Theorem 2’s polynomial algorithm in the explicitly listed agents and goods gives no algorithm polynomial in \(|T|,|G|,\log K\).
The asymptotic repair is worse for the anchor. With fixed good classes and per-capita supplies, the number of copies of every class grows linearly with \(K\). For a fixed valuation type,
\[ q_{t,K}(b)\longrightarrow \sum_g b_g v_t(g), \]
up to bounded indivisibility effects. Thus the maximin-share benchmark converges to the ordinary per-capita average value. Simultaneously,
\[ \frac{K-1}{K}\longrightarrow 1,\qquad \beta_K\longrightarrow \frac12. \]
The paper’s distinctive statement—one agent may be left behind while the other \(K-1\) receive a finite-\(K\) MMS guarantee—disappears. The exceptional agent has measure zero, and the MMS partition itself becomes an average-value constraint. This is not merely a tractable answer; the central finite indivisibility phenomenon has vanished.
Keeping the goods fixed instead does not help. Once \(K\) exceeds the number of positively valued goods, every \(K\)-partition contains a zero-valued bundle, so \(q_{t,K}(b)=0\) for the relevant types and the guarantee becomes vacuous. Preserving a nontrivial MMS benchmark would require letting item sizes, valuation scales, or the number of good classes grow with \(K\), which introduces a new limit model rather than continuizing this theorem.
A stronger alternative could define an asymptotic support-wise MMS benchmark and protect a fixed positive population fraction rather than one exceptional agent. That would be a sensible new fair-division problem. But it would no longer be Theorem 2’s \((K-1)/K\)-MMS result; it would be a new continuous allocation programme requiring its own theorem.
So the best negative conclusion is narrow but substantive: the proponent’s stated mirror is an inconsistent hybrid of a finite MMS benchmark and an atomless allocation LP, and its two proposed repairs either collapse back to finite high multiplicity or lose the theorem’s defining content. I cannot honestly claim that every repaired population-level MMS problem is worthless—the paper’s explicit focus on fractions of agents makes a broader mirror plausible. The universal negative case is therefore weak; it defeats this formulation, not the entire mirror opportunity.
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.