Research map / Learning theory and algorithms / Submodular and game algorithms
Reducing Leximin Fairness to Utilitarian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
The paper shows any utilitarian-welfare black-box (exact or approximate, possibly randomized) can be turned into a leximin-optimal or alpha-leximin-approximate lottery over states.
Problem
Computing distributions over deterministic states that are leximin-optimal (or alpha-leximin-approximate) in expectation, where the state space may be exponential in n and direct leximin solvers need NP-hard single-objective oracles.
Approach
Reduce leximin to utilitarian welfare maximization: an iterative Ordered-Outcomes-style loop uses a "shallow solver" that only needs to be optimal over solutions using at most alpha probability on non-degenerate states; this is implemented via binary search, a weak feasibility oracle, linearized LP, and an approximate separation oracle built from the utilitarian black-box with weights c_i, preserv
Key results
- Shows an alpha-approximate utilitarian black-box yields an alpha-leximin approximation in time polynomial in n and black-box runtime, with the same factor.
- For submodular utilities, yields a deterministic 1/2-leximin-approximation and a (1-1/e)-leximin-approximation with high probability.
- Gives an FPTAS for leximin in giveaway lotteries and participatory budgeting lotteries via the knapsack FPTAS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the reduction to an α-approximate utilitarian solver | Utilitarian-to-leximin reduction · General social choice problems | leximin approximation ratio: α | Helped |
| Use an exact utilitarian solver | Utilitarian-to-leximin reduction · General social choice problems | leximin optimality | Helped |
| Apply the reduction to greedy utilitarian welfare maximization | Stochastic indivisible allocations · Additive utilities | leximin optimality | Helped |
| Apply the reduction to the deterministic utilitarian approximation algorithm | Stochastic indivisible allocations · Submodular utilities | leximin approximation ratio: \frac{1}{2} | Helped |
| Apply the reduction to the randomized utilitarian approximation algorithm | Stochastic indivisible allocations · Submodular utilities | leximin approximation ratio: (1-\frac{1}{e}) | Helped |
| Apply the reduction to an FPTAS for knapsack | Giveaway lotteries · Giveaway lotteries | approximation scheme | Helped |
| Apply the reduction to an FPTAS for knapsack | Participatory budgeting lotteries · Participatory budgeting lotteries | approximation scheme | Helped |
| Use a randomized α-approximate utilitarian solver with success probability p | Randomized utilitarian-to-leximin reduction · General social choice problems | success probability: p | Helped |
Surprising findings
- The shallow-solver requirement is strictly weaker than the approximately-optimal-solver requirement used in prior work, for t=1 the shallow solver may not satisfy the approximately-optimal requirement.
Limitations
- Requires non-negative utilities due to the degenerate state; negative utilities left open.
- Only ex-ante fairness guaranteed; ex-post fairness not addressed.
- Nash welfare and the deterministic (non-lottery) setting are not covered.
Experimental setup
Metrics: leximin approximation factor polynomial running time
Baselines: Ordered Outcomes (exact leximin) approximate egalitarian solver of Cole and Tao
Builds on: Ordered Outcomes algorithm Cole and Tao stochastic allocation leximin/egalitarian reduction ellipsoid method
Closest papers by meaning
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.86)
- Fair and Efficient Completion of Indivisible Goods (AAAI 2025 · similarity 0.86)
- Repeated Fair Allocation of Indivisible Items (AAAI 2024 · similarity 0.86)
- Distributive Fairness in Large Language Models: Evaluating Alignment with Human Values (NeurIPS 2025 · similarity 0.86)
- Almost Envy-Free Allocations of Indivisible Goods or Chores with Entitlements (AAAI 2024 · similarity 0.86)
- Maxileximin Envy Allocations and Connected Goods (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.