Gusein-Zade problem for directed path

We consider the following online decision problem. The vertices of a directed path are being observed one by one in some random order by a selector. At time t the selector examines the tth vertex and knows the graph induced by the t vertices that have already been examined. The selector's aim is to choose the currently examined vertex maximizing the probability that it belongs to some prescribed subset of vertices. The optimal stopping time for a subset consisting of the two top vertices is given. For the path of cardinality n the numerical approximation of the probability of the right choice according to the optimal algorithm is given. © 2009 Elsevier B.V. All rights reserved.