The best choice problem for upward directed graphs

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 nn 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 c1n for some positive constant c1c1 and the indegree of remaining vertices is bounded by a constant DD, the probability pnpn of the right choice according to our strategy satisfies lim infn→∞pnn≥δ>0, where δδ is a constant depending on c1c1 and DD.