| paper | On Best-of-Both-Worlds Fair-Share Allocations |
| authors | Moshe Babaioff, T. Ezra, U. Feige |
| venue | WINE 2022 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 19
statement extracted from the paper’s text layer
Given finite agent types \(T\) with masses \(\mu_t>0\), item types \(J\) with per-capita supplies \(\sigma_j\ge0\) satisfying \(\sum_j\sigma_j=1\), and additive values \(v_t(j)\ge0\), compute an exchangeable-within-type finite-support lottery over measurable matchings assigning one indivisible item to every infinitesimal agent. Every realization must be Pareto optimal and give every type-\(t\) agent value at least \(\operatorname{TPS}_t=\max\{z\ge0:\sum_j\sigma_j\min(v_t(j),z)=z\}\); if \(U_t\) is the common expected utility of type \(t\), require \(U_t\ge\operatorname{PS}_t=\sum_j\sigma_jv_t(j)\) and \(\exp(\sum_t\mu_t\log U_t)\ge\operatorname{OPT}_\infty/e^{(e+1)/e}\), where \(\operatorname{OPT}_\infty\) is the maximum of \(\exp(\sum_t\mu_t\log(\mu_t^{-1}\sum_jv_t(j)a_{tj}))\) over \(a_{tj}\ge0\) with \(\sum_ja_{tj}=\mu_t\) and \(\sum_ta_{tj}\le\sigma_j\).
A capacitated high-multiplicity matching model with agent-type masses \(\mu_t\) and item-type supplies \(\sigma_j\), indivisible one-item assignments per agent, exchangeable lotteries within types, per-type expected utilities \(U_t\), and weighted \(f\mathrm{NSW}\) as the objective under PS, TPS, and Pareto constraints.
As written, the proposed \(\exp(\sum_t\mu_t\log U_t)\) uses type-average utility, whereas finite-agent \(f\mathrm{NSW}\) averages \(\log\) before exponentiating when copies of one type receive unequal expected utilities; the proponent did not impose exchangeability.
fatal: False
The mirror covers Theorem 19's one-item-per-capita BoBW matching, \(f\mathrm{NSW}\), PS, TPS, and Pareto-efficiency guarantees; it leaves the general \(m>n\) main theorem, Corollary 7's bundle-level PO existence claim, and the paper's other results untouched.
The strongest case is a high-multiplicity market for indivisible goods, with repeated agent and item types. A concrete regime is a national school-seat or aid-package allocation problem: there are \(N\) applicants, many sharing the same valuation vector over a small number of seat/package types, and \(N\sigma_j\) indistinguishable copies of item type \(j\). Each applicant still receives an integral bundle; only the population and supply are represented by masses. Here \(N\) is enormous while \(|T|\) and \(|J|\) are modest.
My lead anchor is Corollary 7, proved in the paper from its main theorem. It states that every additive allocation instance has a randomized allocation supported on at most \(n\) allocations such that every agent receives at least her proportional share ex ante, at least half her truncated proportional share ex post (and hence at least half her MMS), and every supported allocation is Pareto optimal.
I would mirror it with the following problem, which I would call PO-BoBW-TPS\(_\infty\).
An instance consists of a finite voter/agent-type set \(T\), masses \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), a finite item-type set \(J\), per-capita supplies \(\sigma_j\ge 0\), and additive values \(v_t(j)\ge0\). Type \(t\) is a complete valuation type. The corresponding continuous proportional and truncated proportional shares are
\[ \operatorname{PS}_t=\sum_{j\in J}\sigma_jv_t(j) \]
and
\[ \operatorname{TPS}_t=\max\left\{z\ge0:\sum_{j\in J}\sigma_j\min\{v_t(j),z\}=z\right\}. \]
A deterministic allocation is a measurable assignment of an integral bundle \(B\in\mathbb Z_{\ge0}^{J}\) to every infinitesimal agent, subject to the aggregate supply constraints
\[ \int b_j(\omega)\,d\omega\le \sigma_j \]
for every item type \(j\). Thus \(x_{t,B}\) may be fractional as a mass of type-\(t\) agents receiving the integral bundle \(B\), but no individual receives a fractional item.
A solution is a finite lottery \(D\) over such allocations satisfying:
This is not merely an outcome-space relaxation. Given rational \(\mu\) and \(\sigma\), choose \(N\) so that \(N\mu_t\) and \(N\sigma_j\) are integers. The continuous instance expands to a finite instance with \(N\mu_t\) agents of type \(t\) and \(N\sigma_j\) copies of item type \(j\). The finite proportional and truncated shares are exactly the formulas above, and every agent still receives an integral bundle. Conversely, aggregating any such finite allocation by type produces the continuous object. That is precisely the high-multiplicity dictionary the programme wants.
I expect this problem to be a Class A candidate, at least when the number of item types and the per-agent basket size are moderate. The paper’s exceptional-item LP, matching phase, residual allocation LP, and support-reduction LP all have natural capacitated, type-aggregated versions. The main computational question is whether the resulting configuration LP has an efficient pricing algorithm. If unrestricted bundles make pricing knapsack-like, that may identify a genuine continuum-specific boundary rather than invalidate the mirror.
A second, cleaner anchor is Theorem 19, proved in the paper. It says that for additive valuations with at most \(n\) items, there is a randomized allocation in which every agent receives at least her TPS ex post and the allocation is ex-post Pareto optimal; every agent receives at least her PS ex ante; the ex-ante fNSW is within a factor \(e^{(e+1)/e}\approx3.927\) of the optimum; and the associated fractional allocation is computable in polynomial time.
Its continuous mirror is BoBW-Matching-fNSW\(_\infty\). Set \(\sum_j\sigma_j=1\), so there is one indivisible item per unit of population. A realization is a measurable matching assigning one item copy to every agent. Let
\[ U_t(D)=\mathbb E_D\left[\frac{1}{\mu_t}\sum_{j\in J}q^D_{tj}v_t(j)\right], \]
where \(q^D_{tj}\) is the mass of type \(t\) receiving item type \(j\). Require every realization to be Pareto optimal, \(U_t(D)\ge\operatorname{PS}_t\) for every type, and
\[ \exp\left(\sum_{t\in T}\mu_t\log U_t(D)\right) \ge \frac{\operatorname{OPT}_\infty}{e^{(e+1)/e}}, \]
where \(\operatorname{OPT}_\infty\) is the maximum weighted geometric mean over fractional aggregate assignments \(a_{tj}\) satisfying the item-capacity constraints. The output is a finite-support lottery, or equivalently its expected type-by-item assignment together with a decomposition into matchings.
This is especially credible computationally. The fNSW benchmark becomes the weighted concave program
\[ \max \sum_{t\in T}\mu_t \log\left(\frac{1}{\mu_t}\sum_{j\in J}v_t(j)a_{tj}\right), \]
subject to transportation constraints. The paper’s proof transformations, faithful rounding, and Pareto-improving matching step all have direct mass-transport analogues. I would expect this mirror to be tractable to arbitrary precision in time polynomial in \(|T|\), \(|J|\), the encoding length, and \(\log(1/\varepsilon)\).
The authors should recognise both mirrors as their problems, not as unrelated fractional allocation problems. The population is the continuous object; item indivisibility remains at the level of each agent. The repeated-type school-seat interpretation is also stronger than the paper’s motivating story: it supplies a genuine high-multiplicity regime rather than merely relabelling a finite personalized instance.
The weakest point is the Pareto-optimality requirement. The paper explicitly notes that its existential Pareto-improvement step is not claimed to be polynomial-time. In the general bundle version, the continuous PO certificate may therefore become the difficult part, and aggregate type-level Pareto dominance must be defined carefully enough not to lose individual-level meaning. The matching version is safer: Pareto improvements can be found by capacitated matching with per-agent lower bounds.
The paper contains no numbered NP-hardness or coNP-hardness theorem of its own to use as a hardness anchor. Its statement that MMS computation is NP-hard is cited background, not a numbered result proved here. Thus these are algorithmic mirrors, with the general configuration-pricing question left as the natural further challenge.
The strongest negative argument is that the proposed Corollary 7 mirror loses the paper’s central BoBW tension. Write \(x^r_{t,B}\) for the mass of type \(t\) receiving integral bundle \(B\) in realization \(r\). Given a lottery with probabilities \(p_r\), define
\[ \bar{x}_{t,B}=\sum_r p_r x^r_{t,B}. \]
Because supplies and type masses are linear, \(\bar{x}\) is itself feasible. Since every bundle appearing in every realization already gives type \(t\) at least \(\tfrac12\operatorname{TPS}_t\), the atomless type-\(t\) population can simply be partitioned into masses \(\bar{x}_{t,B}\). Every individual still receives an integral bundle, while the average value of type \(t\) is exactly its lottery expectation. Thus the “ex-ante” proportional guarantee and the “ex-post” TPS guarantee coexist in one deterministic continuum allocation.
So, under the proponent’s type-average formulation, randomization and the support bound are artifacts of finite agent granularity. The continuous object is really a configuration allocation, not a continuous analogue of the paper’s best-of-both-worlds mechanism. The Pareto clause does not immediately repair this: a mixture of Pareto-optimal finite allocations need not be Pareto-optimal after type masses are split, while defining Pareto optimality for the aggregate mass allocation produces a stronger, fractional Pareto notion than the paper’s ex-post integral PO.
The obvious repair is to require every infinitesimal agent, rather than merely every type on average, to receive proportional share ex ante. But then one must add an atomless identity space and a specified exchangeable lottery or measure-preserving randomization within each type. Alternatively, one can force all members of a type to move together, but that makes an entire type bloc indivisible and no longer represents the ordinary high-multiplicity regime in which identical agents may receive different bundles. Either repair adds correlation or identity structure not contained in \((\mu,\sigma)\). The paper does not study that extra structure.
The same objection applies to Theorem 19 as stated. The proponent’s weighted objective
\[ \exp\!\left(\sum_t \mu_t\log U_t\right) \]
is not generally the high-multiplicity version of the paper’s fNSW. If copies of one type receive different expected utilities, the finite objective becomes an average of logarithms,
\[ \exp\!\left(\sum_t\int_{I_t}\log u(\omega)\,d\omega\right), \]
not the logarithm of the type-average utility. The two differ by Jensen’s inequality. The proposed mirror therefore silently replaces individual-agent fNSW by a type-average welfare objective. That is a legitimate new problem, but not an exact mirror of Theorem 19.
These objections defeat the mirrors as written, but they do not honestly establish the requested universal negative. A corrected Theorem 19 mirror can impose exchangeability within each type, making every copy have the same ex-ante utility; then the weighted fNSW formula becomes exact. With one item per unit mass, the problem is a genuine capacitated high-multiplicity matching problem in which individuals still receive integral items. The population-continuum question is not merely outcome-space fractionalization.
Consequently, the negative case is materially weaker than the positive one. Corollary 7 is a poor anchor because its BoBW content largely collapses under anonymous mass splitting, and its PO enhancement is not algorithmic in the paper. But the matching/fNSW anchor survives a careful repair, so I cannot honestly 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.