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

DOI10.1016/J.ARTINT.2024.104118MaRDI QIDQ6566645zbMATH OpenFDO

Authors Haris Aziz, Bo Li, Hervé Moulin, Xiaowei Wu, 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) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Approximation algorithms (68W25) Agent technology and artificial intelligence (68T42)

Recommendations

• Approximately EFX allocations for indivisible chores
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources

Cites work

• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• A complete anytime algorithm for number partitioning
• A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
• A tight negative example for MMS fair allocations
• Allocating contiguous blocks of indivisible chores fairly
• Almost envy-freeness with general valuations
• Breaking the 3/4 barrier for approximate maximin share
• Competitive equilibrium with indivisible goods and generic budgets
• Dividing connected chores fairly
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Fair division of indivisible goods: recent progress and open questions
• Fair enough: guaranteeing approximate maximin shares
• Maximum Nash welfare and other stories about EFX
• Multiple birds with one stone: beating 1/2 for EFX and GMMS via envy cycle elimination
• On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources
• Optimal bounds on the price of fairness for indivisible goods
• The price of fairness

Cited in

(1)

• On fairness via picking sequences in allocation of indivisible goods

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)