The fair division of hereditary set systems

DOI10.1007/978-3-030-04612-5_20zbMATH Open1443.91177arXiv1812.09561OpenAlexW3162759032MaRDI QIDQ2190407FDOQ2190407

Authors: Adrian Vetta, Zhentao Li 

Publication date: 18 June 2020

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.

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

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

zbMATH Keywords

polynomial time algorithmfair divisionindivisible itemshereditary set systems

Mathematics Subject Classification ID

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

Cites Work

• Approximation algorithms for computing maximin share allocations
• Title not available (Why is that?)
• A polynomial-time approximation scheme for maximizing the minimum machine completion time
• Title not available (Why is that?)
• Fair enough: guaranteeing approximate maximin shares
• Fair Allocation of Indivisible Goods to Asymmetric Agents

Cited In (5)

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

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)