Loading article…
シモンズ・スー・プロトコルは、羨望のない分割のためのいくつかのプロトコルです。これらは スペルナーの補題に基づいています。これらのプロトコルの利点は、パートナーの好みにほとんど制約を課さず、「どちらのピースがお好みですか？」といった簡単な質問のみをパートナーに尋ねる点にあります。
関連するいくつかの問題を解決するためのプロトコルが開発された。
羨望のないケーキ分割問題では、「ケーキ」（異質な分割可能な資源）を、ケーキの各部分に対する好みが異なるn人のパートナー間で分割する必要があります。ケーキは、次の条件を満たすn個のピースに分割する必要があります。(a) 各パートナーは、連結した単一のピースを受け取り、(b) 各パートナーは、自分のピースが他のすべてのピースよりも（弱く）優れていると信じます。この問題を解決するためのプロトコルは、1980 年にForest SimmonsがMichael Starbirdとの書簡の中で開発しました。これは、 1999 年にFrancis Suによって初めて公表されました。[ 1 ]
ケーキをn個のピースに分割した特定の分割セットが与えられたとき、パートナーが特定のピースを好むとは、そのピースが他のすべてのピースよりもわずかに優れていると信じていることを意味します。「わずかに」とは、パートナーがそのピースと他の1つまたは複数のピースの間で無関心である可能性があり、そのため（同点の場合）複数のピースを「好む」可能性があることを意味します。
本プロトコルは、パートナーの嗜好に関して以下の前提を置いている。
閉鎖条件は、正の望ましさを持つケーキの単一点の存在を排除する。
これらの前提条件は非常に緩やかです。公平なケーキカットのための他のプロトコルとは異なり、効用関数は加法的または単調である必要はありません。
このプロトコルでは、1 次元のカットセットを考慮します。たとえば、ケーキは 1 次元区間 [0,1] であり、各ピースは区間です。または、ケーキは長い辺に沿ってカットされた長方形であり、各ピースは長方形です。すべてのカットセットは、n個の数値x i、i = 1, ..., nで表すことができます。ここで、x iはi番目のピースの長さです。ケーキの全長は 1 であると仮定すると、x 1 + ... + x n = 1 となります。したがって、可能な分割の空間は、R n内のn個の頂点を持つ ( n − 1) 次元単体です。この単体に対して、プロトコルは次のように動作します。
生成されたラベル付けは、スペルナーの補題彩色要件を満たしています。
したがって、スペルナーの補題によれば、ラベルがすべて異なる部分単体が少なくとも1つ存在するはずです。ステップ2では、この部分単体の各頂点を異なるパートナーに割り当てました。その結果、異なるパートナーが異なるケーキを好む、非常に類似したn個のカットセットが見つかりました。
これで部分単体をより細かいサブサブ単体のメッシュに分割し、このプロセスを繰り返すことができます。すると、ますます小さくなる単体の列が得られ、それらは単一の点に収束します。この点は単一のカットセットに対応します。「選好セットは閉じている」という仮定により、このカットセットでは各パートナーが異なるピースを好みます。これは羨望のない分割です！
羨望のない分割の存在は以前に証明されているが、[ 2 ]シモンズの証明は構成的な近似アルゴリズムも提供する。たとえば、ある土地を分割する必要があり、パートナーがプラスマイナス 1 センチメートルの差は関係ないことに同意すると仮定する。すると、元の単体は、辺の長さが 1 cm 未満の単体に三角形分割できる。そして、部分単体内のすべてのラベルが異なる点は、（近似的な）羨望のない分割に対応する。
他の羨望のないプロトコルでは、各パートナーに多数のパンくずが割り当てられる場合があるのに対し、シモンズのプロトコルでは、各パートナーに連結された単一のピースが割り当てられます。さらに、元のケーキが長方形であれば、各ピースも長方形になります。
このアルゴリズムが発表されてから数年後、連結したピースを持つ羨望のない分割は有限プロトコルでは見つけられないことが証明されました。[ 3 ]したがって、有限時間で期待できる最良の方法は近似アルゴリズムです。現在、連結したピースを持つ羨望のないケーキカットのための近似アルゴリズムは、シモンズのアルゴリズムのみです。
シモンズのアルゴリズムは、実装されてオンラインで公開されている数少ない公平な分割アルゴリズムの1つです。 [ 4 ]
このアルゴリズムの良い点のひとつは、パートナーに尋ねる質問が非常にシンプルであることです。パートナーは、各分割において、どのピースを好むかを決めるだけでよいのです。これは、「1/3の価値を持つピースを切り取る」といった数値的な質問をする他のアルゴリズムとは対照的です。
上記のプロトコルを使用すれば、連結したピースを持つエンヴィーフリーの除算を任意の精度で近似できますが、近似には時間がかかる場合があります。特に：[ 5 ]
この問題では、n人のルームメイトが、家主が定めた家賃でnベッドルームの家を借りることにしました。各ルームメイトはそれぞれ異なる好みを持っている可能性があります。広い部屋を好む人もいれば、眺めの良い部屋を好む人もいるでしょう。次の 2 つの問題を同時に解決する必要があります。(a) 各パートナーに部屋を割り当てる、(b) 各パートナーが支払う家賃を決定し、支払額の合計が総家賃と等しくなるようにする。割り当ては羨望のないものでなければなりません。つまり、各パートナーは自分の部屋と家賃の区画を他の区画よりも弱く好みます。つまり、どのパートナーもその部屋に割り当てられた家賃で別の部屋を借りたいとは思わないということです。この問題を解決するためのプロトコルは、1999 年にFrancis Suによって開発されました。 [ 1 ]
アイデアは次のとおりです。総賃料を 1 に正規化します。すると、各価格設定スキームは、次元単体頂点Suのプロトコルは、ケーキカットのためのSimmons–Suプロトコルと同様の方法で、この単体の双対化バージョン上で動作します。つまり、特定の価格体系に対応する双対単体の三角形分割の各頂点について、所有パートナーに「その価格体系でどの部屋がお好みですか？」と尋ねます。これにより、双対単体のSperner彩色が得られ、その結果、部屋と賃料の近似的な羨望のない割り当てに対応する小さな部分単体が存在します。
[ 6 ]と[ 7 ]は、レンタルハーモニープロトコルの一般向け解説を提供している。 [ 8 ]と[ 9 ]は、オンライン実装を提供している。
この問題に対するその他の解決策については、「賃貸物件の調和」をご覧ください。
この問題では、 n人のパートナーで分担しなければならない作業があります。例えば、広いエリアの芝刈りなどです。
賃貸調和プロトコルは、家賃の支払いを家事とみなし、部屋を無視することで、嫉妬のない家事の割り当てをほぼ実現するために使用できます。家事の分割可能性は、家事に費やす時間を分割することで実現できます。[ 1 ]
この問題では、2 つ以上のケーキを 2 人以上のパートナーに同時に分け、各パートナーに各ケーキから 1 切れずつ与える必要があります。もちろん、選好が独立している場合 (つまり、割り当てによる効用が各ケーキの割り当てられた切れからの効用の合計である場合)、この問題は 1 つのケーキの分割方法で解決できます。各ケーキを個別に羨望のない分割を行うだけです。パートナーがケーキに対して連動した選好を持っている場合、つまり、あるパートナーが好むケーキの部分が、割り当てられた別のケーキの部分によって影響を受ける場合、この問題は興味深いものになります。たとえば、「ケーキ」が 2 日間連続の勤務シフトの時間である場合、典型的な従業員は、異なるシフトよりも毎日同じシフト (たとえば、午前 - 午前または午後 - 午後) を好むかもしれません。
パートナーが 2 人、ケーキが 2 個または 3 個の場合のこの問題の解決策は 2009 年に発表されました。[ 10 ] ケーキの数がm 個で、各ケーキがk 個のピースに分割されている場合、分割空間はn頂点d次元多面体で表すことができます。ここで、 d = m ( k − 1)、n = k mです。多面体への Sperner の補題の一般化[ 11 ]は、この多面体が適切な方法で三角形分割されラベル付けされている場合、完全なラベル付けを持つ少なくともn − d個の部分単体が存在することを保証します。これらの単体はそれぞれ、各パートナーが異なるピースの組み合わせを受け取る (近似的な) 羨望のない割り当てに対応します。ただし、組み合わせは重複する可能性があります。あるパートナーは「午前」と「午後」のシフトを受け取り、別のパートナーは「午後」と「午後」を受け取る可能性があります。これらは異なる選択ですが、互換性がありません。[ 10 ]のセクション4では、m = k = 2の場合、互いに分離したピースを持つ2人のパートナーへの羨望のない分割は不可能かもしれないが、 m = 2かつk = 3の場合（つまり、少なくとも1つのケーキが3つのピースに分割され、各パートナーが各ケーキから1つのピースを受け取り、少なくとも1つのピースが捨てられる）は常に可能であることが証明されている。3つのケーキについても同様の結果が証明されている。
