Upgrade to Pro — share decks privately, control downloads, hide ads and more …

ケーキカット問題

ROKTA
March 13, 2017
140

 ケーキカット問題

3/13輪講会分

ROKTA

March 13, 2017
Tweet

Transcript

  1. Waste Makes Haste: Bounded Time Protocols for Envy-Free Cake Cutting

    with Free Disposal Erel Segal-Halevi Avinatan Hassidim Yonatan Aumann 参考⽂献 AAMAS '15 Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems Pages 901-908 参考⽂献 1 For 勉強会
  2. Outline ´ IntroductionWaste Makes Haste: Bounded Time Protocols for Envy-Free

    Cake Cutting with Free Disposal ´ Results ´ Model ´ Protocol ´ For n agents ´ For 3 agents ´ For 4 agents ´ 3 neighbors ´ 2 neighbors ´ 1 neighbor ´ Conclusion and Future Work 2
  3. Introduction ´ Fair cake-cutting (ケーキ分割問題) ´ 1つのケーキを価値観の違う何⼈かで公平に分け合う ´ fairness (公平性)

    ´Proportionality (⽐例性) ´ 全員が、「全体/⼈数」の利益をもらう ´Envy-free ´ 全員が、他の⼈の割り当てを羨まない (他の⼈と割り当てを交換しても得をしない) 3
  4. Introduction ´ Proportionality ´ Envy-free と⽐べて簡単に満たせる ´ 多項式時間で計算可能[1] ´ Envy-free

    ´ ⼈数分のみ切り分けるとき、3⼈でも計算不可能[2] [1] H. Steinhaus. The problem of fair division. Econometrica, 16(1), Jan. 1948. [2] F. E. Su. Rental Harmony: Sperner’s Lemma in Fair Division. The American Mathematical Monthly, 106(10):930+, Dec. 1999. 4
  5. Results ´ もしも free disposal (⾃由処分) が可能なら envy-free な割り当てが有限時間内に求められるか? ´

    もしも free disposal が可能なら 皆に少なくとも利益をもたらす envy-free な割り当てが有限時間内に求められるか 誰にも何も割り当てない 6
  6. Results ´ (全てにおいて Free disposal が許されるとき) 1つのケーキを 定理 1 ´

    ⼈数に⽐例する関数時間で envy-free に分けられる (最悪な場合、利益は1/2n-1 ,n : ⼈数) ´ 定理 2 ´ 3 ⼈で分けるとき、全員が少なくとも全体の1/3の利益を 得られるように有限時間で envy-free に分けられる ´ 定理 3 ´ 4 ⼈で分けるとき、3 ⼈が少なくとも全体の1/7の利益を 得られるように有限時間で envy-free に分けられる 7
  7. Model ´ ケーキ : [0,1]のインターバルで表現 ´ n ⼈でケーキを分ける ´ もらえるのは⼀⽚のみ

    ´ それぞれ異なった価値観 Vi (subjective value) を持つ ´ 割り当てはインターバル Pi (ex. [0,0.5]) で表す 8
  8. Protocol For n agents ´ A, B, Cさんでケーキを分ける時、 A さんが3等分する

    0 0.2 0.4 0.6 切⽚1 切⽚2 切⽚3 Bさん視点 0 0.2 0.4 切⽚1 切⽚2 切⽚3 Aさん視点 0 0.2 0.4 0.6 切⽚1 切⽚2 切⽚3 Cさん視点 10
  9. Protocol For n agents ´ B さんが1番いいと思うものを⼆番⽬の⼤きさまで切る 0 0.2 0.4

    0.6 切⽚1 切⽚2 切⽚3 Bさん視点 0 0.2 0.4 切⽚1 切⽚2 切⽚3 Aさん視点 0 0.2 0.4 0.6 切⽚1 切⽚2 切⽚3 Cさん視点 11
  10. Protocol For n agents ´ C,B,A の順番(逆順)で選んでいく 0 0.2 0.4

    0.6 切⽚1 切⽚2 切⽚3 Bさん視点 0 0.2 0.4 切⽚1 切⽚2 切⽚3 Aさん視点 0 0.2 0.4 0.6 切⽚1 切⽚2 切⽚3 Cさん視点 結果 : envy-free partition かつ proportionality ≥ # $ 12
  11. Protocol For n agents ´ 補題 : EFP ( Envy-Free

    Proportionality ) ´ ケーキが m ピースに分けられていて、その中から各々 (少なくとも他のピースと同じ、もしくは良い)1ピースを選ぶ時 割り当ては envy-free かつ proportionality は少なくとも 1/m ´ 3⼈の時は4ピースに分けることで 少なくとも1/4の利益を得られた ´ 4⼈以上の時は? 13
  12. Protocol For n agents ´ 先程の例を⼀般化すると、n⼈で分ける時 ´ For i =

    1 to n – 1: Ask agent i to Equalize(P(n - i)). ´ For i = n to 1: Ask agent i to select one of the pieces that he trimmed, if any of them is still not taken. Otherwise, he may select any piece. ´ Equalize(x) : 他より価値の⾼い、同じピースを x ピース作る関数 ´ P(x) : ⾃分の後に x ⼈ 切るor選ぶ ⼈がいる時、確保するべき数 14
  13. Protocol For n agents ´ P(1) = 2 ´ P(2)

    = 3 ´ P(3) = ? ´ 次の⼈は P(2) (= 3) ピース確保するために 2 ピース切る ´ その次の⼈は P(1) (= 2) ピース確保するために 1 ピース切る ´ その次の⼈から選んでいく→1ピースとられる ´ P(3) = 5 15
  14. Protocol For n agents ´ P(k) = P(k - 1)

    + P(k - 1) -1 ´ P(k) = 2k – 1 + 1 ´ 結局ピース数は全部で 16
  15. Results ´ (全てにおいて Free disposal が許されるとき) 1つのケーキを 定理 1 ´

    ⼈数に⽐例する関数時間で envy-free に分けられる (最悪な場合、利益は1/2n-1 ,n : ⼈数) ´ 定理 2 ´ 3 ⼈で分けるとき、全員が少なくとも全体の1/3の利益を 得られるように有限時間で envy-free に分けられる ´ 定理 3 ´ 4 ⼈で分けるとき、3 ⼈が少なくとも全体の1/7の利益を 得られるように有限時間で envy-free に分けられる 17
  16. Protocol For 3 agents ´ 前提 ´ A, B, C

    さんの 3 ⼈に分け合ってもらう ´ あらかじめ 3 ⼈には各々平等だと思うような線引きをしてもらう ´ A1 < B1 < C1 (2,3の順序は 3! = 6 通り) ´ 全体のケーキの価値は3 ´ ⼀⼈最低1以上なら 定理2を満たす Aさん Cさん Bさん A1 A2 A3 B1 C1 B2 C2 B3 C3 18
  17. Protocol For 3 agents ´ はじめにAさんが切った時 ´ BさんとCさんが違うピースを⼀番だと⾔った時(ex. B→3, C→2),

    A1 A2 A3 A1 A2 A3 Bさん視点 Cさん視点 B,Cさんにそれぞれ⼀番のピースを、Aさんに残りを割り当てる 19
  18. Protocol For 3 agents ´ はじめにAさんが切った時 ´ BさんとCさんが同じピースを⼀番だと⾔った時(ex. B→3, C→3),

    かつ⼆番⽬に⼤きいピースの⼤きさが1以上の時 ´ B,CさんにEqualize(2)を頼む (A3 を削ってもらう) ´ より削らない⽅(仮にBとする)を採⽤し、A3 を Cに割り当てる A1 A2 A3 A1 A2 A3 Bさん視点 Cさん視点 20
  19. Protocol For 3 agents ´ はじめにAさんが切った時 ´ BさんとCさんが同じピースを⼀番だと⾔った時(ex. B→3, C→3),

    かつ⼆番⽬に⼤きいピースの⼤きさが1より⼩さい時 ´ このままだと少なくとも⼀⼈の割り当てが1より⼩さくなる ´ はじめに切る⼈を変える必要がある ´ 前提より⼀番⽬の分け⽅の⼤きさの順番はA1 < B1 < C1 ´ ⼆番⽬の順番によってはじめに切る⼈を決める A1 A2 A3 A1 A2 A3 Bさん視点 Cさん視点 21
  20. Protocol For 3 agents Case 1 : C2 <B2 <A2

    ´ Cがはじめに切る ´ A,BさんはC2 以外を選ぶ ´ A,BさんにとってC1 C3 は1 よりも⼤きい ´ A,BさんにEqualize(2)を頼んで解決 ´ Case 2 : C2 <A2 <B2 の場合も同様 A1 ⊆ B1 ⊆ C1 C2 ⊆ B2 ⊆ A2 A3 ⊆ B3 ⊆ C3 22
  21. Protocol For 3 agents Case 3 : A2 <B2 <C2

    ´ Bがはじめに切る ´ AさんはB1 もしくはB2 を選ぶ ´ CさんはB2 もしくはB3 を選ぶ (?) ´ B2 でかぶるかもしれない ´ A,Cさん共々2番⽬は1以上 A1 ⊆ B1 ⊆ C1 A2 ⊆ B2 ⊆ C2 C3 ⊆ B3 ⊆ A3 23
  22. Protocol For 3 agents Case 4 : B2 <A2 <C2

    ´ Bがはじめに切る ´ AさんはB1 もしくはB3 を選ぶ ´ CさんはB2 もしくはB3 を選ぶ (?) ´ B3 でかぶるかもしれない ´ Aは⼆番⽬が1以上だがCは⼆番⽬が1以下の可能性がある ´ A1 をAに ´ C3 をCに ´ B2 をBに ´ Case 5 : A2 <C2 <B2 はこのケースの対称版 A1 ⊆ B1 ⊆ C1 B2 ⊆ A2 ⊆ C2 C3 ⊆ A3 ⊆ B3 24
  23. Protocol For 3 agents Case 6 : B2 <C2 <A2

    ´ AさんにB1 とC3 のどちらをより好むか尋ねる ´ B1 の時 ´ Case 4 のように求める ´ B1 を A に、 C3 を C に、 B2 を Bに ´ C3 の時 ´ C3 を A に、 B1 を B に、 C2 を Cに A1 ⊆ B1 ⊆ C1 B2 ⊆ C2 ⊆ A2 A3 ⊆ C3 ⊆ B3 25
  24. Results ´ (全てにおいて Free disposal が許されるとき) 1つのケーキを 定理 1 ´

    ⼈数に⽐例する関数時間で envy-free に分けられる (最悪な場合、利益は1/2n-1 ,n : ⼈数) ´ 定理 2 ´ 3 ⼈で分けるとき、全員が少なくとも全体の1/3の利益を 得られるように有限時間で envy-free に分けられる ´ 定理 3 ´ 4 ⼈で分けるとき、3 ⼈が少なくとも全体の1/7の利益を 得られるように有限時間で envy-free に分けられる 26
  25. Protocol For 4 agents ´ 前提 : ´ B,Cは1つしかエッジを持たない ´

    新しく⼊ったピースは誰からも選ばれない 29
  26. Protocol For 4 agents 1 neighbor ´ Case 1 :

    B,C,Dの⼆番⽬が全て別の場合 ´ B,C,DにEqualize(2)を頼む 35
  27. Protocol For 4 agents 1 neighbor ´ Case 2 :

    B,C,Dの⼆番⽬が全て同じ場合 ´ B,C,DにEqualize(3)を頼む(この場合 D ) 36
  28. Protocol For 4 agents 1 neighbor ´ Case 3 :

    ⼆⼈の⼆番⽬が同じで、⼀⼈だけ別の場合(Dが別) ´ B,C,DにEqualize(3)を頼む ´ Dの場合、case 2 と同じ B,Cの場合は… 37
  29. Conclusion and Future Work ´ Free disposal によって、1⼈1ピースの envy-free な

    割り当てを有限時間で求めることができた ´ 3⼈の場合は free disposal なしで envy-free かつ proportionality allocation を実現した ´ ⼈数が4⼈以上の時のプロトコルが今後の課題である 38