Optimal decision on wait-or-walk if your bus is not coming
How can the dilemma be solved without statistics?
Robert Dochow and Michael Schwarz
You want to visit a friend and arrive there as soon as possible. There is a direct bus connection, but the bus is usually late and sometimes does not come at all. You are at the station on time, but the bus is not there. What are you going to do?
Either you wait for the bus, or you start walking to get to your friend. If you leave the station, you won’t be able to take the bus anymore. On the one hand, you are willing to wait for a ride, since it is faster. On the other hand, there is a chance that the bus will not come. What a dilemma!
Type of problem
Initially, it seems like this is an optimization problem where the goal is to minimize the travel time to your friend. A closer look reveals that only limited information is available, and useful statistical assumptions cannot be made. There is no certain control over the travel time. The real problem is about minimizing personal regret for making the wrong decision. Immediately after you realize the bus is not on time, you waver between two options: wait or walk? The entire problem is a sequential decision problem since the waver time is divisible into discrete sub-problems. Every moment you realize “the bus is still not there”, you have to make a new wait-or-walk decision. Such a sequential problem, where information arrives piece-by-piece in a serial fashion, is called an online problem. In contrast, a corresponding problem where all information is known in advance, like the true future, is called an offline problem. Note that statistical assumptions are not needed if the future is known.
The optimal solution for an online problem
An online problem can usually be solved with different strategies. An online algorithm is a formulation of a strategy as an applicable sequence of steps to solve a concrete scenario. The quality of such an algorithm can be evaluated with a competitive analysis and allows a comparison with alternative algorithms. For this online algorithm, the competitive ratio c needs to be derived. It is defined as the largest ratio of the online solution (ALG) and the corresponding offline solution (OPT) for any scenario. In other words, this ratio is derived by identifying one worst-case scenario, where the algorithmic solution with limited information differs the most from the solution of someone who knows the future.
An online algorithm is denoted as competitive if it is mathematically possible to prove that this c is a constant (with c ≥ 1), which means it is independent of any scenario. This concept has a huge advantage. It provides a performance guarantee for that algorithm, even though the outcome of a practical instance of the problem is not known. Regardless of any scenario, the solution of the online problem will always be smaller than or equal to c times the solution of a rational decision maker who knows the future.
The online algorithm with mathematical provable lowest c has the tightest performance guarantee and is, therefore, optimal. (Note, that the above guarantee formula differs for maximization problems. For more information, examine online optimization.)
The best solution for the offline problem
Assume the distance d to your friend is 3 km, your walking speed v_w is 4 km/h, and the driving speed of the bus v_b is 20 km/h. Hence, by walking, you would need 45 min (3/4 * 60 = 45), but riding the bus would only take 9 min (3/20 * 60 = 9).
However, your personal decision depends on knowing how many minutes you have to wait until the bus arrives at the station t_b. All possible scenarios differ only in that arrival time. If waiting plus the driving time is longer than the pure walking time, then you will always start walking immediately. If not, you will wait.
If you know the future, you will never need longer than 45 minutes to arrive at your friend’s place. In all scenarios of the offline problem, it is only beneficial to wait when the bus arrives within 36 minutes. This would also allow you to arrive in 45 minutes (36 + 9 = 45). Unfortunately, you do not know the future…
Analysis of various online algorithms
Now, take a look at the real practical problem in which you can’t see the future. In an abstract sense, there are only a few ways the problem can be solved:
Algorithm 1 — the athlete (ALG1): One strategy is that you always start walking immediately if the bus is not there. The worst-case scenario for that algorithm looks as follows: You will always walk, and the bus will arrive immediately (assume after ε time, where ε is very small) once you start walking.
You always need 45 minutes but there are many scenarios where you are going to regret your decision, more precisely, in all scenarios where the bus arrives within the next 36 minutes. In the worst-case scenario, the bus arrives ε time after you start walking, where ε time is negligibly small. Then you need 5 times longer than it actually would have been possible (9 vs. 45 minutes because ε is close to 0). The strategy seems to be extreme, but at least you arrive at your friend’s place in each scenario. The algorithm is competitive… but is it also optimal?
Algorithm 2 — the lazy person (ALG2): Another extreme strategy is where you always wait for the bus and never decide to walk. It is easy to foresee that in the worst-case scenario, the bus never comes. You never arrive at your friend’s place. This strategy has no constant c and is, therefore, not competitive.
Algorithm 3 — the optimizer (ALG3): One may always decide to wait for a fixed time x before getting impatient and deciding to walk. It is striking that competitive strategies with different x can significantly differ in the competitive ratio.
For example, suppose you always wait exactly 10 minutes (i.e., x = 1/6 hours) before you start walking. The bus immediately comes after you leave the station in the worst-case scenario. You end up being at your friend’s place after 10+45 = 55 minutes, whereas the offline solution would need 10 + ε +9 = 19 minutes. Hence, you are 2.89 times (55 vs. 19 minutes) worse than the solution for which you would have known the exact arrival time of the bus. Compared to the c = 5 of the athlete (i.e., x = 0 hours), the c = 2.89 is already a significant improvement. But can you do even better?
How to derive the optimal waiting time x*? Regarding the optimal online solution x*, there are two errors you are going to regret. Either you start walking too early or too late. In the too-early case, you regret not having waited longer since the respective offline solution is always going to wait for the bus. In the too-late case, you regret that you didn’t start walking earlier, because the offline solution will immediately start walking when you arrive at the station. The optimal online strategy would balance out both cases to minimize your regret.
Rearranging to x provides the optimal waiting algorithm. By inserting x* in one of the error competitive ratios above, the corresponding optimal competitive ratio c* is derived. It is the lowest possible competitive ratio. If the bus speed is always greater than the walking speed, c* is never larger than 2.
In the concrete example, the optimal waiting time is x* = 0.6 hours (3/4 –3/20 = 0.6) which translates into 36 minutes (0.6 * 60 = 36). The corresponding competitive ratio is c* = 1.8 (2–4/20 = 1.8), where the offline solution arrives after 45 minutes, and the online solution needs 81 minutes (36 + 45 = 81). Based on the given bus and walking speed, there is no better strategy. That means any other waiting time leads always to a higher c.
For a better understanding, consider below the visualization of the competitive ratio for all online strategies in the range between 0 and 120 waiting minutes. The lowest point represents c* with corresponding x*.
Conclusions
So what are you going to do next time when you are at the bus station and the bus is not coming? Before you start walking, think of this article. There exists a strategy that is never 2 times worse than a strategy that knows the exact future. The optimal waiting time is the walking travel time minus bus travel time. This is a worst-case strategy where you have absolutely no information about the future. Realize this: If in practice you make a different decision, you either assume other information, or you are not acting rationally.
Zoom out! What else did you learn? First, you solved a future-related optimization problem without making any statistical or distributional assumptions. The used method is called competitive analysis. Second, your solution has a performance guarantee based on a solution that knows the exact future.
Think about other applications in business and private life: Make or buy? Rent or buy? … Do or not do?
References
- A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis (1998), Cambridge University Press
- J. Chen, S. Kominers and R. Sinnott, Walk versus Wait: The Lazy Mathematician Wins (2008), arXiv Working paper
- C. Thompson, The Bus-wait Formula (2008), New York Times Magazine: Year in Ideas
- A. Morton, A Note on Walking Versus Waiting (2008), arXiv Working paper
- R. Dochow, Online Algorithms for the Portfolio Selection Problem (2016), Springer
