| paper | Online Fair Division: Analysing a Food Bank Problem |
| authors | M. Aleksandrov, H. Aziz, Serge Gaspers, T. Walsh |
| venue | IJCAI 2015 |
| filed under | fairalloc · chores-online |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational population distribution \(\mu\), utility and like data \(u_t(j), b_t(j)\), and an ordered stream of item blocks \((j_r,\lambda_r)\) with \(\lambda_r\) indivisible items per unit population, evolve fluid BALANCED LIKE using load distributions \(\nu_t(\ell)\), compute its egalitarian or utilitarian welfare and the offline optimum, and determine the exact ratio or whether it is bounded by a supplied constant \(c\).
Types \(t\) carry mass \(\mu_t\); block \(r\) supplies \(\lambda_r\) indivisible items per unit population; \(\nu_t(\ell)\) records mass of type \(t\) at load \(\ell\); the online rule assigns arriving mass among eligible minimum-load agents, while offline variables \(x_{t,r}\) optimize egalitarian or utilitarian welfare.
The mirror covers Theorems 9 and 10, including the LIKE competitive guarantee and the unbounded BALANCED-LIKE ratio. It leaves the strategy-proofness, envy-freeness, and price-of-anarchy results unmirrored because strategic deviations and equilibrium concepts require separate treatment in a nonatomic population.
There is a credible mirror, strongest for the paper’s competitive-analysis results. The paper contains no named NP-hardness, membership-in-\(\mathrm{P}\), FPT, or W[1]-hardness theorem, so I would not invent a complexity anchor. The best anchors are Theorems 9 and 10, both proved in this paper.
A plausible high-multiplicity setting is a national network of food pantries or shelters. There may be \(N\) charities but only a small number of recurring service profiles: for example, charities serving particular diets, communities, or fixed meal schedules. A type \(t\) includes its complete utility vector \(u_t(j)\) for package type \(j\), and, under sincere bidding, its like-report \(b_t(j)=1\) exactly when \(u_t(j)>0\). The society is a distribution \(\mu\) over finitely many such types, with \(\mu_t\) the fraction of charities of type \(t\).
The food supply scales with the population. An ordered stream is represented by blocks \((j_r,\lambda_r)\), where \(\lambda_r\) is the number of items of type \(j_r\) per charity. For rational data, a finite realization with population \(N\) has \(N\mu_t\) charities of type \(t\) and \(N\lambda_r\) indivisible items in block \(r\). The continuous model records the limit after dividing allocations by \(N\). Thus items remain indivisible in every finite realization; only aggregate type-level allocations become fractional.
My lead mirror is Continuous-LIKE Competitive Analysis, based on Theorem 9.
Theorem 9, proved in this paper, states: with general utilities and \(k\) agents, the LIKE mechanism is \(k\)-competitive from both an egalitarian and a utilitarian perspective. The paper also establishes tightness. For egalitarian welfare, the bound is met even with \(0/1\) utilities using \(k^2\) items: the first agent values only the first \(k\) items, while every other agent values every item; the offline optimum gives egalitarian welfare \(k\), whereas LIKE gives welfare \(1\). For utilitarian welfare, the bound is approached with \(k\) items where agent \(i\) values item \(i\) at \(1-(k-1)\varepsilon\) and every other item at \(\varepsilon\); the offline welfare approaches \(k\), while LIKE obtains welfare \(1\).
The continuous problem is this. Given \(\mu\), the utilities \(u_t(j)\), and the item stream \((j_r,\lambda_r)\), compute the egalitarian and utilitarian welfare of sincere LIKE and compare it with the offline optimum.
Let \(q_r=\sum_{t:b_t(j_r)=1}\mu_t\) be the mass of charities bidding for block \(r\). LIKE induces the aggregate allocation \(x^{\mathrm{L}}_{t,r}=\lambda_r\mu_t/q_r\) for bidding types and \(0\) otherwise. The per-charity welfare of type \(t\) is \(w_t=\mu_t^{-1}\sum_r u_t(j_r)x^{\mathrm{L}}_{t,r}\). The continuous egalitarian welfare is \(\min_{t:\mu_t>0}w_t\), and utilitarian welfare is \(\sum_t\mu_t w_t\).
The offline benchmark is the underlying allocation problem, not an encoding: choose \(x_{t,r}\ge 0\) with \(\sum_t x_{t,r}=\lambda_r\), maximizing either \(\sum_{t,r}u_t(j_r)x_{t,r}\), or the largest \(z\) satisfying \(\sum_r u_t(j_r)x_{t,r}\ge \mu_t z\) for every type \(t\). A solution consists of the optimal aggregate allocation and the exact ratio between offline and LIKE welfare, or a certificate that the ratio is at most a supplied \(c\).
I expect this mirror to be tractable, Class A. LIKE’s allocation is given directly by the formula above, while both offline benchmarks are finite linear programs over the type and item-block representation. If \(\mu_{\min}=\min\{\mu_t:\mu_t>0\}\), the natural continuous analogue of the paper’s \(k\)-bound is a \(1/\mu_{\min}\) bound. When there are \(k\) equally sized types, \(\mu_t=1/k\), this becomes exactly \(k\). The important point is that \(N\), the number of charities, disappears from the computation while repeated finite instances retain the original problem.
The secondary anchor is Continuous-BALANCED-LIKE Competitive Analysis, based on Theorem 10.
Theorem 10, also proved here, states: with general utilities and two agents, BALANCED LIKE is not \(c\)-competitive from either an egalitarian or a utilitarian perspective for any constant \(c\). The paper’s witness has items \(a,b,c,d\). Agent 1 has utilities \(\varepsilon,1-2\varepsilon,0,\varepsilon\), while agent 2 has utilities \(0,\varepsilon,\varepsilon,1-2\varepsilon\). The offline allocation gives \(a,b\) to agent 1 and \(c,d\) to agent 2, yielding egalitarian welfare \(1-\varepsilon\) and utilitarian welfare \(2-2\varepsilon\). BALANCED LIKE gives \(a,d\) to agent 1 and \(b,c\) to agent 2, yielding egalitarian welfare \(2\varepsilon\) and utilitarian welfare \(4\varepsilon\). Hence the ratio tends to infinity as \(\varepsilon\) tends to zero.
The continuous version retains the same construction with only two types. Set \(\mu_1=\mu_2=1/2\), and let the ordered item stream have four blocks \(a,b,c,d\), each of mass \(1/2\) per charity. BALANCED LIKE is defined as the fluid limit of the finite mechanism: for each type \(t\), maintain the mass \(\nu_t(\ell)\) of agents who have received \(\ell\) items; each arriving item mass is assigned to eligible agents at the smallest current load, splitting ties proportionally by mass.
The first block goes to type 1, the second to type 2, the third again to type 2, and the fourth to type 1. Thus each type receives two low-value items and has welfare \(2\varepsilon\). The offline solution gives \(a,b\) to type 1 and \(c,d\) to type 2, giving welfare \(1-\varepsilon\) to each type. Both continuous competitive ratios are therefore \((1-\varepsilon)/(2\varepsilon)\), unbounded.
This is still a plausible mirror: it preserves the online order, indivisible package units, sincere like reports, least-loaded allocation rule, and the same offline welfare benchmark. It is not replacing the problem with divisible goods; the fractional quantities describe masses of charities receiving integral bundles.
I would expect exact evaluation of this fluid BALANCED-LIKE instance to be tractable for an explicit finite block stream, though the complexity of evaluating heavily binary-compressed streams is a worthwhile further question. The substantive result is that the continuous limit preserves the paper’s unbounded-performance phenomenon rather than averaging it away.
The mirror covers Theorems 9 and 10 only. I would not force mirrors for the strategy-proofness, envy-freeness, or price-of-anarchy theorems: nonatomic individual deviations become degenerate, and those questions would require a separate coalition or Wardrop-style model.
The weakest point is BALANCED LIKE’s dependence on individual load histories. The population distribution \(\mu\) alone is insufficient; the continuous state must also record the load distribution \(\nu_t(\ell)\). If the programme insists on a finite-dimensional society description containing only \(\mu\), the LIKE mirror remains strong but the BALANCED-LIKE mirror is vulnerable. The positive case therefore rests primarily on Theorem 9: it gives a clean, finite-dimensional high-multiplicity problem whose exact continuous welfare analysis is an LP-plus-closed-form computation, while remaining recognisably the authors’ original online food-bank problem.
The strongest case against this paper is that it contains no theorem about the computational complexity of a problem. Its numbered results concern strategy-proofness, envy, competitive ratios, and price of anarchy. Thus the proposed mirrors are not continuizations of a complexity landscape; they are fluid reformulations of performance analyses for two fixed mechanisms. That is a genuine mismatch with ChoCo’s central ambition.
Theorem 9 is the weaker anchor. If the item stream remains finite while the population tends to a continuum, every individual receives vanishing welfare, so the mirror must also scale the item supply. That repair is permitted by the programme, but it turns the model into a batch-fluid allocation problem. For LIKE, the mechanism then has the closed form
\[ q_r=\sum_{t:b_t(j_r)=1}\mu_t,\qquad x^{\mathrm{L}}_{t,r}=\lambda_r\frac{\mu_t}{q_r}. \]
The random online mechanism has disappeared into this formula. The utilitarian offline benchmark is itemwise, while the egalitarian benchmark is an ordinary finite linear program. There is no difficult separation problem, no exponentially represented type space, and no computational phenomenon arising from the continuous population. The parameter \(N\) merely replicates the same instance: after normalization, the ratio is already determined by \(\mu\).
The proposed \(1/\mu_{\min}\) bound is mathematically sensible, but it is principally a re-expression of the paper’s \(k\)-bound. The rare type that drives the ratio is a parameter of the distribution, not a source of high-multiplicity computation. Asking for the exact ratio or for an LP certificate would be a legitimate optimization exercise, but it is a weak ChoCo mirror: the paper supplies no complexity question, and the continuous version supplies no interesting algorithmic obstruction either. One could enlarge the problem by optimizing over type distributions or streams, but that would be a new online fair-division project rather than a computational mirror of Theorem 9.
Theorem 10 is harder to dismiss. The obvious objections do not work. Scaling the supply is explicitly an admissible co-modification; aggregate fractional allocations are exactly what high multiplicity produces; and welfare depends on utility types rather than personal identities. The load-history issue is also repairable by adding the state distribution \(\nu_t(\ell)\) of loads within each type.
Indeed, the proponent’s example is a valid high-multiplicity realization. Take \(N/2\) agents of each type and \(N/2\) copies of each item \(a,b,c,d\). BALANCED LIKE assigns the \(a,d\) blocks to type \(1\), and the \(b,c\) blocks to type \(2\). Every agent of either type receives two low-value items, giving welfare \(2\varepsilon\). The offline allocation gives \(a,b\) to type \(1\) and \(c,d\) to type \(2\), giving welfare \(1-\varepsilon\). Hence the ratio is
\[ \frac{1-\varepsilon}{2\varepsilon}, \]
which is unbounded as \(\varepsilon\to0\). This is not merely an asymptotic analogy: for suitable integer \(N\), the finite replicated instance has exactly that aggregate behaviour.
One might object that this is only cloning a two-agent counterexample, or that the fluid state \(\nu\) makes the model more than a distribution \(\mu\). Neither objection is fundamental. Cloning identical agents is precisely the high-multiplicity regime, and dynamic allocation mechanisms naturally require state in addition to the population distribution. The four-block instance is also a legitimate continuous online question, even if its answer is easy.
Accordingly, the negative case can make Theorem 9 look unambitious and can insist that the paper has no genuine complexity theorem to continuize. It cannot honestly defeat Theorem 10. That anchor gives a coherent population-continuum model, preserves indivisible items in every finite realization, and retains the paper’s unbounded competitive phenomenon. Since one surviving anchor is enough, the universal claim that this paper has no worthwhile continuous mirror is not defensible.
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.