Almost envy-free allocations with connected bundles

DOI10.1016/J.GEB.2021.11.006MaRDI QIDQ2078044zbMATH OpenOpenAlexFDO

Authors Vittorio Bilò, I. Caragiannis, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker, Michele Flammini

Publication date 25 February 2022

Published in Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.09406, https://drops.dagstuhl.de/opus/volltexte/2018/10107/

zbMATH Keywords

resource allocationalgorithmic game theorycake-cuttingenvy-free division

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Algorithmic game theory and complexity (91A68)

Abstract: We study the existence of allocations of indivisible goods that are envy-free up to one good (EF1), under the additional constraint that each bundle needs to be connected in an underlying item graph. If the graph is a path and the utility functions are monotonic over bundles, we show the existence of EF1 allocations for at most four agents, and the existence of EF2 allocations for any number of agents; our proofs involve discrete analogues of the Stromquist's moving-knife protocol and the Su--Simmons argument based on Sperner's lemma. For identical utilities, we provide a polynomial-time algorithm that computes an EF1 allocation for any number of agents. For the case of two agents, we characterize the class of graphs that guarantee the existence of EF1 allocations as those whose biconnected components are arranged in a path; this property can be checked in linear time.

Recommendations

• The price of connectivity in fair division
• Almost envy-freeness with general valuations
• On the number of almost envy-free allocations
• Almost envy-freeness with general valuations
• An algorithm for envy-free allocations in an economy with indivisible objects and money

Cites work

• scientific article; zbMATH DE number 3831632 (Why is no real title available?)
• scientific article; zbMATH DE number 3949734 (Why is no real title available?)
• scientific article; zbMATH DE number 3511203 (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 3315017 (Why is no real title available?)
• A constructive proof of a permutation-based generalization of Sperner's lemma
• A moving-knife solution to the four-person envy-free cake-division problem
• Algorithmic solutions for envy-free cake cutting
• Allocating contiguous blocks of indivisible chores fairly
• Almost envy-free allocations with connected bundles
• Approximation Algorithms for Computing Maximin Share Allocations
• Cake cutting algorithms
• Cake division with minimal cuts: envy-free procedures for three persons, four persons, and beyond
• Computing an st-numbering
• Envy-free cake division without assuming the players prefer nonempty pieces
• Fair enough: guaranteeing approximate maximin shares
• Graph theory
• How to Cut A Cake Fairly
• How to Cut a Cake Fairly
• Maximin share allocations on cycles
• Rental Harmony: Sperner's Lemma in Fair Division
• Some Combinatorial Lemmas in Topology
• The Approximation of Fixed Points of a Continuous Mapping

Cited in

(11)

• Two-person fair division of indivisible items when envy-freeness is impossible
• Fairly taking turns
• Envy-free allocations respecting social networks
• Approximate envy-freeness in graphical cake cutting
• Fair division with two-sided preferences
• Reachability of fair allocations via sequential exchanges
• Dividing a graphical cake
• The price of connectivity in fair division
• Fair division of graphs and of tangled cakes
• Mind the gap: cake cutting with separation
• Almost envy-free allocations with connected bundles

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: Almost envy-free allocations with connected bundles

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