- @ThothChildren
- 2018.10.20
- PV 389
Austin moving-knifeの手順
ー 概要 ー
Austin moving-knifeの手順は、二人ないし複数人でリソースを厳密に公平に分ける分割手法です.二人で分ける時には恨みっこなし(envy-free)の半分の成果物がそれぞれ得られます.
この章を学ぶ前に必要な知識
条件
- 二人かそれ以上の人間
効果
- 二人の場合はenvy-freeで公平分割
- 複数人の場合はenvy-freeでも公平分割でもありません
ポイント
- Divide and Choiceでは公平性が保証されていなかったが、Austinでは二人のとき保証
解 説
Austin moving-knifeの手順は、二人ないし複数人でケーキを厳密に公平に分ける分割手法です.
二人で分ける時には恨みっこなし(envy-free)の半分の成果物がそれぞれ得られます.そのためこの手法では公平になります.
以下ではケーキを分割するものとして話を進めます. | Austin moving-knifeの手順について |
Divide and Choiceもenvy-freeでしたが、公平性は保証されていませんでした. | Divide and Choice |
Austin moving-knifeの手順
Aが切る役, Bが"Stop"と言う役とします.
ナイフを二つ使います.
1. まずAが二本のナイフのうち左側をケーキの左端に、もう片方をAがケーキの真ん中と思うところに構えます.
2. Aが半分だと思っている距離を二つのナイフの間で保ちながら右に動きます.
3. 2.でAが右に写っているときにBがケーキの真ん中と思うところで"Stop"と言います.
4. "Stop"のところでケーキを切ります.
5. 二人でコイントス等で半分になったケーキのどちらを選択するか決めます.
以下に図解を示します.
| Austin moving-knifeの手順の詳細 |
Austin moving-knifeの図解 | |
Austin moving-knifeの手順においては、
中間値の定理によってその公平性が保証されます.
はじめにAが半分より小さい長さで構えていても、右端に到達したら左側のナイフは初めに右側のナイフがあったところに来なくてはなりません.
そのため初めの長さをx、全体をLとするとx, L-xが切ろうとしていたケーキの右側と左側の長さになります.中間値の定理よりL/2は必ずこの間にあるはずなため、もしBが的確な判断をするなら、かならずstopと言います.
そのため、Aは半分だと思って動かしており、Bも半分だと思ったところできっているので、
これはどちらも公平と納得する形になります.exactに半分にしたと見做すことができます(実際に計測してどうなっているかはさておき) | Austin moving-knifeの手順の解説 |
この章を学んで新たに学べる
Comments
Reasons
知識: Divide and Choice
Divide and Choiceは、真に公平になることを保証しないが、単純に恨むことがない分割をすることができる手法.ケーキの場合、Aが切り、Bが好きな方を選び、残った方をAが受け取る段取り.