Trolley problems are commonly used as thought experiments in philosophy of ethics. One can regularly see new variants come by on Twitter: some are just poking fun, others are bringing the ethical dilemma to new levels of complexity. Recently, the variant below caught my eye. This combinatorial trolley problem seemed interesting from a computational complexity perspective, so I decided to look at it in more depth.

This combinatorial trolley problem looks an awful lot like an instance of the notorious Traveling Salesman problem (TSP). In the TSP, one is given a set of n cities, with cost of travel specified for each pair of cities, and the goal is to determine a tour that visits each city once with minimal total cost. It is known that TSP is a computationally intractable problem, meaning that there exists no tractable (read: polynomial time¹) algorithm that can compute the optimal tour for all possible instances of the problem. It is possible to solve TSP by exhaustively searching all tours to find one with the lowest cost, but since the number of tours grows factorially with the number of cities, that would not yield a polynomial time algorithm (i.e., a factorial like n! grows faster than any polynomial n^c, where c is some constant).

The combinatorial trolley problem is stated as follows (from the picture above):

There is one person on every track between two stations. Every station must be hit at least once before the trolley stops. If you do nothing, the trolley will take the least efficient route. What do you do?

The most ethical solution, it seems, is to choose a route that kills the smallest number of people on the tracks. The problem states that this has to be done under the constraint that each station is visited at least once. While pondering the similarities and dissimilarities between this combinatorial trolley problem and TSP, I decided to create two polls and find out what other people thought.

Most people correctly thought that there are billions of possible tours in the combinatorial trolley problem. As one can see in the picture, there are 14 stations that the trolley needs to visit at least once. Hence, there are (14 – 1)! tours that visit each station exactly once. Approximately 6 billion tours. If the trolley revisits stations the number of tours is even larger.²

As for the second question — Is the combinatorial trolley problem tractable? — the poll showed little consensus. My answer? The problem is absolutely tractable, unlike TSP. Here is why:

There is one person on every track between two stations. Every station must be hit at least once before the trolley stops. Hitting each station at least once is only possible if we traverse at least 13 distinct tracks. To see that this is the case, consider that to get from the 1st station to the 2nd in our route we need to traverse at least one previously unvisited track, to get from the 2nd to the 3rd station we need another previously unvisited track, etc. Hence, it is inevitable that the trolley kills at least 13 people.

Now, observe that no matter which route we pick, as long as that route does not revisit any station and stops as soon as it has visited each station once, we kill exactly 13 people. In other words, an algorithm that picks every next station at random, without replacement, is guaranteed to yield the optimal route.

This solution³ also generalizes to an n-station generalisation of the combinatorial trolley problem: To visit n stations, we will need to minimally traverse n – 1 tracks, and hence will minimally kill n – 1 people on the tracks. An algorithm that picks at random the next station to visit will kill exactly n – 1 people and will run in polynomial time (linear time, to be exact). In conclusion, the combinatorial trolley problem, as specified, is tractable.

Now of course, one could make different variants of the problem by putting an unequal  number of people per track and requiring the trolley to return to its starting position.⁴ In that case, indeed the combinatorial trolley problem would become equivalent to the TSP. But in its current form it isn’t.

Why is this of interest? For one, it illustrates a common myth about what causes intractability in a problem:⁵ Combinatorial explosion of the search space (in the trolley problem, the number of possible routes) is an enabling factor for intractability, but it is far from a determining factor. There exist many problems with combinatorially complex search spaces that are computationally tractable to solve. Take, for instance, the Minimum Spanning Tree problem, whose search space even far exceeds that of TSP, or the Shortest Path problem which only lacks the constraint of TSP that the path has to be a closed tour that returns to the start.

The take-home message When assessing a problem’s intractability, don’t be fooled by superficial resemblances between problems nor the size of their search spaces. Knowing whether or not a given problem is intractable requires mathematical proof.

---

¹ An algorithm is said to run in polynomial time if its running time can be upper bounded by some function n^c where c is some constant and n is the input size. For instance, in the case of TSP n is the number of cities. Polynomial-time algorithms are also said to be tractable, because their running times scale reasonably with the input size making it possible to solve larger inputs. Non-polynomial time algorithms do not have this property, which is why problems that require non-polynomial time algorithms for their solution (such as TSP) are said to be intractable.

² I realized only after the poll that the combinatorial trolley problem does not in fact state that the trolley needs to return to its starting position. This means that the ‘routes’ in the problem statement are possibly best interpreted as ‘paths’ instead of ‘tours’ (closed paths).

³ Sridhar Ramesh has kindly pointed out that I assumed that every two stations have a track between them, but that, interestingly, the same conclusion would still apply without that assumption: “given any connected graph on n nodes, one can find a path that reaches each node using only n – 1 unique edges overall (some travelled just once, some travelled forward and back), by making random moves to a yet unvisited node whenever possible and backtracking otherwise. In jargon, this is finding a spanning tree via depth-first search” (Sridhar Ramesh). 

⁴ I wrote a text in Dutch some time ago about this myth and several other common myths about intractability, and how they play a limiting factor in cognitive science, and discussions of rationality and modularity of mind specifically.

⁵ This additional constraint that the trolley must return to the start station is vital. Without it the problem would be equivalent to the Shortest Path problem, which is tractable.