Almost envy-free allocations with connected bundles

DOI10.1016/J.GEB.2021.11.006zbMATH Open1483.91102arXiv1808.09406OpenAlexW3216166910MaRDI QIDQ2078044FDOQ2078044

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)

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.

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

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

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)

Cites Work

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

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

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)