Fair Cake-Cutting Methods for Envy-Free Allocations
undefined
"
וּ
נְ
חַ
לְ
תֶּ
ם
א
וֹ
תָ
הּ
אִ
י
שׁ
כְּ
אָ
חִ
י
ו
"
(
י
ח
ז
ק
א
ל
מ
ז
1
4
)
ENVY-FREE CAKE-CUTTING
IN BOUNDED TIME
Erel Segal-Halevi
Advisors:
Yonatan Aumann
Avinatan Hassidim
n
a
g
e
n
t
s
w
i
t
h
d
i
f
f
e
r
e
n
t
t
a
s
t
e
s
What is Fair?
P
r
o
p
o
r
t
i
o
n
a
l
E
a
c
h
a
g
e
n
t
g
e
t
s
a
p
i
e
c
e
w
o
r
t
h
t
o
i
t
a
t
l
e
a
s
t
1
/
n
E
n
v
y
F
r
e
e
:
N
o
a
g
e
n
t
p
r
e
f
e
r
s
a
p
i
e
c
e
a
l
l
o
t
t
e
d
t
o
s
o
m
e
o
n
e
e
l
s
e
What is Fair?
2 agents:
Blue,
Green
G
B
•
Green
: divide to two
subjectively-equal parts.
•
Blue
: pick more
valuable part.
Proportional
Envy free
2 agents:
Blue,
Green
G
B
•
Each agent divides to 2
subjective halves.
•
Cut between two lines.
•
Each agent receives
part with his line.
Proportional
Envy free
n
agents
S
h
i
m
o
n
E
v
e
n
a
n
d
A
z
a
r
i
a
P
a
z
,
1
9
8
4
B
R
G
P
Proportional
X
Envy-free!
"
קָ
שָׁ
ה
כִ
שְׁ
א
וֹ
ל
קִ
נְ
אָ
ה
"
(
ש
י
ר
ה
ש
י
ר
י
ם
ח
6
)
Fair Cake-Cutting: Connected pieces
Envy-Free Cake-Cutting
This work:
Waste Makes Haste
(Segal-Halevi et al, AAMAS 2015)
This work:
Waste Makes Haste
(Segal-Halevi et al, AAMAS 2015)
Envy-Free, Connected Pieces, 3 agents
R
R
e
e
d
d
B
B
l
l
u
u
e
e
G
G
r
r
e
e
e
e
n
n
Envy-Free Division and
Matching
General scheme for envy-free division:
Create the
agent-piece bipartite graph
:
Each agent points to its best piece/s.
Find a
perfect matching
in that graph:
Each agent receives a best piece.
Perfect matching = Envy-free division!
Perfect matching = Envy-free division!
R
R
e
e
d
d
G
G
r
r
e
e
e
e
n
n
Envy-Free Division and
Matching
Red: Equalize(3)
Red: Equalize(3)
action
action
creates bipartite graph:
creates bipartite graph:
Each agent points to its best pieces.
Each agent points to its best pieces.
Perfect matching = Envy-free division!
Perfect matching = Envy-free division!
B
B
l
l
u
u
e
e
Blue: Equalize(2)
Blue: Equalize(2)
action
action
transforms best-piece graph.
transforms best-piece graph.
Perfect matching = Envy-free division!
Perfect matching = Envy-free division!
R
R
e
e
d
d
G
G
r
r
e
e
e
e
n
n
Envy-Free, Connected Pieces, 3 agents
B
B
l
l
u
u
e
e
R
R
e
e
d
d
G
G
r
r
e
e
e
e
n
n
B
B
r
r
o
o
w
w
n
n
B
B
l
l
u
u
e
e
R
R
e
e
d
d
B
B
l
l
u
u
e
e
G
G
r
r
e
e
e
e
n
n
B
B
r
r
o
o
w
w
n
n
R
R
e
e
d
d
G
G
r
r
e
e
e
e
n
n
B
B
l
l
u
u
e
e
B
B
r
r
o
o
w
w
n
n
R
R
e
e
d
d
G
G
r
r
e
e
e
e
n
n
B
B
l
l
u
u
e
e
B
B
r
r
o
o
w
w
n
n
Can We Do Better?
One of:
Red: Equalize(3).
Red: Equalize(3);
Green:Equalize(2) .
Red: Equalize(3);
Blue:Equalize(2) .
Green: Equalize(3) .
Green: Equalize(3);
Red:Equalize(2) .
Green: Equalize(3);
Blue:Equalize(2) .
Blue: Equalize(3) .
Blue: Equalize(3);
Red:Equalize(2) .
Blue: Equalize(3);
Green:Equalize(2) .
R
R
B
B
G
G
G
G
G
G
G
R
R
R
R
R
B
B
B
B
B
Green: Equalize(3);
Red:Equalize(2) .
R
R
B
B
G
G
R
R
B
B
G
G
R
R
e
e
d
d
B
B
l
l
u
u
e
e
G
G
r
r
e
e
e
e
n
n
R
R
e
e
d
d
B
B
l
l
u
u
e
e
G
G
r
r
e
e
e
e
n
n
Envy-Free Cake-Cutting with Waste
Envy-Free and Proportional?
With Waste: Envy-Free Proportional.
Can we find in bounded time a division:
Envy-Free
Proportional (
Value
≥
1/
n
)
:
Connected pieces
?
For
n=3:
Yes!
For
n
≥ 4:
Open question.
"
וּ
נְ
חַ
לְ
תֶּ
ם
א
וֹ
תָ
הּ
אִ
י
שׁ
כְּ
אָ
חִ
י
ו
"
(
י
ח
ז
ק
א
ל
מ
ז
1
4
)
ENVY-FREE CAKE-CUTTING
IN BOUNDED TIME
Collaborations welcome!
e
r
e
l
s
g
l
@
g
m
a
i
l
.
c
o
m
Various fair cake-cutting methods for allocating divisible goods among multiple agents are explored in this content. These methods ensure that each agent receives a share proportionate to their preferences, without feeling envious of others' allocations. Techniques such as connected pieces, bounded-time divisions, and maintaining proportional values are discussed. The goal is to achieve fairness while considering different agent preferences and ensuring efficient division processes.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
" " ) 14 ( ENVY-FREE CAKE-CUTTING IN BOUNDED TIME Erel Segal-Halevi Advisors: Yonatan Aumann Avinatan Hassidim
n agents with different tastes I want lots of trees I love the western areas I want to be far from roads!
What is Fair? Proportional Each agent gets a piece worth to it at least 1/n Envy Free: No agent prefers a piece allotted to someone else
What is Fair? Each agent i has a value density: ??? Value = integral: ??? = ???? ?? Proportional: For all ? : ???? 1 Envy Free: For all ?,? : ???? ???? ????
2 agents: Blue, Green Green: divide to two subjectively-equal parts. Blue: pick more valuable part. B G Proportional Envy free
n agents Shimon Even and Azaria Paz, 1984 Each agent divides to 2 subjective halves. Cut in median. Each n/2 players divide their half-cake recursively. ?(? log ?) queries. B G R P Proportional X Envy free!
" " 6 ) ( youtube.com/watch?v=WUquKkTmbww
Fair Cake-Cutting: Connected pieces Proportional Envy Free 2 agents 2 queries ?(?log?) queries ?( ) queries! 3 agents (Even&Paz 1984) (Woeginger&Sgall 2007) (Su, 1999) (Stromquist, 2008)
Envy-Free Cake-Cutting Pieces: Disconnected Connected 2 agents 2 queries 3 agents 6 queries (1963) ?( ) queries! 4 agents 200 queries (2015) ?????? (2008) queries (2016) ? agents Lower bound: ?2
This work: Waste Makes Haste (Segal-Halevi et al, AAMAS 2015)
This work: Waste Makes Haste (Segal-Halevi et al, AAMAS 2015) We want: Positive value per agent function of ?: f(n)>0 Ideally: f(n)=1/n Envy-free Connected pieces Bounded-time
Envy-Free, Connected Pieces, 3 agents Green Red Blue 1. Red: Equalize(3) 2. Blue: Equalize(2) 3. Green chooses, then Blue, then Red Envy-free Each gets at least
Envy-Free Division and Matching General scheme for envy-free division: Create the agent-piece bipartite graph: Each agent points to its best piece/s. Find a perfect matching in that graph: Each agent receives a best piece. Perfect matching = Envy-free division!
Envy-Free Division and Matching Red Green Blue Red: Equalize(3) action creates bipartite graph: Each agent points to its best pieces. Perfect matching = Envy-free division!
Envy-Free, Connected Pieces, 3 agents Red Green Blue Blue: Equalize(2) action transforms best-piece graph. Perfect matching = Envy-free division!
Envy-Free, Connected Pieces, ? agents Red Blue Green Brown Equalize (?) an agent trims some pieces to get ? equal best pieces. Algorithm: For ? = 1, ,? 1 Ask agent i to Equalize(2? ? 1+ 1) Red:Equalize(5); Blue: Equalize(3); Green:Equalize(2)
Envy-Free, Connected Pieces, ? agents Red Blue Green Brown Equalize (?) an agent trims some pieces to get ? equal best pieces. Algorithm: For ? = 1, ,? 1 Ask agent i to Equalize(2? ? 1+ 1) Red:Equalize(5); Blue: Equalize(3); Green:Equalize(2)
Envy-Free, Connected Pieces, ? agents Red Blue Green Brown Equalize (?) an agent trims some pieces to get ? equal best pieces. Algorithm: For ? = 1, ,? 1 Ask agent i to Equalize(2? ? 1+ 1) Red:Equalize(5); Blue: Equalize(3); Green:Equalize(2)
Envy-Free, Connected Pieces, ? agents Red Blue Green Brown Equalize (?) an agent trims some pieces to get ? equal best pieces. Algorithm: For ? = 1, ,? 1 Ask agent i to Equalize(2? ? 1+ 1) Red:Equalize(5); Blue: Equalize(3); Green:Equalize(2)
Can We Do Better? For ? = 3: Bounded procedure. Value 1 3for all players. Optimal.
Envy-Free and Proportional, 3 agents One of: Red: Equalize(3). Red: Equalize(3); Green:Equalize(2) . Red: Equalize(3); Blue:Equalize(2) . Green: Equalize(3) . Green: Equalize(3); Red:Equalize(2) . Green: Equalize(3); Blue:Equalize(2) . Blue: Equalize(3) . Blue: Equalize(3); Red:Equalize(2) . Blue: Equalize(3); Green:Equalize(2) .
Envy-Free and Proportional, 3 agents R B G G B R B G R R B G G R B R G B B G R
Envy-Free and Proportional, 3 agents R B G G B R Green: Equalize(3); Red:Equalize(2) .
Envy-Free and Proportional, 3 agents R B G G B R
Envy-Free Cake-Cutting with Waste Pieces: Disconnected Connected 2 agents Prop=1/2 3 agents Prop = 1/3 4 agents Prop = 1/4 Prop = 1/7 Prop = 1 ? ? ? agents Prop = 2 (? 1) 4?ln(1 ?) queries
Envy-Free and Proportional? With Waste: Envy-Free Proportional. Can we find in bounded time a division: Envy-Free Proportional (Value 1/n): Connected pieces? For n=3: Yes! For n 4: Open question.
" " ) 14 ( ENVY-FREE CAKE-CUTTING IN BOUNDED TIME Collaborations welcome! erelsgl@gmail.com
