Kim Lukas Kiehn: Online Optimisation of the Nash Social Welfare

 We consider the problem of assigning a sequence of items appearing online to a set of \(n\) agents. Each agent has a different non-negative value for each item, which is only revealed when the item arrives. Then the allocation has to be carried out immediately and irrevocably. The goal is to maximise Nash social welfare, that is, the (weighted) geometric mean of the agents' values.
We give a \((1 - \varepsilon)\)-competitive algorithm for the case in which items are revealed in random order and there is a large number of small items.
Our main technique to obtain the result is exploit the fact that the gradients of the geometric mean are stable when considering points sufficiently far away from the coordinate hyperplanes.