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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-11
Main Authors: Hartman, Eden, Aumann, Yonatan, Hassidim, Avinatan, Segal-Halevi, Erel
Format: Article
Language:English
Subjects:
Allocations
Lotteries
Maximization
Optimization
Solvers
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422