How to cut a cake with a Gram matrix

DOI10.1016/J.LAA.2018.09.028MaRDI QIDQ1625485zbMATH OpenOpenAlexWikidataFDO

Authors Guillaume Chèze, Luca Amodei

Publication date 29 November 2018

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

cake cutting algorithmfair divisionGram matrix

Mathematics Subject Classification ID

Theory of matrix inversion and generalized inverses (15A09) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: In this article we study the problem of fair division. In particular we study a notion introduced by J. Barbanel that generalizes super envy-free fair division. We give a new proof of his result. Our approach allows us to give an explicit bound for this kind of fair division. Furthermore, we also give a theoretical answer to an open problem posed by Barbanel in 1996. Roughly speaking, this question is: how can we decide if there exists a fair division satisfying some inequalities constraints? Furthermore, when all the measures are given with piecewise constant density functions then we show how to construct effectively such a fair division.

Recommendations

• Super envy-free cake division and independence of measures
• An algorithm for super envy-free cake division
• An Envy-Free Cake Division Protocol
• scientific article; zbMATH DE number 1409181
• Fair multi-cake cutting

Cites work

• An algorithm for super envy-free cake division
• Existence of a simple and equitable fair division: a short proof
• Fair division of a measurable space
• Generalized inverses. Theory and applications.
• Handbook of computational social choice
• How to Cut A Cake Fairly
• 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?)
• On the possibilities for partitioning a cake
• Relations among certain ranges of vector measures
• Resource-monotonicity and population-monotonicity in connected cake-cutting
• Solvability and Consistency for Linear Equations and Inequalities
• Super envy-free cake division and independence of measures

Cited in

(4)

• Super envy-free cake division and independence of measures
• An algorithm for super envy-free cake division
• Fairer than fair: sharp bounds for connected super-proportional cake cutting
• Envy-free cake cutting: a polynomial number of queries with high probability

This page was built for publication: How to cut a cake with a Gram matrix

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