Reducing Leximin Fairness to Utilitarian Optimization
<|reference_start|>Reducing Leximin Fairness to Utilitarian Optimization: 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 outcomes that is leximin in expectation. Importantly, the scheme is robust in the sense that, given an approximate utilitarian solver, it produces an outcome 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.<|reference_end|>
@article{hartman2024reducing,
    title={Reducing Leximin Fairness to Utilitarian Optimization},
    author={Eden Hartman, Yonatan Aumann, Avinatan Hassidim, Erel Segal-Halevi},
    journal={arXiv preprint arXiv:2409.10395},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.10395},
    primaryClass={cs.GT cs.DS cs.MA}
}