| paper | d4-conf-ijcai-2021-0375 |
| 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}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 5
statement extracted from the paper’s text layer
Given a finite road graph \(G=(V,E)\), a time horizon, a finite support \(\Theta\) of rider types \(\theta=(o,d,\gamma)\) with rational masses \(\mu_\theta\ge 0\) summing to \(1\), and a fleet with initial locations and capacities measured in normalized mass units, choose feasible vehicle routes and type-level assignments \(x_{\theta p}\ge 0\) to feasible travel plans \(p\), with \(\sum_p x_{\theta p}=\mu_\theta\). Each unit of mass must receive an integral travel plan, assignments must match vehicle routes and respect capacity at every time, and taxi plans have the paper’s taxi cost. What is the complexity of finding a feasible solution minimizing \(\sum_{\theta,p}x_{\theta p}c_\theta(p)+\beta\sum_k T^c_k\), under a stated normalization of fleet supply and route costs?
A continuous-demand ridesharing allocation problem: types carry rational mass, vehicle routes remain discrete, and variables assign type mass to integral travel plans. The objective combines mass-weighted rider costs with fleet fuel costs, with capacities and cost units specified consistently under population normalization.
The reduction uses a cohort-sized vehicle and retains its route fuel cost while rider costs are mass-weighted, so the normalization needs to be specified for this stylized regime and does not establish the same hardness for fixed-seat fleets.
fatal: False
The mirror covers Proposition 5’s minimum-cost allocation problem. It leaves the truthfulness, individual-rationality, budget-balance, and polynomial-time mechanism results, including Theorem 2, unaddressed.
My lead is Mass Ridesharing Social-Cost Minimization (MRS-SCM), anchored on Proposition 5, proved in the paper’s Appendix A. It states that finding an optimal solution to the paper’s RS problem is NP-hard: given a road network, riders’ origins and destinations, vehicles and capacities, and the cost parameters, find a feasible allocation \(\pi\) minimizing
\[
CF(N,\pi)=\sum_{i\in N}c_i(\pi)+c_F(\pi).
\]
The paper proves this by reducing TSP to a special case with one autonomous vehicle, capacity for all riders, riders at the graph’s vertices, and destinations at the vehicle’s initial location. The only relevant cost is then the vehicle’s fuel cost for visiting the riders.
In MRS-SCM, the instance is a finite road graph and time horizon; a finite set \(\Theta\) of rider types \(\theta=(o,d,\gamma)\), each with rational mass \(\mu_\theta\ge 0\) and \(\sum_\theta\mu_\theta=1\); and a finite fleet with initial locations, capacities measured in mass units, and autonomy status. A type includes every detail the model uses, so riders of that type have the same trip and value of time. Choose feasible vehicle routes \(r\), and assign each type’s mass across feasible complete travel plans \(p\), with \(x_{\theta p}\ge0\) and \(\sum_p x_{\theta p}=\mu_\theta\). A plan specifies the rider’s path and vehicle use, including any transfers or taxi use. Assignments must match vehicle routes and respect capacity at every time. Each unit of mass receives an integral travel plan; it is the type-level allocation that may be fractional.
The objective is the mass-weighted version of the paper’s social cost:
\[
\min_{r,x}\quad
\sum_{\theta\in\Theta}\sum_{p}x_{\theta p}c_\theta(p)
+\beta\sum_k T^c_k(r),
\]
where \(c_\theta(p)=\gamma_\theta T(p)\) for ridesharing and uses the paper’s taxi cost for taxi plans. A solution is a feasible fleet route profile and mass assignment attaining the minimum. The decision version asks whether such a solution has cost at most a given rational bound \(B\).
A plausible high-multiplicity setting is an event or campus transport service: many people travel from a small set of pickup zones to a hub, and people from the same zone with similar values of time form a type. For \(\tau\) pickup types, suppose there are \(H\) riders per type, so \(N=H\tau\) while the support remains \(\tau\). The hardness subfamily uses one autonomous, cohort-sized shuttle or convoy, represented as a vehicle with capacity \(1\) in normalized mass units. This capacity scaling is part of the mirror: \(H\) copies of each type give total discrete capacity \(N\), which becomes capacity \(1\) when the population is normalized.
The TSP reduction still works in this mirror. For each vertex \(v\) of a directed Hamiltonian-cycle instance, create a type with origin \(v\), destination \(s\), and mass \(1/|V|\); put the vehicle at \(s\), give it capacity \(1\), and set all riders’ values of time to zero. Make taxi use sufficiently costly and set the horizon to \(|V|\). A feasible solution within the corresponding tour-cost threshold must collect the mass from every vertex and return it to \(s\) within \(|V|\) unit-length edges. That is possible exactly when the graph has a Hamiltonian cycle. Thus the mirror remains hard for reasons in the road-network structure, even as each type represents arbitrarily many riders. I expect this anchor to be Class B: hardness transfers.
This mirrors only Proposition 5’s underlying allocation problem. It does not claim a continuous version of Theorem 2’s truthful, individually rational, budget-balanced mechanism; truthfulness for infinitesimal agents would need a separate formulation. The main follow-up questions are whether hardness survives fixed per-vehicle capacity and a fixed vehicle-to-population ratio, and whether MRS-SCM admits approximation or parameterized algorithms in the support size or graph structure.
The weak point is the regime used by the clean reduction: one capacity-scaled vehicle and zero value of time are stylized, and do not establish hardness for ordinary urban fleets with fixed-seat cars. The case is narrower but direct: the paper itself uses this vehicle-routing subproblem to prove Proposition 5, and a large cohort from a small set of pickup types gives a coherent continuous-population version of it.
I don’t see a decisive ground for rejecting this mirror. Proposition 5 is an explicit computational result, and its object—minimum social cost over feasible ridesharing allocations—is separable from the paper’s individual truthfulness claims. The mechanism-design results may be difficult to continuize, but they do not dispose of this anchor.
The strongest objection is to the proposed *regime*: its TSP reduction uses one vehicle with capacity for the entire population, one demand type per graph vertex, and a graph whose size grows with the number of types. That is a stylized shuttle model. With fixed-seat cars and a fleet that grows with demand, the vehicle supply and the cost normalization also need to scale; simply replacing rider counts by masses while retaining the original fleet costs may change the welfare objective.
Those are real limits on what the reduction establishes, but they don’t defeat a better mirror. A continuous demand model with repeated origin–destination cohorts and a fleet whose supply scales per capita is coherent. Route choices can remain discrete while demand and assignments are masses. That is a recognizable capacitated routing problem, and asking for its complexity or approximation landscape is worthwhile even if the answer is hard. The programme explicitly allows resource scaling as part of the mirror.
Nor does the fact that the reduction’s difficulty comes from the road network count against it: transferred hardness is a valid outcome under the programme’s trichotomy. The honest negative case is therefore weak. The single-vehicle construction is narrow, but it does not rule out a sensible, computationally interesting continuous-population version of the allocation problem.
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.