Pith. sign in

REVIEW 4 major objections 5 minor 6 references

Fair and Efficient Investment in Public Transportation

T0 review · 4 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Fair transit investment is easy for one or two riders, provably hard for many.

desk verdict The NTP/PTP complexity dichotomy is mostly believable, but two load-bearing proofs are missing and the abstract overpromises; worth sending out, not publishing as-is. read the letter →

arxiv 2602.03687 v2 pith:TSU62LDQ submitted 2026-02-03 cs.GT cs.MA

Martin Bullinger , Edith Elkind , Kassian Köck This is my paper · ORCID
classification cs.GTcs.MA MSC 68Q1768Q2568W2590B20
keywords publictransportationegalitarianwelfareutilitariancomputationalcomplexityinapproximabilityDijkstra'salgorithmnetworkdesignbusstopplacement
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how hard it is to spend a fixed infrastructure budget fairly. It shows that in a line-based bus-stop model, maximizing the welfare of the worst-off traveler is NP-complete and cannot be approximated within a factor of 2, even when bus rides are free. In a network model where edges can be discounted, optimal upgrades for one or two travelers can be computed in polynomial time with a modified shortest-path algorithm; once the number of travelers is variable, both efficiency and fairness objectives become NP-hard, and fairness is inapproximable. The headline conclusion: egalitarian planning is computationally much harder than utilitarian planning, and the difficulty shows up already on very simple topologies.

What carries the argument

The algorithmic workhorse is a modified Dijkstra's algorithm that operates on 'routing pairs' (vertex, budget) instead of plain vertices. It stores for each vertex and each used budget the minimal cost of a path from the source, using three update rules (non-reducing, reducing, budget-increasing). This yields budget mappings that, for two agents, can be merged by convolutions over budget allocations. On the hardness side, the central constructions reduce Set Cover to the network model and Vertex Cover to the path model, encoding coverage requirements as travel-cost thresholds such that feasibility of the target social-welfare cost exactly matches the existence of a cover.

What would settle it

Find a No-instance of the Set Cover reduction for some alpha in (0,1) in which an egalitarian-optimal solution has cost strictly below 1+alpha, for example by having an agent travel along three reduced edges with total cost below that threshold. If such an instance exists, the claimed (alpha+1)/(2alpha) inapproximability ceiling cannot hold.

Watch

Extended reading notes

Core claim

The paper's central claim is a complexity dichotomy. With a single agent, the network transit problem is solvable in polynomial time by a budget-layered variant of Dijkstra's algorithm; with two agents, the same algorithm can be combined via budget-mapping decomposition to stay polynomial. With an arbitrary number of agents, the problem is NP-complete for every discount factor alpha in [0,1), and when alpha=0 no finite polynomial-time approximation exists for either objective. For egalitarian welfare and 0<alpha<1, the paper proves a lower bound of (alpha+1)/(2alpha) on any polynomial-time approximation ratio. In the line-based path transit model, egalitarian bus-stop placement is NP-complet

Load-bearing premise

The inapproximability lower bound for egalitarian network transit with 0<alpha<1 rests on the assertion that any solution in the reduced Set Cover instances whose egalitarian cost lies strictly between 2alpha and 1+alpha can be modified—without increasing any agent's cost—so that every agent uses exactly two discounted edges.

Editorial extensions

If this is right

  • PTP(EG) is NP-complete even for alpha=0 and is gamma-inapproximable for any gamma<2; bus-stop placement for the worst-off traveler cannot be solved or closely approximated in polynomial time.
  • 1-NTP* is solvable in O(beta m log m + beta ell) time; 2-NTP* is solvable in O(beta m^2 log m + m beta ell + m^2 beta^2) time.
  • NTP* is NP-complete for every alpha in [0,1); with alpha=0 it is inapproximable for both objectives, and with alpha in (0,1) the egalitarian version is gamma-inapproximable for gamma < (alpha+1)/(2alpha).
  • Tail-matching greedy algorithms that add or remove edges one at a time cannot give a better worst-case guarantee than buying nothing (an alpha^{-1} approximation).
  • The paper's abstract further claims W[1]-hardness in the number of agents, a corresponding XP algorithm, and a fixed-parameter tractable special case when all agents share a common hub.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A practical takeaway: if a transit agency wants guarantees about the worst-off rider, exact optimization is feasible only in very small or fixed-size settings; real deployments would likely need approximation heuristics, welfare trade-offs, or constraints on the demand set.
  • The inapproximability ratio (alpha+1)/(2alpha) shrinks as alpha grows, meaning the computational barrier is strongest exactly when discounted travel is cheapest—the regime where equity is most relevant.
  • The two-agent algorithm's budget-mapping convolution could plausibly extend to any fixed number k of agents with runtime polynomial in the network size but exponential in k (an XP-style scaling), so the hardness really bites only when k is part of the input.
  • Under the unit-weight budget interpretation discussed in the appendix, the network-transit hardness results carry over to the railway-design variant studied there, broadening the practical reach beyond bus routes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper studies two stylized public-transport investment models. In the path transit problem (PTP), a planner chooses bus stops on a line; in the network transit problem (NTP), a planner discounts a limited number of edges in a weighted graph. For PTP, the paper claims that egalitarian welfare maximization is NP-complete even when α=0 and is inapproximable within factor 2, contrasting with known polynomial-time utilitarian optimization. For NTP, the paper claims a polynomial-time algorithm for one agent (Algorithm 1), an extension to two agents, NP-completeness for a variable number of agents for both welfare objectives, and inapproximability results for α=0 and for egalitarian welfare when α∈(0,1). The central claimed dichotomy is that fixed small numbers of agents are tractable while variable numbers are intractable, and that egalitarian fairness is computationally harder than utilitarian efficiency in these settings.

Significance. If correct, the results are a meaningful contribution to computational social choice and transportation network design. The single-agent modified Dijkstra algorithm is concrete, and the reduction from SetCover for NTP hardness is elegant; the PTP negative results on a line are also striking. The paper gives explicit algorithmic running times and formal reduction structures rather than fitted or empirical claims, which is a strength. The main value lies in the boundary between poly-time solvability for 1–2 agents and NP-hardness/inapproximability for variable numbers, and in the contrast between utilitarian and egalitarian objectives. However, the full significance of the paper depends on two unproven structural/replacement arguments and on results claimed in the abstract but not present in the body.

major comments (4)
  1. [§5.3, Theorem 10] The proof of polynomial-time solvability for 2-NTP assumes that an optimal pair of agent paths either is disjoint or has an intersection that is a single connected subpath from p to q. No proof is supplied for this structural claim. In arbitrary weighted undirected graphs, two shortest paths can share several disconnected edge segments (e.g., one path uses edges a–b and c–d, another uses a–b and c–d but connects them by a different middle segment). The decomposition into five branches and the budget convolution (μ_sp + μ_pq + μ_qt) are defined only for a single shared subpath. Unless an uncrossing lemma is proved, the claimed O(βm^2 log m + mβℓ + m^2β^2) bound for 2-NTP is not established. This is load-bearing for the central tractability result.
  2. [§5.4, proof of Theorem 11 (α=0 case)] In the direction (⇐) of the SetCover reduction, the proof for α=0 says only: 'one can argue by a finite sequence of replacements—see Figure 8—that any longer path can be shortened to two edges without increasing cost.' This is not a proof. The correctness of the reduction at α=0 requires the following: if some agent has a zero-cost path of length >2 using only reduced edges, then the solution can be transformed into one in which every agent uses exactly two reduced edges, without breaking feasibility or budget. Absent a formal replacement argument, a No-instance of SetCover could admit a zero-cost NTP solution whose longer paths do not correspond to a set cover, which would invalidate the NP-hardness claim for α=0.
  3. [§5.4 / Appendix B.2, proof of Theorem 14] The claimed inapproximability bound (α+1)/(2α) depends on the No-case lower bound c^(EG) ≥ 1+α. That lower bound is justified only by 'the same reasoning used earlier (see Figure 8), we can modify the solution by replacing item edges with subset edges so that each agent ultimately uses only two reduced edges.' This replacement is not formalized for α∈(0,1), where an agent cost strictly between 2α and 1+α need not be zero. Since the entire gap separating Yes from No instances rests on this assertion, the inapproximability theorem is not currently proved.
  4. [Abstract vs. body] The abstract claims an XP algorithm parameterized by the number of agents, W[1]-hardness with respect to the number of agents, and an FPT result for the common-hub case. None of these claims appears in the body or appendices; Section 6 instead lists extending the algorithms to an arbitrary fixed number of agents as future work. As submitted, the manuscript does not contain these results, so the abstract overstates the paper's content. This needs to be corrected by either adding the missing theorems and proofs or revising the abstract.
minor comments (5)
  1. [Appendix B.1, proof of Theorem 4] The sentence 'An edge agent has one terminal at a vertex stop and the other at a detour stop 0.1 away' contradicts the construction, where edge agents are (ι(u), ι(v)) and both terminals are vertex stops. The following reasoning is understandable, but this sentence should be fixed.
  2. [Throughout] There are unresolved placeholders '??5' and '??3' in the text (in Observation 3 and Section 5.4) that should be proper cross-references to Observation 3 or other lemmas.
  3. [Appendix A] The statement of the greedy-algorithm lower bound in the appendix begins 'Let α∈]0,1[ and 1≤γ≤α^{-1} or α=0 and γ≥1. Then G↑ and G↓ are not γ-approximation algorithms...' but the first clause is grammatically incomplete; it should be part of a sentence such as 'Then for any such γ, G↑ and G↓ are not γ-approximation algorithms.'
  4. [§5.2, Theorem 8] The theorem states the running time as O(βm log m + βℓ), while the abstract states O(β m^2 log m + mβℓ + m^2β^2) for the two-agent case. The one-agent version is clear, but the later simplification 'the runtime simplifies to O(βm^3)' should be justified more carefully, since β≤m and ℓ≤m^2 give O(βm^3) only after using ℓ≤m^2; this is true, but the one-line statement may confuse readers.
  5. [§6 / Table 2] The table lists 'NTP⋆ NP-complete' under restrictions 'Any α∈[0,1[' but does not reflect that the α=0 case and the α>0 case currently have different proof status (the former relies on the unproven replacement argument). The table should be updated once the proof is completed.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: new hardness results and algorithms are derived from standard reductions and self-contained proofs; the only self-citations are background/contrast, not load-bearing.

full rationale

The paper's central contributions are the PTP(EG) NP-completeness and inapproximability theorems, the 1- and 2-agent NTP algorithms, the variable-agent NTP NP-completeness, and the NTP(EG) inapproximability gap. These are argued from Vertex Cover and Set Cover reductions, from Dijkstra-style dynamic-programming arguments, and from standard complexity assumptions (P≠NP). No step defines a predicted quantity in terms of the input in a way that makes the result true by construction. The only self-citation is Bullinger et al. (2025), which shares two authors, and it is used for the already-known PTP(UT) polynomial-time baseline and the terminal-restriction observation for the utilitarian objective. These uses are contextual and contrastive; no new theorem in this paper is derived from them. The two-agent algorithm's assumption that the intersection of optimal agent paths is a single connected subpath, and Theorem 14's unformalized 'same reasoning used earlier (see Figure 8)' replacement argument, are genuine proof gaps and correctness risks, but they are not circularity: the paper does not assume the conclusion it is proving, nor does it rename a fitted parameter as a prediction. Thus the appropriate circularity finding is 'no significant circularity,' with a low score reflecting only the presence of minor, non-load-bearing self-citation.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No empirical fitting; the results are conditional on P≠NP and on the model definitions. The only notable unproved structural premises are the single-intersection assumption in the 2-agent argument and the replacement argument in Theorem 14; both are listed in axioms.

assumptions (5)
  • standard math P ≠ NP
    All hardness and inapproximability results are conditional on P≠NP (stated in §1 and invoked in Theorems 4,6,11,12,14).
  • domain assumption In NTP, reducing an edge scales its travel time by a uniform factor α; budget counts number of upgraded edges, not total weight
    Model definition in §3; the entire complexity landscape is relative to this cost/budget model.
  • domain assumption In PTP, bus travel cost between stops is α times distance, and walking distances are Euclidean; agents choose min of walking or bus+walking
    Cost formula in §3 used by all PTP reductions.
  • ad hoc to paper For two agents, optimal shortest paths can be assumed to intersect in one connected subpath between branch vertices p and q
    Assumed in §5.3 without proof; decomposition into five branches depends on it.
  • ad hoc to paper In the SetCover reduction, a solution with cost in (2α, 1+α) can be rearranged so each agent uses exactly two reduced edges (Figure 8 replacement)
    Used in Theorem 11 (α=0) and Theorem 14; not formally proved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fair and Efficient Investment in Public Transportation." pith.science (2026). https://pith.science/paper/TSU62LDQ

@misc{pith2026260203687,
  author       = {Pith},
  title        = {Pith review of: Fair and Efficient Investment in Public Transportation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TSU62LDQ}},
  note         = {Machine review of arXiv:2602.03687}
}
read the original abstract

We study a stylized model of infrastructure investment in public transportation. In our model, each agent travels between a pair of terminals in a network captured by a weighted graph, where edge weights represent distances. The central planner can improve the travel time along a fixed number of edges, with the goal of maximizing the utilitarian or egalitarian welfare. When there is only one agent, we provide a polynomial-time algorithm that combines Dijkstra's algorithm with a dynamic program. We then demonstrate how to use this algorithm as a subroutine to solve the problem for two agents. Generalizing this idea, we present an XP algorithm parameterized by the number of agents. However, our problem turns out to be W[1]-hard with respect to the number of agents. Nevertheless, we obtain a fixed-parameter tractability result for the special case where all agents travel to a common hub. If the number of agents is variable, we obtain NP-completeness and inapproximability results. We discuss implications of our results for a related model of railway network design.

Figures

Figures reproduced from arXiv: 2602.03687 by the authors.

Figure 1
Figure 1. Illustration of the path transit problem. The upper panel displays agent routes, potential bus stops, and walking cost, while the lower panel presents the solution S1 = {1, 5} (marked in orange) with its corresponding travel costs. We consider the problem of selecting a set of bus stops (in PTP) or a set of discounted edges (in NTP) so as to minimize the (egalitarian or utilitarian) cost. Formally, an instance I = ⟨… view at source ↗
Figure 2
Figure 2. Illustration of the network transit problem. The upper panel shows the original graph, the left panel depicts the shortest paths used by walking agents, and the right panel demonstrates how reducing the cost on the dashed edge alters these routes. As a final preliminary remark, we note that evaluating an agent’s travel cost for a given solution can be done in polynomial time for both models. In the PTP, an agent can… view at source ↗
Figure 3
Figure 3. Inferiority of terminal selection (left) compared to nonterminal selection (right) for the egalitarian objective. Observation 5. PTP(EG) is α −1 -approximable for α ∈ ]0, 1[. For α = 0, we will now show that the problem remains hard to approximate: adapting the N P-hardness construction of ?? 5, we show that no polynomial-time algorithm can guarantee an approximation factor of less than 2. Theorem 6. Let γ < 2. Then… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: Illustration of instances constructed in Section 5.1. The greedy algorithms yield an arbitrarily suboptimal solution. (2) For all i ∈ [β]: Let e ∈ arg mine∈E\Si−1 c ⋆ (Si−1 ∪ {e}) and set Si = Si−1 ∪ {e}. As the final output, G↑ returns Sβ. The top-down greedy algorith…
Figure 5
Figure 5. Figure 5: Instance for illustrating the execution of the algorithm. We display the shortest paths without (left) and with optimal (right) investment. || 13 s→ s t t → s→ s t t → q q→ [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Pattern of 2-NTP with non-empty intersection of shortest paths of the agents. The necessity of the budget-increasing update may not be obvious at first. Its purpose is to enforce (v, b) ≤ (v, b − 1) for all routing pairs with budget indicator b ≥ 1. If omitted, the alg…
Figure 7
Figure 7. Figure 7: Illustration of the reduction from SetCover to NTP for the instance ⟨U, S, 2⟩ with U = {a, b, c, d} and S = {{a, b}, {b, c}, {c, d}}. The left panel shows the constructed NTP instance and the right panel highlights a feasible solution corresponding to the set cover S ′…
Figure 8
Figure 8. Figure 8: If the solution in the left panel constitutes a feasible solution, then the solution in the right panel is likewise feasible. All shortest paths passing through y1 or x2 can reach t with the same or even lower costs. (⇐) Assume there is a feasible solution for H′ achie…
Figure 9
Figure 9. Figure 9: Illustration of converting a VertexCover instance into a PTP instance: the upper left panel presents the original VertexCover instance, while the upper right panel shows the transformed PTP instance. The lower panels display a solution for both problems, ensuring that …
Figure 10
Figure 10. Figure 10: Comparison of RDP and NTP: the top diagram shows the base graph; the left subfigure highlights a solution minimizing utilitarian cost in NTP (dashed edges), while the right subfigure displays the corresponding solution in RDP, where all edge weights are scaled by ζ = …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 1 linked inside Pith

  1. [2]

    The objective is now to determine which edge to preserve at its original cost, while all others are scaled byζ

    Instead of listing individual agents, we define a demand functionτwithτ(s, t) =τ(s ′, t′) = 1and all other entries zero3. The objective is now to determine which edge to preserve at its original cost, while all others are scaled byζ. Clearly, if the same edge is retained, the resulting total cost is exactly twice the previous value, that is,38, consistent...

    2024

  2. [4]

    This implies membership inN P, see??3

    Proof.Given a candidate solution toPTP, computing its egalitarian cost (and thus verifying feasibility) can be done in polynomial time. This implies membership inN P, see??3. We now establishN P-hardness by reduction fromVertexCover(Garey and Johnson, 1979), defined as: given a graphG= (U, K)and integerρ≤ |U|, decide whether there existsU′ ⊆Uwith|U ′| ≤ρs...

    1979

  3. [11]

    We now argue that, in the No-instance case, any egalitarian-optimal solution must havec(EG) ≥1 +α

    We established that ifIis a Yes-instance, thenI′ has a solution withc(EG) = 2α, and ifIis a No-instance, then every feasible solution hasc(EG) >2α. We now argue that, in the No-instance case, any egalitarian-optimal solution must havec(EG) ≥1 +α. Suppose, for contradiction, that2α < c(EG) <1 +α. This would imply that all agents still traverse only reduced...

    2024

  4. [1979]

    Fair railway network design.arXiv preprint arXiv:2409.02152,

    Zixu He, Sirin Botan, Jérôme Lang, Abdallah Saffidine, Florian Sikora, and Silas Workman. Fair railway network design.arXiv preprint arXiv:2409.02152,

    arXiv

  5. [2019]

    Towards fair and efficient public transportation: A busstopmodel

    Martin Bullinger, Edith Elkind, and Mohamad Latifan. Towards fair and efficient public transportation: A busstopmodel. InProceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025),

    2025

  6. [2024]

    Customized bus route optimization with the real-time data.Journal of Advanced Transportation, 2020(1):8838994,

    Kai Huang, Lin Xu, Yao Chen, Qixiu Cheng, and Kun An. Customized bus route optimization with the real-time data.Journal of Advanced Transportation, 2020(1):8838994,

    2020

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.