We consider the problem of allocating a set of divisible goods to N agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of T periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial O(N), unless it is given additional information about the agents' values. Then, in line with the emerging area of “algorithms with predictions”, we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the T periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of O(log N) and O(log T) if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of O(log1–∊ N) or O(log1–∊ T) for any constant ∊ > 0.

In many settings, resources are allocated among agents repeatedly over time without the use of monetary transfers: consider, for example, allocating server-time to company employees, rooms to students, or food among food banks. Here, the central challenge is to allocate resources efficiently despite the absence of payments. In this work we study a simple online variant of the standard Fisher market, where we endow all agents with a budget of artificial credits, and then repeatedly run simultaneous first-price auctions for each item in each period. Owing to their simplicity, such mechanisms have been gaining in popularity, with several recent successful implementations, most notably, by Feeding America for US food banks. Our goal in this paper is to understand the incentive and efficiency properties of these mechanisms.

Non-monetary mechanisms for repeated resource allocation are gaining widespread use in many real-world settings. Our aim in this work is to study the allocative efficiency and incentive properties of simple repeated mechanisms based on artificial currencies. Within this framework, we make three main contributions: