Reducing Leximin Fairness to Utilitarian Optimization
Eden Hartman, Yonatan Aumann, Avinatan Hassidim, Erel Segal-Halevi
Abstract
Two prominent objectives in social choice are utilitarian - maximizing the sum of agents' utilities, and leximin - maximizing the smallest agent's utility, then the second-smallest, etc. Utilitarianism is typically computationally easier to attain but is generally viewed as less fair. This paper presents a general reduction scheme that, given a utilitarian solver, produces a distribution over states (deterministic outcomes) that is leximin in expectation. Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces a lottery that is approximately-leximin (in expectation) - with the same approximation factor. We apply our scheme to several social choice problems: stochastic allocations of indivisible goods, giveaway lotteries, and fair lotteries for participatory budgeting.
BibTeX
@article{Hartman_Aumann_Hassidim_Segal-Halevi_2025, title={Reducing Leximin Fairness to Utilitarian Optimization}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/33521}, DOI={10.1609/aaai.v39i13.33521}, abstractNote={Two prominent objectives in social choice are utilitarian - maximizing the sum of agents’ utilities, and leximin - maximizing the smallest agent’s utility, then the second-smallest, etc. Utilitarianism is typically computationally easier to attain but is generally viewed as less fair. This paper presents a general reduction scheme that, given a utilitarian solver, produces a distribution over states (deterministic outcomes) that is leximin in expectation. Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces a lottery that is approximately-leximin (in expectation) - with the same approximation factor. We apply our scheme to several social choice problems: stochastic allocations of indivisible goods, giveaway lotteries, and fair lotteries for participatory budgeting.}, number={13}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Hartman, Eden and Aumann, Yonatan and Hassidim, Avinatan and Segal-Halevi, Erel}, year={2025}, month={Apr.}, pages={13905-13914} }