-
@ThothChildren
- 2018.10.20
- PV 231
二人でケーキを公平に分けたい
ー 概要 ー
二人でケーキを公平に分けるときに恨みっこなしの公平なケーキ分割になる方法についてまとめます.これは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解説記事へのリンクも貼っておきます. | 外部リンク Envy Free Cake Cutting(Wikipedia 英) |
また、ナイフの動かし方の問題もこちらにリンクしておきます. | 外部リンク Moving Knife Procedure(Wikipedia 英) |
この章を学んで新たに学べる
Comments
Reasons
知識: Divide and Choice
Divide and Choiceは、真に公平になることを保証しないが、単純に恨むことがない分割をすることができる手法.ケーキの場合、Aが切り、Bが好きな方を選び、残った方をAが受け取る段取り.
知識: Austin moving-knifeの手順
Austin moving-knifeの手順は、二人ないし複数人でリソースを厳密に公平に分ける分割手法です.二人で分ける時には恨みっこなし(envy-free)の半分の成果物がそれぞれ得られます.