Loading article…
公平なケーキカット問題の次の変種は、1983年にテッド・ヒルによって導入されました。 [ 1 ]
n の国に隣接する領域Dが存在する。各国はDの異なる部分集合をそれぞれ異なる価値で評価している。各国はD を公平に分割したいと考えており、「公平」とは比例配分を意味する。さらに、各国に割り当てられる部分は、その国に隣接していなければならない。この地理的な制約が、この問題を古典的な公平なケーキカット問題と区別する。
形式的には、すべての国C i はDの互いに素な部分D iを受け取り、C iとDの間の境界の一部がC i ∪ D iの内部に含まれるようにする必要があります。
解決できない問題もある。
1983年、ヒルは、 D内の各点がすべての国に対して0の値を持ち、 Dの境界がすべての国に対して0の値を持つ場合、隣接制約を持つ比例分割が存在することを証明した。彼の証明は存在証明のみであり、アルゴリズムは記述されていない。[ 1 ]
4年後、アナトール・ベックは、そのような分割を実現するためのプロトコルを説明した。[ 2 ]本質的に、このプロトコルはラストディミニッシャープロトコルの発展形である。各国がDの一部に入札できるようにし、最も低い入札額を入札者に与え、残りを残りのn - 1カ国に分配する。隣接制約が満たされることを保証するために、いくつかの変更が必要となる。
Dが単連結である場合、以下のアルゴリズムが使用されます。
1. D を単位円盤に写像するリーマン写像hを見つけ、すべての国について、原点を中心とするすべての円の値が 0 であり、原点からのすべての半径の値が 0 であるようにします (このようなhの存在は計数論法によって証明されます)。
2. 各国に、単位円盤地図h ( D ) 上に、原点を中心とし、値が 1/ nの円盤を描くように依頼します。これは、原点を中心とするすべての円の値が 0 であるという条件のおかげで可能です。
3.半径が最小の円盤D 1を見つけます。r 1。
2つのケースがあります。
4. D 1 が単一の国、例えばC iによってのみ引かれた場合、このディスクをC iに与えます。他の国にとってのその値は厳密に 1/ nより小さいので、 C iに割り当てられたディスクに接続する小さな追加ピースを与えることができます。
これを行うには、 D 1とC iとDの境界の画像を結ぶ扇形を描きます。C i以外の各国は、円盤と扇形の和集合をすべての国が最大で 1/ nと評価するように、この扇形を切り取ります。これは、原点からのすべての半径の値が 0 であるという条件のおかげで可能です。D 1と切り取られた扇形の和集合をC iに割り当てます。
残りの部分は単連結であり、残りのn − 1 の国に対して少なくとも ( n − 1)/ nの値を持つため、ステップ 1 で分割を再帰的に進めることができます。
D 1がk > 1 の国によって抽選された場合、ディスクと接続セクターを与えることができる国を見つけるために、より高度なオークションが必要になります。
5. 任意の勝者国を選び、宣言国C1とする。宣言国はD1と自国の現在の領土を結ぶセクターを追加し、他の国々はそのセクターを以下のように縮小する。
6. 勝利した各国が、トリミングされたセクターと半径rの円盤の合計値がちょうど 1/ nとなるような新しい半径r (最初の入札値よりも小さい値) を入札するとします。そのような円盤の中で最小のものをD 2 とします。ここでも 2 つのケースがあります。
C 1 がD 2を入札している国の 1 つである場合、D 2 (元のD 1よりわずかに小さい) と接続セクターをC 1 に与えます。C 1は値が 1/ nであることに同意し、他の国はそれが最大で 1/ nであることに同意し、ステップ 1 から再帰的に進めることができます。
そうでなければ、C 1 はD 2と接続セクターの合計値が1/ n未満であることに同意します。D 2 はD 1より小さいため、すべての非勝者もこれに同意しなければなりません。したがって、C 1とこれに同意する他のすべての国は勝者の集合から除外されます。
7. 残りの勝者の中から、新たな宣言者C 2を選出する。C 2 は、 D 2と現在の領土を結ぶ別のセクターを追加し、他の国々はステップ 5 と同様にそのセクターを縮小する。
ここで、D 2はC 1とC 2という 2 つの異なる領域に接続されていることに注意してください。これは、残りの領域が分断されるため問題です。これを解決するために、C 2 は別のセクターを取得することが許可されますが、今回は接続性を損なわないように長さが 1 未満になります。[ 2 ]その 3 番目のセクターは、ステップ 5 と同様にすべての国によって再びトリミングされます。その代わりに、C 2は、 D 2とC 1を接続するセクターの一部を放棄する必要があります。その価値は、受け取った 3 番目のセクターの価値と同じです。
C 2の候補割り当てには、D 2 、 D 2とC 2を接続する長さ 1 の単一のセクター、およびDの境界に達しない 2 つの短いセクターが含まれます。この構成のC 2に対する値は1/ nであり、非勝者に対する値は 1/ n未満であり、残りの勝者に対する値は最大で 1/ nです。
このプロセスは残りの勝者に対しても続けられ、最終的に勝者が1人だけになるまで続きます。
領域Dが有限のkでk連結である場合、分割はkに関する帰納法によって進めることができます。
k = 1の場合 、Dは単連結であり、前のセクションのプロトコルによって分割できます。
それ以外の場合（k > 1）、 D の外側境界をB 1で、内側境界をB 2、...、B kでマークします。
外側境界B 1と内側境界B kを結ぶ線Lを見つけ、すべての国がL の値を 0 と評価するようにします。これは、次の計数論法によって可能です。B 1とB kを結び、 Dに含まれる互いに素な線は、数えきれないほど無限に存在します。しかし、 Dの測度は有限なので、正の測度を持つ線の数は有限でなければなりません。
集合D \ Lは ( k − 1) 連結である。これを再帰的に分割し、隣接する任意の国にL を任意に割り当ててもよい。すべての国でLの値は 0 であるため、この操作は割り当ての公平性に影響を与えない。