Online Decentralised Mechanisms for Dynamic Ridesharing

The paper contains no numbered theorem, lemma, corollary, or proposition asserting a computational complexity classification or algorithmic guarantee. The proposed fluid model is also a substantial centralized re-modeling involving route-state distributions, arrival processes, and ordering rules. Regardless of whether that re-modeling is worthwhile, bit (a) fails under the selection rule.

The objection that survived

The proposed fluid problem changes the sequential decentralized mechanism into a centralized fluid-control problem and requires additional route-state, arrival, and ordering structure.

What the mirror covers

The proposed mirror would cover the Compensation mechanism's utility, myopic-truthfulness, and budget-balance properties in an aggregate fluid setting, but it does not mirror a qualifying computational result and leaves the FIFO, Discount, and experimental claims without computational anchors.

Open questions for a prover

The case FOR (proponent)

The strongest honest conclusion is conditional: this paper admits a plausible continuous-population mirror, but it has no qualifying named computational result to anchor one.

The numbered results are Theorem 5.1, proved here, stating that Compensation ex-post utility is at least projected utility; Theorem 5.2, proved by the authors (with the full proof in the extended version), stating DSIC for myopic riders; and Theorem 5.4, proved here, stating budget balance. None is a complexity result asserting membership in \( \mathrm{P} \), NP-hardness, FPT, W[1]-hardness, or similar. The only computational claims are unnumbered: FIFO needs two shortest-path computations, while unrestricted route generation is exponential and Algorithm 4 restricts it to quadratically many insertion positions. Therefore, under the requested rubric, there are zero valid anchors and hence no anchor-by-anchor continuous problems to report.

The best positive case would nevertheless be a fluid version of the Compensation mechanism. Consider a large metropolitan commuter service with many repeated requests from a finite set of origin–destination zones, discrete arrival slots, and finitely many value-of-time classes. A rider type is the complete tuple
\[ \theta=(t,a,b,v)\in [T]\times L\times L\times V. \]
The instance gives rational arrival masses \(\mu_\theta\), a directed city graph with shortest-path metric \(\delta\), and a large homogeneous fleet with rational masses of vehicle types \((d,C,c)\). Mass \(\mu_\theta\) represents the fraction of requests of that cohort; time remains discrete, while the population becomes continuous.

A natural lead problem would be Fluid Compensation Allocation. Given the current fluid distribution over vehicle route states, compute at every time \(t\) a nonanticipatory flow \(x_{\sigma,\theta,\rho}\) assigning mass of arriving type \(\theta\), from vehicle state \(\sigma\), to feasible routes \(\rho\) obtained by the paper’s RouteGenerator. The flow must satisfy pickup/drop-off precedence, vehicle-capacity, and state-conservation constraints. Each used route must quote the Compensation payment
\[ p_{\rho} = c\max\{0,\phi(\rho)-\phi(\sigma)\} + \int h_{\theta'}(\rho,\sigma)\,d\eta_\sigma(\theta'), \]
where \(h_{\theta'}\) is the compensation owed to existing passenger mass. The arriving mass must be assigned only to routes maximizing its reported utility. A solution is the complete route-flow and payment policy over the horizon, together with the induced next-state distributions; one may optimize aggregate rider utility subject to these implementation constraints.

For fixed capacity \(C\) and an explicit finite type/state representation, this looks plausibly Class A: Algorithm 4 gives only \(O(C^2)\) insertion choices per route state, and the aggregate assignment and compensation constraints become a finite transportation or linear-programming problem. The resulting fluid solution could also provide rounding-based approximations for a large discrete market. With unrestricted route reorderings or unbounded capacity, route-state explosion may instead produce a genuinely hard boundary.

This mirror would naturally cover the content of Theorems 5.1, 5.2, and 5.4, with Theorem 5.2 as the strongest near-anchor: continuous mass does not remove the mechanism’s central myopic-truthfulness question, but turns repeated identical requests into aggregate flows.

The weakest point is substantial: ordinary ridesharing requests are strongly individuated by arrival time and location, and making them homogeneous requires a constructed commuter-cohort scenario. Moreover, DSIC for infinitesimal myopic agents may be easier than DSIC for individually consequential riders. Thus this is a credible mirror of the mechanism’s setting, but not a positive case satisfying the paper-selection rule’s required computational anchor.

The case AGAINST (opponent, writing after the proponent)

The paper should be rejected under ChoCo’s selection rule. The proponent’s central concession is decisive: the paper has no qualifying named computational result. Theorem 5.1 is a utility guarantee, Theorem 5.2 is a truthfulness property, and Theorem 5.4 is budget balance. None gives a complexity classification or an exact, approximation, or parameterized algorithm for a computational problem. Algorithm 4’s restricted route enumeration is an implementation choice, not a theorem about the complexity of the underlying route problem.

Theorem 5.2 is the strongest apparent anchor, but its continuous analogue degenerates. In the paper, one named rider can misreport and thereby change a vehicle’s finite route, affecting later riders. In a nonatomic population, one rider has measure zero and cannot change the aggregate route state or future menu. DSIC then reduces to choosing truthfully from an effectively exogenous menu, which is not the paper’s strategic phenomenon. To preserve an effect, one must let a positive-mass cohort deviate jointly. That is group or coalition incentive compatibility, a new problem not implied by Theorem 5.2.

Theorem 5.1 has a similar problem. Its proof relies on inserting one new rider into an existing ordered route and charging that rider compensation for the finite delays caused to particular incumbents. A distribution over \((t,a,b,v)\) does not specify the order in which a positive mass of riders is inserted. Different orders produce different routes, finishing times, and compensation obligations. One can add an arrival-order law or a canonical ordering, but that is an additional dynamic stochastic-control model, not a direct population continuization. An aggregate inequality such as
\[ \int U^{\mathrm{ex\text{-}post}}\,d\mu \ge \int U^{\mathrm{projected}}\,d\mu \]
would merely integrate the original pointwise guarantee; it would not be a computational result.

Theorem 5.4 is weaker still. Budget balance is a scalar accounting identity. Replacing
\[ \sum_i p_i\ge \sum_j c_j\chi_j \]
by the corresponding integrals gives no new computational question. If route costs are instead divided meaningfully among a mass of simultaneous riders, that creates a new cost-sharing mechanism rather than mirroring the theorem.

The best repaired scenario is a large commuter service with finitely many origin–destination zones, arrival slots, value-of-time classes, and a fleet scaled with demand. That scenario is not inherently nonsensical. But its correct state is a measure over partial vehicle routes, onboard riders, route positions, and future arrival states—not merely a society distribution over rider types. It also requires an arrival process and an ordering rule. Optimizing aggregate utility over those states would turn the paper’s decentralized menu mechanism into a new centralized fluid-control problem; omitting the objective leaves only a fluid simulation of a sequential rule.

Thus a worthwhile fluid ridesharing project may exist, but it would be new mean-field routing or dynamic mechanism-design work, not a continuous mirror of this paper’s computational content. The paper supplies no computational anchor for ChoCo, and each proposed theorem-level anchor either loses its strategic meaning in the nonatomic limit or becomes a tautological integral restatement.

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.