| paper | d4-conf-aaai-2015-0012 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\) for every fixed \(S\geq2\), with exact rational masses and optimal route witnesses. A running-time bound is \((2S)!\operatorname{poly}(m,L,S,K_S)\), where \(K_S=\tau\binom{\tau+S-1}{S-1}+\tau\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite road graph with rational edge weights, rational type masses \(\mu_t\) summing to \(1\), fixed car capacity \(S\), and a type-level trust graph, find a minimum-cost allocation of commuters to car configurations and transit singletons. Each type records pickup and destination hubs, driver status, capacity, cost parameters, and trust class; linked classes have mutually eligible members. A car configuration is a multiset of at most \(S\) commuters satisfying the paper’s driver and connectivity constraints. Let \(d_C\) be its minimum valid route cost, computed by Theorem 1 under antimonotonic route costs, and let \(d_t\) be the transit cost for a non-driver singleton. Find configuration masses \(x_C \ge 0\) minimizing \(\sum_C d_C x_C\), subject to \(\sum_C a_{tC}x_C=\mu_t\) for every type \(t\), where \(a_{tC}\) counts type-\(t\) commuters in \(C\); return route witnesses for car configurations.
A continuous configuration-allocation LP over commuter types and mass. Variables are masses \(x_C\) of finite car configurations and transit singletons; the objective sums their route or transit costs, and type-mass constraints ensure every unit of population is assigned. For fixed \(S\), there are \(O(\tau^S)\) configurations, and Theorem 1 computes each route cost using a bounded number of point orderings.
Covers system-wide travel-cost minimization for fixed capacity \(S\), with commuter types encoding hubs, vehicle details, costs, and uniform trust classes. It does not cover arbitrary individual friendship graphs, rider-specific time constraints, or transfer the paper’s empirical \(1.41\) approximation guarantee.
The strongest case I see is a continuous version of the paper’s system-wide ridesharing optimization for commuter populations with repeated trip and trust profiles. The paper gives no named NP-hardness or polynomial-time classification. My anchor is narrower: Theorem 1, proved in the paper’s appendix, gives an exact way to compute the route cost of a proposed carload. It says that if time, cognitive, and fuel costs worsen as path length grows, then the optimal route for a car is the shortest among routes formed by taking each valid ordering of the riders’ pickup and destination points and joining consecutive points by shortest paths. This is a computational result the paper uses when evaluating coalitions, though it does not classify the complexity of the full ridesharing problem.
A plausible high-multiplicity regime is a campus, employer, or city carpool service with thousands or tens of thousands of commuters but perhaps hundreds of distinct profiles. A type records pickup and destination hubs, driver status and seat capacity, relevant cost parameters, and a social-trust class. Mass \(\mu_t\) is the fraction of commuters with type \(t\). For social feasibility to be determined from types alone, assume the trust classes have uniform ties: members within a class, and members of linked classes, are mutually eligible to ride. A group of types is socially feasible when its induced type graph is connected. This describes a restricted regime, such as opt-in carpool circles, rather than arbitrary individual friendship networks.
Call the mirror Continuous Social Ridesharing Configuration Optimization. Its input is a finite road graph with rational edge weights; rational type masses \(\mu_t\) summing to one; a maximum car capacity \(S\); and a type-level trust graph. A configuration \(C\) is a multiset of at most \(S\) commuters. It must satisfy the paper’s car and social constraints: a nonsingleton carload has one driver with enough seats, and its types induce a connected trust graph. A passenger without a car may instead travel alone by public transport. For each car configuration, its cost \(d_C\) is the cost of its shortest valid route, computed using Theorem 1; a transit singleton has its ticket cost.
The decision variable \(x_C\geq 0\) is the number of copies of configuration \(C\) per commuter in the population. If \(a_{tC}\) counts type-\(t\) commuters in \(C\), the problem is
\[ \min \sum_C d_C x_C \qquad\text{subject to}\qquad \sum_C a_{tC}x_C=\mu_t \quad\text{for each type }t. \]
A solution is an optimal vector of configuration masses, with the route for each car configuration available as its witness. For a finite population of \(n\) commuters, the corresponding configuration counts would satisfy \(n x_C\in\mathbb{Z}_{\geq 0}\); the continuous problem replaces those integer counts with masses.
I expect this fixed-capacity version to be Class A. With \(S\) fixed, there are \(O(\tau^S)\) type multisets to consider, where \(\tau\) is the support size. Each route calculation has only a number of pickup/drop-off orderings bounded in terms of \(S\); shortest paths on the road graph can be computed in polynomial time. The resulting configuration LP therefore has polynomial size in \(\tau\), the map size, and the rational input length. That classification is my inference from the mirror and Theorem 1, not a claim made by the paper.
This covers the paper’s central system objective—minimizing total travel cost subject to vehicle and social constraints—while preserving finite carloads and actual routes. It does not claim that the paper proves a complexity result for coalition-structure generation, or that its empirical \(1.41\) approximation guarantee carries over. Further questions include whether continuous solutions admit useful rounding guarantees for large finite populations, what happens when capacity is part of the input, and whether similar algorithms survive less structured social graphs or rider-specific time constraints.
The weakest point is the social model: real friendship graphs are seldom uniform across large type classes. If representing each commuter’s actual social neighborhood forces \(\tau\) close to the number of commuters, the compression and its algorithmic benefit largely disappear. I would present this as a credible mirror for trust-circle or cohort-based ridesharing, not as a continuous model of every network in the paper’s experiments. The route objective and feasible carloads remain recognizable; the limit is the instance regime in which social eligibility can genuinely be described at type level.
The strongest objection is that Theorem 1 is local to a carload, not a result about the population. It computes a route once a set of riders is fixed. In the paper’s experiments, a car holds at most five people, so the route search remains bounded even as the population grows. A continuous population does not create a new limiting route problem; it leaves those finite route calculations intact and changes how carloads are allocated across society.
The proposed configuration LP makes that distinction clear. Its coefficients come from computing the route cost of each allowed configuration, then it allocates type mass among configurations. That is a sensible system-wide optimization problem, but its tractability comes chiefly from bounded car capacity and linear programming over the resulting configurations. Theorem 1 supplies route costs; it does not supply the population-level algorithm.
The sharper objection is that the mirror’s useful compression needs unusually regular social and travel data. Exact types must preserve pickup and destination, driver status, capacity, costs, and the social relationships that determine coalition feasibility. In ordinary friendship networks, those relationships often distinguish commuters who would otherwise share a type. Grouping them into uniform trust classes changes the paper’s central graph constraint to a particularly structured case. One can preserve more detail by including each person’s neighborhood in their type, but then the support may approach the number of commuters and the claimed small-profile regime disappears.
That narrows the mirror, but it does not defeat its best version. Commuters traveling between common hubs and joining institutionally defined, mutually trusted circles are plausible; in that regime the type graph can represent social feasibility, and a fixed seat limit \(S\) gives only polynomially many type configurations in the support size \(\tau\). The resulting mass allocation is still a legitimate continuous-population computational question. Calling it a routine fractional reformulation would not be enough: continuous optimization is precisely the programme’s interest, and a tractable answer is still an answer worth establishing.
So the case against is weak at its decisive point. The paper supports no broad claim that arbitrary ridesharing networks have a useful low-support continuous model, and Theorem 1 itself has no population-scale limit to analyze. But the hub-and-trust-circle mirror remains plausible and computationally well-posed. I cannot honestly claim that this anchor has been defeated; the strongest negative case only confines it to a narrower instance regime.
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.