Ido Kahana

Ido Kahana, Erel Segal-Halevi, Noam Hazon

Many decision processes run for a long and unknown duration: in each round new requests arrive, an irrevocable choice must be made immediately, and the system is judged by ongoing fairness requirements. Examples include food banks allocating donated items as they arrive, computing systems repeatedly scheduling scarce resources across users, and institutions making repeated public decisions (e.g., which proposals or cases to prioritize) while remaining fair over time. A key challenge in such settings is that fairness requirements are often naturally \emph{scale-dependent}. For example, in fair item allocation, it is common to require that the unfairness is bounded by the highest values of items seen so far. Thus, the scale of fairness changes over time. We propose a general approach to online fairness based on \emph{deficits}, which measure each requirement's current shortfall relative to a time-varying benchmark. Within this framework, we analyze a simple fully online rule that, in each round, chooses the action that best improves the next-round deficit profile. We prove anytime (prefix-wise) guarantees: after every round, all tracked requirements remain satisfied up to a slack that grows only on the order of $\sqrt{t}$ (up to logarithmic factors), and we show this growth is unavoidable in general. We instantiate the framework for online allocation of indivisible goods (yielding natural relaxations of proportionality and envy-freeness) and for online public decision-making. In contrast to previous works on online fair allocation, our rule does not need to know the horizon (the total number of rounds), nor any other information on the future (e.g. the maximum item value). Moreover, our guarantees hold perpetually, at each individual time step.

Ido Kahana, Noam Hazon

In many situations, several agents need to make a sequence of decisions. For example, a group of workers that needs to decide where their weekly meeting should take place. In such situations, a decision-making mechanism must consider fairness notions. In this paper, we analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. We consider both offline and online settings, and concentrate on the fairness notion of proportionality and its relaxations. Specifically, in the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome, even if such an outcome exists. We thus introduce a new fairness property that captures this requirement, and show that a variant of the leximin mechanism satisfies the new fairness property. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations. We thus consider a natural restriction on the agents' preferences, and show that the leximin mechanism guarantees the best possible additive approximation to proportionality and satisfies all the relaxations of proportionality.