| paper | d4-conf-ijcai-2016-0130 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered Lemmas 3.1 and 3.2 and Theorem 3.3 establish incentive properties, not a computational result. Section 4’s NP-hardness claim supports a plausible continuous optimization question, but it is unnumbered, so no eligible result anchors the mirror.
fails bit a — no named computational result to mirror
The proposed mirror covers the offline optimal-assignment benchmark in a single dispatch wave; it leaves the online IORS mechanism and its incentive-compatibility results aside.
The anchor requirement is the weak point in the paper: I find no numbered result that asserts an algorithmic complexity classification. Theorem 3.3, proved here, says IORS is ex-post incentive compatible when other passengers report truthfully and keep their fare-acceptance decisions fixed. Lemmas 3.1 and 3.2 establish parts of that claim. They are named results, but they do not classify a problem as tractable or hard. Section 4 does call the offline optimal-assignment problem NP-hard, but that claim is unnumbered. So I cannot honestly present a mirror as anchored to a qualifying named result.
The strongest candidate, if the unnumbered Section 4 claim is allowed as a lead, is Continuous Batch Optimal Assignment. It mirrors the paper’s offline benchmark: assign shared rides to minimize operating cost per unit of effective demand.
Take a single dispatch wave on a finite road network. Passenger type \(r\) records every feature that affects feasibility or demand, such as origin, destination, arrival time, latest departure, and effective demand \(\ell_r\). Its mass \(\mu_r\) is the fraction of passengers of that type, with \(\sum_r\mu_r=1\). Vehicle type \(v\) records its starting state and operating characteristics; \(\nu_v\) is the available mass of those vehicles per passenger. For a large commute cohort, there could be hundreds of thousands of passengers but only hundreds of recurring request types, with a correspondingly scaled fleet.
For each vehicle type \(v\), let \(Q_v\) be its feasible shared-ride plans. Each plan \(q\) serves at most four passengers, follows a feasible route, and has operating cost \(c_{vq}\). Let \(a_{qr}\) be the number of passengers of type \(r\) served by that plan. The decision variable \(y_{vq}\ge 0\) is the mass of vehicles of type \(v\) assigned to plan \(q\). The question is to return a feasible allocation maximizing
\[ \frac{\sum_{r}\ell_r\sum_{v,q}a_{qr}y_{vq}} {\sum_{v,q}c_{vq}y_{vq}}, \]
subject to
\[ \sum_q y_{vq}\le \nu_v \quad\text{and}\quad \sum_{v,q}a_{qr}y_{vq}\le \mu_r. \]
Assume at least one nonempty feasible plan exists and its operating cost is positive. Each plan still gives its passengers an integral ride; the fractional quantities describe how a large mass of identical vehicles and passengers is distributed across plans.
For a one-wave instance with fixed seat capacity four, I would expect this mirror to be Class A. There are polynomially many multisets of up to four request types, and only constantly many pickup/drop-off orders per multiset. On a finite network with the paper’s distance-based cost and travel model, those plans can be checked and costed, then the resulting linear-fractional optimization can be solved as an LP. The plausible gain is that the discrete matching hardness may dissolve when repeated requests and vehicles are represented by masses. Questions this raises include the rounding or additive error for finite cohorts, and whether tractability survives variable capacity or multiple dispatch waves.
This is plausibly a mirror of the paper’s *offline assignment benchmark*: it retains its cost-per-effective-demand objective, vehicle capacity, and route feasibility. I would not claim that the authors’ online posted-price mechanism or its incentive-compatibility result has been mirrored.
The weakest point is that this is a static, single-wave assignment problem, while the paper’s main mechanism handles online arrivals over time. That restriction may make the proposed question too narrow to count as a mirror of the paper’s main result. More fundamentally, because the NP-hardness claim is unnumbered, this remains a concrete candidate—not an anchor-grounded positive case under your stated rule.
The strongest negative point is that the proposed mirror has no qualifying named result to attach to. The paper’s numbered Lemmas 3.1 and 3.2 and Theorem 3.3 concern incentive compatibility, not computational complexity. Section 4 does call the offline benchmark NP-hard, but gives no numbered complexity result or precise formal definition of that optimization problem. The stated runtimes for Algorithms 1 and 2 are procedural bounds, not a complexity classification for the continuous-population problem. Under the task’s anchor requirement, Continuous Batch Optimal Assignment is therefore not an anchor-grounded mirror.
Theorem 3.3 also has a serious continuum problem. Its claim is about what one passenger can gain by changing a report or delaying a request. In an atomless society, one passenger has zero mass, so their report cannot change aggregate costs or the mechanism’s mass-level prices; the incentive claim risks becoming vacuous. Treating a positive mass of identical passengers as the deviator preserves an effect on the outcome, but changes the theorem into a claim about coordinated group deviations. That is a different question.
The proposed offline mirror has a separate limitation: its one-wave plan LP sets aside the online arrivals, evolving vehicle states, and posted-price mechanism that define IORS. A more faithful version could use time-expanded passenger and vehicle types and columns for complete feasible vehicle schedules. That would be a coherent continuous-population optimization question, but it would formalize a benchmark the paper does not precisely specify or analyze. Its worth as a new problem would not supply the missing named anchor.
That is the strongest case against. It does not establish the universal claim that no worthwhile mirror exists. Repeated commute cohorts on a finite network could plausibly yield moderate support, and fractional allocation across feasible ride plans is a natural high-multiplicity model. I cannot honestly dismiss that as meaningless or out of scope. The negative case is strong on the paper’s named-result anchor requirement, but weak as a claim that no scenario merits study.
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.