4.7 Article

Fair allocation of indivisible goods: Beyond additive valuations

相关参考文献

注意:仅列出部分参考文献,下载原文获取全部文献信息。
Article Computer Science, Artificial Intelligence

An improved approximation algorithm for maximin shares

Jugal Garg et al.

Summary: This paper investigates fair division in the case of indivisible items with additive valuations, focusing on the concept of maximin share (MMS). It presents a simple algorithm for the existence of a 3/4-MMS allocation and shows that there is always a (3/4 + 1/12n)-MMS allocation, improving previous factors. The approach introduced in the paper can be easily extended to a strongly polynomial time algorithm and better approximation guarantees.

ARTIFICIAL INTELLIGENCE (2021)

Article Computer Science, Hardware & Architecture

Fair Enough: Guaranteeing Approximate Maximin Shares

David Kurokawa et al.

JOURNAL OF THE ACM (2018)

Article Computer Science, Theory & Methods

Approximation Algorithms for Computing Maximin Share Allocations

Georgios Amanatidis et al.

ACM TRANSACTIONS ON ALGORITHMS (2017)

Article Economics

Gross substitutability: An algorithmic survey

Renato Paes Leme

GAMES AND ECONOMIC BEHAVIOR (2017)

Article Automation & Control Systems

Characterizing conflicts in fair division of indivisible goods using a scale of criteria

Sylvain Bouveret et al.

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS (2016)

Article Computer Science, Software Engineering

An efficient polynomial time approximation scheme for load balancing on uniformly related machines

Leah Epstein et al.

MATHEMATICAL PROGRAMMING (2014)

Article Computer Science, Theory & Methods

Submodular Secretary Problem and Extensions

Mohammadhossein Bateni et al.

ACM TRANSACTIONS ON ALGORITHMS (2013)

Article Computer Science, Theory & Methods

ON MAXIMIZING WELFARE WHEN UTILITY FUNCTIONS ARE SUBADDITIVE

Uriel Feige

SIAM JOURNAL ON COMPUTING (2009)