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 n _e ≥ 0, and we write n =∑ _e∈En _e. 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 c _G > 0 when (n _e/n : e ∈ E) converges to a point in the interior of a certain convex set R _G, and goes to 0 exponentially when (n _e/n : e ∈ E) is bounded away from R _G. We also obtain estimates in the near-critical region, that is when (n _e/n : e ∈ E) lies close to ∂R _G. We supply quantitative error bounds in our arguments.