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)- 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
- Fair Partitions
- On a method of obtaining an approximate solution of an exact fair division problem
- A sparse colorful polytopal KKM theorem
- 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)
