PHASE TRANSITION IN A SEQUENTIAL ASSIGNMENT PROBLEM ON GRAPHS
成果类型：
Article
署名作者：
Jarai, Antal A.
署名单位：
University of Bath
刊物名称：
ANNALS OF APPLIED PROBABILITY
ISSN/ISSBN：
1050-5164
DOI：
10.1214/16-AAP1250
发表日期：
2017
页码：
2098-2129
关键词：
摘要：
We study the following game on a finite graph G = (V,E). Each edge e is an element of E starts with an integer value n(e) >= 0, and we write n = Sigma eE n(e). At time t, 1 <= t <= n, a uniformly random vertex v is an element of 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 -> infinity, the expected reward under the optimal policy approaches a constant c(G) > 0 when (n(e)/n : e is an element of 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 is an element of E) is bounded away from R-G. We also obtain estimates in the near-critical region, that is when (ne/n : e. E) lies close to partial derivative RG. We supply quantitative error bounds in our arguments.
来源URL：