Fair division and generalizations of Sperner- and KKM-type results
From MaRDI portal
Publication:4604649
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 927016 (Why is no real title available?)
- A constructive proof of a permutation-based generalization of Sperner's lemma
- A discrete and bounded envy-free cake cutting protocol for four agents
- A generalization of Caratheodory's theorem
- A polytopal generalization of Sperner's lemma
- A proof of the lower bound conjecture for convex polytopes
- Algorithmic construction of sets for k -restrictions
- Bisection of Circle Colorings
- Complexity results on a paint shop problem.
- Discrete splittings of the necklace
- Equilibrium in a discrete exchange economy with money
- Equipartition of mass distributions by hyperplanes
- Extensions of Sperner and Tucker's lemma for manifolds
- Hyperplane mass partitions via relative equivariant obstruction theory
- KKM type theorems with boundary conditions
- Lower-bound theorems for pseudomanifolds
- Measure partitions using hyperplanes with fixed directions
- Non-partitionable point sets
- On the facial structure of convex polytopes
- Rental Harmony: Sperner's Lemma in Fair Division
- Rigidity and the lower bound theorem. I
- Simultane Vierteilung zweier Körper
- Sperner labellings: A combinatorial approach
- Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
- Splitting multidimensional necklaces
- Splitting necklaces
- The Borsuk-Ulam Theorem and Bisection of Necklaces
- Thieves can make sandwiches
- Topology and combinatorics of partitions of masses by hyperplanes
- Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
- 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
Cited in
(19)- Different versions of the nerve theorem and colourful simplices
- Envy-free cake division without assuming the players prefer nonempty pieces
- Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
- On a method of obtaining an approximate solution of an exact fair division problem
- Fair Partitions
- Generalized rental harmony
- Achieving rental harmony with a secretive roommate
- A sparse colorful polytopal KKM theorem
- Envy-free division of multi-layered cakes
- Splitting necklaces, with constraints
- Fair distributions for more participants than allocations
- Rental Harmony: Sperner's Lemma in Fair Division
- Logarithmic algorithms for fair division problems
- Envy-free division in the presence of a dragon
- Splitting loops and necklaces: variants of the square peg problem
- Thieves can make sandwiches
- How to share a cake with a secret agent
- A survey of mass partitions
- The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
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)
