| paper | Maximin-Aware Allocations of Indivisible Chores with Symmetric and Asymmetric Agents |
| authors | Tianze Wei, Bo Li, Minming Li |
| venue | IJCAI 2023 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 1
Given finite agent types \(\Theta\), mass distribution \(\mu\), entitlements \(r_\theta\) with \(\sum_\theta \mu_\theta r_\theta=1\), type-dependent chore costs \(a_{\theta j}\), and per-capita supplies \(\sigma_j\) of \(q\) indivisible chore classes, choose a configuration measure \(p_{\theta,b}\) over \(b\in\mathbb{Z}_{\ge0}^q\) satisfying \(\sum_b p_{\theta,b}=1\) and \(\sum_{\theta,b}\mu_\theta p_{\theta,b}b_j=\sigma_j\), minimizing \(\alpha\) subject to \(A_\theta(b)-a_{\theta j}\le\alpha H_\theta\) for every supported \(b\) and every \(j\) with \(b_j>0\), where \(A_\theta(b)=\sum_j a_{\theta j}b_j\) and \(H_\theta=r_\theta\min_z\max_{z_{\theta',b}>0}A_\theta(b)/r_{\theta'}\) over configuration measures \(z\) matching \(\mu\) and \(\sigma\).
A high-multiplicity allocation model with agent-type mass \(\mu\), per-capita chore supply \(\sigma\), integral bundle configurations \(b\), configuration policy \(p\), and objective of minimizing the MMAX approximation factor \(\alpha\) relative to the continuous weighted maximin-share benchmark \(H_\theta\).
In the limit, removing one agent changes the remaining supply by vanishing mass, so \(H_\theta\) becomes policy-independent and may no longer capture the paper's distinctive tagged-agent epistemic semantics; compact pricing and rounding are also absent.
fatal: False
The mirror covers Theorem 1, Corollary 1, and Corollary 2 in repeated-workload high-multiplicity regimes, but leaves the paper's relational propositions and non-computational fairness comparisons untouched.
There is a credible positive mirror, but it requires the right regime: many agents and a recurring, standardized workload, rather than a fixed handful of agents sharing a fixed handful of chores. My strongest anchor is Theorem 1.
Take a finite set of complete agent types \(\Theta\), where a type \(\theta\) specifies an additive cost \(a_{\theta j}\) for every chore class \(j\in\{1,\ldots,q\}\), together with a relative entitlement \(r_\theta\). The society is a distribution \(\mu\) over \(\Theta\). Thus \(\mu_\theta\) is the fraction of agents with exactly that cost vector and entitlement. Assume \(\sum_\theta \mu_\theta r_\theta=1\).
The natural regime is a large cloud, public-works, or operations workforce: \(N\) agents, \(N\mu_\theta\) agents of type \(\theta\), and \(N\sigma_j\) individually indivisible tickets of chore class \(j\). A ticket is assigned whole to one agent. The number of types \( \tau=|\Theta| \) and chore classes \(q\) is small compared with \(N\). Roles, locations, contracts, and standardized responsibilities explain why agents share complete types. The mass \(\mu_\theta\) is genuinely population mass; the \(\sigma_j\)'s are only per-capita supplies of discrete chore copies.
A bundle pattern is \(b\in\mathbb Z_{\ge 0}^q\), where \(b_j\) is the number of class-\(j\) chores assigned to one agent. Let \(p_{\theta,b}\) be the fraction of type-\(\theta\) agents receiving bundle \(b\). Feasibility requires \(\sum_b p_{\theta,b}=1\) for every \(\theta\), and \(\sum_{\theta,b}\mu_\theta p_{\theta,b}b_j=\sigma_j\) for every chore class \(j\). The cost of \(b\) to type \(\theta\) is \(A_\theta(b)=\sum_j a_{\theta j}b_j\).
The continuous weighted maximin-share benchmark is the configuration value \(H_\theta=r_\theta\min_z\max_{z_{\theta',b}>0}A_\theta(b)/r_{\theta'}\), where \(z_{\theta',b}\ge0\), \(\sum_bz_{\theta',b}=\mu_{\theta'}\), and \(\sum_{\theta',b}z_{\theta',b}b_j=\sigma_j\). This is exactly the limit of the paper's weighted maximin share for one type-\(\theta\) agent after removing one agent: removing one agent changes population mass by \(1/N\), which vanishes in the limit.
The action variable is therefore the population distribution \(p\) over indivisible bundle configurations. The objective is to minimize the smallest approximation factor \(\alpha\) satisfying the relevant MMA condition.
The lead problem is:
*Continuous Asymptotic MMAX.* Given \((\Theta,\mu,r,a,\sigma)\) and \(\varepsilon>0\), output a feasible policy \(p\) such that, for every type \(\theta\), every bundle \(b\) used by that type, and every chore \(j\) with \(b_j>0\), \(A_\theta(b)-a_{\theta j}\le (1+\varepsilon)H_\theta\).
Equivalently, one may minimize \(\alpha\) subject to these inequalities. This is a direct continuum version of MMAX: the “any item” quantifier remains over indivisible chore copies, while the population of agents is represented by mass.
This is anchored in the paper's Theorem 1, proved there. For a finite expansion with \(N\) agents, the theorem gives a \((1+\lambda_N)\)-MMAX allocation, where for \(N\ge3\), \(\lambda_N=(3-N+\sqrt{N^2+10N-7})/(4N-4)\). Since \(\lambda_N\) tends to \(0\), the theorem predicts an exact MMAX condition in the continuum limit, or an arbitrarily accurate \((1+\varepsilon)\)-MMAX policy for sufficiently large \(N\). The asymmetric-agent feature survives through the type entitlements \(r_\theta\).
I expect this problem to be Class A in the fixed-catalogue regime. The policy is a configuration measure, and the relevant feasibility and pricing problems have the same column-generation shape as other high-multiplicity allocation problems. The paper's swap algorithm becomes a redistribution of mass between bundle configurations. For unrestricted \(q\), however, the configuration pricing problem may itself encode packing; that would be a possible Class C boundary rather than evidence that the mirror is artificial.
The second question is the exact one-item relaxation:
*Continuous MMA1 Allocation.* Given the same instance, output a feasible policy \(p\) such that for every type \(\theta\) and every used nonempty bundle \(b\), there exists \(j\) with \(b_j>0\) and \(A_\theta(b)-a_{\theta j}\le H_\theta\).
This is the exact high-multiplicity analogue of the paper's MMA1 definition. It is anchored in Corollary 1, stated and derived in this paper. The proof uses Lemma 1, also proved there, together with the polynomial-time weighted-EF1 algorithm cited from Wu et al. (2023). Every finite expansion admits an MMA1 allocation; taking the empirical distribution of bundle assignments and passing to a high-multiplicity limit gives the continuous policy.
I would also expect this to be Class A for a fixed finite chore catalogue. The “there exists one item” choice is over \(q\) chore classes rather than over \(N\) named agents, and the underlying finite problem is already polynomial-time solvable. The main technical question is whether the type-level configuration problem admits a polynomial pricing oracle when \(q\) is variable.
A third, useful specialization is:
*Equal-Entitlement Continuous MMAX.* Impose \(r_\theta=1\) for every type and output a feasible policy satisfying \(A_\theta(b)-a_{\theta j}\le H_\theta\) for every used bundle and every item in it.
This mirrors Corollary 2, stated in the paper and obtained from Lemma 2 together with the cited polynomial-time EFX algorithms of Li et al. (2022) and Bhaskar et al. (2021). It is a particularly plausible regime for a large workforce in which every worker has the same formal entitlement but different task disutilities. Here the expected classification is again Class A for a fixed catalogue, with the unrestricted configuration-pricing version left as an interesting possible continuum-specific hardness problem.
These mirrors cover the paper's computational existence and construction results: Theorem 1, Corollary 1, and, in the equal-entitlement specialization, Corollary 2. They do not claim to continuize every relationship in Figure 1. In particular, Proposition 1 warns against replacing MMA by PROPX: a naïve proportional continuous mirror would lose the very maximin-aware content that makes the paper distinctive.
The main weakness is that a literal limit with a fixed finite chore set does not work: as the population becomes nonatomic, almost everyone receives the empty bundle. The proposed mirror therefore uses \(N\sigma_j\) copies of each chore class as \(N\) grows. That is a scaling of discrete supply, not fractionalization of an individual chore: every finite instance still contains indivisible tickets, every bundle pattern \(b\) is integral, and only the distribution of agents over bundle patterns is continuous. A referee who insists that only the number of agents may scale, while the number of chores remains fixed, can reasonably reject the mirror. In the realistic recurring-workload regime, though, the authors' own cloud-scheduling motivation makes the construction recognizable as their problem in a high-multiplicity form.
The strongest negative case is that all three anchors depend on the same feature that disappears in a population limit: MMAX asks what happens after removing one particular agent and comparing that agent’s bundle with the worst possible distribution of the remainder.
With a fixed finite chore set, the mirror is immediately degenerate. If there are \(N\) agents but only \(m\) indivisible chores, at most \(m\) agents receive nonempty bundles. The mass of all nonempty bundles is at most \(m/N\), so the limiting allocation assigns the empty bundle to almost everyone. The continuous policy \(p_{\theta,0}=1\) is then feasible and satisfies the fairness conditions vacuously. Thus a population-only limit cannot carry any of the paper’s content.
The proponent’s repair—\(N\sigma_j\) copies of each chore class—is the best possible response, but it concedes the central objection. This is no longer merely a continuization of the population. It is a new repeated-resource model in which every item in a class has identical costs for every agent type. If one preserves the paper’s arbitrary item-specific costs, the number of chore types grows with the instance and the compression disappears. If one fixes \(q\) chore classes, one has changed the resource ontology and restricted the problem to a highly structured extension. That extension may be sensible, but it is not what Theorem 1, Corollary 1, or Corollary 2 established.
More importantly, the proposed \(H_\theta\) exposes a semantic collapse. In an \(N\)-agent clone expansion, give a type-\(\theta\) agent weight \(r_\theta/N\), and suppose that agent receives a finite bundle \(b\). Removing her changes the normalized supply by only \(b/N\). Consequently,
\[ \operatorname{MMS}_i(X_{-i},N-1) \longrightarrow r_\theta \min_z \max_{z_{\theta',b}>0} \frac{A_\theta(b)}{r_{\theta'}}=H_\theta, \]
independently of the actual allocation policy \(p\) and, in the limit, independently of the tagged agent’s bundle. The paper’s allocation-dependent “maximin-aware” benchmark therefore becomes a fixed population-wide threshold. MMAX has lost the feature that made it a hybrid of envy and maximin share: the identity and removal of the particular agent no longer matter.
There are only three ways around this. Let a tagged agent retain positive mass, which produces a mixed atom-and-continuum model rather than a population continuum. Remove a positive-mass coalition, which changes MMA into a coalition notion. Or make each individual’s bundle infinitesimal, in which case the chore costs and the fairness constraints collapse to zero. None preserves the original one-agent epistemic semantics.
Theorem 1 does not repair this. The fact that
\[ \lambda_N= \frac{3-N+\sqrt{N^2+10N-7}}{4N-4} \longrightarrow 0 \]
is a finite-instance approximation guarantee, not a continuous algorithm. Running Algorithm 1 on \(N\) replicated agents and \(N\sigma_j\) replicated chores is polynomial in the expanded value of \(N\), not in the binary encoding of \(\mu\), \(\sigma\), and the type catalogue. The proposed configuration formulation introduces bundle columns whose multiplicities may be exponentially large in the input length. Computing the relevant \(H_\theta\) is itself a high-multiplicity partition/configuration problem. The paper supplies neither a compact pricing oracle nor a rounding theorem from the proposed mass policy back to the finite indivisible problem. Thus the theorem predicts a limit heuristically, but does not establish a Class-A continuous problem.
Corollary 1 is no stronger. Its polynomial algorithm is polynomial in the explicit numbers of agents and chores. Cloning a compressed type instance can be exponentially larger than its rational description, so the corollary gives no polynomial algorithm for the proposed continuous input. The “there exists one item” condition can be retained over chore classes, but doing so yields a new support-constrained configuration problem. It is not a computational consequence of the corollary.
The same objection defeats Corollary 2. Equal entitlements remove asymmetry in the weights, but they do not restore the lost tagged-agent semantics. The proposed equal-entitlement MMAX problem still uses the fixed threshold \(H_\theta\), and the cited finite EFX machinery still operates on an explicit list of items and agents. Extending it to a compact distribution over integral bundle configurations requires a new high-multiplicity algorithm and a new proof that its support constraints can be priced or rounded efficiently.
So the best negative verdict is: the literal population limit is trivial, while the only nontrivial repair is a recognizable but substantial repeated-workload re-modelling. All three anchors then become new configuration-allocation problems whose MMAX benchmark has lost its allocation-dependent meaning and whose compressed complexity is not supplied by the paper.
This is not an airtight universal impossibility claim. A standardized recurring workload with repeated chore tickets is genuinely plausible, and a reader who accepts extension-level mirrors may judge it worthwhile. But it does not support the proponent’s stronger claim that Theorem 1, Corollary 1, and Corollary 2 straightforwardly yield continuous ChoCo problems.
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.