Abstract
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∈E}n _{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 nearcritical region, that is when (n _{e}/n : e ∈ E) lies close to ∂R _{G}. We supply quantitative error bounds in our arguments.
Original language  English 

Pages (fromto)  20982129 
Number of pages  32 
Journal  Annals of Applied Probability 
Volume  27 
Issue number  4 
Early online date  30 Aug 2017 
DOIs  
Publication status  Published  31 Aug 2017 
Keywords
 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
Fingerprint Dive into the research topics of 'Phase transition in a sequential assignment problem on graphs'. Together they form a unique fingerprint.
Profiles

Antal Jarai
 Department of Mathematical Sciences  Senior Lecturer
 EPSRC Centre for Doctoral Training in Statistical Applied Mathematics (SAMBa)
 Probability Laboratory at Bath
Person: Research & Teaching