CMS57opmtr cine Week 6:Algorithms for fair allocation Instructor:Shengyu Zhang
Instructor: Shengyu Zhang 1
Resource allocation General goals: Maximize social welfare. o Fairness. o Stability. 2
Resource allocation ◼ General goals: ❑ Maximize social welfare. ❑ Fairness. ❑ Stability. 2
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. a This valuation info is private. Goal:divide the cake to make all people happy. 3
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. 3
Cake cutting A cake cutting protocol is fair if each person gets 1/n fraction by her measure. No matter how other people behave. a A cake cutting protocol is envy-free if each person thinks that she gets the most by her measure. aEny-free→fair: aij:how much person j gets in person i's measure. Eny-free:aii≥ai,Vj →fair:at≥1/n,i. 4
Cake cutting ◼ A cake cutting protocol is fair 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 ⇒ fair: ❑ 𝑎𝑖𝑗 : how much person 𝑗 gets in person 𝑖’s measure. ❑ Envy-free: 𝑎𝑖𝑖 ≥ 𝑎𝑖𝑗 , ∀𝑗 ⇒ fair: 𝑎𝑖𝑖 ≥ 1/𝑛, ∀𝑖. 4
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
𝑛 = 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