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 \mathrm{\infty }$, the probability that the player wins approaches a constant $c_G>0$ when $(n_e/n : e \in E)$convergestoapointintheinteriorofacertainconvexset$$\mathcal{R}$_G$,andgoesto$0$exponentiallywhen$(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\mathrm{/}n:e\in E)$ lies close to $\partial $\mathcal{R}$_G$. We supply quantitative error bounds in our arguments.