香港中文大学：《Topics in Theoretical Computer Science》课程教学资源（PPT课件讲稿）Lecture 6 Algorithms for resource allocation

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

备 6

6

envy-free Theorem.The outcome is envy-free (and thus fair). Proof. Alice:gets exactly half,no matter which piece Bob chooses. 口 Bob:gets at least half,no matter how Alice cuts the cake

envy-free ◼ Theorem. The outcome is envy-free (and thus fair). ◼ Proof. ❑ Alice: gets exactly half, no matter which piece Bob chooses. ❑ Bob: gets at least half, no matter how Alice cuts the cake. 7

n=3 Stage 0:Player 1 divides into three equal pieces 0 according to his valuation. Player 2 trims the largest piece s.t.the remaining is the same as the second largest. The trimmed part is called Cake 2;the other form Cake 1. 8

𝑛 = 3 ◼ Stage 0: Player 1 divides into three equal pieces ❑ according to his valuation. ◼ Player 2 trims the largest piece s.t. the remaining is the same as the second largest. ◼ The trimmed part is called Cake 2; the other form Cake 1. 8

Stage 1:division of Cake 1 Player 3 chooses the largest piece. If player 3 didn't choose the trimmed piece, player 2 chooses it. ■ Otherwise,player 2 chooses one of the two remaining pieces. Either player 2 or player 3 receives the trimmed piece;call that player T ▣ and the other player by T'. Player 1 chooses the remaining (untrimmed) piece 9

Stage 1: division of Cake 1 ◼ Player 3 chooses the largest piece. ◼ If player 3 didn’t choose the trimmed piece, player 2 chooses it. ◼ Otherwise, player 2 chooses one of the two remaining pieces. ◼ Either player 2 or player 3 receives the trimmed piece; call that player 𝑇 ❑ and the other player by 𝑇 ′ . ◼ Player 1 chooses the remaining (untrimmed) piece 9

Stage 2(division of Cake 2) T'divides Cake 2 into three equal pieces 0 according to his valuation. Players T,1,and T'choose the pieces of Cake 2,in that order. 10

Stage 2 (division of Cake 2) ◼ 𝑇 ′ divides Cake 2 into three equal pieces ❑ according to his valuation. ◼ Players 𝑇, 1, and 𝑇 ′ choose the pieces of Cake 2, in that order. 10