| paper | Fair Distribution of Delivery Orders |
| authors | Hadi Hosseini, Shivika Narang, Tomasz Wąs |
| venue | IJCAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5
statement extracted from the paper’s text layer
Given a rooted unweighted tree \(G=(V,E)\) with hub \(h\), \(n\) couriers, and a rational distribution \(\mu\in\mathbb{Q}^{T}_{\ge 0}\) over \(T=V\setminus\{h\}\), where \(x_{it}\ge 0\) and \(\sum_i x_{it}=\mu_t\), compute a feasible mass allocation that is MMS and Pareto optimal under \(c_i(x)=\sum_{e\in E}\mathbf{1}[\sum_{t\in D_e}x_{it}>0]\), with \(M_\infty=\min_y\max_i c_i(y)\), requiring \(c_i(x)\le M_\infty\) for all \(i\) and no feasible \(y\) with \(c_i(y)\le c_i(x)\) for every \(i\), strictly for one.
A high-multiplicity population of delivery orders: \(\mu_t\) is the fraction of orders at route-location type \(t\), \(x_{it}\) assigns mass to courier \(i\), and each courier's cost is the support-induced number of visited subtree edges.
Because route costs depend only on support, \(\mu\)'s magnitudes are operationally irrelevant and duplicate co-located orders require a natural multiset extension of the paper's graph model.
fatal: False
The mirror covers the MMS/PO computation and related decisions in Theorem 5, the MMS-SO hardness in Proposition 3, and MMS hardness in Theorem 1; it leaves EF1-specific questions, EFX, price-of-fairness results, and experiments unmirrored.
The strongest affirmative case is a high-multiplicity mirror on the delivery-order population. I would describe it as an extension mirror, but one the authors should recognise as their problem rather than as an unrelated fractional-allocation model.
Consider a large postal or Meals-on-Wheels campaign. There are \(N\) delivery orders, with \(N\gg \tau\), concentrated on \(\tau\) route-relevant location types. A type records everything affecting the problem: graph location, service requirements, and package class. The mass \(\mu_t\) is the fraction of orders of type \(t\). The \(n\) couriers remain the finite allocation recipients, typically a small number of interchangeable volunteer teams. Thus this is a population-of-orders mirror: many demand units share types, while the delivery decision is still made over the same rooted graph.
Let \(G=(V,E)\) be the paper’s rooted tree with hub \(h\), let \(T=V\setminus\{h\}\), and let \(\mu\in\mathbb{Q}^{T}_{\ge 0}\) satisfy \(\sum_{t\in T}\mu_t=1\). For each edge \(e\), write \(D_e\) for the delivery types below that edge. A mass allocation is
\[ x=(x_{it})_{i\in[n],t\in T},\qquad x_{it}\ge 0,\qquad \sum_{i=1}^{n}x_{it}=\mu_t. \]
Courier \(i\)'s route cost is
\[ c_i(x)=\sum_{e\in E} \mathbf{1}\!\left[\sum_{t\in D_e}x_{it}>0\right]. \]
Thus a positive mass of orders below an edge still forces that courier to visit the edge. This preserves the paper’s coverage-function/subtree cost rather than replacing it by an additive valuation.
My lead anchor is Theorem 5, proved in this paper. It gives an XP algorithm parameterized by \(n\) that computes an MMS and PO allocation, and decides the existence of MMS and SO, EF1 and PO, and EF1 and SO allocations. The corresponding continuous problem is:
\[ \textsf{MMS\text{-}PO}_{\infty} \]
Given \((n,G,h,\mu)\), compute a mass allocation \(x\) that is both MMS and Pareto optimal. Define
\[ M_\infty(\mu,G,n) = \min_{y} \max_{i\in[n]} c_i(y), \]
where the minimum ranges over all feasible mass allocations \(y\). The allocation \(x\) must satisfy \(c_i(x)\le M_\infty\) for every \(i\), and there must be no feasible \(y\) with \(c_i(y)\le c_i(x)\) for all \(i\), with strict inequality for at least one courier.
This is recognisably the authors’ MMS-and-PO problem: the graph, hub, route cost, fairness threshold, and Pareto predicate are unchanged. Only the multiplicity of indistinguishable delivery orders has become a rational mass. If \(\mu_t=a_t/N\) and \(x_{it}=b_{it}/N\), clearing denominators recovers \(a_t\) identical orders of type \(t\) and an ordinary allocation of those clones.
I expect this mirror to be Class A in the natural small-\(n\) regime. Theorem 4 already gives the crucial structural mechanism: retain only nondominated cost vectors. In an unweighted tree each coordinate lies in \(\{0,\ldots,|E|\}\), so the number of relevant cost vectors depends polynomially on the number of route types for fixed \(n\), not on the denominator of \(\mu\). The continuous analogue should therefore admit a type-level Pareto-frontier dynamic programme, or a configuration formulation with rational mass-conservation constraints, running in \(f(n)\operatorname{poly}(\tau,L)\) time. The paper’s \(O((n+2)!m^{3n+2})\) algorithm is not already such a theorem, but it supplies the exact invariant one would need to remove dependence on the number \(N\) of cloned orders.
A second, genuinely different anchor is Proposition 3, also proved here. It states that an SO allocation satisfying MMS need not exist, and that checking whether such an allocation exists is NP-hard. Its continuous counterpart is:
\[ \textsf{MMS\text{-}SO\text{-}Existence}_{\infty} \]
Given \((n,G,h,\mu)\), decide whether there exists a feasible mass allocation \(x\) satisfying both
\[ c_i(x)\le M_\infty(\mu,G,n) \quad\text{for every }i \]
and
\[ \sum_{i=1}^{n}c_i(x) = \sum_{e\in E} \mathbf{1}\!\left[\sum_{t\in D_e}\mu_t>0\right]. \]
The second condition is the continuous SO condition: every used edge is visited by exactly one courier. Outputting \(x\) is a certificate of yes; outputting no is the decision answer.
I expect this problem to be Class B. Under SO, positive mass from two couriers cannot lie below the same edge. In particular, each branch leaving the hub must be assigned wholly to one courier, so the branch-partition combinatorics survives continuization. The hardness is therefore carried by graph topology and multiway partitioning, not by the number of separately named orders. Rational masses and denominator clearing do not obviously remove it. This is exactly the kind of boundary the ChoCo programme wants: \(\textsf{MMS\text{-}PO}_{\infty}\) may admit a compact frontier algorithm, while the SO restriction retains discrete branch hardness.
Theorem 1, proved here using Proposition 2, gives further support for the same programme: the paper’s ordinary MMS problem is NP-hard even though MMS allocations always exist. The plain continuous version is obtained by asking only for an \(x\) attaining \(M_\infty\). I would expect its unrestricted complexity to depend on whether the fractional mass relaxation admits an integrality theorem. Establishing that dichotomy would itself be a useful result: either MMS hardness transfers through branch structure, or the population relaxation dissolves the discrete partition obstruction.
The authors should find the scenario plausible. Their own motivating applications include postal delivery, Meals on Wheels, newspapers, and leaflets, all of which naturally generate large cohorts of orders over a relatively small set of route-relevant locations. The mirror covers the paper’s unweighted-tree MMS, PO, SO, Pareto-frontier, and XP results. It does not claim to cover EF1 directly: “up to one order” has no stable atomless limit unless one retains a finite granularity parameter or replaces it with an \(\varepsilon\)-notion.
The weakest point is that the paper’s fairness agents are couriers, whereas the continuous population above consists of delivery orders. Moreover, repeated orders at the same vertex do not increase a route’s travel cost, so the magnitude of \(\mu_t\) can matter less than in ordinary continuous allocation models. I would therefore label this an author-recognisable high-multiplicity extension, not a literal direct mirror. A stricter two-sided version would also give courier types masses \(\rho_r\), scale orders and couriers together, and represent allocations as distributions over route configurations. That extension is more demanding, but it preserves the same MMS, Pareto, and subtree-cost questions. The central open questions are whether mass splitting changes the MMS threshold, whether Theorem 5 can become polynomial in \((\tau,L)\) for fixed \(n\), and exactly which part of Proposition 3’s hardness survives denominator-free population scaling.
The proponent’s mirror fails before complexity enters: in this paper, delivery cost is a function of support, not mass. Let \(T=V\setminus\{h\}\), and let \(x_{it}\) be the mass of type \(t\) assigned to courier \(i\). Define \(S_i=\{t:x_{it}>0\}\). For every \(t\) with \(\mu_t>0\), choose one courier \(i(t)\) with \(x_{i(t)t}>0\), and assign all of \(t\)’s mass to that courier. This produces an unsplit allocation \(\bar{x}\) with \(S_i(\bar{x})\subseteq S_i(x)\) for every \(i\). Since the route cost is monotone,
\(c_i(\bar{x})\le c_i(x)\)
for every courier.
Thus every fractional mass allocation can be purified without worsening any courier’s cost. In particular,
\(M_\infty(\mu,G,n)=\min_{A\in\Pi_n}\max_i c(A_i)\),
where the right-hand side is exactly the paper’s original MMS-cost problem on the vertices having positive mass. The numerical values of \(\mu_t\) disappear entirely; only whether \(\mu_t=0\) matters. A society with proportions \(1/2,1/2\) and one with proportions \(10^{-9},1-10^{-9}\) induce exactly the same optimization problem whenever their supports coincide.
This defeats the proposed anchor based on Theorem 5. A Pareto-optimal mass allocation can also be purified: if purification strictly lowered some cost, the original allocation was not Pareto optimal; otherwise the purification gives an ordinary allocation with the same cost vector. Consequently, the continuous MMS-and-PO problem has the same Pareto frontier as the discrete vertex-partition problem. The paper’s frontier algorithm is already operating on precisely those cost vectors. Recasting the assignment variables as rational masses does not create an LP or a genuinely continuous configuration problem, because the indicator \(\mathbf{1}[\sum_{t\in D_e}x_{it}>0]\) preserves the original support combinatorics.
There is also no meaningful compression of the type space. To evaluate a courier’s cost, a type must retain its exact route-relevant location, namely which edges lie on its path from \(h\). Distinct vertices generally have distinct effects on the union of visited edges. If they are merged into a coarser “route type,” the cost is no longer determined by the type distribution. Hence either \(\tau\) is essentially the number of graph vertices, in which case this is the original finite problem, or the type definition loses information needed to state the problem.
The denominator-clearing argument does not repair this. If \(\mu_t=a_t/N\), clearing denominators creates \(a_t\) cloned orders at the same route-relevant type. But such clones are a new multiset-delivery model, not the paper’s graph, which has one order per vertex. Under the paper’s coverage cost, duplicating an order at the same location does not increase the route cost. Splitting clones among several couriers can only add shared edges, and purification removes that split. Multiplicity therefore has no substantive operational meaning.
The same point defeats the Proposition 3 anchor. For a mass allocation,
\(\sum_i c_i(x)=\sum_{e\in E}\left|\{i:\sum_{t\in D_e}x_{it}>0\}\right|\).
Social optimality requires every used edge to be counted exactly once. Any type with positive mass assigned to two couriers would make every edge on its hub-to-type path count at least twice. Therefore every socially optimal mass allocation is already unsplit at the relevant branch level. The proposed MMS-and-SO question is exactly the paper’s finite branch-partition question on the support of \(\mu\). Its hardness may well survive; that would be a legitimate result about the discrete problem. But it would not be a continuous-population result, because the population proportions again play no role.
Theorem 1 collapses in the same way. The continuous MMS threshold is identical to the discrete MMS threshold, not because a valuable high-multiplicity phenomenon has been exposed, but because the purported continuous variable is mathematically inert. This is not merely the objection that “continuization does not help.” The stronger obstruction is that the proposed continuation has no mass-sensitive society: \(\mu\) is a dummy parameter, and the only information determining the answer is the finite support and its tree topology.
The better alternatives do not rescue the mirror. If the population is instead the couriers, a continuum of agents facing finitely many delivery vertices gives almost every agent an empty bundle. Individual EF1, MMS, and Pareto comparisons then degenerate; grouping couriers into finitely many teams simply restores the paper’s original \(n\)-agent model. If the graph and the order locations are also scaled with the number of couriers, the route-relevant type space grows with the graph, so there is again no fixed finite type population being continuized.
One could introduce package volumes, vehicle capacities, congestion, or edge costs depending on delivered mass. That could produce an interesting continuous routing-and-fairness problem. But it would replace the paper’s coverage function, its MMS thresholds, its SO condition, and its Pareto structure with different objects. It would be a new delivery model, not a continuous mirror of Theorem 1, Proposition 3, or Theorem 5.
The negative case is therefore strong for every faithful version of the proposed mirror: repeated orders either have no effect, or their spatial identities must be retained, while a continuum of couriers makes the fairness notions degenerate. I cannot claim that no imaginative new delivery model could ever be worthwhile. I can claim that none of the paper’s named computational results yields a substantive continuization under the paper’s own cost and fairness structure.
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.