| paper | Fair Division Under Cardinality Constraints |
| authors | Arpita Biswas, Siddharth Barman |
| venue | IJCAI 2018 |
| filed under | fairalloc · indivisible |
| 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: the \(1/3\) guarantee is universally achievable, with exact allocation of every supply and polynomial-size sparse output. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 2
Given valuation types \(t\) with masses \(\mu_t\), good types \(q\) partitioned into categories \(\mathcal Q_h\), cardinality limits \(k_h\), and per-capita supplies \(\lambda_q\), let \(\mathcal B\) be the integral bundles satisfying \(\sum_{q\in\mathcal Q_h}b_q\le k_h\). Compute a mass assignment \(x_{t,b}\) satisfying \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}b_qx_{t,b}=\lambda_q\), together with the largest \(\alpha\) such that every used bundle satisfies \(v_t(b)\ge\alpha z_t^\infty\), where \(z_t^\infty=\max_\rho\min_{\rho_b>0}v_t(b)\) over distributions \(\rho\) on \(\mathcal B\) with the same per-capita supplies; decide whether \(\alpha\ge 1/3\).
A high-multiplicity configuration model in which types \(t\) carry mass \(\mu_t\), integral bundle configurations \(b\) receive decision mass \(x_{t,b}\), good supplies are \(\lambda_q\), and the objective is to maximize the common MMS-approximation factor \(\alpha\).
For MMS, a vanishing-mass bundle can determine the finite minimum while disappearing from a limiting supply vector, so \(z_t^\infty\) is not topologically continuous and is not an exact worst-agent limit.
fatal: False
The mirror covers Theorems 2 and 1, while leaving Theorem 3's existence result under identical valuations and general matroid constraints untouched.
There is no named hardness result in this paper. I therefore would not manufacture one. The strongest positive case rests on Theorem 2, with Theorem 1 as a second, closely related anchor. Both are proved in the paper.
The natural regime is a large network of standardized satellite museums, or an analogous resource-allocation system. There are \(N\) branches, with \(N\) much larger than the number \(\tau\) of branch profiles. A type \(t\) is a complete additive valuation vector over recurring exhibit signatures, together with the common cardinality constraints. An exhibit type \(q\) represents many physically distinct exhibits with the same valuation signature and category. Thus \(\mu_t\) is the fraction of branches of profile \(t\), while \(\lambda_q\) is the number of exhibits of type \(q\) per branch in the large-market normalization.
The exhibits remain indivisible. A branch receives an integral bundle, but a positive mass of branches may receive the same bundle. This is not divisible-goods fair division: the fractional object is the population-level frequency of integral bundles.
Formally, let \(\mathcal Q_h\) be the exhibit types in category \(h\), and let
\[ \mathcal B=\left\{b\in\mathbb Z_{\ge 0}^{\mathcal Q}: \sum_{q\in\mathcal Q_h}b_q\le k_h\text{ for every }h\right\}. \]
The decision variable is \(x_{t,b}\), the mass of type-\(t\) agents receiving integral bundle \(b\). It must satisfy
\[ \sum_{b\in\mathcal B}x_{t,b}=\mu_t \]
for every \(t\), and
\[ \sum_{t}\sum_{b\in\mathcal B}b_qx_{t,b}=\lambda_q \]
for every good type \(q\). This is the exact high-multiplicity dictionary: a finite instance with \(n_t\) agents of type \(t\) and \(g_q\) copies of good type \(q\) induces \(\mu_t=n_t/N\) and \(\lambda_q=g_q/N\), while an \(x\) with denominator \(N\) reconstructs a finite allocation.
My lead mirror is Continuum \(1/3\)-MMS under cardinality constraints.
The anchor is Theorem 2, proved in this paper in Section 5. It states that, for every fair-division instance with additive valuations and cardinality constraints, provided the feasible allocation set \(F\) is nonempty, a \(1/3\)-MMS allocation can be computed in polynomial time. Here the constrained maximin share of agent \(i\) is
\[ \mathrm{CMMS}_i= \max_{(P_1,\ldots,P_n)\in F}\min_{j\in[n]}v_i(P_j), \]
and the output allocation \(A\) must satisfy
\[ v_i(A_i)\ge \frac13\,\mathrm{CMMS}_i \]
for every agent \(i\). The theorem is proved here, although its proof invokes the previously published \(1/3\)-MMS algorithm for unconstrained submodular valuations.
The continuous question is this. For each type \(t\), define its continuum constrained maximin share by
\[ z_t^\infty= \max_{\rho} \min\{v_t(b):\rho_b>0\}, \]
where \(\rho\) ranges over distributions on integral bundles \(b\in\mathcal B\) satisfying
\[ \sum_b\rho_b=1 \quad\text{and}\quad \sum_b\rho_bb_q=\lambda_q \]
for every good type \(q\). Thus \(z_t^\infty\) is the best value that type \(t\) can guarantee if the per-capita supply is partitioned into unit-mass integral bundles.
The problem is to compute an allocation \(x\) and the largest \(\alpha\) such that
\[ x_{t,b}>0 \quad\Longrightarrow\quad v_t(b)\ge \alpha z_t^\infty \]
for every type \(t\). The decision version asks whether \(\alpha\ge 1/3\).
This is recognisably the authors’ problem: the categories, additive values, indivisible bundles, and MMS benchmark are unchanged. Only the population counts have been replaced by masses. The expected classification is Class A, at least in the natural bounded-load regime where \(K=\sum_h k_h\) is fixed or small. Then the integral bundle configurations can be handled explicitly, \(z_t^\infty\) is a finite configuration optimization, and the allocation step is a finite mass-assignment problem. For unrestricted succinct \(k_h\), the interesting remaining issue is the pricing/configuration complexity; that is a genuine boundary question rather than a reason to reject the mirror.
The second anchor is Theorem 1, also proved in this paper, in Section 4. It states that every fair-division instance with \(m\) indivisible goods, \(n\) agents, nonnegative additive valuations, partition categories \(C_h\), thresholds \(k_h\), and nonempty feasible set \(F\) admits a polynomial-time computable feasible EF1 allocation. EF1 means that for every pair \(i,j\), there is a good \(g\in A_j\) such that
\[ v_i(A_i)\ge v_i(A_j\setminus\{g\}). \]
Its continuous counterpart is Continuum EF1 under cardinality constraints: find \(x\) satisfying the mass and supply equations above and, for every pair of positive-mass configurations,
\[ x_{t,b}>0,\ x_{u,b'}>0 \quad\Longrightarrow\quad \exists q\text{ with }b'_q>0: \ v_t(b)\ge v_t(b'-e_q). \]
Here \(e_q\) removes one indivisible good of type \(q\). This is the pointwise, bundle-level analogue of EF1, not an average-value relaxation. It asks that almost every branch be EF1 with respect to almost every other branch.
I would also expect this problem to be Class A in the bounded-load regime. The paper’s Greedy-Round-Robin and envy-graph construction can be viewed as operating on repeated type masses rather than enumerating every individual branch. Finite high-multiplicity approximations give a direct existence bridge: apply Theorem 1 to larger and larger replicated instances and take the resulting bundle-frequency limit.
The weakest point is unavoidable: a continuum of agents with only finitely many goods would be degenerate, so the mirror must scale the supply of goods with the population. In addition, it focuses on recurring valuation signatures rather than completely idiosyncratic goods and agents. That is a real modelling restriction, but it is exactly the high-multiplicity regime in which this paper’s cardinality-constrained allocation problem has a natural interpretation. Without repeated branch profiles and repeated exhibit signatures, the number of types grows with \(N\), and there is no meaningful continuous population mirror.
The strongest case against the proposed mirror is that MMS does not have a stable continuum limit. Theorem 2 is a genuine named computational result, so “there is nothing to mirror” is unavailable. The problem is instead that its central benchmark is intrinsically sensitive to agents of vanishing population mass.
For \(N\) agents, \(\mathrm{CMMS}_i\) takes a minimum over all \(N\) bundles. In the proposed limit, \(\rho\) may assign arbitrarily small mass to a bundle, while the proposed \(z_t^\infty\) still lets that bundle determine the minimum whenever \(\rho_b>0\). This creates a discontinuous object rather than a robust continuous relaxation. For example, suppose every bundle may contain at most one good, there are \(N-1\) goods worth \(1\) to an agent and one good worth \(0\). Every finite \(N\)-agent partition contains a zero-valued bundle, so the finite MMS is \(0\). The normalized supply of the bad good tends to \(0\), however, and at the limiting supply vector with no bad good the proposed continuum MMS jumps to \(1\).
There are only three ways out, and each changes the anchor. Retaining the exact finite minimum retains the finite granularity \(1/N\), so there is no genuine continuum problem. Using an essential infimum discards vanishing-mass agents and turns the paper’s universal guarantee into an almost-everywhere guarantee. Requiring robustness against arbitrarily small exceptional masses restores the discontinuity. The resulting mass-assignment problem may be well-defined, but it is not a faithful continuous version of Theorem 2’s maximin-share guarantee. The claimed finite-to-continuous dictionary therefore fails precisely on the worst-case feature that makes MMS meaningful.
Theorem 1 has the same, though weaker, problem. EF1 is quantified over every named pair of agents. A finite allocation can fail because of one exceptional agent or one exceptional bundle, whereas a population distribution cannot record that agent once its mass tends to zero. The proposed condition over positive-support configurations is a legitimate almost-everywhere reformulation, but it is not the theorem’s universal pairwise guarantee. Requiring every individual, including measure-zero exceptions, would require extra atomic data and defeat the pure population-continuum model.
The proponent’s repair—scaling the goods as well as the branches—is mathematically coherent and avoids the trivial fixed-supply limit. It also makes the negative case less decisive: a large system of repeated branch profiles and repeated exhibit signatures is a plausible high-multiplicity regime. The resulting configuration problem is genuinely about population masses, not merely fractional outcomes. Thus the objection cannot honestly be that the model is impossible or meaningless.
The honest negative conclusion is narrower. The paper’s two strongest anchors do admit worthwhile high-multiplicity formulations, but neither preserves the paper’s worst-agent semantics without becoming discontinuous or reintroducing finite granularity. This is a serious warning against presenting the mirror as a direct continuization of EF1 or MMS. It is not, however, enough to sustain the universal claim that no worthwhile continuous mirror exists; the standardized-branch model remains a credible mirror under the programme’s broader, almost-everywhere interpretation.
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.