Envy-free division in the presence of a dragon

DOI10.1007/S11784-022-00997-YzbMATH Open1504.91127arXiv2112.12969OpenAlexW4309673443MaRDI QIDQ2106889FDOQ2106889

Rade Živaljević, G. Panina

Publication date: 29 November 2022

Published in: Journal of Fixed Point Theory and Applications (Search for Journal in Brave)

Abstract: We prove several results addressing the envy-free division problem in the presence of an unpredictable (secretive) player, called the "dragon". There are two basic scenarios. 1. There are $r-1$ players and a dragon. Once the "cake" is divided into $r$ parts, the dragon makes his choice and grabs one of the pieces. After that the players want to divide the remaining pieces in an envy-free fashion. 2. There are $r+1$ players who divide the cake into $r$ pieces. A ferocious dragon comes and swallows one of the players. The players want to cut the cake in advance in such a way that no matter who is the unlucky player swallowed by the dragon, the remaining players can share the tiles in an envy-free manner. In both settings the players are allowed to choose degenerate pieces of the cake. Moreover, they construct in advance both a cut of the cake and a "decision tree", allowing them to minimize the uncertainty of what pieces can be given to each of the players.

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

Recommendations

• Envy-free division via configuration spaces
• Envy-free division of discrete cakes
• Envy-free division of discrete cakes
• Envy-free cake division without assuming the players prefer nonempty pieces
• Two-player envy-free multi-cake division

zbMATH Keywords

chessboard complexesKKM theoremenvy-free divisionconfiguration space/test map schemedragon marriage theorem

Mathematics Subject Classification ID

Applications of game theory (91A80) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Fixed points and coincidences in algebraic topology (55M20)

Cites Work

• Title not available (Why is that?)
• 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
• Permutohedra, Associahedra, and Beyond
• Chessboard Complexes and Matching Complexes
• Equilibrium in a discrete exchange economy with money
• The colored Tverberg's problem and complexes of injective functions
• On a topological generalization of the Tverberg theorem
• How to Cut a Cake Fairly
• Chessboard complexes indomitable
• Dividing a cake fairly
• Fair Division and Generalizations of Sperner- and KKM-type Results
• Multilabeled Versions of Sperner's and Fan's Lemmas and Applications
• Envy-free cake division without assuming the players prefer nonempty pieces
• Splitting Necklaces, with Constraints
• Envy-free division via configuration spaces

Cited In (2)

• Envy-Free Division of Land
• Envy-free division via configuration spaces

This page was built for publication: Envy-free division in the presence of a dragon

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