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.
- Critical phenomenon
- Discrete stochastic optimal control
- Markov decision process
- Phase transition
- Stochastic dynamic programming
- Stochastic sequential assignment
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty
FingerprintDive into the research topics of 'Phase transition in a sequential assignment problem on graphs'. Together they form a unique fingerprint.
- Department of Mathematical Sciences - Senior Lecturer
- EPSRC Centre for Doctoral Training in Statistical Applied Mathematics (SAMBa)
- Probability Laboratory at Bath
Person: Research & Teaching