Almost proportional allocations of indivisible chores: computation, approximation and efficiency

DOI10.1016/J.ARTINT.2024.104118zbMATH Open1542.68195MaRDI QIDQ6566645

Hervé Moulin, Xiaowei Wu, Bo Li, Haris Aziz, Xinran Zhu

Publication date: 3 July 2024

Published in: Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

Pareto optimalityordinal preferencesindivisible choresPROPX

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Agent technology and artificial intelligence (68T42)

Cites Work

• Title not available (Why is that?)
• Dividing connected chores fairly
• A complete anytime algorithm for number partitioning
• Allocating contiguous blocks of indivisible chores fairly
• A tight negative example for MMS fair allocations
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• Maximum Nash welfare and other stories about EFX
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• Optimal bounds on the price of fairness for indivisible goods
• The Price of Fairness
• Fair Enough
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Competitive Equilibrium with Indivisible Goods and Generic Budgets
• Almost Envy-Freeness with General Valuations
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• Fair division of indivisible goods: recent progress and open questions
• Breaking the 3/4 barrier for approximate maximin share

This page was built for publication: Almost proportional allocations of indivisible chores: computation, approximation and efficiency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566645)