Cake cutting: explicit examples for impossibility results
From MaRDI portal
Publication:2334852
DOI10.1016/J.MATHSOCSCI.2019.09.005zbMATH Open1426.91144arXiv1907.04810OpenAlexW2975846008MaRDI QIDQ2334852FDOQ2334852
Authors: Guillaume Chèze 
Publication date: 8 November 2019
Published in: Mathematical Social Sciences (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1907.04810
Recommendations
Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Algebraic number theory: global fields (11R99)
Cites Work
- The Galois groups of the polynomials \(X^ n+aX\ell +b\)
- On the irreducibility of certain trinomials
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Galois' theory of algebraic equations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Truth, justice, and cake cutting
- How to Cut A Cake Fairly
- Title not available (Why is that?)
- Cake cutting algorithms
- An Envy-Free Cake Division Protocol
- On the complexity of cake cutting
- Title not available (Why is that?)
- \(N\)-person cake-cutting: there may be no perfect division
- On the existence of equitable cake divisions
- Envy-free cake divisions cannot be found by finite protocols
- A note on cake cutting
- No Agent Left Behind: Dynamic Fair Division of Multiple Resources
- Children crying at birthday parties. Why?
- A discrete and bounded envy-free cake cutting protocol for four agents
- On the computability of equitable divisions
- Resource-monotonicity and population-monotonicity in connected cake-cutting
- Existence of a simple and equitable fair division: a short proof
- On Envy-Free Cake Division
- Title not available (Why is that?)
- Cake cutting really is not a piece of cake
Cited In (1)
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)
