<<展開

二人でケーキを公平に分けたい

Facebookシェア Twitterツイート LINEで送る Googleシェア このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
Up
0
Down

要約

概要

二人でケーキを公平に分けるときに恨みっこなしの公平なケーキ分割になる方法についてまとめます.これはfair cake-cutting(envy-free cake-cutting)と言われる問題です.それぞれが少なくとも相手より少なくならないよう動きます.
ー 条件 ー
  • 相手よりも自分の取り分が少なくならないようにしたい
ー 効果 ー
  • 二人でケーキをenvy-freeに分けられる
  • 公平かは手法による
ーポイントー
  • 紹介する手法は両方ともenvy-free

解  説

二人でケーキを公平に分ける方法は、複数の方法が存在します. 今回は有名な二つの手法を紹介します. ・Divide and Choice envy-freeだけど公平性の保証なし ・Austin Moving-Knife Procedure envy-freeかつ公平
二人でケーキを公平に分けたい
Divide and Choiceは、二人で簡単にenvy-freeな分割を行える手法です. まず片方がケーキを半分と思う大きさに切ります. もう片方が半分になったケーキのうち好きな方をとり、 残った方をケーキをきった人がとります. これはenvy-freeですが、公平性は保証されません.
Divide and Choice
Austin Moving-Knife Procedureは、二人でenvy-freeかつ公平になるように選択することができます. 手順はリンク先を参照してください. 複数人の時は、envy-freeも公平にもなりません.
Austin moving-knifeの手順
Envy Free Cake CuttingのWikipedia解説記事へのリンクも貼っておきます.
また、ナイフの動かし方の問題もこちらにリンクしておきます.
この章を学んで新たに学べる
Comments

Reasons
>>隠す

知識: Divide and Choice
Divide and Choiceは、真に公平になることを保証しないが、単純に恨むことがない分割をすることができる手法.ケーキの場合、Aが切り、Bが好きな方を選び、残った方をAが受け取る段取り.
知識: Austin moving-knifeの手順
Austin moving-knifeの手順は、二人ないし複数人でリソースを厳密に公平に分ける分割手法です.二人で分ける時には恨みっこなし(envy-free)の半分の成果物がそれぞれ得られます.