Computing fair and efficient allocations with few utility values

DOI10.1016/J.TCS.2023.113932MaRDI QIDQ6159026zbMATH OpenOpenAlexFDO

Authors Jugal Garg, Aniket Murhekar

Publication date 1 June 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2023.113932

zbMATH Keywords

EFXEQXfair and efficient allocationNash welfare

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Computing fair and efficient allocations with few utility values
• Maximum Nash welfare and other stories about EFX
• Computing welfare-maximizing fair allocations of indivisible goods
• Generalized binary utility functions and fair allocations
• Almost envy-freeness with general valuations

Cites work

• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Almost envy-freeness with general valuations
• Approximating the Nash social welfare with budget-additive valuations
• Approximating the Nash social welfare with indivisible items
• APX-hardness of maximizing Nash social welfare with indivisible items
• Assigning papers to referees
• Computing fair and efficient allocations with few utility values
• Efficient reallocation under additive and responsive preferences
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• Improving Nash social welfare approximations of indivisible goods
• Maximizing Nash product social welfare in allocating indivisible goods
• Maximum Nash welfare and other stories about EFX
• Microeconomic theory
• Near fairness in matroids
• On (1,)-restricted assignment makespan minimization
• On fair division for indivisible items
• On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
• Random Matching Under Dichotomous Preferences
• Sur la division pragmatique

Cited in

(10)

• scientific article; zbMATH DE number 6466174 (Why is no real title available?)
• Computing welfare-maximizing fair allocations of indivisible goods
• The frontier of intractability for EFX with two agents
• When is truthfully allocating chores no harder than goods?
• Tractable graph structures in EFX orientation
• The price of EF1 for few agents with additive ternary valuations
• Weighted EF1 allocations for indivisible chores
• Proportional allocation of indivisible goods up to the least valued good on average
• Best-of-both-worlds fair allocation of indivisible and mixed goods
• Fair division of indivisible items: envy-freeness vs. efficiency revisited

This page was built for publication: Computing fair and efficient allocations with few utility values

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