| paper | Dynamic Fair Division Problem with General Valuations |
| authors | Bo Li, Wen-Yang Li, Yingkai Li |
| venue | IJCAI 2018 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | unclear |
Theorem 4 and Theorem 5 both supply named computational results, so the paper clears bit (a). However, the proposed mirrors replace one-player recall with batch cohort recall and do not specify a finite representation of arrival uncertainty or allocation states. A rate-scaled, measure-valued repair is plausible and recognizably related to the paper, but the cases do not settle that it is the same problem.
fails bit b-changes — the continuum limit changes the question
The proposed \(x_q^r\) state treats one recalled cohort as batch recourse; preserving one-player recall instead gives vanishing mass per event and requires a distribution of holdings.
fatal: False
It is undecided whether a rate-scaled, measure-valued recall model is the legitimate high-multiplicity limit of one-player recall rather than a new batch-recourse game. Specifying the arrival scenarios, recall-budget scaling, holding-state representation, and finite encoding would settle it.
The proposed mirror covers Theorems 4 and 5, but leaves Theorems 1–3 and their history-dependent valuation constructions unmirrored.
The strongest positive case is the paper’s uniform-with-demand subproblem, not its fully general valuation model. It has a natural high-multiplicity regime and a matched lower/upper-bound pair.
Consider a cloud-computing or server-allocation system with a very large number of jobs arriving in waves. Every job values any unit of capacity equally, but jobs have different saturation demands. A type is therefore a complete pair consisting of its demand \(d_t\) and its arrival cohort; agents in the same type are interchangeable. If cohort \(q\) has mass \(w_q\), the normalized population distribution is \(\mu_q=w_q/M\), where \(M=\sum_q w_q\). The number of agents \(M\) is large, while the number of demand/cohort types is small.
The resource remains the paper’s divisible resource \([0,1]\); its divisibility is not the continuization target. Let \(x_q^r\) be the total resource assigned to cohort \(q\) after the \(r\)-th arrival, with equal allocation within each cohort. Each member of \(q\) receives \(x_q^r/w_q\), and has value \(v_q(a)=\min\{a/d_q,1\}\).
To preserve the dynamic content, I would use a scalable cohort version of one-recallability: when a new mass cohort arrives, the policy may take resource from at most one previously arrived cohort; allocations of all other cohorts remain unchanged. This is the natural mass-level analogue of recalling one previous player. The fairness requirement is exactly the paper’s one with integer multiplicities replaced by masses:
\[ v_q\!\left(\frac{x_q^r}{w_q}\right) \ge \frac{1}{\eta\max\left\{\sum_{\ell\le r}w_\ell d_\ell,1\right\}} \]
for every arrived cohort \(q\) and every prefix \(r\). The objective is to minimize the worst-case \(\eta\) over all online arrival sequences, without seeing future cohorts.
My lead anchor is Theorem 5, proved in this paper. It states:
For any \(1\)-recallable algorithm \(A\) for the uniform-with-demand problem, \(A\) is \(\Omega(\log n)\)-fair with \(n\) players.
This is a genuine result of the paper, not a citation. It applies to every deterministic \(1\)-recallable algorithm and constructs a geometric adversarial instance with \(m=\log n/3\) stages. Stage \(j\) has \(n/(2\cdot4^{j-1})\) players, each with demand \(8^j/n\). The number of players decreases geometrically while demand increases geometrically, and the proof shows that every such algorithm must have fairness ratio \(\Omega(\log n)\).
The corresponding continuous problem is:
Continuous UD-Recall Minimax. Given a finite demand-type system, a maximum population scale \(N\), and an online arrival protocol over rational mass cohorts, decide whether there exists a deterministic cohort-\(1\)-recallable policy guaranteeing fairness factor at most \(K\) at every prefix. A solution is the causal policy together with the aggregate mass transfers it performs; failure means that an adversarial legal continuation forces some cohort below the \(K\)-fairness threshold.
The most revealing instances are direct mass versions of the theorem’s construction: cohort \(j\) has mass \(N/(2\cdot4^{j-1})\), demand \(8^j/N\), and there are only \(O(\log N)\) distinct cohorts. Even the smallest cohort has growing mass, so this is genuinely high multiplicity: \(N\) is much larger than the number of types. The continuous question is whether the \(\Omega(\log N)\) barrier survives, becomes a function of the smallest positive mass or demand scale, or disappears once individual identities are removed.
I expect this problem to be Class A for explicit finite arrival protocols, at least in a parameterized sense: with finitely many cohorts and types, the allocation quantities are continuous and the fairness constraints are linear once the recalled cohort is fixed. The remaining combinatorial choice is which old type to recall, so fixed-\(\tau\) or fixed-horizon versions should admit enumeration, dynamic programming, or mixed LP techniques. The important point is that tractability would not make the question vacuous: it would determine whether the paper’s logarithmic obstruction is caused by population multiplicity or by the online demand geometry.
A complementary anchor is Theorem 4, also proved here:
For every \(n\ge1\), the \(1\)-recallable algorithm \(A_{\mathrm{UD}}\) is \(O(\log n)\)-fair for the uniform-with-demand problem with \(n\) players.
The algorithm partitions demand values into dyadic bands, recalls an earlier player from the same band, and allocates a carefully chosen amount of resource. The paper proves feasibility and an \(O(\log n)\) fairness guarantee for arbitrary demands. Together, Theorems 4 and 5 establish a tight \(\Theta(\log n)\) approximation scale for this dynamic problem.
Its continuous counterpart is:
Continuous UD-Recall Policy Synthesis. Given a finite type distribution and an online cohort-arrival model, construct a cohort-level \(1\)-recallable policy whose fairness factor is \(O(\log N)\), or determine the best achievable factor. The natural candidate is the paper’s dyadic-band policy with masses replacing player counts and sums of demands replaced by mass-weighted demand totals.
I would expect this constructive problem also to be Class A at the approximation level. The paper’s proof is based on demand bands and aggregate resource accounting, both of which survive fractional masses and lose their integer-rounding complications. The exact optimum may still be difficult when the recall target is part of the decision, but an efficient \(O(\log N)\) policy is a credible continuous result.
This mirror is plausible because it preserves all of the paper’s substantive ingredients: arrival uncertainty, limited recall, demand heterogeneity, prefix-by-prefix fairness, and the same uniform-with-demand utility. It does not merely replace a fractional outcome by another fractional outcome. The continuous object is the population: large cohorts of indistinguishable jobs represented by mass.
I would not extend the claim to Theorems 1–3 without qualification. Their adversaries use highly individualized, adaptively chosen valuation sets, so they do not provide as clean a high-multiplicity regime. The uniform-with-demand section is much stronger: its lower-bound construction already consists of many repeated demand classes.
The weakest point is the recall rule. If “recall one player” is interpreted literally after passing to an atomless population, its aggregate effect vanishes. My mirror therefore replaces it with “recall from one prior mass cohort,” which is a substantive but necessary co-modification. If the authors reject that scaling, the dynamic part collapses toward a static fluid allocation problem. That objection does not invalidate the population mirror itself, but it makes the exact continuous limit of their \(1\)-recallable model an important question rather than an automatic translation.
Finally, this paper supplies no named NP-hardness, membership-in-\(\mathrm P\), or parameterized-complexity theorem. The positive case is therefore a strong model mirror and approximation-complexity question, not a headline hardness-transfer result. Its value for ChoCo is precisely to test whether the paper’s tight \(\Theta(\log n)\) population-dependent phenomenon survives when the society is represented by a small distribution of repeated types.
The strongest negative case is that the proponent’s two anchors are not actually continuous-population versions of Theorems 4 and 5. They are new fluid-control models obtained by changing the paper’s arrival and recall mechanisms at the same time as replacing players by mass.
The difficulty is sharpest for Theorem 5. Its \(\Omega(\log n)\) lower bound concerns individually arriving players and permits recalling at most one previous player per arrival. If a cohort of mass \(w_q\) is treated as one event and the policy may “recall one previous cohort,” then one action can withdraw the entire allocation of \(w_q\) agents. That is not the mass interpretation of one recall; it is batch recourse. Conversely, if one preserves the original rule, a single recall has infinitesimal aggregate mass in the continuum. The aggregate variable \(x_q^r\) is then insufficient: one must track the distribution of holdings among agents of the same demand type, because recalling one member creates an outlier.
The proposed equal-allocation convention does not solve this. Equal treatment is not invariant under one-player recall, and the original theorem quantifies over all algorithms, including algorithms that distinguish otherwise identical players by arrival history and current allocation. To preserve that quantifier, a type must include enough state to identify an agent’s position in the arrival stream and its current holding. That produces a measure over dynamic allocation states rather than the finite distribution over demand/cohort types that the mirror claims to use.
There is also a scale problem. In the paper, the fairness benchmark contains the absolute quantity \(\max\{\sum_i d_i,1\}\). A normalized society distribution \(\mu\) contains only proportions, since \(\sum_q w_qd_q=M\sum_q\mu_qd_q\). The continuous model therefore needs an additional population scale \(M\), together with a decision about whether resource supply, demands, or recall capacity scale with \(M\). Those choices are legitimate modelling decisions, but they are not a harmless translation. They determine whether the limiting object is a batch-allocation problem, a rate-limited fluid queue, or a measure-valued control problem.
Theorem 4 has the same problem in constructive form. Its dyadic demand bands survive formally, but “Continuous UD-Recall Policy Synthesis” is not yet a computational problem with a finite input. A policy is a function over all continuous histories and all admissible future arrival streams. To make it decidable, one must specify a finite horizon, a representation of the adversary’s continuation set, the timing of mass arrivals, the recall-rate constraint, and the encoding of continuous actions. If the arrival protocol is fixed, much of the online uncertainty disappears; if it is adversarial, the model becomes a new dynamic game. Either version may be interesting, but neither is supplied by the paper’s theorem.
The proposed cohort construction also quietly shifts the source of complexity. The paper’s players arrive one at a time, while the proposed mirror presents \(O(\log N)\) mass cohorts. The “one recall” action is consequently redefined at precisely the point where the lower-bound construction uses it. A faithful fluid version would need a recall budget per unit of arriving mass and a time-indexed measure of allocations. That is a plausible research programme, but it is not an LP over a finite type distribution of the kind ChoCo is meant to classify.
The other results do not provide a fallback anchor. Theorem 3 constructs each new valuation from the allocation currently held by player 1, \(v_i(I)=|I\cap A_1^{i-1}|/|A_1^{i-1}|\). The moving valuation target is tied to the individual history of the allocation. Repeating such agents in a type does not preserve the construction; making the history part of the type destroys finite multiplicity. The fully general valuation model has the same issue in a more severe, infinite-dimensional form.
This is not an airtight impossibility result. One can define a legitimate dynamic fluid model with a population scale, a time-indexed arrival measure, a recall-rate constraint, and a measure-valued allocation state. It could be worth studying. But that concession is also the weakness of the negative case: the paper does not rule out such a mirror, and Theorem 5’s repeated-demand construction gives the proponent a credible starting point. The most that can honestly be argued is that the proposed mirror is under-specified and materially changes the computational object; a universal claim that no worthwhile continuous mirror exists is not supportable.
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.