Summary
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.
Strengths
The presentation is clear and accessible. Although some of the modeling choices felt initially unintuitive, the authors did an excellent job of justifying those choices, as discussed above. The main result is satisfying, both in terms of the simple explore-then-commit algorithm and the regret bound. Essentially, the authors successfully solved the problem they chose to study.
I found the either-uniform-allocation-or-slack property (and the result that EFE and PE satisfy it) to be quite interesting as well. This result captures an important intuition in a simple way. The authors argue that this property may be of independent interest, and I agree.
Weaknesses
Although I think the problem is reasonable and meshes well with prior work, I question whether the mathematical model has any real-world relevance. The authors use a running example of a food bank with multiple branches, with the idea that unpredictable perishable donations must be allocated immediately and fairly among the branches. I have several problems with this analogy:
1. Surely food banks wish to allocate according to need without worrying that one branch might “envy” another if the second branch simply has higher need?
2. The paper assumes additive utility, and each branch’s utility would be extremely non-additive (no one needs infinite cereal).
3. It’s hard to imagine the donations being so unpredictable.
To be clear: I’m not claiming that a mathematical model must perfectly match reality in order to provide real-world insights. But this paper’s model seems only tenuously connected to the real-world scenario that is used as motivation. If the authors have further justification for the food bank analogy, I would be interested to hear it.
To me, the most compelling story in this paper actually centers on the either-uniform-allocation-or-slack property. The authors establish this intuitive but nontrivial property, and demonstrate how it can be applied in a bandit context. I can easily imagine this property being useful for other fair division problems that might have more real-world relevance.
This is more minor, but I think the citation below is quite relevant and should be discussed along with Benadè et al.
Hakuei Yamada, Junpei Komiyama, Kenshi Abe, and Atsushi Iwasaki. Learning fair division from bandit feedback. International Conference on Artificial Intelligence and Statistics, 2024.
Questions
Do you agree with my criticisms of the food bank analogy? Is there a different real-world situation that you believe is captured by your mathematical model? More broadly, do you believe that your mathematical model provides real-world insights, and if so, what are they?
Below is feedback that you're welcome to take or leave. I don't expect responses, even though some are phrased as questions.
1. I would suggest naming Property 2 so that I don’t have to keep calling it the either-uniform-allocation-or-slack property :)
2. “This distribution is independent of both player i’s distributions for other item types and other players’ distributions.” Distributions can’t really be independent; I think this should state that samples from those distributions are independent.
3. “Intuitively, this is equivalent to assuming that players have non-zero values for all item types and that their values have a finite upper bound.” I don’t think this is quite right. Assuming non-zero values would just require mu_{ik}^* > 0. I would describe this assumption as saying that the distribution means are “well-conditioned”.
4. Definitions 1 and 2: mu_i^* is a vector, right? I don’t think this was ever explicitly defined. (Only mu^* and mu_{ik}^* were, I think.) The definitions are also missing “for all i”.
5. “proof” should be capitalized at the start of proofs
6. Why not just use gamma_0 in Property 2? Why have for all gamma < gamma_0?
7. Is it intentional for the “2” in C_{P2} to be a hyperlink to property 2?
8. Consider mentioning the actual value of (or a bound on) gamma_0 is for each property?
9. For readability in Algorithm 1, consider writing indicator variables as \mathbb{1}(stuff) instead of \mathbb{1}_{stuff}.
10. The notation “\mu in \hat{\mu} \pm \varepsilon” is non-standard to my knowledge. Consider “\mu in [\hat{\mu} - \varepsilon, \hat{\mu} + \varepsilon]”
11. I found lines 154-178 to be quite compelling and and also quite important. Consider making this its own subsection? And maybe even including some of the Theorem statements from Appendix B?
12. I really like lines 323-330.
Limitations
The authors thoroughly discussed the technical limitations of their work, but did not discuss what I see as the greatest limitation: the weak motivation of the problem and the potential lack of real-world insights.