Fair Cake-Cutting Methods for Envy-Free Allocations

Slide Note

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.

mat_ge Follow

Uploaded on Oct 04, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

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 and Proportional, 3 agents

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.