| paper | Weighted Proportional Allocations of Indivisible Goods and Chores: Insights via Matchings |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.3
statement extracted from the paper’s text layer
Given worker types \(\Theta\) with masses \(\mu_\theta\), entitlement intensities \(e_\theta\) satisfying \(\sum_\theta \mu_\theta e_\theta=1\), class-level ordinal rankings \(\pi_\theta\), class-constant competences \(u_{\theta b}\), and chore classes \(B\) with per-capita supplies \(\rho_b\), where \(N\rho_b\) indivisible copies of class \(b\) are interchangeable and tied in the ordinal domain, find masses \(z_{\theta,S}\) over integral class-count bundles \(S\) such that \(\sum_S z_{\theta,S}=\mu_\theta\), \(\sum_{\theta,S}z_{\theta,S}k_b(S)=\rho_b\), every supported bundle injects into \(q_\theta=\lfloor\rho e_\theta\rfloor+1\) WSD-PROP1 slots with class rank \(R_\theta(b)\ge(\ell-1)/e_\theta\), and \(\sum_S z_{\theta,S}k_b(S)=\mu_\theta e_\theta\rho_b\) for every \(\theta,b\) to realize the BoBW marginal guarantee.
A two-sided high-multiplicity clone market: worker mass is distributed over finitely many complete types, chore supplies scale proportionally, each realized worker still receives an integral bundle, and feasibility is represented by a capacitated bipartite matching or transportation polytope.
The proposed class-total constraints do not reproduce WSD guarantees over strict rankings and instance-specific values of named copies unless copies are explicitly interchangeable and ordinally tied.
fatal: False
The mirror covers the chores-side matching characterization, WSD-PROP1 existence and computation, linear efficiency optimization, and the ex-ante WSD-EF/ex-post WSD-PROP1 construction; it leaves the goods-only full-version results, Pareto incompatibility, mixed resources, and strict-copy rank-maximality variants untreated.
The strongest mirror is a high-multiplicity chore-assignment market, not a model in which chores become divisible. Think of a national maintenance or hospital operation with thousands of workers and thousands of task instances, but only a modest number of worker types. A type \(\theta\) specifies the worker’s complete ordinal ranking \(\pi_\theta\), entitlement intensity \(e_\theta\), and, when efficiency is optimized, competence \(u_{\theta b}\) for each chore class \(b\).
Let \(\mu_\theta\) be the mass of workers of type \(\theta\), with \(\sum_\theta\mu_\theta=1\) and \(\sum_\theta\mu_\theta e_\theta=1\). Let \(\rho_b\) be the number of indivisible copies of chore class \(b\) per unit population, and let \(\rho=\sum_b\rho_b\). A rational \(N\)-replica has \(N\mu_\theta\) workers of type \(\theta\), \(N\rho_b\) physical copies of chore \(b\), and entitlement \(e_\theta/N\) for each worker. Thus the original entitlement convention is preserved exactly: total entitlement is one, while each individual’s entitlement shrinks as the population grows.
The continuous object is the distribution of workers over integral bundles. Chores remain indivisible. If \(S\) is a finite multiset of chore copies, write \(k_b(S)\) for the number of copies of \(b\) in \(S\). A continuous allocation is a mass \(z_{\theta,S}\), meaning that mass \(z_{\theta,S}\) of type-\(\theta\) workers receives the integral bundle \(S\).
The relevant WSD-PROP1 condition has a direct limiting form. Put \(q_\theta=\lfloor \rho e_\theta\rfloor+1\), and let \(R_\theta(b)\) denote the normalized rank of chore \(b\), obtained by dividing its rank in the \(N\)-replica by \(N\). A bundle is admissible for \(\theta\) if its chores can be assigned injectively to slots \(\ell=1,\ldots,q_\theta\), with a chore in slot \(\ell\) satisfying \(R_\theta(b)\ge(\ell-1)/e_\theta\). This is precisely the normalized version of the slot condition in Lemma 3.1 and Proposition 3.2.
My lead anchor is Theorem 3.6, proved in this paper. It states that every chore instance has a WSD-PROP1 allocation; immediately afterwards, the authors give an \(O(m^{2.5})\) Hopcroft–Karp algorithm. Proposition 3.2, also proved here, supplies the key equivalence between WSD-PROP1 allocations and \(B\)-perfect matchings.
The corresponding continuous problem is:
Continuous WSD-PROP1 Chore Allocation. Given \((\Theta,B,\mu,e,\rho,\pi)\), find nonnegative masses \(z_{\theta,S}\) such that every supported bundle \(S\) is admissible for \(\theta\), every type is fully allocated, and every chore supply is exhausted:
\(\sum_S z_{\theta,S}=\mu_\theta\) for every \(\theta\), and \(\sum_{\theta,S}z_{\theta,S}k_b(S)=\rho_b\) for every \(b\).
The decision variable is the population mass \(z\). The feasibility version has objective \(0\); the natural optimization version, matching Section 4.1 of the paper, maximizes aggregate competence, \(\sum_{\theta,S}z_{\theta,S}\sum_bu_{\theta b}k_b(S)\), or minimizes an analogous aggregate cost.
This is a genuine population mirror of Theorem 3.6. At finite scale, \(Nz_{\theta,S}\) workers receive \(S\), and each physical chore copy goes to one worker. No worker receives a fractional chore. The continuous computation is a capacitated version of the paper’s allocation graph: slot \((\theta,\ell)\) has capacity \(\mu_\theta\), chore class \(b\) has supply \(\rho_b\), and edges are exactly the WSD-PROP1 eligibility edges. The expected classification is Class A: a capacitated bipartite matching or transportation LP solves the problem, and the nested-neighborhood argument behind Theorem 3.6 supplies feasibility.
A second, stronger anchor is Theorem 5.3, proved here. It states that Algorithm 1 produces an allocation that is ex-ante WSD-EF and ex-post WSD-PROP1. Theorem 5.2, the Birkhoff–von Neumann decomposition used by the algorithm, is cited from classical matching theory rather than proved here.
The continuous problem is:
Continuous Best-of-Both-Worlds Chore Allocation. Using the same input, find \(z_{\theta,S}\) such that every supported \(S\) is WSD-PROP1 and each type has the proportional marginal allocation \(\sum_S z_{\theta,S}k_b(S)=\mu_\theta e_\theta\rho_b\) for every \(\theta\) and \(b\).
The marginal equation says that each type-\(\theta\) worker receives, on average, \(e_\theta\rho_b\) copies of chore class \(b\). Since \(\sum_\theta\mu_\theta e_\theta=1\), all chore supplies are exhausted automatically. In the \(N\)-replica this is exactly the paper’s fractional WSD-EF allocation in Lemma 5.1: each worker receives the entitlement-proportional share of every chore, but the population is partitioned into workers receiving integral WSD-PROP1 bundles.
This is not merely outcome-space randomization. The finite paper uses a lottery over allocations; the continuum turns that lottery into an actual deterministic division of the population into cohorts. A mass \(z_{\theta,S}\) of real workers receives \(S\). The expected classification is again Class A: Lemma 5.1 gives the fractional matching, Theorem 5.2 decomposes it into integral matchings, and Theorem 5.3 supplies the two fairness guarantees. The decomposition weights become population masses rather than probabilities attached to a single person.
The authors should recognize both formulations as their problem. The preference order, arbitrary entitlement structure, robust “for every compatible cardinal valuation” fairness notion, indivisibility of each chore, and matching-based algorithmic structure are all retained. Only the regime changes: a large cohort of interchangeable workers replaces a small list of named agents. The type grouping is not an artificial loss of information; a type includes every feature used by the problem, including preferences, entitlements, and competence.
The mirror covers the chores-side results around Lemma 3.1, Proposition 3.2, Theorem 3.6, Lemma 5.1, Algorithm 1, and Theorem 5.3. I would not claim that the paper’s Pareto-incompatibility example, the mixed goods-and-chores open problem, or the goods results available only in the full version have been mirrored here.
The weakest point is that the scaling is essential. If one keeps only finitely many unique chores while sending the number of agents to infinity, individual entitlements go to zero and WSD-PROP1 becomes largely vacuous. Likewise, if the application is a one-off inheritance division with a handful of unique items, the high-multiplicity interpretation is poor. The positive case therefore depends on accepting repeated task instances—many workers and many physical copies of a relatively small chore catalogue—as a legitimate regime of the paper’s assignment problem. That is a real limitation, but it is also a concrete, operational scenario in which the continuous population mirror is mathematically faithful and computationally useful.
The strongest negative case is a limit objection, not a complexity objection. The paper plainly contains named computational results—especially Proposition 3.2, Theorem 3.6, Lemma 5.1, and Theorem 5.3—so “there is nothing computational to mirror” is unavailable. Nor is high multiplicity itself objectionable.
The problem is that the paper has no nondegenerate one-sided population limit. If the chore set \(B\) remains fixed while the number of agents grows, then \(\alpha_i=O(1/N)\). Consequently, for sufficiently large \(N\),
\[ \lfloor |B|\alpha_i\rfloor+1=1. \]
By Lemma 3.1, every agent may then receive at most one chore and remove it as the exceptional item. Since there are only finitely many chores, only \(O(1)\) agents receive anything; a measure-one population receives the empty bundle. The WSD-PROP1 guarantee, the competence objective, and the ex-ante allocation all collapse to a null-set phenomenon. The continuum is not describing a large society with meaningful per-capita allocation; it is describing finitely many chores assigned to a population almost all of whom receive nothing.
The proponent’s rescue—scaling the number of chores with the number of agents—is the only plausible one. But it changes the object in a more serious way than their formulation admits. In the paper, every chore is a named item and every preference is a strict permutation of those items. With \(N\rho_b\) copies of a chore class \(b\), a faithful type must specify a ranking of all \(N\rho\) named copies. That ranking space changes with \(N\), and there is no fixed finite type space of the kind used by the continuization programme.
Aggregating copies into classes avoids this explosion only by imposing a new assumption: copies are interchangeable, effectively tied, and have identical relevance to every valuation and objective. But WSD-PROP1 is defined against all additive valuations consistent with a strict ordinal ranking. The class-level marginal condition
\[ \sum_S z_{\theta,S} k_b(S)=\mu_\theta e_\theta\rho_b \]
does not reproduce the paper’s per-item condition unless every copy of \(b\) is genuinely indistinguishable. A canonical tie-breaking order does not solve this: under the paper’s valuation domain, different copies can still have different ranks and values, while the proposed flow records only their class totals.
This defeats the proposed mirror of Theorem 3.6. In the fixed-item limit, the matching graph has only finitely many real item vertices and almost all population slots are irrelevant. In the repeated-copy limit, the capacitated matching formulation is correct only for a tied, homogeneous-copy variant. It is then a new class-based allocation problem, not a continuous version of the theorem as stated. Proposition 3.2 and Theorem 3.6 certify the finite named-item model; they do not supply the missing limit theorem showing that class capacities preserve robust ordinal fairness.
The same problem is sharper for Theorem 5.3. Lemma 5.1 gives each individual agent an \(\alpha_i\)-fraction of every named chore. The proposed condition gives each type the right aggregate number of chores in each class. Those are not equivalent when copies within a class differ in rank, value, or competence. Thus the claimed ex-ante WSD-EF guarantee is either false for the original valuation domain or relies on the additional identical-copy assumption. Under that assumption, turning the Birkhoff lottery into population cohorts is a legitimate interpretation, but it is still exactly the paper’s fractional/randomized allocation implemented by a continuum of clones; the population limit adds no new fairness notion.
The same fault affects stronger variants. Type-constant competence \(u_{\theta b}\) is compatible with the class model only because it assumes away instance-specific competence. If competence is attached to named chore copies, the type space again grows with \(N\). Likewise, the rank-maximal and sequencibility results depend on a finite global order of named items. A “sequence of cohorts” in the limit would require a new definition rather than being the limit of the paper’s picking sequence.
This is nevertheless not an airtight negative case. A genuinely homogeneous market with repeated, interchangeable task copies and weak ordinal preferences is a sensible high-multiplicity allocation problem. If ChoCo accepts that two-sided clone limit as a valid population continuization, then the proponent has a coherent mirror, and existing high-multiplicity matching work supports rather than undermines it.
So the honest conclusion is conditional rather than universal: the exact paper does not yield a nondegenerate continuous population mirror without changing its item semantics. But the claim that no worthwhile scenario exists cannot be defended.
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.