Envy-freeness and the relaxation to Envy-freeness up to one item (EF-1) have been used as fairness concepts in the economics, game theory, and social choice literatures since the 1960s, and have recently gained popularity within the recommendation systems communities. In this short position paper we will give an overview of envy-freeness and its use in economics and recommendation systems; and illustrate why envy is not appropriate to measure fairness for use in settings where personalization plays a role.

In addition to this matching distribution constraint, we also require that the recipient's

It was past midnight and I was awake, scrolling through WhatsApp group messages I'd sent earlier. I'd been trying to be funny, quick, effervescent. But each message now felt like too much. I'd overreached again – said more than I should, said it wrong. I had that familiar ache of feeling overexposed and ridiculous.

Explore-and-exploit tradeoffs play a key role in recommendation systems (RSs), aiming at serving users better by learning from previous interactions. Despite their commercial success, the societal effects of explore-and-exploit mechanisms are not well understood, especially regarding the utility discrepancy they generate between different users. In this work, we measure such discrepancy using the economic notion of envy. We present a multi-armed bandit-like model in which every round consists of several sessions, and rewards are realized once per round. We call the latter property reward consistency, and show that the RS can leverage this property for better societal outcomes. On the downside, doing so also generates envy, as late-to-arrive users enjoy the information gathered by early-to-arrive users. We examine the generated envy under several arrival order mechanisms and virtually any anonymous algorithm, i.e., any algorithm that treats all similar users similarly without leveraging their identities. We provide tight envy bounds on uniform arrival and upper bound the envy for nudged arrival, in which the RS can affect the order of arrival by nudging its users. Furthermore, we study the efficiency-fairness trade-off by devising an algorithm that allows constant envy and approximates the optimal welfare in restricted settings. Finally, we validate our theoretical results empirically using simulations.

Fair division of indivisible resources is a well-researched problem at the intersection of theoretical computer science and economics. The problem arises in a variety of practical settings, from allocating slots or assets to distributing aid or shared goods. One of the most intuitive notions of fairness is envy-freeness (EF) [Fol67], where each individual is content with their share compared to others. However, when the resources are indivisible - such as physical objects, housing units, or assets like artwork -- achieving true envy-freeness becomes impossible in many cases. While EF provides a natural measure of fairness, the combinatorial nature of indivisible goods often renders EF allocations unattainable, highlighting the necessity for more nuanced fairness criteria.

We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our goal is to maximize social welfare subject to allocating the goods fairly in expectation. When a player's value for an item is unknown at the time of allocation, we show that this problem reduces to a variant of (stochastic) multi-armed bandits, where there exists an arm for each player's value for each type of good. At each time step, we choose a distribution over arms which determines how the next item is allocated. We consider two sets of fairness constraints for this problem: envy-freeness in expectation and proportionality in expectation. Our main result is the design of an explore-then-commit algorithm that achieves $\tilde{O}(T^{2/3})$ regret while maintaining either fairness constraint. This result relies on unique properties fundamental to fair-division constraints that allow faster rates of learning, despite the restricted action space.

Ensuring fair and stable allocation of scarce resources is a fundamental challenge in a wide range of applications. Traditional literature assumes that information regarding agents' preferences, whether available centrally to the designer or held privately by the agents, is known before the allocation process (the mechanism). However, this assumption hinders application in practical settings where agents typically evaluate resources only after receiving or consuming them. Furthermore, such preference information is often noisy and expensive for the central designer to gather from all agents, thus complicating the implementation of traditional mechanisms. Examples of domains where these challenges manifest include applications where geographical and time constraints impede information collection, such as distributing resources to food banks and providing humanitarian aid to disaster areas and war zones [1, 6].

We consider a practically motivated variant of the canonical online fair allocation problem: a decision-maker has a budget of perishable resources to allocate over a fixed number of rounds. Each round sees a random number of arrivals, and the decision-maker must commit to an allocation for these individuals before moving on to the next round. The goal is to construct a sequence of allocations that is envy-free and efficient. Our work makes two important contributions toward this problem: we first derive strong lower bounds on the optimal envy-efficiency trade-off that demonstrate that a decision-maker is fundamentally limited in what she can hope to achieve relative to the no-perishing setting; we then design an algorithm achieving these lower bounds which takes as input $(i)$ a prediction of the perishing order, and $(ii)$ a desired bound on envy. Given the remaining budget in each period, the algorithm uses forecasts of future demand and perishing to adaptively choose one of two carefully constructed guardrail quantities. We demonstrate our algorithm's strong numerical performance - and state-of-the-art, perishing-agnostic algorithms' inefficacy - on simulations calibrated to a real-world dataset.