Antal Jarai: Phase transition in discrete sequential assignment

A simple example of stochastic sequential assignment is the following game. You start with N empty boxes laid out in a sequence. A die is rolled N times, and after each roll in turn, you have to place the value rolled into one of the boxes (and this choice cannot be altered on subsequent rolls). After the N-th roll, you have an N-digit number, your score. Your objective is to maximize the score. This can be made sense of in at least two ways: (i) maximize the expectation of the score; (ii) maximize the probability of achieving the "perfect score", i.e. the probability of the event that the assignment is monotonic. With the objective (i) the problem has been introduced and solved by Derman, Lieberman, and Ross (1972), in the sense that they gave a recursive procedure to calculate the optimal strategy (that admits a simple description). In this talk we will mainly be interested in the objective (ii), that allows an interesting generalization of the problem to graphs, where a phase transition occurs.