Cake cutting: explicit examples for impossibility results

DOI10.1016/J.MATHSOCSCI.2019.09.005MaRDI QIDQ2334852zbMATH OpenOpenAlexFDO

Authors Guillaume Chèze

Publication date 8 November 2019

Published in Mathematical Social Sciences (Search for Journal in Brave)

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

zbMATH Keywords

Galois theoryfair divisionmodel of computation

Mathematics Subject Classification ID

Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Algebraic number theory: global fields (11R99)

Abstract: In this article we suggest a model of computation for the cake cutting problem. In this model the mediator can ask the same queries as in the Robertson-Webb model but he or she can only perform algebraic operations as in the Blum-Shub-Smale model. All existing algorithms described in the Robertson-Webb model can be described in this new model.We show that in this model there exist explicit couples of measures for which no algorithm outputs an equitable fair division with connected parts.We also show that there exist explicit set of measures for which no algorithm in this model outputs a fair division which maximizes the utilitarian social welfare function.The main tool of our approach is Galois theory.

Recommendations

• Algorithms for cake cutting with equal and unequal shares
• scientific article; zbMATH DE number 1234106
• Algorithmic solutions for envy-free cake cutting
• Fair multi-cake cutting
• On the complexity of cake cutting

Cites work

• scientific article; zbMATH DE number 5017566 (Why is no real title available?)
• scientific article; zbMATH DE number 1234106 (Why is no real title available?)
• scientific article; zbMATH DE number 1015852 (Why is no real title available?)
• scientific article; zbMATH DE number 2153479 (Why is no real title available?)
• scientific article; zbMATH DE number 1409181 (Why is no real title available?)
• A discrete and bounded envy-free cake cutting protocol for four agents
• A note on cake cutting
• An Envy-Free Cake Division Protocol
• Cake cutting algorithms
• Cake cutting really is not a piece of cake
• Children crying at birthday parties. Why?
• Envy-free cake divisions cannot be found by finite protocols
• Existence of a simple and equitable fair division: a short proof
• Galois' theory of algebraic equations
• How to Cut A Cake Fairly
• No Agent Left Behind: Dynamic Fair Division of Multiple Resources
• On Envy-Free Cake Division
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the complexity of cake cutting
• On the computability of equitable divisions
• On the existence of equitable cake divisions
• On the irreducibility of certain trinomials
• Resource-monotonicity and population-monotonicity in connected cake-cutting
• The Galois groups of the polynomials \(X^ n+aX\ell +b\)
• Truth, justice, and cake cutting
• \(N\)-person cake-cutting: there may be no perfect division

Cited in

(1)

• Three persons, two cuts: a new cake-cutting algorithm

This page was built for publication: Cake cutting: explicit examples for impossibility results

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