Phase transition in a sequential assignment problem on graphs

Abstract: We study the following game on a finite graph

G = (V, E)

. At the start, each edge is assigned an integer

n_{e} g e 0

,

n = s u m_{e i n E} n_{e}

. In round

t

,

1 l e t l e n

, a uniformly random vertex

v i n 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, d o t s, 0)

is reached; in other words, the edge values never go negative. Our main result is that there is a phase transition: as

n o i n f t y

, the probability that the player wins approaches a constant

c_{G} > 0

when

(n_{e} / n : e i n E)

converges to a point in the interior of a certain convex set

m a t h c a l R_{G}

, and goes to

0

exponentially when

(n_{e} / n : e i n E)

is bounded away from

m a t h c a l R_{G}

. We also obtain upper bounds in the near-critical region, that is when

(n_{e} / n : e i n E)

lies close to

p a r t i a l m a t h c a l R_{G}

. We supply quantitative error bounds in our arguments.

Recommendations

Cited in

(2)

This page was built for publication: Phase transition in a sequential assignment problem on graphs