| paper | On Lower Bounds for Maximin Share Guarantees |
| authors | Halvard Hummel |
| venue | IJCAI 2023 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | unclear |
The paper's numbered theorems are existence guarantees, not complexity-class, algorithmic, approximation, or parameterized results. Therefore bit (a) fails regardless of whether the proposed repeated-goods model is worthwhile. Moreover, scaling inventory per capita changes the paper's fixed-\(n+c\) regime and does not preserve its exceptional-item combinatorics.
fails bit a — no named computational result to mirror
The repaired model scales goods with population, so it discards the fixed-\(c\) exceptional-item regime that drives Theorem 1; the proponent acknowledges this extension but does not show that the theorem's phenomenon survives.
fatal: True
The proposed construction covers only a goods analogue of Theorem 1; it leaves Theorems 2, 3, and 24, the structural lemmas, and the chores result outside the mirror.
Strictly applying the anchor rule, this paper has no qualifying computational anchor. Theorem 1, Theorem 2, Theorem 3, and Theorem 24 are existence theorems; none states that a named problem is in \(\mathrm{P}\), \(\mathrm{NP}\)-hard, fixed-parameter tractable, or otherwise complexity-classified. The paper’s efficient-algorithm statements are background or citations, not named results proved here. Thus the formal positive case has no eligible anchor.
The strongest broader case is nevertheless a mirror of the phenomenon proved in Theorem 1, proved in this paper: for every integer \(c>0\), there is \(n_c\le\lfloor 0.6597^c c!\rfloor\) such that every goods instance with \(n\ge n_c\) and at most \(n+c\) goods has an MMS allocation. I would treat this as a non-qualifying existence anchor, and as the lead only if the rubric permits named constructive-existence results.
The mirror would be Typed Repeated-Goods MMS\(_\infty\). Let \(T\) be a finite set of complete additive valuation types, let \(\mu\in\Delta(T)\) be the population distribution, and let \(J\) be a finite catalogue of good types. A type \(t\) has values \(v_t(j)\ge0\); a bundle is an integral vector \(b\in\mathbb Z_{\ge0}^{J}\), with value \(v_t(b)=\sum_j b_jv_t(j)\). Let \(\sigma_j\) be the number of copies of good type \(j\) per unit population. A finite realization with scale \(N\) has \(N\mu_t\) agents of type \(t\) and \(N\sigma_j\) indivisible copies of good \(j\).
The continuous decision variable is \(x_{t,b}\), the mass of type-\(t\) agents receiving the whole integral bundle \(b\). It must satisfy
\[ \sum_b x_{t,b}=\mu_t \]
for every \(t\), and
\[ \sum_{t,b}b_jx_{t,b}=\sigma_j \]
for every \(j\). The fractional variable records the distribution of whole bundles among a mass of exchangeable agents; it does not split an individual good.
For each type \(t\), define its continuum MMS threshold by
\[ \lambda_t(\sigma)= \sup_y\; \inf_{b:y_b>0}v_t(b), \]
where \(y\) ranges over bundle distributions satisfying
\[ \sum_b y_b=1 \qquad\text{and}\qquad \sum_b b_jy_b=\sigma_j. \]
The problem asks whether there exists an allocation law \(x\) satisfying the supply equations and
\[ x_{t,b}>0\quad\Longrightarrow\quad v_t(b)\ge\lambda_t(\sigma) \]
for every type with positive mass. Equivalently, one can maximize the common MMS factor \(\alpha\) subject to \(v_t(b)\ge\alpha\lambda_t(\sigma)\), and ask whether \(\alpha^\star\ge1\).
The regime is a large repeated-allocation market: for example, many households receiving bundles of repeated food, training, housing, or care goods, with only finitely many complete valuation profiles. Here \(N\gg |T|,|J|\), and rational masses correspond exactly to finite clone populations after denominator clearing. The paper’s ordered-instance machinery makes the scenario particularly plausible: agents may share a common ranking of goods while differing in their cardinal values.
I would expect the ordered fixed-\(c\) version to be a Class A candidate. Lemmas 15 and 16 show that, when \(m=n+c\), all but \(O(c)\) goods can be isolated as singleton bundles; the remaining combinatorics concern only finitely many exceptional bundle configurations. That suggests a configuration-flow or column-generation formulation whose complexity depends on the number of valuation and good types and perhaps on \(c\), rather than on the population scale. The unrestricted exact problem may instead retain Class B hardness through integral partitioning or knapsack-like pricing. I would not predict Class C: the apparent difficulty lives in indivisible bundle structure, not in population mass itself.
The mirror covers only the paper’s goods-existence phenomenon represented by Theorem 1. Theorem 3 suggests an analogous chores problem with \(v_t(j)\le0\), but I would not add it as a second anchor: it is not an independent computational result, and the chores threshold dictionary needs separate care.
The main weakness is substantial: to avoid degeneration, the number of indivisible goods must scale with the population. With a fixed finite stock and a nonatomic population, almost everyone receives the empty bundle and MMS becomes trivial. Thus the proposed model is not population-only in the narrowest literal sense; it is a high-multiplicity population-and-inventory limit. That is defensible because the paper itself studies \(m\) growing with \(n\), and every finite rational allocation law expands to an allocation of indivisible clones. But it remains a model extension, not a continuous theorem already delivered by this paper.
The resulting research questions are whether the MMS thresholds admit efficient type-level computation, whether rational allocation laws round exactly to finite indivisible allocations, and whether the \(n+c\) guarantees yield an FPT or polynomial algorithm in the repeated-goods representation.
The negative case is decisive under ChoCo’s anchor rule: this paper supplies no qualifying computational anchor. Theorem 1 is an existence theorem, not a complexity, algorithmic, approximation, or parameterized result. It gives no computational input/output problem, representation, or running-time claim. The same is true of Theorems 2, 3, and 24. The cited approximation algorithms are prior work, not results proved by this paper. Wrapping Theorem 1 in a newly invented decision problem therefore cannot make it a computational result of the paper.
Even if existence theorems are admitted as broader anchors, the proposed mirror does not preserve the phenomenon of Theorem 1.
In the literal population limit with a fixed stock of goods, the goods case degenerates. Once \(N>m\), every \(N\)-partition has an empty bundle, so every additive-goods agent has MMS \(0\). The MMS requirement is then automatically satisfied. In the paper’s regime \(m=n+c\) with fixed \(c\), the \(c\) exceptional goods have vanishing per-capita supply as \(n\to\infty\). Yet those exceptional goods are exactly where the theorem’s content lies: the \(2c\) residual items, Stirling-number partition counts, domination chains, and the bound \(0.6597^c c!\). A distribution over population types cannot see finitely many named goods of zero mass.
One can retain those goods as distinguished atoms, but then the model is no longer a society represented only by type masses. The allocation condition must remember which individual agents receive the exceptional items, and zero-measure agents cannot be ignored. That is a hybrid atomic/nonatomic model, not the proposed continuous society.
The proponent’s stronger repair scales the inventory with the population: each unit population receives a fixed supply vector \(\sigma\). This avoids degeneration and is a legitimate repeated-goods fair-division model. But it is an extension, not a mirror of Theorem 1. The theorem studies \(n+c\) distinct goods with arbitrary ordered valuations and fixed additive excess \(c\); the repaired model studies a new asymptotic regime with per-capita inventory, often with many interchangeable copies of each good type. If one keeps the original item distinctions and valuation vectors, the catalogue of item types grows with \(N\), so the population compression largely disappears. If one keeps a fixed catalogue, one has changed the instance family and removed the item-level combinatorics used in the proof.
The proposed \(\lambda_t(\sigma)\) and configuration-flow variables are therefore a sensible new research object, but they are not a continuous version of the paper’s named result. They ask about an asymptotic repeated-resource allocation problem that the paper neither formulates nor computationally classifies. Choosing \(c=\delta N\) would make the model still more meaningful, but would produce a new positive-inventory-density theorem rather than continuize the fixed-\(c\) lower bound.
Thus no anchor survives as a ChoCo computational mirror: formally there is no eligible anchor, and the literal continuous limit of the goods theorem is vacuous. The honest qualification is that the repeated-goods model is not worthless mathematics; it could become a worthwhile high-multiplicity fair-division project. Its weakness is precisely that it is a re-modeling or extension, not a continuous computational mirror of this 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.