Fair division and generalizations of Sperner- and KKM-type results

DOI10.1137/17M1116210zbMATH Open1385.54013arXiv1701.04955WikidataQ130168570 ScholiaQ130168570MaRDI QIDQ4604649FDOQ4604649

Authors: Megumi Asada, Florian Frick, Vivek Pisharody, Maxwell Polevy, David Stoner, Ling Hei Tsang, Zoe Wellner 

Publication date: 5 March 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We treat problems of fair division, their various interconnections, and their relations to Sperner's lemma and the KKM theorem as well as their variants. We prove extensions of Alon's necklace splitting result in certain regimes and relate it to hyperplane mass partitions. We show the existence of fair cake division and rental harmony in the sense of Su even in the absence of full information. Furthermore, we extend Sperner's lemma and the KKM theorem to (colorful) quantitative versions for polytopes and pseudomanifolds. For simplicial polytopes our results turn out to be improvements over the earlier work of De Loera, Peterson, and Su on a polytopal version of Sperner's lemma. Moreover, our results extend the work of Musin on quantitative Sperner-type results for PL manifolds.

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

Recommendations

• Rental Harmony: Sperner's Lemma in Fair Division
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• Splitting necklaces, with constraints
• Splitting multidimensional necklaces
• Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

zbMATH Keywords

Sperner's lemmafair divisionKKM theoremcake cuttingnecklace splittingcombinatorial fixed point theorem

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Fixed-point and coincidence theorems (topological aspects) (54H25)

Cites Work

• A generalization of Caratheodory's theorem
• Rental Harmony: Sperner's Lemma in Fair Division
• A proof of the lower bound conjecture for convex polytopes
• Algorithmic construction of sets for k -restrictions
• Equipartition of mass distributions by hyperplanes
• Hyperplane mass partitions via relative equivariant obstruction theory
• Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
• Topology and combinatorics of partitions of masses by hyperplanes
• A polytopal generalization of Sperner's lemma
• Extensions of Sperner and Tucker's lemma for manifolds
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
• Lower-bound theorems for pseudomanifolds
• Non-partitionable point sets
• Rigidity and the lower bound theorem. I
• Splitting necklaces
• Complexity results on a paint shop problem.
• Splitting multidimensional necklaces
• Equilibrium in a discrete exchange economy with money
• Title not available (Why is that?)
• Simultane Vierteilung zweier Körper
• Bisection of Circle Colorings
• On the facial structure of convex polytopes
• KKM type theorems with boundary conditions
• The Borsuk-Ulam Theorem and Bisection of Necklaces
• A discrete and bounded envy-free cake cutting protocol for four agents
• Sperner labellings: A combinatorial approach
• A constructive proof of a permutation-based generalization of Sperner's lemma
• Discrete splittings of the necklace
• Measure partitions using hyperplanes with fixed directions
• Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
• Thieves can make sandwiches

Cited In (17)

• Splitting necklaces, with constraints
• Envy-free division in the presence of a dragon
• How to share a cake with a secret agent
• Different versions of the nerve theorem and colourful simplices
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• Thieves can make sandwiches
• Splitting loops and necklaces: variants of the square peg problem
• Generalized rental harmony
• Envy-free division of multi-layered cakes
• On a method of obtaining an approximate solution of an exact fair division problem
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• A survey of mass partitions
• Rental Harmony: Sperner's Lemma in Fair Division
• Logarithmic algorithms for fair division problems
• Fair distributions for more participants than allocations
• Achieving rental harmony with a secretive roommate
• Envy-free cake division without assuming the players prefer nonempty pieces

This page was built for publication: Fair division and generalizations of Sperner- and KKM-type results

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