| paper | Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations |
| authors | Siddharth Barman, Paritosh Verma |
| venue | ATAL 2021 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), counting value-oracle calls at unit cost. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\) with rational masses \(\mu_\theta\), good classes \(G\) with rational per-capita supplies \(\rho_g\), and value-oracle matroid-rank valuations \(r_\theta\), compute a mass allocation \(x_{\theta,B}\) over integral bundles \(B\subseteq G\) satisfying \(\sum_B x_{\theta,B}=\mu_\theta\), \(\sum_{\theta,B\ni g}x_{\theta,B}\le\rho_g\), and \(x_{\theta,B}>0\Rightarrow r_\theta(B)\ge\lambda_\theta(\rho)\), where \(\lambda_\theta(\rho)\) is the largest integer \(q\) supported by a distribution over integral bundles of rank at least \(q\) under the same capacities; maximize \(\sum_{\theta,B}x_{\theta,B}r_\theta(B)\) over all capacity-feasible allocations in time polynomial in the type and good dimensions and the input bit length.
A high-multiplicity configuration LP over integral bundles: \(\mu\) is type mass, \(\rho\) is per-capita parallel-good supply, \(x_{\theta,B}\) is assigned mass, \(\lambda_\theta(\rho)\) is the exact per-agent MMS threshold, and the objective is aggregate rank welfare.
The finite polynomial-time theorem does not establish a polynomial-time algorithm in the binary type-level encoding: support-wise configuration pricing and exact computation of \(\lambda_\theta(\rho)\) still require proof.
fatal: False
The mirror covers Theorem 1's exact \(\mathrm{MMS}\) and welfare-maximization result and Theorem 5's threshold computation for matroid-rank types. It leaves Theorem 4's partial \(\mathrm{PMMS}\) result, the \(\mathrm{PMMS}\)-to-\(\mathrm{EF1}\) and approximate-\(\mathrm{MMS}\) results, and the binary-XOS and weighted-rank nonexistence results outside the stated mirror.
The strongest honest positive case is the paper’s main result, Theorem 1. The paper contains no named NP-hardness result—Theorems 2 and 3 are nonexistence results—so I would not manufacture a hardness anchor. Instead, the mirror asks whether the paper’s exact fairness-and-efficiency theorem survives the high-multiplicity transition.
A natural regime is a large recurring population of students, households, or applicants. There is a finite set \(\Theta\) of complete preference types, with \(\tau=|\Theta|\ll N\): two agents of type \(\theta\) have the same matroid-rank valuation \(r_\theta\), including the same substitutability and eligibility constraints. There are also finitely many good classes \(G\), with \(N\rho_g\) physical copies of class \(g\), where \(\rho_g\) is its per-capita supply. Copies of the same class are parallel elements of the matroid. Thus the \(N\)-agent instance has \(N\mu_\theta\) agents of type \(\theta\), but every individual still receives an integral bundle of indivisible goods.
This is a genuine high-multiplicity regime, not an assumption that prices or costs are artificially identical: the valuation matroid is part of the type. It is plausible in course allocation, housing, or repeated hiring markets where many agents share a small number of preference and eligibility patterns.
Here is the lead mirror, which I would call Continuum MMS-Welfare Allocation under Matroid-Rank Types. Its input is:
For a type \(\theta\), define its continuum maximin share by
\[ \lambda_\theta(\rho) = \max\left\{ q\in\mathbb{Z}_{\ge0}: \begin{array}{l} \text{there is a probability distribution }p^\theta\text{ over integral bundles }B\subseteq G,\\ \sum_{B\ni g}p^\theta_B\le \rho_g\text{ for every }g,\text{ and }p^\theta_B>0\Rightarrow r_\theta(B)\ge q \end{array} \right\}. \]
This is the continuum limit of the paper’s \(\mu_i(n,[m])\): a type-\(\theta\) agent partitions the whole per-capita inventory into a distribution of integral bundles and maximizes the worst bundle value. The distribution is only an aggregate description; no individual receives a fractional bundle.
A solution is a collection \(x_{\theta,B}\ge 0\), where \(x_{\theta,B}\) is the mass of type-\(\theta\) agents receiving integral bundle \(B\), satisfying
\[ \sum_B x_{\theta,B}=\mu_\theta \]
for every \(\theta\), and
\[ \sum_{\theta}\sum_{B\ni g}x_{\theta,B}\le \rho_g \]
for every good class \(g\). It must satisfy exact MMS fairness,
\[ x_{\theta,B}>0\quad\Longrightarrow\quad r_\theta(B)\ge \lambda_\theta(\rho), \]
and among all feasible allocations it must maximize normalized social welfare
\[ \operatorname{SW}_\infty(x) = \sum_{\theta}\sum_B x_{\theta,B}r_\theta(B). \]
The output is therefore a mass allocation whose every infinitesimal agent receives an integral bundle meeting her type’s exact MMS guarantee, while the aggregate allocation is welfare-maximizing. Unused parallel copies can be assigned arbitrarily afterward, since matroid-rank valuations are monotone.
My lead anchor is Theorem 1, proved in this paper. In full, it states that every finite fair-division instance with matroid-rank valuations admits a maximin-share allocation that also maximizes social welfare, and that such an allocation can be computed in polynomial time with value-oracle access to the valuations.
The proposed problem mirrors every substantive part of that theorem: matroid-rank valuations, exact MMS rather than approximation, welfare maximization across all allocations, and an algorithmic question. For rational \(\mu\) and \(\rho\), choose \(N\) so that all \(N\mu_\theta\) and \(N\rho_g\) are integers, expand the population into \(N\) agents and the supplies into \(N\rho_g\) physical copies, and apply Theorem 1 to the resulting parallel-extension instance. The empirical distributions of the resulting allocations have limit points of exactly the form \(x\) above. This gives a strong existence reason for the continuum problem.
The expected classification is Class A. The paper’s exchange-graph argument should compress into mass transfers between repeated types. The threshold \(\lambda_\theta\) can be tested through a capacity-constrained matroid-polymatroid feasibility problem, while the welfare allocation itself has a configuration-LP form over integral bundles. Although there may be exponentially many bundle configurations, the relevant pricing problems are matroid optimization problems rather than arbitrary combinatorial searches. The resulting question is whether this structure yields an algorithm polynomial in \(\tau\), \(|G|\), and the bit length of \(\mu,\rho\), rather than polynomial only in the expanded population size \(N\).
That distinction is important. Applying the paper’s algorithm literally to \(N\mu_\theta\) cloned agents is not a high-multiplicity algorithm: \(N\) may be exponentially larger than the input encoding. The continuous mirror is therefore not a restatement of the finite theorem. It asks whether the matroid-union and exchange arguments admit a type-level, bit-compressed implementation.
A second, narrower anchor is Theorem 5, also proved in the paper. It states that, given any fair-division instance with matroid-rank valuations and value-oracle access, the maximin share \(\mu_i(n,[m])\) of every agent can be computed in polynomial time. The paper computes it using an \(n\)-fold matroid union followed by balancing independent bundles.
Its direct continuous counterpart is Continuum MMS-Threshold: given a type \(\theta\), its matroid-rank oracle, and the per-capita supply vector \(\rho\), compute \(\lambda_\theta(\rho)\) exactly. Equivalently, one can ask for the largest integer \(q\) for which the per-capita inventory supports a distribution over independent \(q\)-element bundles. This can be expressed through the matroid independent-set polytope:
\[ \exists y\in P(r_\theta) \quad \text{such that} \quad 0\le y_g\le \rho_g \quad\text{and}\quad \sum_{g\in G}y_g=q. \]
The expected classification is again Class A, using the same matroid-union/polymatroid machinery that underlies Theorem 5. This threshold problem is not an arbitrary relaxation: it is precisely the type-level version of the paper’s individual MMS computation.
The mirror covers only the matroid-rank results, principally Theorem 1 and its threshold subroutine Theorem 5. It does not claim to continuize the paper’s binary-XOS or weighted-rank counterexamples, nor does it turn fractional outcomes into the object of study. The population is continuous; bundles remain indivisible and valuations remain matroid ranks.
The weakest point is that the paper already proves the corresponding finite problem is in P, so this case cannot display the especially compelling phenomenon of discrete hardness dissolving under continuization. Moreover, Theorem 1 alone does not automatically provide a polynomial algorithm in the compressed high-multiplicity encoding. That algorithmic compression is the real open part of the mirror. Still, this is a legitimate and nontrivial continuous question: the input may describe exponentially many cloned agents, while the output is a type-level mass allocation with exact individual fairness. A referee sympathetic to high-multiplicity computation should recognize it as the population analogue of the paper’s problem, not as a change to fractional outcomes.
It also generates natural follow-up questions: whether the continuous welfare-maximizing MMS allocation always has polynomial-size rational support; whether a complete continuous PMMS analogue exists; and whether the paper’s nonexistence phenomena for weighted-rank valuations persist in the continuum or reveal a genuinely continuum-specific boundary.
The strongest negative case is that the literal population limit degenerates. If the paper’s \(m\) goods and matroids are held fixed while the number of cloned agents \(N\) grows, then every rank is at most \(m\). Once \(N>m\), every \(N\)-partition contains an empty bundle, so \(\mu_i(N,[m])=0\). The continuous MMS condition is then vacuous, and normalized welfare also vanishes. This defeats a population-only mirror of both Theorem 1 and Theorem 5.
The proponent’s per-capita-supply repair is much harder to defeat. With \(N\rho_g\) parallel copies of each good class, their distribution \(p^\theta\) is exactly the empirical distribution of integral bundles in an \(N\)-agent instance. For rational \(\mu\) and \(\rho\), a common denominator realizes the distribution as a finite allocation; conversely, every finite allocation aggregates into such a distribution. Leftover copies can be assigned arbitrarily because rank valuations are monotone. Thus the proposed \(\lambda_\theta(\rho)\) is not merely a lottery over fractional bundles: it is the high-multiplicity form of the paper’s individual MMS threshold.
The same applies to their welfare allocation \(x_{\theta,B}\). It retains integral bundles and only makes the population aggregate continuous. Since MMS and welfare depend on agents through their valuations, and those valuations are identical within a type, aggregation loses no information relevant to either objective. The paper’s Theorem 1 therefore supplies genuine existence evidence for this mirror after finite expansion. The programme explicitly permits the accompanying scaling of supplies, so calling that modification a scope violation would be wrong.
There is a legitimate weakness in the proponent’s algorithmic argument: the proposed threshold is support-wise, requiring \(r_\theta(B)\ge q\) for every bundle in the support. It cannot simply be replaced by an expected-value constraint. Likewise, saying that the configuration LP has “matroid pricing” does not by itself prove a polynomial algorithm in the binary encoding of \(\rho\). Those are real proof obligations. But failure of the first attempted pricing formulation would be a computational result about a well-posed mirror, not a reason that the mirror is meaningless.
Theorem 5 is therefore not defeated either. With fixed goods its continuous version is trivial, but with per-capita parallel supply it becomes a legitimate high-multiplicity matroid-union question. Whether the resulting threshold computation is routine or unexpectedly difficult is precisely the sort of boundary the programme is meant to identify.
Consequently, the negative case is honestly weak. It rules out only the naive fixed-inventory limit. The better version raised by the other analyst survives: it has a sensible repeated-population interpretation, preserves indivisible bundles, and creates a genuine type-level computational problem. I cannot defend the universal claim that no worthwhile continuous mirror exists.
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.