Phase transition in a sequential assignment problem on graphs

Research output: Contribution to journalArticlepeer-review

141 Downloads (Pure)

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∈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.

Original languageEnglish
Pages (from-to)2098-2129
Number of pages32
JournalAnnals of Applied Probability
Volume27
Issue number4
Early online date30 Aug 2017
DOIs
Publication statusPublished - 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.

Cite this