To wait or not to wait? analysis for the traveler's waiting problem with incomplete information

摘要

Based on the traditional Ski-Rental Problem, an ongoing decision-making problem in our everyday life, namely the travelerpsilas waiting problem, is studied in this paper. The realistic background of the problem is that a traveler's decision on whether he should wait for a bus with uncertain arriving time. Three approaches for decision-making with incomplete information, i.e. worst-case competitive analysis, average case analysis and average-case competitive analysis, have been employed to address the problem respectively. Some interesting results are obtained through the analysis. The approaches and these results are formulated in detail. Furthermore, a more general version of this problem is proposed, and some online strategies are also discussed in this paper.