How To Serve Impatient Users

Matthias Englert ( University of Warwick )

Consider the following problem of serving impatient users: we are given a set of customers we would like to serve. We can serve at most one customer in each time step (getting value v_i for serving customer i). At the end of each time step, each as-yet-unserved customer i leaves the system independently with probability q_i, never to return. What strategy should we use to serve customers to maximize the expected value collected?

We present some results and their limitations in the setting of a competitive analysis which compares a strategy with one that knows all the coin tosses of the customers in advance. We then discuss a more fair comparison with an optimal online strategy which does not have this unfair advantage.

Joint work with Marek Cygan, Anupam Gupta, Marcin Mucha, and Piotr Sankowski.