| paper | Asymptotic Analysis of Weighted Fair Division |
| authors | Pasin Manurangsi, Warut Suksompong, Tomohiko Yokoyama |
| venue | IJCAI 2025 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite type set \(T\) with rational masses \(\mu_t\), \(\sum_t\mu_t=1\), weights \(w_t>0\), a finite set \(G\) of item classes, rational per-capita supplies \(\rho_g\), and additive values \(u_t(g)\), decide whether there exists a finite-support family \(\lambda_{t,z}\ge0\), \(z\in\mathbb{Z}_{\ge0}^{G}\), such that \(\sum_z\lambda_{t,z}=\mu_t\), \(\sum_{t,z}\lambda_{t,z}z_g\le\rho_g\) for every \(g\), and \(\sum_g z_g u_t(g)\ge (w_t/W)V_t\) whenever \(\lambda_{t,z}>0\), where \(W=\sum_t\mu_t w_t\) and \(V_t=\sum_g\rho_g u_t(g)\); if the answer is YES, construct \(\lambda\).
A high-multiplicity weighted fair-division model in which each type \(t\) is a complete valuation-and-entitlement template, \(\mu_t\) is its population mass, \(\lambda_{t,z}\) assigns mass to integral bundles \(z\), and \(\rho_g\) is per-capita indivisible supply; the objective is exact WPROP feasibility and construction.
The mirror replaces the iid atomless valuation matrix with deterministic finite templates, so Theorem 3’s high-probability threshold and Erdős–Rényi proof do not carry over; it is therefore an extension rather than a direct continuization.
fatal: False
The mirror covers the constructive weighted-proportionality result in Theorem 3 as a high-multiplicity extension, but leaves Theorem 1’s weighted envy-freeness, Theorem 2’s non-existence threshold, Theorems 4–5’s two-agent asymptotics, and the original iid probability thresholds aside.
There is a credible positive case, but it is an extension of the paper’s setting rather than a literal replacement of \(n\) by a continuum. My lead anchor is Theorem 3, proved in this paper:
If \(D\) is PDF-bounded, the weight ratio is bounded, and \(m\ge (1+\varepsilon)n/(1-\mu)\), then a WPROP allocation exists with high probability; moreover, one can be found in polynomial time.
The natural regime is a large population of residents divided into finitely many valuation-and-entitlement cohorts. A type \(t\) contains the complete utility vector \(u_t\), its weight \(w_t\), and every other parameter used by the allocation problem. The mass \(\mu_t\) is the fraction of the population of that type, with \(\tau\ll N\), where \(N\) is the population scale. This is plausible for communities, employment cohorts, or groups of residents with common valuations and entitlements.
Items remain indivisible, but their supply must scale with population. Let \(G\) be a finite set of item classes, with \(\rho_g\) indivisible copies of class \(g\) per unit population. Thus a finite realization at scale \(N\) has \(N\rho_g\) copies and \(N\mu_t\) agents of type \(t\). This scaling is essential: with finitely many indivisible items and an atomless population, almost every agent would receive nothing.
I would call the continuous problem Community Weighted-Proportional Allocation, \( \mathrm{CWPROP}_\infty \). Its input is rational data \(T,\mu,w,u,\rho\), where \(u_t(g)\) is the value that type \(t\) assigns to one copy of item class \(g\). Define \(W=\sum_t\mu_t w_t\) and \(V_t=\sum_g\rho_g u_t(g)\).
A solution is a finite-support family of nonnegative masses \(\lambda_{t,z}\), where \(z\in\mathbb Z_{\ge 0}^{G}\) is an integral bundle configuration. The constraints are \( \sum_z\lambda_{t,z}=\mu_t \) for every type \(t\), and \( \sum_{t,z}\lambda_{t,z}z_g\le\rho_g \) for every item class \(g\). Every configuration receiving positive mass must satisfy \( \sum_g z_g u_t(g)\ge (w_t/W)V_t \). If no such \(\lambda\) exists, the answer is NO; otherwise the finite list of configurations and masses is the certificate.
This is not fractional allocation of goods. Each \(z_g\) is integral; \(\lambda\) merely says what fraction of identical agents receive each whole bundle. Clearing denominators gives \(N\mu_t\) finite agents and \(N\rho_g\) indivisible item copies, so the rational-clone dictionary is exact.
Theorem 3’s Algorithm 2 suggests a Class A result for the dense, bounded-weight regime. For a threshold \(\theta\), type \(t\) needs \(s_t=\lceil (w_t/W)V_t/\theta\rceil\) items valued at least \(\theta\). Construct a capacitated bipartite graph joining \(t\) to \(g\) whenever \(u_t(g)\ge\theta\), with demand \(\mu_t s_t\) on the type side and supply \(\rho_g\) on the item side. A feasible flow gives a WPROP allocation. The paper’s Lemma 5 and Theorem 3 show why such a matching should exist in the dense random regime; aggregation reduces the computation to a flow problem over types and item classes rather than over \(N\) individual agents.
The paper’s exact threshold \(m/n\ge(1+\varepsilon)/(1-\mu)\) should be treated as a benchmark, not as an automatic theorem for arbitrary type distributions. With atomic types, utilities are correlated across agents, so the concentration proof needs to be redone. Still, the underlying computational question is recognizably the authors’ question: weighted proportionality for additive utilities over indivisible goods, with the same entitlement semantics and a constructive allocation algorithm.
I would not use Theorem 4 as an anchor: it concerns only two agents, so it does not genuinely continuize the population. I would also avoid claiming that unrestricted \( \mathrm{CWPROP}_\infty \) is automatically in P. Without the dense-threshold structure, the configuration formulation may have a knapsack-like pricing problem and could be hard.
The weakest point is therefore substantial: the paper’s non-atomic distribution \(D\) almost surely gives every agent a distinct complete utility type, whereas my mirror requires many exact clones. Repeated item classes and per-capita supply also modify the item side. The positive case survives because the paper itself motivates community allocation, and the proposed model preserves indivisible goods, additive utilities, weights, WPROP, and finite-instance recoverability. The mirror should be labelled an author-recognizable high-multiplicity extension, not a direct translation of the paper’s iid random model.
The strongest anchor is Theorem 3, since it contains a genuine computational statement: Algorithm 2 finds a weighted-proportional allocation in polynomial time with high probability. The best objection is not indivisibility; the proposed scaling of items and rational-clone interpretation handles that correctly. The deeper problem is that the theorem’s asymptotics and its high-multiplicity interpretation pull in opposite directions.
In Theorem 3, every agent’s valuation vector \((u_i(1),\ldots,u_i(m))\) is sampled from an atomless distribution. With probability one, no two agents have the same complete valuation vector. Since a type must include every feature relevant to allocation, the random instance has essentially \(n\) distinct agent types, not \(\tau\ll n\) recurring types. The same issue appears on the item side: the utility vector induced by each item is almost surely unique. Thus the paper’s random model has no genuine finite-type population regime to continuize.
The proposed community model repairs this by replacing the iid valuation matrix with finitely many valuation-and-entitlement templates and finitely many item classes. But that is not a harmless change of presentation. The proof of Theorem 3 depends on the threshold graph being an Erdős–Rényi random bipartite graph: the edges \(u_i(g)\ge\theta\) are independent across individual agents and items. After aggregation, there is only one deterministic edge between each type and item class, repeated for every clone. Increasing the population merely repeats the same graph; it does not produce the concentration phenomenon behind Lemmas 5–7 or the threshold \(m\ge (1+\varepsilon)n/(1-\mu)\).
There is no way to preserve both features. If agents in a cohort share exact valuations, the iid randomness and its high-probability theorem disappear. If they retain independent valuations, their complete types are almost surely distinct. Coarsening valuation vectors into bins would create a potentially useful approximate-fairness problem, but it changes exact WPROP and introduces a quantization parameter. Making item classes random instead requires a second high-multiplicity model for items, again departing from the paper’s instance.
The proposed \(\mathrm{CWPROP}_\infty\) is nevertheless a coherent problem. Its configuration variables \(\lambda_{t,z}\) have an exact finite-clone interpretation, so this is not a merely fractional allocation disguised as continuity. But it is a new deterministic high-multiplicity fair-division problem. The threshold-flow construction is only a sufficient allocation method; exact feasibility requires a configuration formulation whose difficulty is driven by bundle configurations and item classes, not by the population limit. Theorem 3 supplies neither its feasibility theorem nor its complexity classification.
Accordingly, the negative case can defeat the claim that Theorem 3 has a faithful continuous mirror: the named theorem’s computational content is inseparable from iid, agent-specific valuations, while exact high multiplicity removes precisely that structure. The proposed cohort version remains author-recognizable and arguably worthwhile as an independent high-multiplicity extension, however. I cannot honestly defend the stronger universal claim that no continuous mirror is worthwhile in any scenario; that would turn a real mismatch with the paper’s theorem into an objection to a plausible new research problem.
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.