Search

We consider a generalization of the best choice problem to upward directed graphs. We describe a strategy for choosing a maximal element (i.e., an element with no outgoing edges) when a selector knows in advance only the number n of vertices of the graph. We show that, as long as the number of elements dominated directly by the maximal ones is not greater than c 1 n for some positive constant c 1 and the indegree of remaining vertices is bounded by a constant D , the probability p n of the right choice according to our strategy satisfies lim inf n → ∞ p n n ≥ δ > 0 , where δ is a constant depending on c 1 and D .

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.