The fair division of hereditary set systems

DOI10.1007/978-3-030-04612-5_20MaRDI QIDQ2190407zbMATH OpenOpenAlexFDO

Authors Adrian Vetta, Zhentao Li

Publication date 18 June 2020

Full work available at URL https://arxiv.org/abs/1812.09561

zbMATH Keywords

fair divisionhereditary set systemsindivisible itemspolynomial time algorithm

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: We consider the fair division of indivisible items using the maximin shares measure. Recent work on the topic has focused on extending results beyond the class of additive valuation functions. In this spirit, we study the case where the items form an hereditary set system. We present a simple algorithm that allocates each agent a bundle of items whose value is at least $0.3667$ times the maximin share of the agent. This improves upon the current best known guarantee of $0.2$ due to Ghodsi et al. The analysis of the algorithm is almost tight; we present an instance where the algorithm provides a guarantee of at most $0.3738$. We also show that the algorithm can be implemented in polynomial time given a valuation oracle for each agent.

Recommendations

• On Fair Division under Heterogeneous Matroid Constraints
• Fair Partitions
• The problem of fair division for countably many participants
• scientific article; zbMATH DE number 599450
• A hierarchy of hereditarily finite sets
• Extensions of cut-and-choose fair division
• The theory of hereditarily bounded sets
• The fair sharing graph and its Helly property
• Hereditary equality of domination and exponential domination

Cites work

• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Approximation algorithms for computing maximin share allocations
• Fair Allocation of Indivisible Goods to Asymmetric Agents
• Fair enough: guaranteeing approximate maximin shares
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)

Cited in

(5)

• Approximating Nash social welfare under binary XOS and binary subadditive valuations
• An improved approximation algorithm for maximin shares
• Fair allocation of indivisible goods: improvement
• On Fair Division under Heterogeneous Matroid Constraints
• Improved maximin guarantees for subadditive and fractionally subadditive fair allocation problem

This page was built for publication: The fair division of hereditary set systems

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