Honor Among Bandits: No-Regret Learning for Online Fair Division

The paper studies online fair division of indivisible items, where items arrive one at a time, and each item must be permanently assigned to a player upon arrival. Player utilities are initially unknown and must be learned via bandit-style feedback: there are a finite number of types of goods, and each player’s value for a good of type k is drawn independently from a distribution D_k. The authors aim to maximize utilitarian welfare (the sum of utilities) while satisfying a hard constraint of either envy-freeness in expectation (EFE) or proportionality in expectation (PE).

EFE and PE are evaluated with respect to the randomized allocation on each time step. That is, before observing the type of the new item, the learner proposes a randomized allocation X_t which determines how the item will be allocated for each possible type. Each X_t is required to satisfy the fairness constraint (EFE and PE), not the cumulative realized allocation. I initially found this rather unintuitive, but the authors effectively justify this choice by showing that:

1. Any EFE algorithm achieves realized cumulative envy at most $\sqrt{T} \log(T)$, while optimal is at least $\sqrt{T}$.
2. EFE at each time step does not cause any welfare loss compared to only requiring EFE at the end.

The main result is a simple explore-then-commit algorithm which is EFE or PE while achieving regret $\tilde{O}(T^{2/3})$ wrt welfare.

Along the way, the authors prove that the EFE and PE constraints satisfy the following property: either all players receive the same allocation, or the constraint can be satisfied with slack. This novel result formalizes the intuition that the “hardest case” for fair division is when all agents have the same utilities. EFE/PE can trivially be satisfied in that case by the uniform allocation, and in all other cases, EFE/PE can be satisfied with slack.

The authors study an online fair division problem where items arrive online and need to be assigned to agents to maximize welfare while satisfying one of envy-freeness or proportionality. The novel consideration in their model is that the item valuations are drawn from an unknown distribution. They approach this as both a learning problem as well as an allocation problem. They provide a simple algorithm with small regret compared to an algorithm that knew the distributions beforehand. They also prove several structural results regarding their model.

In this work, the authors consider the problem of maximising the total utility in online fair allocation settings, where: (i) T items having types in set [m] arrive online in T distinct rounds; (ii) the value $V_{i}(t)$ that each agent $i$ assigns to each item $t\in [T]$, when its type is $k$, is independently drawn from a sub-Gaussian distribution with unknown mean $\mu_{i,k}^*$; (iii) for each item that arrives online, its type is known, and based on this information and previous observations, it must be irrevocably assigned to some agent; (iv) the value $V_{i}(t)$ of each item $t$ can only be observed after it has been assigned, and this information allows the estimation of the unknown probability distributions as $t = 1, \ldots, T$ varies.

The authors design an Explore-Then-Commit algorithm that maximises the total utility of the various players over $T$ rounds, with a regret of the order $\tilde{O}(T^{2/3})$, where the maximisation is constrained by achieving fairness properties (envy-freeness or proportionality) in expected value, with high probability.

We would like to thank all the reviewers for their time and comments! We respond to specific comments in the individual rebuttals below.

Shortly after submitting our paper, we found a simple lower bound which shows that for our setting, no algorithm can do better than the ones we presented. We plan to include this in the revision and we believe the new result will strengthen the paper. We include a brief discussion here in case the reviewers are interested, but please feel free to ignore this section if not.

A weakness of the current paper (as acknowledged in the discussion section) is that perhaps a more sophisticated algorithm such as UCB or Thompson Sampling would be able to achieve a better regret of $\tilde{O}(\sqrt{T})$. However, we are actually able to show that $\tilde{O}(T^{2/3})$ is the best that any algorithm can do with a very simple example, given below.

The example and informal proof is as follows. Suppose there are two item types and two players. In this case envy-freeness and proportionality are equivalent, and therefore we will focus on the former. Consider the following two value matrices (with rows = players, columns = item types).

\mu_1 = \\begin{bmatrix} 2 & 3 \\\\ 1 & 1 \\end{bmatrix}

\mu_2 = \\begin{bmatrix} 2 & 3 \\\\ 1 & 1 +T^{-1/3}. \\end{bmatrix}

We can show that no algorithm can with probability $1-1/T$ achieve regret of less than $\tilde{\Omega}(T^{2/3})$ and satisfy envy-freeness in expectation for both of these distributions. First, note that the expected social welfare maximizing allocation for $\mu_1$ is to give all items of type 1 to player 2 and all items of type 2 to player 1. On the other hand, any envy-free allocation for $\mu_2$ must give $\tilde{\Omega}(T^{-1/3})$ fraction of items of type 2 to player 2. This implies that if an algorithm is unable to distinguish between $\mu_1$ and $\mu_2$, then either the regret will be $\tilde{\Omega}(T^{2/3})$ for $\mu_1$ or the algorithm will not be envy-free for $\mu_2$.

Therefore, any algorithm that has regret of less than $\tilde{\Omega}(T^{2/3})$ and satisfies envy-freeness for both $\mu_1$ and $\mu_2$ must distinguish betwen $\mu_1$ and $\mu_2$. The only way to do this is to allocate at least $\tilde{\Omega}(T^{2/3})$ items of type $2$ to player 2. However, this will result in regret under $\mu_1$ of $\tilde{\Omega}(T^{2/3})$.

A more rigorous version of this argument using standard techniques for lower bounds in multi-armed bandit problems would be included in the final paper.

The paper analyzes an interesting setting on online allocation constrained to return envy-free allocations. The setting is interesting and novel. The adopted techniques are also interesting and require non-trivial effort. Results are relevant. The presentation of the paper can be improved by a better organization of the content and a more detailed discussion about some of the assumption (see, e.g., additivity).