| paper | Improved Approximation of Weighted MMS Fairness for Indivisible Chores |
| authors | Fangxiao Wang, Bo Li, Pinyan Lu |
| venue | IJCAI 2024 |
| filed under | fairalloc · shares |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given finite rational agent types \(T\) with masses \(\mu_t\), weight densities \(\eta_t>0\) satisfying \(\sum_t\mu_t\eta_t=1\), chore categories \(O\) with rational per-capita supplies \(q_o\), and additive costs \(v_t(o)\), choose masses \(y_{t,b}\ge0\) over whole integer bundles \(b\in\mathbb Z_{\ge0}^{O}\) satisfying \(\sum_b y_{t,b}=\mu_t\) and \(\sum_{t,b}y_{t,b}b_o=q_o\), minimizing \(\alpha\) subject to the support-wise constraints \(v_t(b)\le\alpha W_t^\infty\) whenever \(y_{t,b}>0\), where \(W_t^\infty=\eta_t\inf_z\sup\{v_t(b)/\eta_r:z_{r,b}>0\}\) and \(z_{r,b}\) denotes mass of recipient type \(r\) receiving bundle \(b\).
A high-multiplicity allocation of repeated indivisible chore copies: \(\mu_t\) is employee-role mass, \(\eta_t\) is normalized responsibility density, and \(y\) is a configuration flow assigning whole integer bundles to agent mass while chore supplies scale proportionally.
The proponent's essential-supremum formulation would erase \(o(N)\) exceptional agents and therefore fails to preserve the source's every-agent guarantee; support-wise fairness and a finite-realization theorem are still required.
fatal: False
It covers the offline all-agent \(O(\log n)\)-approximation setting of Theorem 1, while leaving the two-agent optimal ratio in Theorem 2 and the online \(O(\sqrt n)\) guarantee in Theorem 3 unmirrored.
The strongest honest mirror is for the paper’s Theorem 1: “For any fair allocation instance, there is an \(O(\log n)\)-approximate WMMS allocation.” This is proved in the paper, using Algorithm 2 and Lemmas 1–6; Lemma 4 is credited to Feige and Huang (2023), although its proof is reproduced. The paper contains no named hardness result, so this is a tractability mirror rather than a hardness-transfer case.
The natural regime is a large organization with many employees and a recurring workload. There are \(N\) employees but only \(\tau\) genuinely different roles. A type records an employee’s complete valuation vector over chore categories and her responsibility level. Thus all employees of type \(t\) have the same additive costs \(v_t\) and the same weight density \(\eta_t\). Think of thousands of employees in a small number of standardized roles, jointly handling many repeated but still indivisible jobs. We take \(N\gg\tau\), with the supply of each chore category scaling proportionally with \(N\).
Here is the continuous problem I would put forward.
Continuous WMMS Allocation\(_\infty\) — lead mirror of Theorem 1. An instance consists of a finite type set \(T\), a population distribution \(\mu\) with \(\sum_t\mu_t=1\), positive weight densities \(\eta_t\) satisfying \(\sum_t\mu_t\eta_t=1\), a finite set of chore categories \(O\), a per-capita supply \(q_o\) of each chore category \(o\), and additive costs \(v_t(o)\). A bundle is an integral vector \(b\in\mathbb Z_{\ge 0}^{O}\), with cost \(v_t(b)=\sum_{o\in O}v_t(o)b_o\).
A solution is a nonnegative mass assignment \(y_{t,b}\): \(y_{t,b}\) is the mass of type-\(t\) agents receiving the whole indivisible bundle \(b\). It must satisfy \(\sum_b y_{t,b}=\mu_t\) for every type \(t\), and \(\sum_{t,b}y_{t,b}b_o=q_o\) for every chore category \(o\). Thus continuity applies to the population of agents, not to an individual chore: a chore copy is always assigned whole to one agent.
For a focal type \(t\), define its continuous weighted maximin share by \(W_t^\infty=\eta_t\lambda_t^\infty\), where \(\lambda_t^\infty\) is the infimum, over all feasible population allocations \(z\), of the essential maximum of \(v_t(b)/\eta_r\) over bundles \(b\) assigned to recipient type \(r\). Given an allocation \(y\), its approximation ratio is \(\alpha(y)=\max_t \operatorname*{ess\,sup}_{b\sim y_{t,\cdot}}v_t(b)/W_t^\infty\). The computational task is to find a feasible \(y\) minimizing \(\alpha(y)\), or to decide whether an \(\alpha\)-WMMS\(_\infty\) allocation exists.
This is genuinely the high-multiplicity form of the paper’s problem. For any sufficiently large \(N\), construct \(N\mu_t\) agents of type \(t\), give each such agent weight \(\eta_t/N\), and create \(Nq_o\) copies of chore \(o\). Then the discrete WMMS of a type-\(t\) agent is
\( \displaystyle \frac{\eta_t}{N}\min_A\max_{r,j}\frac{v_t(B_{r,j})}{\eta_r/N} =\eta_t\min_A\max_{r,j}\frac{v_t(B_{r,j})}{\eta_r}. \)
The continuous benchmark is therefore the mass-limit of the paper’s benchmark, with named-agent granularity removed. Rational continuous allocations can be approximated by sufficiently large discrete instances, giving the required downward and upward dictionary.
I would expect this mirror to be Class A, at least for the ordered and proportional regimes that drive the paper’s analysis. Algorithm 2 already constructs an aggregate fractional allocation based only on weights and rankings, rather than on agent identities. In the high-multiplicity model, duplicate agents can be grouped into type masses, and the allocation becomes a configuration-flow problem over bundles. The finite-agent rounding step in Lemma 4 is precisely the correction that must be replaced by a population-level packing argument. The likely outcome is a type-sensitive approximation algorithm, perhaps with a guarantee depending on the number of distinct type or weight classes rather than on \(N\), using a configuration LP and separation over feasible bundles. The continuous version may even be exact in special ordered cases.
The main questions it generates are whether the relevant configuration LP has polynomial-time separation, whether the paper’s ordered-instance reductions survive aggregation without loss, and whether every feasible continuous allocation admits a finite-\(N\) integral realization with vanishing additive error. If bundle pricing remains knapsack-like even after continuization, that would mark a possible continuum-specific boundary; the paper itself does not settle this.
I would not use Theorem 2 as an anchor: its statement is specifically for \(n=2\), so it has no convincing many-agent regime. Theorem 3 is also a possible future online mirror, but its \(O(\sqrt n)\) guarantee suffers from the same problem as Theorem 1 when \(n\) becomes the population scale.
The weakest point is that Theorem 1’s stated \(O(\log n)\) guarantee becomes vacuous as \(N\to\infty\). The positive case therefore cannot honestly claim that the theorem transfers unchanged. Its claim is narrower: the theorem exposes an aggregate allocation structure whose natural high-multiplicity formulation is Continuous WMMS Allocation\(_\infty\), and that problem is a credible candidate for a type-parameterized Class A result. A referee could reject the mirror if “continuous” were interpreted as splitting one chore among agents; the bundle-mass formulation is essential to keep it a population continuization rather than an unrelated divisible-goods problem.
The only serious anchor is Theorem 1, and it does clear the named-result gate: it gives an \(O(\log n)\)-approximation algorithm for WMMS. The negative case therefore has to attack the limit, not pretend the theorem is merely axiomatic.
If the population is replicated while the chore set remains fixed, the mirror degenerates. With \(m\) chores, at most \(m\) agents receive nonempty bundles, so
\[ \frac{\#\{i:A_i\neq\varnothing\}}{n}\le \frac{m}{n}\longrightarrow 0. \]
Almost every atomless agent receives nothing. The source predicate is an every-agent guarantee,
\[ v_i(A_i)\le \alpha\,\mathrm{WMMS}_i\quad\text{for every }i, \]
whereas the proposed essential supremum only constrains agents almost everywhere. The finitely many agents who carry all chores disappear into a null set. That is a semantic collapse of WMMS, not an uninteresting algorithmic answer.
The proposed rescue—scaling the chore supply with the population and introducing repeated chore categories—is coherent, but it is no longer a direct mirror of Theorem 1. The paper has an arbitrary finite item set, arbitrary item-specific valuations, and no canonical relationship between \(m\) and \(n\). The rescue adds a second asymptotic regime, a finite item-type alphabet, per-capita inventories, and a configuration space of integer bundles. Clearing denominators recovers only the restricted family of replicated-agent, replicated-chore instances; it does not recover the theorem’s general instances.
More importantly, the proposed \(y_{t,b}\) formulation has to choose between two failures. If fairness is imposed through expected or average bundle cost, indivisible WMMS has been replaced by a divisible or lottery relaxation. If it is imposed support-wise, as the original every-agent condition requires, then every positive-mass integer bundle configuration must satisfy the constraint. The resulting problem is an infinite configuration-packing problem with knapsack-like pricing. None of Lemmas 1–6 establishes separation, finite support, or preservation of the ordered/proportional reductions in that model. Calling it “likely Class A” is therefore speculation, not a transferred consequence of the paper.
The essential-supremum formulation also loses \(o(n)\) exceptional agents: a finite realization may contain a bad bundle assigned to one agent, while the limiting measure records no violation. Replacing essential fairness by a support-wise or uniform condition repairs this, but creates a new fairness predicate and new finite-realization obligations. The weight-density parameter \(\eta_t\) is similarly a sensible rescaling, but it is not literally the paper’s normalized individual weight; it is an additional modelling choice justified by scale invariance.
Thus the strongest negative conclusion is that Theorem 1 has no non-degenerate direct population limit. Fixed supplies make the limit vacuous; scaled supplies produce a new two-sided high-multiplicity configuration problem whose central questions are not supplied by the paper. I would classify the proponent’s construction as a plausible independent extension, not a faithful continuous mirror of the theorem.
The negative case is not airtight. A recurring standardized-workload organization with repeated employee roles and repeated chore categories is genuinely plausible, and whole-bundle mass assignments do preserve indivisibility better than a fractional-goods relaxation. So I could defend “no direct mirror” strongly, but not honestly claim that no worthwhile continuous research problem exists in any such 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.