Phase transition in a sequential assignment problem on graphs

We study the following game on a finite graph $$G = (V, E)$$. At the start, each edge is assigned an integer $$n_e \ge 0$$, $$n = \sum_{e \in E} n_e$$. In round $$t$$, $$1 \le t \le n$$, a uniformly random vertex $$v \in V$$ is chosen and one of the edges $$f$$ incident with $$v$$ is selected by the player. The value assigned to $$f$$ is then decreased by $$1$$. The player wins, if the configuration $$(0, \dots, 0)$$ is reached; in other words, the edge values never go negative. Our main result is that there is a phase transition: as $$n \to \infty$$, the probability that the player wins approaches a constant $$c_G > 0$$ when $$(n_e/n : e \in E)$$ converges to a point in the interior of a certain convex set $$\mathcal{R}_G$$, and goes to $$0$$ exponentially when $$(n_e/n : e \in E)$$ is bounded away from $$\mathcal{R}_G$$. We also obtain upper bounds in the near-critical region, that is when $$(n_e/n : e \in E)$$ lies close to $$\partial \mathcal{R}_G$$. We supply quantitative error bounds in our arguments.