Fair division with multiple pieces

DOI10.1016/J.DAM.2019.12.018MaRDI QIDQ2192068zbMATH OpenOpenAlexWikidataFDO

Authors Kathryn Nyman, Francis Edward Su, Shira Zerbib

Publication date 29 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

fair divisionshift assignmentKKMSdual Komiyamultiple piecesrental harmony in two buildings

Mathematics Subject Classification ID

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

Abstract: Given a set of $p$ players we consider problems concerning envy-free allocation of collections of $k$ pieces from a given set of goods or chores. We show that if $plen$ and each player can choose $k$ pieces out of $n$ pieces of a cake, then there exist a division of the cake and an allocation of the pieces where at least $fracp2(k^2-k+1)$ players get their desired $k$ pieces each. We further show that if $plek(n-1)+1$ and each player can choose $k$ pieces, one from each of $k$ cakes that are divided into $n$ pieces each, then there exist a division of the cakes and allocation of the pieces where at least $fracp2k(k-1)$ players get their desired $k$ pieces. Finally we prove that if $pgek(n-1)+1$ and each player can choose one shift in each of $k$ days that are partitioned into $n$ shifts each, then, given that the salaries of the players are fixed, there exist $n(1+lnk)$ players covering all the shifts, and moreover, if $k=2$ then $n$ players suffice. Our proofs combine topological methods and theorems of F"uredi, Lov'asz and Gallai from hypergraph theory.

Recommendations

• Two-player envy-free multi-cake division
• Envy-free cake division without assuming the players prefer nonempty pieces
• Envy-free two-player \(m\)-cake and three-player two-cake divisions
• Envy-free division of discrete cakes
• Envy-free division of discrete cakes

Cites work

• scientific article; zbMATH DE number 3154393 (Why is no real title available?)
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 3422228 (Why is no real title available?)
• A polytopal generalization of Sperner's lemma
• A simple proof of K-K-M-S theorem
• Achieving rental harmony with a secretive roommate
• Edge-covers in \(d\)-interval hypergraphs
• Envy-free two-player \(m\)-cake and three-player two-cake divisions
• Intersection properties of families of convex (n,d)-bodies
• Maximum degree and fractional matchings in uniform hypergraphs
• On the ratio of optimal integral and fractional covers
• Rental Harmony: Sperner's Lemma in Fair Division
• Two-player envy-free multi-cake division

Cited in

(14)

• Discrete geometry. Abstracts from the workshop held September 20--26, 2020 (hybrid meeting)
• Fair multi-cake cutting
• Fair Division
• Cutting a Cake Fairly for Groups Revisited
• Generalized rental harmony
• Multi resource allocation with partial preferences
• Games of fair division
• Envy-free division of multi-layered cakes
• Envy-free two-player \(m\)-cake and three-player two-cake divisions
• A sparse colorful polytopal KKM theorem
• On Fair Division under Heterogeneous Matroid Constraints
• Fair distributions for more participants than allocations
• Simple fair division of a square
• Envy-free cake division without assuming the players prefer nonempty pieces

This page was built for publication: Fair division with multiple pieces

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