| paper | Towards Fair and Efficient Public Transportation: A Bus Stop Model |
| authors | — |
| venue | AAMAS 2025 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.5
Given finite \(V\subseteq\mathbb Q\), budget \(b\), \(\alpha\in[0,1)\), finite endpoint types \(\Theta\subseteq V^2\), and rational masses \(\mu\), output \(S\subseteq V\) with \(|S|\le b\) such that for every \(R\subseteq V\), \(\mu(\{\theta:c_\theta(R)<c_\theta(S)\})<2|R|/b\), where \(c_\theta(S)=\min\{r_\theta-\ell_\theta,\min_{x,y\in S}(|\ell_\theta-x|+\alpha|x-y|+|r_\theta-y|)\}\).
A high-multiplicity corridor with endpoint types \(\theta=(\ell_\theta,r_\theta)\), passenger mass \(\mu_\theta\), indivisible stop decisions \(S\subseteq V\), and fairness constraints measured over improving passenger mass.
The mirror covers population-weighted forms of Theorems 3.2, 4.2, and 4.5; it leaves Proposition 3.5's binary stop-cost hardness, Proposition 4.6's strong-JR impossibility, and exact core non-emptiness unresolved.
The strongest positive case is a narrow but genuine one: the paper admits a direct high-multiplicity mirror in which passengers become mass, while bus stops remain indivisible physical decisions. This is not relying on the paper’s observation that \(V\) could be \(\mathbb Q\); that would be continuity of the outcome space. The mirror below keeps \(V\) finite and continuizes the population.
A plausible regime is a heavily used corridor serving repeated origin–destination classes: for example, \(10^5\) daily trips generated by \(10^2\)–\(10^3\) recurring neighbourhood-to-destination types. A type is \(\theta=(\ell_\theta,r_\theta)\), together with any cost parameters relevant to the model. Two passengers of the same type are interchangeable. The society is a rational mass vector \(\mu\in\mathbb Q_{\ge 0}^{\Theta}\) with \(\sum_{\theta}\mu_\theta=1\), where \(\mu_\theta\) is the passenger share of type \(\theta\).
For a stop set \(S\subseteq V\), define
\[ c_\theta(S)= \min\left\{ r_\theta-\ell_\theta,\ \min_{x,y\in S} \bigl( |\ell_\theta-x|+\alpha|x-y|+|r_\theta-y| \bigr) \right\}, \]
with the second term omitted when \(S=\varnothing\). A rational mass \(\mu_\theta=a_\theta/q\) can be replaced exactly by \(a_\theta\) cloned passengers. Thus the mirror preserves the paper’s costs, feasible stop sets, and comparisons; it merely represents repeated passengers compactly.
My lead anchor is Mass-\(2\)-Core Bus-Stop Placement\(_\infty\), mirroring Theorem 4.5, proved in this paper. An instance consists of \(V\subseteq\mathbb Q\), a budget \(b\), \(\alpha\in[0,1)\), a finite type set \(\Theta\subseteq V^2\), and rational masses \(\mu\). The task is to output \(S\subseteq V\) with \(|S|\le b\) such that, for every deviation set \(R\subseteq V\),
\[ \mu\bigl(\{\theta:c_\theta(R)<c_\theta(S)\}\bigr) < \frac{2|R|}{b}. \]
Equivalently, no coalition of passenger mass at least \(2|R|/b\) can unanimously improve by pooling its proportional entitlement to build \(R\). Stops remain whole stops: only the passenger coalition is divisible.
The continuous analogue of Algorithm 1 computes the terminal measure
\[ \lambda_\mu(v) = \sum_{\theta\in\Theta} \mu_\theta \bigl( \mathbf 1[\ell_\theta=v]+\mathbf 1[r_\theta=v] \bigr) \]
and chooses stops at successive terminal-mass quantiles of size \(2/b\). The proof of Theorem 4.5 carries over by replacing terminal counts with terminal mass: every gap between selected stops contains less than \(2/b\) mass of terminals, so a deviation using \(|R|\) stops can improve fewer than \(2|R|/b\) passenger mass. I therefore expect this problem to be Class A, with a polynomial-time quantile algorithm and a tight factor \(2\). The paper’s tightness construction also survives denominator clearing, so this is not merely an upper-bound artefact.
A second, sharper fairness anchor is Mass-JR-\(0\)-BSP\(_\infty\), mirroring Theorem 4.2, proved in this paper. Here \(\alpha=0\), and the task is to output \(S\) with \(|S|\le b\) such that for every pair \(R\subseteq V\), \(|R|=2\),
\[ \mu\bigl(\{\theta:c_\theta(R)<c_\theta(S)\}\bigr) < \frac{2}{b}. \]
This is exactly the mass form of “there is no coalition of at least \(2n/b\) agents for whom the same pair of stops is strictly better.” The paper’s algorithm becomes a weighted quantile algorithm over terminal mass. For rational \(\mu\), multiplying all masses by a common denominator divisible by \(b\) recovers the paper’s integer thresholds and its floor convention. Hence the finite and continuous versions have the same certificates and the same feasible stop sets. This is also Class A. It covers the paper’s exact JR result, while the \(2\)-core problem above covers its broader approximation guarantee.
The efficiency result gives an independent anchor: Weighted \(\alpha\)-BSP\(_\infty\), mirroring Theorem 3.2, proved in this paper. The instance is the same typed society, and the task is to find
\[ S^\star\in\arg\min_{S\subseteq V,\ |S|\le b} \sum_{\theta\in\Theta}\mu_\theta c_\theta(S). \]
This is the paper’s total-cost problem with passenger counts replaced by passenger mass. The dynamic program only ever updates sums of agent costs, so those sums become weighted sums over \(\Theta\). Its running time should become polynomial in \(\tau=|\Theta|\), \(m=|V|\), and the encoding length of the rational data, rather than in the number \(n\) of individual passengers: essentially \(O(\tau m+m^3)\) arithmetic operations. This is a direct Class A mirror, not a relaxation: all stop locations, bus routes, walking choices, and budget constraints are unchanged.
The authors should recognise these as their problems. Their own model already makes \((\ell_i,r_i)\) the relevant agent type, their fairness proofs count terminal multiplicities, and their objective is additive over agents. Replacing those counts by rational masses is therefore the natural high-multiplicity regime. It also explains why the mirror is computationally useful: the same physical planning question can be posed for millions of riders without listing millions of identical records.
The scope is deliberately limited. I would not claim a population-continuous interpretation for Proposition 3.5 without reconstructing its Knapsack reduction, because that hardness appears to come from binary stop-construction costs rather than population multiplicity. Nor do I claim that the exact core is computable: the paper explicitly leaves core non-emptiness open. Natural follow-up questions are whether the exact \(1\)-core is always non-empty in the mass model, whether JR exists for \(\alpha>0\), how the \(2\)-approximation behaves under separable type-dependent costs, and how rational mass solutions round back to finite populations with controlled quota violations.
The weakest point is the regime itself. The mirror is compelling for repeated commuter cohorts or discretised origin–destination zones, but much weaker if every passenger has an idiosyncratic terminal pair or walking-cost profile, in which case \(\tau\) approaches \(n\). That is a limitation of the high-multiplicity scenario, not of the formulation. Within the repeated-type corridor regime, however, the paper supplies three recognisable computational anchors, and the strongest two are naturally expressed in population proportions rather than individual counts.
The strongest negative case is that these are not genuinely new continuous computational problems, but weighted restatements of finite ones.
For Mass-\(2\)-Core Bus-Stop Placement\(_\infty\), every rational mass vector can be cleared to a denominator \(q\) and replaced by \(q\) cloned passengers. The condition
\[ \mu\bigl(\{\theta:c_\theta(R)<c_\theta(S)\}\bigr)<\frac{2|R|}{b} \]
is then exactly the paper’s finite \(2\)-core condition. The proof of Theorem 4.5 does not acquire a new idea: each bound on the number of agents with terminals in a gap becomes the identical bound on terminal mass. The proposed quantile algorithm is therefore a weighted implementation of Algorithm 1, not a new continuous optimization problem.
The same objection defeats Mass-JR-\(0\)-BSP\(_\infty\) even more directly. Its condition is precisely the finite JR condition after replacing counts by weights, and denominator clearing reproduces the original instance and certificates exactly. There is no new population-level phenomenon, separation problem, or complexity question. Theorem 4.2 already contains the entire argument.
For Weighted \(\alpha\)-BSP\(_\infty\), aggregation is immediate. Whenever the dynamic program sums costs over agents, one instead sums \(\mu_\theta c_\theta(S)\) over types. Thus the claimed \(O(\tau m+m^3)\) algorithm is a routine preprocessing consequence of Theorem 3.2: group identical endpoint pairs, attach their multiplicities, and run the same dynamic program. The result is useful data compression, but not a substantive continuization.
One might try to rescue the proposal by allowing a genuinely nonatomic distribution over endpoint pairs rather than finite support. That creates a different difficulty: an arbitrary measure is not a finite computational input. With finite support or a succinct discretisation, the model collapses back to the weighted versions above; with densities or other distributional oracles, one has introduced a new facility-location problem whose complexity depends on the chosen representation, rather than mirrored a named result of this paper. Likewise, allowing continuously many stop positions does not strengthen the efficiency anchor in the stated model, since Proposition 3.6 reduces an optimum to terminal locations whenever those are finite.
This is the best case against the anchors: all three are exact high-multiplicity encodings whose algorithms and proofs transfer by replacing sums with weighted sums. If “worthwhile” requires a new structural or complexity-theoretic challenge, they are weak candidates.
But this negative case is not decisive under ChoCo’s stated standard. The repeated-commuter corridor is a plausible high-multiplicity regime; endpoint pairs are complete types; the objective and fairness conditions are anonymous; and a compact exact algorithm for millions of riders is precisely the kind of population continuization the programme defines as valuable. I therefore cannot honestly defend the universal claim that no worthwhile mirror exists. The mirrors may be low-novelty, but they are well-posed and materially supported by the paper’s results.
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.