A Bounded and Envy-Free Cake Cutting Algorithm

被引：8

作者：

Aziz, Haris ^{[1
,2
]}

Mackenzie, Simon ^{[2
]}

机构：

[1] UNSW Sydney, Sydney, NSW, Australia

[2] CSIRO Data61, Sydney, NSW, Australia

来源：

COMMUNICATIONS OF THE ACM | 2020年 / 63卷 / 04期

关键词：

D O I：

10.1145/3382129

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the well-studied cake cutting problem in which the goal is to find an envy-free allocation of a divisible resource based on queries from agents. The problem has received attention in mathematics, economics, and computer science. It has been a major open problem whether there exists a discrete and bounded envy-free protocol. We report on our algorithm that resolved the open problem.

引用

页码：119 / 126

页数：8

共 9 条

[1] A Discrete and Bounded Envy-Free Cake Cutting Protocol for Four Agents [J].

Aziz, Haris ;

Mackenzie, Simon .

STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, :454-464

[2] A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents [J].

Aziz, Haris ;

Mackenzie, Simon .

2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, :416-427

[3]

Brams S. J., 1996, Fair Division: From Cake -Cutting to Dispute Resolution

[4] AN ENVY-FREE CAKE DIVISION PROTOCOL [J].

BRAMS, SJ ;

TAYLOR, AD .

AMERICAN MATHEMATICAL MONTHLY, 1995, 102 (01) :9-18

[5]

Dehghani S, 2018, SODA'18: PROCEEDINGS OF THE TWENTY-NINTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P2564

[6] Cake Cutting: Not Just Child's Play [J].

Procaccia, Ariel D. .

COMMUNICATIONS OF THE ACM, 2013, 56 (07) :78-87

[7]

Procaccia AD, 2009, 21ST INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-09), PROCEEDINGS, P239

[8]

Robertson J, 1998, CAKE CUTTING ALGORIT

[9]

Steinhaus H., 1948, Econometrica, V16

← 1 →