| paper | No agent left behind: dynamic fair division of multiple resources |
| authors | Ian A. Kash, Ariel D. Procaccia, Nisarg Shah |
| venue | ATAL 2013 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 4
statement extracted from the paper’s text layer
Given \(m\) resources, \(K\) ordered arrival cohorts with rational masses \(\rho_1,\ldots,\rho_K\) summing to \(1\), normalized positive demand vectors \(d^1,\ldots,d^K\in\mathbb{Q}_{>0}^m\), and \(q_k=\sum_{\ell\le k}\rho_\ell\), compute at each epoch \(k\) an irrevocable per-unit allocation \(a^k_\ell=y^k_\ell d^\ell\) maximizing \(M_k\) subject to \(y^k_\ell\ge M_k\), \(y^k_\ell\ge y^{k-1}_\ell\) for \(\ell<k\), and \(\sum_{\ell\le k}\rho_\ell y^k_\ell d^\ell_r\le q_k\) for every resource \(r\); determine whether the rule satisfies continuum analogues of SI, DEF, DPO, and a specified strategyproofness notion in time polynomial in \(m\), \(K\), and encoding length \(L\).
A finite-support society over operational types \((k,d^k)\) with mass \(\rho_k\); each unit of mass receives a proportional Leontief bundle \(a^k_\ell=y^k_\ell d^\ell\), aggregate resource use is weighted by \(\rho_\ell\), and the mechanism maximizes the minimum per-unit dominant share subject to irrevocability and prefix capacity \(q_k\).
The opponent’s best point is that a zero-mass individual cannot affect the weighted LP, so the paper’s individual strategyproofness proof does not automatically provide a meaningful continuum guarantee; a pointwise nonatomic convention or positive-mass bloc notion must be fixed.
fatal: False
The mirror covers the LP-based mechanisms and guarantees in Theorems 4 and 11 for finitely supported arrival-demand populations, while leaving the arbitrary individual-arrival model, the impossibility result in Theorem 3, and the empirical comparisons outside its scope.
There is a credible continuous mirror here, although it is an algorithmic one rather than a hardness-dissolution result. The paper contains no named NP-hardness, coNP-hardness, or parameterized-hardness theorem. Its strongest anchors are Theorem 4 and Theorem 11, both proved in the paper, each asserting polynomial-time implementability.
My lead mirror is the continuous version of Theorem 4.
Consider a cloud or cluster serving a very large population of jobs. Jobs arrive in \(K\) batches, with batch \(k\) having mass \(\rho_k>0\), \(\sum_k\rho_k=1\). Every job in a batch has the same normalized Leontief demand vector \(d^k\in\mathbb{Q}_{>0}^m\), with \(\max_r d^k_r=1\). The operational type is therefore \((k,d^k)\): arrival epoch matters because allocations are irrevocable. The total population may contain billions of jobs, while \(K\) and the number of distinct demand vectors are small.
Let \(q_k=\sum_{\ell\le k}\rho_\ell\). Resources have total capacity \(1\), and at epoch \(k\) the mechanism may use at most a \(q_k\)-fraction of each resource, mirroring the paper’s \(k/n\) entitlement. If a unit of mass of type \(d\) receives bundle \(a\), its utility is
\[ u_d(a)=\min_{r\in R}\frac{a_r}{d_r}. \]
The action variable is the per-unit allocation \(a^k_{\ell}\) assigned to each previously arrived batch \(\ell\), subject to irrevocability and aggregate resource feasibility. In the non-wasteful form \(a^k_{\ell}=y^k_{\ell}d^\ell\), the continuous analogue of the paper’s DYNAMIC DRF LP is
\[ \begin{aligned} \max\quad & M_k\\ \text{s.t.}\quad & y^k_\ell\ge M_k &&(\ell\le k),\\ & y^k_\ell\ge y^{k-1}_\ell &&(\ell<k),\\ & \sum_{\ell\le k}\rho_\ell y^k_\ell d^\ell_r\le q_k &&(r\in R). \end{aligned} \]
The output is the allocation path \(a^k_\ell=y^k_\ell d^\ell\) at every arrival epoch. When every batch has mass \(1/n\) and \(y^k_\ell=nx^k_\ell\), this is exactly the paper’s finite LP, since
\[ \sum_{\ell\le k}\frac1n y^k_\ell d^\ell_r = \sum_{\ell\le k}x^k_\ell d^\ell_r \le \frac{k}{n}. \]
The named anchor is Theorem 4: “DYNAMIC DRF satisfies SI, DEF, DPO, and SP, and can be implemented in polynomial time.” Here SI means every present agent receives at least its equal-share utility; DEF means an agent may envy an earlier agent only if that earlier agent has received nothing since the later agent arrived; DPO means the current allocation is not Pareto-dominated by an allocation using only the current agents’ cumulative \(k/n\) resource entitlement; SP means no agent can misreport its demand and become strictly better off at any stage. The theorem is proved in this paper.
My continuous problem is therefore:
Continuum-Dynamic-DRF. Given \(m\), rational batch masses \(\rho_1,\ldots,\rho_K\), and demand reports revealed batch by batch, compute an irrevocable allocation rule that, at every prefix, maximizes the minimum per-unit dominant share subject to aggregate feasibility, SI, DEF, DPO, and individual strategyproofness.
For finitely supported populations, I expect this to be tractable in \(\operatorname{poly}(m,K,L)\), independent of the number of individual jobs. The LP has only \(K+1\) variables and \(K+m\) constraints at each stage. This is not merely “resources are divisible”: the population itself has become a mass distribution, and the algorithm operates on batch masses rather than named agents.
The strategyproofness clause needs care. Literal individual SP survives only as a pointwise condition for a zero-mass agent and can become nearly vacuous in a purely aggregate implementation. A stronger and more interesting follow-up is positive-mass bloc strategyproofness: can a submass of a homogeneous type jointly misreport and improve its true utility? Theorem 4 does not establish that stronger property.
The second anchor is Theorem 11, also proved here: “CAUTIOUS LP satisfies SI, EF, CDPO, and SP, and can be implemented in polynomial time.” EF requires that no present agent prefer another present agent’s allocation. CDPO requires that the current allocation is not Pareto-dominated by an alternative allocation that remains extendable to an envy-free allocation for every possible future demand sequence. SP again forbids profitable demand misreports.
The corresponding continuous problem is:
Continuum-Cautious-LP. Given a current mass allocation and an unknown future mass \(1-q_k\), compute an irrevocable allocation that is envy-free, SI, strategyproof, and not Pareto-dominated by any allocation that can be extended to an envy-free allocation for every future demand distribution.
The continuous version of the paper’s cautious constraint is
\[ \sum_{\ell\le k}\rho_\ell y^k_\ell d^\ell_r + (1-q_k)y^k_t d^t_r \le 1 \qquad(t\le k,\ r\in R), \]
where the second term represents the worst case in which all future mass has the demand type \(d^t\). The jump-start condition is
\[ y^k_k\ge \max_{\ell<k} \left( y^{k-1}_\ell \min_{r\in R}\frac{d^\ell_r}{d^k_r} \right). \]
This is supported directly by Lemma 9, proved in the paper: an allocation is EF-extensible for every possible future demand sequence if and only if it has an EF extension whenever all future agents share the demand vector of one of the currently present agents. In the continuous model, that reduces an apparently infinite family of future distributions to one constraint for each current type. Lemma 10 supplies the corresponding minimum EF extension.
I would also expect Continuum-Cautious-LP to be tractable for finite support, with complexity polynomial in \(m\), \(K\), and the encoding length. The high-multiplicity gain is especially clear here: the mechanism reasons about the remaining mass \(1-q_k\), not about each future agent separately.
These mirrors are plausible because they preserve the paper’s actual question: online, irrevocable allocation of multiple resources under Leontief demands and dynamic fairness constraints. They do not continuize time; arrival remains an ordered finite sequence of epochs. They do not rely merely on the paper’s already-divisible outcome space; the new object is the population measure over demand-and-arrival types.
The weakest point is that this paper is a relatively modest ChoCo candidate. Its results are axiomatic mechanism-design results, not discrete computational hardness results. Thus the continuous versions are expected to remain tractable rather than reveal whether population multiplicity dissolves hardness. Moreover, if the authors insist that agents must arrive individually in an arbitrary order, replacing them by positive-mass batches may be viewed as a restriction. The positive case is strongest in the realistic high-multiplicity regime of repeated job templates and arrival cohorts, where the compressed population is genuinely the intended object.
The strongest negative case is that the proposed mirrors preserve the paper’s resource-allocation LP only by abandoning the paper’s genuinely dynamic and strategic object.
For Theorem 4, the batch formulation is mathematically coherent, but it is an exact aggregation of identical agents. Once all agents sharing an arrival epoch and demand vector receive the same bundle, the displayed weighted LP is simply the finite DYNAMIC DRF LP after rescaling \(x\) to per-unit mass \(y\). The population measure contributes weights, but no new computational structure: the mechanism still operates on finitely many labelled cohorts.
More seriously, the paper’s strategyproofness is individual. In a nonatomic society, one agent has zero mass and cannot affect the aggregate LP. Its report is therefore either irrelevant to the allocation, making strategyproofness vacuous, or it selects from a report-dependent menu, in which case the paper’s proof no longer applies. That proof relies on the manipulator consuming a positive term in a tight resource constraint. A positive-mass bloc can affect that constraint, but “no bloc can profitably misreport” is a new coalition-strategyproofness requirement, not the SP asserted by Theorem 4.
Trying to retain arbitrary arrival order does not repair this. Arrival time is part of an agent’s operational type, because it determines when its report is available and which allocations are irrevocable. If agents retain distinct arrival positions, the type space contains \((d,\theta)\), and high multiplicity disappears in the relevant coordinate. If arrival is discretized into \(K\) cohorts, the model has been changed to synchronized batch arrivals. That may be a reasonable new model, but it is not the paper’s sequential mechanism with a continuous population substituted for \(n\).
Theorem 11 has the same defect. With finitely many synchronized cohorts, the cautious constraints are a sensible weighted restatement, and Lemma 9 may well extend. But then EF-extensibility and CDPO are being checked for cohort allocations, while the paper’s SP again concerned individually arriving, individually reporting agents. With a genuinely continuous demand or arrival distribution, the constraints become an infinite-dimensional robust-extension problem whose representation and separation oracle are not supplied by the paper. The proponent’s finite-support LP avoids that issue precisely by returning to a finite batch model.
Thus the alternatives are unsatisfactory in opposite ways: finite cohorts yield a compressed implementation of an already explicit LP, while preserving individual arrival and manipulation makes the population continuum either strategically vacuous or a different mechanism-design problem. A positive-mass strategyproofness theory could certainly be worth studying, but it would be a new theory of dynamic group reporting, not a continuous mirror of Theorems 4 or 11.
This is not an airtight impossibility claim: synchronized cohorts of repeated cloud jobs are a plausible high-multiplicity regime. The negative conclusion is instead that the paper does not offer a worthwhile ChoCo mirror without replacing its central strategic unit—an individual arrival and report—with a new one.
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.