| paper | d4-conf-aaai-2022-1582 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-hard, even with \(\tau=3\), \(C=1\), \(R=0\), and constant edge traversal times. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a directed road network, a horizon, worker types with masses μ_d, and order types with per-worker demands ν_q, find a feasible allocation minimizing the range of time-normalized worker incomes. Each feasible schedule π assigns whole orders, respects routing, timing, and capacity constraints, and serves k_q(π) orders of type q. Choose schedule masses z_{d,π}≥0 such that Σ_π z_{d,π}=μ_d for each worker type and Σ_{d,π} z_{d,π}k_q(π)=ν_q for each order type; minimize ess sup_{z_{d,π}>0} I(d,π) minus ess inf_{z_{d,π}>0} I(d,π), where I(d,π) is the schedule’s driving and waiting income divided by available time.
A high-multiplicity dispatch model with worker-type masses μ_d and recurring order-type demands ν_q. The decision variables z_{d,π} allocate worker mass to feasible whole-worker schedules; schedules retain indivisible orders, and the objective minimizes the income range across workers assigned positive mass.
Exact worker and order types may nearly identify every actor in the measured cities, while compact supports require recurring templates that the paper’s data do not establish.
fatal: False
The mirror covers Theorem 1’s income-gap hardness result and Corollary 1’s distance-constrained variant; it leaves Theorem 2’s running-time claim for the heuristic and the empirical evaluations alone.
The strongest mirror I can defend is a high-volume, recurring city delivery market. A city may have tens of thousands of active workers but only a much smaller set of worker types: the same vehicle class, starting area, shift, travel characteristics, pay rates, and order restrictions. A finite catalogue of restaurant-to-customer routes, time slots, and preparation-time classes can likewise recur across many orders. The relevant comparison is therefore between the number of workers and the number of distinct types, not between workers and the number of possible types in the abstract.
Let \(\mu_d\) be the fraction of workers of type \(d\), with \(\sum_d\mu_d=1\). A worker’s type includes every fixed feature the model uses, including availability and pay parameters. Let \(q\) range over a finite catalogue of order types, each specifying locations, arrival slot, and preparation time; let \(\nu_q\) be the number of orders of type \(q\) per unit of worker population. These rational masses co-scale with the workforce: with \(N\) workers, a rational instance represents \(N\mu_d\) workers of type \(d\) and \(N\nu_q\) orders of type \(q\), when those quantities are integral.
The action still respects the paper’s indivisible deliveries. For each worker type \(d\), let \(\Pi_d\) be the set of feasible whole-shift schedules: each schedule assigns whole orders, respects pickup-before-drop-off, route timing, and vehicle capacity, and accounts for driving and restaurant waiting. Write \(k_q(\pi)\) for the number of type-\(q\) orders served in schedule \(\pi\), and \(D_{d,\pi}\) and \(W_{d,\pi}\) for its driving and waiting time. If workers of type \(d\) have available time \(a_d\), their income rate under that schedule is
\[
I(d,\pi)=\frac{w_1D_{d,\pi}+w_2W_{d,\pi}}{a_d}.
\]
The decision variable \(z_{d,\pi}\) is the mass of workers of type \(d\) assigned to schedule \(\pi\). Thus a schedule is integral for each worker, while the population can divide among schedules.
Lead mirror: Continuous Fair Income Gap. Given the road network, horizon and time slots, worker types and masses \(\mu_d\), order types and masses \(\nu_q\), payment parameters, and capacity, find a feasible \(z\) minimizing
\[
\operatorname*{ess\,sup}_{z_{d,\pi}>0} I(d,\pi)
-
\operatorname*{ess\,inf}_{z_{d,\pi}>0} I(d,\pi)
\]
subject to
\[
\sum_{\pi\in\Pi_d}z_{d,\pi}=\mu_d
\quad\text{for every }d,
\qquad
\sum_{d,\pi}z_{d,\pi}k_q(\pi)=\nu_q
\quad\text{for every }q.
\]
A solution is a mass allocation over feasible whole-worker schedules that covers the order demand exactly. It is the paper’s income-gap objective at workforce scale, not a fractional delivery to any one worker or customer. The input size can be stated in the graph size, worker-type support \(\tau_D\), order-type support \(\tau_O\), time slots \(H\), \(\mathrm{MaxO}\), and rational bit length \(L\).
This mirrors Theorem 1, proved in the paper: “There is no PTIME algorithm that can approximate Prob. 2 within any constant factor \(c\), where \(0<c\le1\), unless P = NP.” Problem 2 is the paper’s minimum time-normalized income-gap assignment problem. Its proof reduces from Subset Sum, with a zero optimum on YES instances and a positive optimum on NO instances. The mirror asks the right follow-up: does that obstruction survive when many workers share types and repeated order classes can be distributed across worker mass? The paper’s particular reduction does not answer that. Its individually weighted orders are exactly the sort of finite collection whose partition obstruction may disappear when each order class has high multiplicity.
Second anchor: Continuous Distance-Bounded Fair Food Delivery. Use the same instance and schedules, but require every order in a positive-mass schedule to satisfy the paper’s assignment-distance condition. At the assignment time \(t\), an order \(q\) can be assigned only to workers within \(\Gamma\) times the nearest available worker’s distance to its restaurant. Formally, define \(\operatorname{near}_z(q,t)\) as the infimum distance to the restaurant among locations holding positive available worker mass at time \(t\); require
\[
\operatorname{dist}(x,r_q)\le \Gamma\,\operatorname{near}_z(q,t)
\]
for every served order assigned at location \(x\). The question is to minimize the same income gap over schedules satisfying that condition.
This mirrors Corollary 1, also proved in the paper: “There exists no PTIME algorithm that can approximate Prob. 3 within any constant factor \(c\), where \(0<c\le1\), unless P = NP.” Problem 3 is Problem 2 with the stated assignment-distance bound. The corollary’s proof makes the bound nonbinding by choosing \(\Gamma\) larger than the network diameter times the minimum positive distance, thereby reducing Problem 2 to Problem 3. So the result gives a valid hardness anchor for this mirror, but does not establish hardness at a tight, operationally meaningful radius.
I would provisionally expect continuum-specific hardness for the full-shift versions, rather than claim that the paper’s subset-sum hardness transfers. A mass allocation may erase that particular partition barrier, but the exact model still chooses among integral pickup-and-delivery schedules; pricing those schedules while accounting for time-dependent routes, capacities, and income bounds may itself be hard. A central question is whether that pricing problem admits a tractable configuration-LP or dynamic-programming treatment, and whether any hardness survives when both type supports are small relative to the workforce and order count. A restricted setting with a fixed network, time grid, and bundle size may be tractable. The paper’s theorem does not settle either case.
I would make Theorem 1 the lead because it directly anchors the unconstrained income-gap objective and supplies the clearest hardness question. Corollary 1 is useful as a separate mirror of the paper’s customer-protection variant, though its reduction inherits the first result rather than adding new combinatorics. I would leave out Theorem 2: its running-time claim concerns the proposed heuristic, without a solution-quality guarantee for the underlying optimum. This case covers only the paper’s theoretical results for Problems 2 and 3, not its empirical findings, fairness principles, or FAIRFOODY itself.
The main weakness is that recurring order classes must be credible in the scenario and compact enough to give a meaningful high-multiplicity regime. Exact restaurant, customer, and arrival-time identities could make the support grow with the data, restoring an almost entirely discrete instance. And worker mass does not make whole-shift routing fractional: if schedule pricing is hard, the mirror may remain hard. That is a real limit on the positive case, but not a reason to reject the question. The income-gap and distance-constrained dispatch problems remain the authors’ problems, in a workforce regime the paper itself motivates.
The strongest case against is about support, not about fractionalizing delivery routes. The paper does contain named computational results: Theorem 1 for the income-gap problem and Corollary 1 for its distance-constrained version. So the decisive “nothing computational to mirror” argument is unavailable.
For Theorem 1, the paper’s model depends on detailed state. A worker’s feasible assignments depend on location, availability, current route and capacity; an order’s depend on its restaurant, customer, request time and preparation time. Treating workers as the same type only when these details agree can leave \(\tau_D\) close to the number of vehicles. Treating orders as the same type only when their routing and timing details agree can leave \(\tau_O\) close to the number of orders. The large workforce cited in the paper does not by itself give a useful high-multiplicity regime.
The schedule formulation is the strongest response to this objection. It preserves whole-worker schedules and can aggregate workers and repeated order classes. But it gets a compact model only when the city has many copies of a small set of complete worker and order types. Coarsening locations or time slots to create that repetition merges cases with different travel times, routes or nearest-vehicle constraints. Keeping those details exact can restore the large supports. The schedule LP is coherent, but its most promising instances describe a deliberately recurring, template-based market. The paper’s city-scale data do not establish that this regime is common enough to make the mirror a broad account of its problem.
That is a serious limitation on the case against, though. The programme asks whether a sensible high-multiplicity regime exists, not whether the paper’s six-day dataset already has small support. A market with recurring shifts, depots and order corridors is plausible. The question of whether the subset-sum barrier survives there is also exactly the kind of question the programme is meant to ask. I cannot dismiss the Theorem 1 mirror just because the paper’s own instance may have too many distinct types.
Corollary 1 adds less. Its hardness construction makes the distance bound nonbinding by choosing a sufficiently large \(\Gamma\); it gives no separate evidence about a tight, operationally useful radius. At such a radius, eligibility depends on the spatial distribution of available worker mass, so exact worker locations again risk a large support, while spatial pooling can alter eligibility. A recurring spatial-template model could handle this, but then it inherits the same limitation as the schedule mirror: it is a plausible restricted market regime, not a direct compression of the paper’s measured cities.
The honest negative case is therefore conditional. Exact spatial and temporal detail may make the continuous model track nearly every worker and order, while the compact version requires recurring types the paper does not demonstrate. That undercuts the breadth and immediate applicability of these anchors. It does not defeat the best proposed mirror: a recurring city market with repeated worker and order types remains plausible, and the income-gap question remains the authors’ problem. On the programme’s stated standard, I cannot honestly argue that no worthwhile scenario exists.
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.