Networked Fairness in Cake Cutting Xiaohui Bei Youming Qiao Shengyu Zhang
Networked Fairness in Cake Cutting Xiaohui Bei Youming Qiao Shengyu Zhang
Economics In a nutshell,economics studies how resources are managed and allocated. One of the most fundamental targets is to achieve certain fairness in the allocation of resources
Economics • In a nutshell, economics studies how resources are managed and allocated. • One of the most fundamental targets is to achieve certain fairness in the allocation of resources
Cake cutting ·Problem setting: One cake,n people (who want to split it). Each person might value different portions of the cake differently. Some like strawberries,some like chocolate,.. Normalization:Each one values the whole cake as 1. This valuation info is private. Goal:divide the cake to make all people happy
Cake cutting • Problem setting: • One cake, 𝑛 people (who want to split it). • Each person might value different portions of the cake differently. • Some like strawberries, some like chocolate, … • Normalization: Each one values the whole cake as 1. • This valuation info is private. • Goal: divide the cake to make all people happy
Cake cutting A cake cutting protocol is proportionally fair (or proportional for short)if each person gets =1/n fraction by her measure. No matter how other people behave. A cake cutting protocol is envy-free if each person thinks that she gets the most by her measure. 。Eny-free→proportional: aij:how much person j gets in person i's measure. ·Envy-free:ai≥ai,j→ proportional:aii >1/n,Vi
Cake cutting • A cake cutting protocol is proportionally fair (or proportional for short) if each person gets ≥ 1/𝑛 fraction by her measure. • No matter how other people behave. • A cake cutting protocol is envy-free if each person thinks that she gets the most by her measure. • Envy-free ⇒ proportional: • 𝑎𝑖𝑗 : how much person 𝑗 gets in person 𝑖’s measure. • Envy-free: 𝑎𝑖𝑖 ≥ 𝑎𝑖𝑗 , ∀𝑗 ⇒ proportional: 𝑎𝑖𝑖 ≥ 1/𝑛, ∀𝑖
Envy-free when n 2 1.Alice cuts the cake into two equal pieces ·by her measure 2.Bob chooses a larger piece ·by his measure 常 3.Alice takes the other piece 5
5 Envy -free when 𝑛 = 2 1. Alice cuts the cake into two equal pieces • by her measure 2. Bob chooses a larger piece • by his measure 3. Alice takes the other piece