How to cut a cake with a gram matrix
| Autor: | Luca Amodei, Guillaume Chèze |
|---|---|
| Přispěvatelé: | Institut de Mathématiques de Toulouse UMR5219 (IMT), Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS) |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Inequality Existential quantification Open problem media_common.quotation_subject 010103 numerical & computational mathematics 01 natural sciences Fair division Computer Science - Computer Science and Game Theory Discrete Mathematics and Combinatorics Computer Science - Multiagent Systems 0101 mathematics Mathematics media_common Gramian matrix Discrete mathematics Cake cutting algorithm Numerical Analysis Algebra and Number Theory 010102 general mathematics 16. Peace & justice [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] Linear algebra Piecewise Geometry and Topology Construct (philosophy) Computer Science and Game Theory (cs.GT) Multiagent Systems (cs.MA) |
| Zdroj: | Linear Algebra and its Applications Linear Algebra and its Applications, Elsevier, 2019, 560 Linear Algebra and its Applications, 2019, 560 |
| ISSN: | 0024-3795 |
| DOI: | 10.48550/arxiv.1707.02871 |
| Popis: | In this article we study a problem of fair division. In particular we study a notion introduced by J. Barbanel that generalizes super envy-free fair division. We call this notion hyper envy-free. We give a new proof for the existence of such fair divisions. Our approach relies on classical linear algebra tools and 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 inequality constraints? Furthermore, when all the measures are given with piecewise constant density functions then we show how to construct effectively such a fair division. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect