Envy-free two-player m-cake and three-player two-cake divisions

Nicolas Lebert; Frédéric Meunier; Quentin Carbonneaux

doi:10.1016/j.orl.2013.07.010

Envy-free two-player m-cake and three-player two-cake divisions

Nicolas Lebert
, Frédéric Meunier
, Quentin Carbonneaux

Research output: Contribution to journal › Article › peer-review

Abstract

Cloutier, Nyman, and Su (2005) initiated the study of envy-free cake-cutting problems involving several cakes. They showed that when there are two players and two or three cakes it is possible to find envy-free cake-divisions requiring few cuts, under natural assumptions. We prove that such a result also exists when there are two players and any number of cakes and when there are three players and two cakes. The proof relies on the fractional matching number in m-partite hypergraphs.

Original language	English
Pages (from-to)	607-610
Number of pages	4
Journal	Operations Research Letters
Volume	41
Issue number	6
DOIs	https://doi.org/10.1016/j.orl.2013.07.010
Publication status	Published - 13 Sept 2013

Keywords

Envy-free
Fair division
Matching
Polytope
Sperner's lemma
m-partite hypergraph

Access to Document

10.1016/j.orl.2013.07.010

Cite this

@article{19200719dcef47429879ef8b00f39a98,

title = "Envy-free two-player m-cake and three-player two-cake divisions",

abstract = "Cloutier, Nyman, and Su (2005) initiated the study of envy-free cake-cutting problems involving several cakes. They showed that when there are two players and two or three cakes it is possible to find envy-free cake-divisions requiring few cuts, under natural assumptions. We prove that such a result also exists when there are two players and any number of cakes and when there are three players and two cakes. The proof relies on the fractional matching number in m-partite hypergraphs.",

keywords = "Envy-free, Fair division, Matching, Polytope, Sperner's lemma, m-partite hypergraph",

author = "Nicolas Lebert and Fr{\'e}d{\'e}ric Meunier and Quentin Carbonneaux",

year = "2013",

month = sep,

day = "13",

doi = "10.1016/j.orl.2013.07.010",

language = "English",

volume = "41",

pages = "607--610",

journal = "Operations Research Letters",

issn = "0167-6377",

number = "6",

}

TY - JOUR

T1 - Envy-free two-player m-cake and three-player two-cake divisions

AU - Lebert, Nicolas

AU - Meunier, Frédéric

AU - Carbonneaux, Quentin

PY - 2013/9/13

Y1 - 2013/9/13

N2 - Cloutier, Nyman, and Su (2005) initiated the study of envy-free cake-cutting problems involving several cakes. They showed that when there are two players and two or three cakes it is possible to find envy-free cake-divisions requiring few cuts, under natural assumptions. We prove that such a result also exists when there are two players and any number of cakes and when there are three players and two cakes. The proof relies on the fractional matching number in m-partite hypergraphs.

AB - Cloutier, Nyman, and Su (2005) initiated the study of envy-free cake-cutting problems involving several cakes. They showed that when there are two players and two or three cakes it is possible to find envy-free cake-divisions requiring few cuts, under natural assumptions. We prove that such a result also exists when there are two players and any number of cakes and when there are three players and two cakes. The proof relies on the fractional matching number in m-partite hypergraphs.

KW - Envy-free

KW - Fair division

KW - Matching

KW - Polytope

KW - Sperner's lemma

KW - m-partite hypergraph

UR - https://www.scopus.com/pages/publications/84883618053

U2 - 10.1016/j.orl.2013.07.010

DO - 10.1016/j.orl.2013.07.010

M3 - Article

AN - SCOPUS:84883618053

SN - 0167-6377

VL - 41

SP - 607

EP - 610

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -

Envy-free two-player m-cake and three-player two-cake divisions

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this