Phase transition in a sequential assignment problem on graphs

We study the following sequential assignment problem on a finite graph G = (V, E). Each edge e . E starts with an integer value ne . 0, and we write n = .e.E ne. At time t, 1 . t . n, a uniformly random vertex v . V is generated, and one of the edges f incident with v must be selected. The value of f is then decreased by 1. There is a unit final reward if the configuration (0,..., 0) is reached. Our main result is that there is a phase transition: as n . ., the expected reward under the optimal policy approaches a constant cG > 0 when (ne/n : e . E) converges to a point in the interior of a certain convex set ..G, and goes to 0 exponentially when (ne/n : e . E) is bounded away from ..G. We also obtain estimates in the near-critical region, that is when (ne/n : e . E) lies close to ...G. We supply quantitative error bounds in our arguments.