The Leximin Approach for a Sequence of Collective Decisions
This addresses fairness in sequential decision-making for groups like workers, with incremental contributions to mechanism design.
The paper analyzes fairness of three mechanisms for sequential group decisions, showing they fail to achieve proportionality in offline settings and introducing a new property satisfied by a leximin variant, while in online settings, it proves proportionality is impossible but leximin guarantees the best additive approximation under preference restrictions.
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.