孤独な仕切り

孤立分割法は、比例ケーキカットの手順です。誕生日ケーキなどの異種で分割可能なリソースと、ケーキのさまざまな部分に対する好みが異なるn人のパートナーが関係します。これにより、 n人の人々がケーキを分割し、各人が自分の主観的な評価に従って合計値の少なくとも 1/ nの価値を持つピースを受け取ることができます。

この手順は、ヒューゴ・シュタインハウスによってn = 3人を対象に開発された。^[1]その後、フロベニウス・ケーニッヒ定理を用いてハロルド・W・クーンによってn > 3に拡張された。 ^[2]n = 3、n = 4の場合の説明は^[3] ^:31–35^{に、一般的なケースは[4]}^:83–87に記載されている。

説明

便宜上、すべてのエージェントにとってケーキ全体の価値がn になるように評価を正規化します。目標は、各エージェントに少なくとも 1 の価値を持つピースを与えることです。

ステップ 1。任意に選ばれた 1 人のプレーヤー (分割者)が、ケーキを、彼/彼女の目から見てちょうど 1 の価値を持つ n個のピースに切ります。

ステップ 2.他のn − 1 人のパートナーはそれぞれ、結果として得られたn 個のピースを評価し、そのうちのどれが「許容可能」、つまり少なくとも 1 の価値があると考えるかを述べます。

ここで、ゲームはステップ 3 のプレイヤーの返答に従って進行します。最初にn = 3 の場合を示し、次に一般的な場合を示します。

シュタインハウスの訴訟手続きん= 3

2つのケースがあります。

ケース A: 分割しない人の少なくとも 1 人が、2 つ以上のピースを許容できるものとしてマークします。次に、3 番目のパートナーが許容できるピースを選択します (鳩の巣の原理により、少なくとも 1 つは持っている必要があります)。2 番目のパートナーが許容できるピースを選択します (以前に少なくとも 2 つ持っていたため、少なくとも 1 つは残ります)。最後に、分割する人が最後のピースを選択します (分割する人にとっては、すべてのピースが許容できます)。
ケース B: 他の 2 人のパートナーは、1 つのピースだけを許容できるものとしてマークします。すると、分割者だけが許容できるピースが少なくとも 1 つあります。分割者はこのピースを受け取って帰ります。このピースは残りの 2 人のパートナーにとって 1 未満の価値しかないため、残りの 2 つのピースは少なくとも 2 の価値があります。分割と選択を使用して、2 人でそれを分割します。

手続きはん

一般的なケースを説明する方法はいくつかあるが、より短い説明は^{[5]に示されており、これは}羨望のないマッチングの概念に基づいている。これは、マッチングされていないエージェントがマッチングされたピースに隣接しないマッチングである。

ステップ 3 . Xの各頂点がエージェント、 Y の各頂点がピースであり、 x の値が y の少なくとも 1 である場合に限り、エージェントx とピース y の間にエッジが存在する二部グラフG = ( X + Y , E )を構築します。

ステップ 4 。 G内で最大基数のエンヴィーフリーマッチングを見つけます。仕切りはn個のピースすべてに隣接しているため、 | N _G ( X )| = n ≥ | X | となります (ここで、N _G ( X ) はY内のXの隣接ピースの集合です)。したがって、空でないエンヴィーフリーマッチングが存在します。

ステップ 5 . マッチした各ピースを、マッチしたエージェントに渡します。マッチした各エージェントの価値は少なくとも 1 であるため、満足して帰宅することに注意してください。

ステップ 6。残りのケーキを残りのエージェント間で再帰的に分割します。残りの各エージェントは、配られた各ケーキの価値を 1 未満と評価するため、残りのケーキの価値はエージェントの数よりも大きくなり、再帰の前提条件が満たされます。

クエリの複雑さ

各反復で、アルゴリズムは、孤立したディバイダに最大n 回の マーククエリを要求し、他の各エージェントに最大n 回の evalクエリを要求します。反復は最大n回です。したがって、 Robertson-Webb クエリモデルでのクエリの合計数は、エージェントあたりO( n ² )、全体では O( n ^{3 ) です。これは}、最後のディミニシャ(エージェントあたり O( n )) やEven-Paz (エージェントあたり O(log n )) に必要な数よりもはるかに多くなっています。

参照

同じ問題を解く他の手順については、比例ケーキカットを参照してください。
孤立分割器の利点の 1 つは、対称的で公平なケーキカット手順を実現するように変更できることです。
公平な分割： Cut-the-Knotでの単独分割法。

参考文献

^ シュタインハウス、ヒューゴ（1948年） 。「公平な分割の問題」。エコノメトリカ。16 （1）：101-4。JSTOR 1914289。
^ クーン、ハロルド（1967年）「公正な分割のゲームについて」、オスカー・モルゲンシュテルンを称えて数理経済学論文集、プリンストン大学出版、pp. 29–37、2019年1月16日時点のオリジナルよりアーカイブ、 2019年1月15日取得
^ Brams, Steven J.; Taylor, Alan D. (1996).公正な分割：ケーキカットから紛争解決まで。ケンブリッジ大学出版局。ISBN 0-521-55644-9。
^ ロバートソン、ジャック、ウェッブ、ウィリアム (1998)。ケーキカットアルゴリズム：できる限り公平に。マサチューセッツ州ネイティック：AKピーターズ。ISBN 978-1-56881-076-8LCCN 97041258. OL 2730675W .
^ Segal-Halevi, Erel; Aigner-Horev, Elad (2022). 「二部グラフにおける羨望のないマッチングと公平な分割への応用」.情報科学. 587 : 164–187. arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID 170079201.

[steinhaus48-1] シュタインハウス、ヒューゴ（1948年） 。「公平な分割の問題」。エコノメトリカ。16 （1）：101-4。JSTOR 1914289。

[2] クーン、ハロルド（1967年）「公正な分割のゲームについて」、オスカー・モルゲンシュテルンを称えて数理経済学論文集、プリンストン大学出版、pp. 29–37、2019年1月16日時点のオリジナルよりアーカイブ、 2019年1月15日取得

[bt96-3] Brams, Steven J.; Taylor, Alan D. (1996).公正な分割：ケーキカットから紛争解決まで。ケンブリッジ大学出版局。ISBN 0-521-55644-9。

[4] ロバートソン、ジャック、ウェッブ、ウィリアム (1998)。ケーキカットアルゴリズム：できる限り公平に。マサチューセッツ州ネイティック：AKピーターズ。ISBN 978-1-56881-076-8LCCN 97041258. OL 2730675W .

[5] Segal-Halevi, Erel; Aigner-Horev, Elad (2022). 「二部グラフにおける羨望のないマッチングと公平な分割への応用」.情報科学. 587 : 164–187. arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID 170079201.