| paper | Maximin Fairness with Mixed Divisible and Indivisible Goods |
| authors | Xiaohui Bei, Shengxin Liu, Xinhang Lu, Hongao Wang |
| venue | AAAI 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: Polynomial-time solvable for every fixed positive approximation tolerance; the algorithm achieves nearly full MMS. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 4.1
Given a finite type set \(T\), rational society masses \(\mu\in\Delta_T\), per-capita supplies \(q_g\) of indivisible good kinds, additive values \(v_{rg}\), and non-atomic cake densities \(f_r\) in the Robertson–Webb model, compute a finite-support mass allocation \(x_{r,b}\) of integral bundles \(b\in\mathbb{Z}_{\ge0}^{\mathcal{G}}\) together with a finite cake-allocation protocol, satisfying \(\sum_b x_{r,b}=\mu_r\) and \(\sum_{r,b}x_{r,b}b_g\le q_g\), such that every type-\(r\) recipient receives at least \((1-\epsilon)\alpha' s_r\), where \(\alpha'\ge\min\left\{1,\frac12+\min_{r:\mu_r>0}\frac{h_r}{2s_r}\right\}\), \(h_r=\int f_r\), and \(s_r\) is the per-capita MMS benchmark obtained by partitioning normalized resources into unit mass of integral bundles and cake shares.
High-multiplicity mixed fair division with type masses \(\mu\), per-capita indivisible supplies \(q\), additive valuations \(v_r\), and atomless cake densities \(f_r\). Decision variables are configuration masses \(x_{r,b}\) and cake pieces; the objective is to maximize the guaranteed ratio to each type's per-capita MMS \(s_r\), or to achieve the theorem's target \(\alpha_\infty=\min\left\{1,\frac12+\min_{r:\mu_r>0}\frac{h_r}{2s_r}\right\}\).
The paper does not prove that its finite-agent MMS benchmark converges to \(s_r\), nor provide a finite certificate or compressed algorithm for the mass allocation; this leaves the computational relationship to the anchor open but does not invalidate the question.
fatal: False
The mirror covers the mixed-goods MMS guarantee, approximate MMS estimation, and population-level computation. It leaves Theorem 3.4, the EFM comparison, and most structural existence discussion without mirrors; Theorem 3.2 and Corollary 3.3 are supporting equalities rather than independent computational anchors.
The strongest positive case is a genuine high-multiplicity version of the paper’s mixed-goods allocation problem. The paper already has a divisible cake, so the mirror must not merely point to that cake. It should make the population of recipients continuous while retaining integral bundles of indivisible goods.
A plausible regime is a large public allocation: \(K\) households receive standardized indivisible goods and a divisible resource such as money, land, or service capacity. There are only \(\tau\) household types. Type \(r\) completely specifies the household’s values \(v_{rg}\) for each indivisible good kind and its density \(f_r\) over the divisible resource. A society is \(\mu\in\Delta_\tau\). The finite \(K\)-agent realization has \(K\mu_r\) agents of type \(r\), \(Kq_g\) copies of each indivisible good kind \(g\), and \(K\) copies of the divisible resource. Thus \(\mu\) and \(q\) are per-capita quantities.
The continuous allocation has mass variables \(x_{r,b}\), where \(x_{r,b}\) is the mass of type-\(r\) agents receiving the integral bundle \(b\in\mathbb Z_{\ge0}^{G}\). They satisfy \(\sum_b x_{r,b}=\mu_r\) and \(\sum_{r,b}x_{r,b}b_g\le q_g\). Only the masses \(x_{r,b}\) are fractional: every realized individual bundle remains integral. Atomless cake is allocated among these cohorts, with a measurable cake allocation \(\eta_{r,b}\). The utility of a type-\(r\) cohort is \(v_r\cdot b\) plus its per-agent cake value.
Let \(s_r\) be the high-multiplicity MMS benchmark for type \(r\): the largest \(z\) for which the per-capita resource can be decomposed into mass one of integral bundles, with cake shares, every bundle having type-\(r\) value at least \(z\). Equivalently, \(s_r\) is the normalized limit of the finite MMS value in the \(K\)-agent realizations. Let \(h_r=\int f_r\) be type \(r\)’s value for one per-capita copy of the divisible resource.
My lead anchor is Theorem 4.1, proved in this paper. It says that every finite mixed-goods instance has an \(\alpha\)-MMS allocation, where \( \alpha=\min\left\{1,\frac12+\min_{i\in N}\frac{u_i(C)}{2(n-1)\mixMMS_i}\right\} \). Moreover, for every constant \(\epsilon>0\), the paper computes in time polynomial in \(n,m,L\) a ratio \(\alpha'\ge\alpha\) and an allocation that is \((1-\epsilon)\alpha'\)-MMS.
The corresponding continuous problem is:
\(\textsc{HM-Mixed-MMS-Approx}\). Given \((\mu,q,v,f)\) and \(\epsilon>0\), output a measurable mixed-goods allocation, together with a computable ratio \(\alpha'\), such that \(\alpha'\ge\alpha_\infty\) and every type-\(r\) agent receives utility at least \((1-\epsilon)\alpha' s_r\), where \( \alpha_\infty=\min\left\{1,\frac12+\min_{r:\mu_r>0}\frac{h_r}{2s_r}\right\} \).
The normalization is forced by the high-multiplicity regime: in a \(K\)-agent realization, \(u_r(C)=Kh_r\), while the denominator \(n-1\) is approximately \(K\). This is therefore the direct population analogue of Theorem 4.1, not a cake-only restatement.
I expect this problem to be Class A, at least with finitely many agent and good types and a fixed approximation parameter. The paper’s two-phase proof has a natural mass version. The “big-good” phase becomes allocation of positive mass to integral configurations; the bag-filling phase becomes a flow/configuration allocation; and the cake step is already an atomless mass-allocation problem. Weighted proportionality is especially natural here. The underlying optimization is an LP over masses of integral configurations, with pricing over configurations—the same continuous-optimization shape emphasized by the programme.
The paper’s Theorem 3.2 and Corollary 3.3 also support this reading: Theorem 3.2 preserves every agent’s utility and MMS value when replacing cake pieces by frozen indivisible pieces, and Corollary 3.3 concludes \( \gamma_I=\gamma_M \). Thus the mixed-goods fairness problem is not merely about divisible outcomes; indivisibility remains structurally meaningful even after the population is made high-multiplicity.
A useful secondary anchor is Lemma 4.6, also proved in the paper, although it uses Woeginger’s cited PTAS for indivisible goods. It states that, for any mixed-goods instance, constant \(\epsilon>0\), and agent \(i\), one can compute in polynomial time a partition \(P_1,\ldots,P_n\) of the goods such that \( \min_j u_i(P_j)\ge(1-\epsilon)\mixMMS_i(n,M\cup C) \). The proof discretizes the cake into \(O(n/\epsilon)\) small intervals, treats them as indivisible goods, and invokes the indivisible-goods PTAS. The lemma also yields a computable value \(\mixMMS'_i\) satisfying \( \mixMMS_i\ge\mixMMS'_i\ge(1-\epsilon)\mixMMS_i \).
Its population mirror is:
\(\textsc{HM-MMS-Estimate}\). Given \((\mu,q,v,f)\), a type \(r\), and \(\epsilon>0\), output a computable lower bound \(s'_r\) and a mass-one decomposition of the normalized resources into integral configurations such that every configuration has type-\(r\) value at least \(s'_r\), with \(s_r\ge s'_r\ge(1-\epsilon)s_r\).
I again expect Class A. Cake discretization becomes a constant-\(\epsilon\) collection of per-capita micro-resources, and the resulting high-multiplicity configuration problem is exactly the sort of object for which configuration LPs and high-multiplicity optimization are appropriate. This estimate can then feed the lead problem’s computation of \(\alpha'\).
The paper contains no named NP-hardness theorem of its own that I would honestly use as an anchor. Its statement that exact MMS computation is NP-hard is attributed to Kurokawa, Procaccia, and Wang; it is not presented here as a numbered theorem. I therefore would not manufacture a hardness-transfer claim. The two anchors above are algorithmic and the expected outcome is tractability, with continuum-specific hardness as a meaningful possible boundary if compressed configuration pricing proves difficult.
The weakest point is the encoding issue. The paper’s polynomial bounds are in the explicit number \(n\) of agents and \(m\) of goods. Our mirror compresses \(K\) repeated agents and \(K\) repeated goods into \(\mu\) and \(q\). It does not follow automatically that the paper’s algorithms remain polynomial in the compressed input size. In particular, high-multiplicity configuration pricing may be hard when the number of good kinds is part of the input. That is a real technical vulnerability. It does not undermine the mirror itself: if pricing is hard, this becomes a precise Class C result rather than evidence that the population continuization was artificial.
The scope is therefore deliberately focused on the paper’s Section 4 MMS existence, approximation, and computation results. Further questions include whether finite \(K\)-agent allocations converge to the mass allocation with an explicit rounding rate; whether the normalized analogue of Corollary 4.2 holds under the threshold \(h_r\ge s_r\); whether the paper’s “cake can hurt” phenomenon from Theorem 3.4 survives at the population level; and whether high-multiplicity MMS estimation is polynomial, FPT in the number of good types, or continuum-specifically hard.
The proponent’s case succeeds in showing that a high-multiplicity mixed-goods model can be invented. It does not show that the paper’s results survive as computational results in that model. The strongest negative case is therefore that both anchors lose their algorithmic content exactly at the compression step that makes them relevant to ChoCo.
For Theorem 4.1, the limiting ratio is plausible: under \(K\)-fold scaling, \(u_r(C)=Kh_r\), \(n=K\), and one may expect \(\mathrm{MMS}_{r,K}\) to converge to a per-capita benchmark \(s_r\). But the theorem’s algorithm does not continuize with it. Its two phases remove agents and goods one at a time, perform up to \(K-1\) rounds, and invoke an MMS approximation procedure on an explicitly expanded instance. A compressed input containing rational supply rates \(q_g\) may encode \(K\) exponentially large in its bit length. Thus the paper’s polynomial bound in \(n,m,L\) becomes exponential in the high-multiplicity input size.
The proposed repair—an LP over masses \(x_{r,b}\) of integral configurations—is a legitimate new problem, but not a consequence of Theorem 4.1. The configuration set is potentially infinite when multiplicities are binary encoded, and the cake allocation \(\eta_{r,b}\) has no finite output representation as stated. A finite formulation requires proving bounded support, a rounding theorem, and an efficient pricing or separation procedure. That pricing problem is a high-multiplicity packing problem, not the paper’s bag-filling algorithm. It may be tractable, or it may be continuum-specifically hard, but either outcome would be new work rather than a continuous mirror already motivated computationally by the theorem.
Lemma 4.6 is weaker still as an anchor. Its discretization uses \(\lceil 2n/\epsilon\rceil\) cake intervals. Under \(K\)-fold scaling, the total cake value is \(Kh_r\), so the construction needs \(\Theta(K/\epsilon)\) pieces, not \(O(1/\epsilon)\) pieces in the compressed representation. Treating a per-capita cake slice as one indivisible micro-good silently replaces the individual cake portions by a fractional resource and changes the partition problem. Treating the slices as genuine indivisible goods leaves an explicitly expanded instance. Woeginger’s PTAS for that expanded list therefore gives no polynomial-time algorithm in the high-multiplicity encoding.
The same issue defeats the claimed algorithmic support from Theorem 3.2 and Corollary 3.3. The reduction freezes the cuts from every agent’s MMS partition. With \(K\) agents, each partition has up to \(K-1\) cuts, so even after identifying equal valuation types there are generally \(\Theta(K)\) cake pieces per type. In the continuum there is no finite frozen-piece instance of the kind used in the proof. Moreover, the reduction is explicitly noncomputational because it assumes the MMS values and partitions are already known. Corollary 3.3 is a worst-case equality of guarantees, not a compressed algorithm or a population-level complexity result.
There is also a genuine modelling fork that the positive case papers over. If the original finite stock of indivisible goods is kept fixed while the population grows, per-agent supply tends to zero and the MMS benchmark often degenerates. If goods are scaled per capita, one has introduced repeated good kinds, binary multiplicities, configuration distributions, and a new notion of per-capita MMS. That is a sensible high-multiplicity fair-division problem, but it is not merely the paper with voters replaced by masses. The paper supplies no result that distinguishes whether its finite guarantee converges to that benchmark, whether convergence has a usable rate, or whether the resulting allocation has a finite certificate.
This is not an objection that the answer might be easy; an easy answer would still be worthwhile. It is an objection that the proposed mirrors have not yet identified a computational problem inherited from the paper. The continuous population is doing the compression, while the paper’s actual algorithms rely on the uncompressed number of agents, cake pieces, and goods.
The honest limitation is that this does not establish the universal negative claim. A carefully formalized finite-type, per-capita-supply configuration problem is a worthwhile ChoCo question, and its eventual classification could be Class A or Class C. What the negative case defeats is the stronger claim that Theorem 4.1, Lemma 4.6, or Theorem 3.2 already provide a substantive continuous computational anchor. The paper is therefore a weak negative verdict, not a convincing “no mirror in any scenario.”
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.