雑用分担

家事の分担は公平な分担問題であり、分担されたリソースは望ましくないため、各参加者はできるだけ少ないリソースしか得ようとしません。これは公平なケーキカット問題と対称的な問題で、公平なケーキカット問題では、分担されたリソースは望ましいため、各参加者はできるだけ多くのリソースを得ようとします。どちらの問題もリソースが不均一であり、リソースが均一ではありません。ケーキの分担では、ケーキには端、角、中央のピースがあり、アイシングの量は異なります。一方、家事の分担では、家事の種類が異なり、各家事を完了するのに必要な時間も異なります。同様に、どちらの問題もリソースが分割可能であることを前提としています。家事は無限に分割可能です。なぜなら、家事の有限集合は家事または時間で分割できるからです。たとえば、洗濯物は衣類の数や洗濯機にセットするのにかかる時間で分割できます。ただし、問題はリソースの望ましさが異なります。家事分担問題は1978年にマーティン・ガードナーによって提唱されました。 ^[1]

家事の分担は、より一般的な問題である「財の公平な分担」（経済的な悪は経済的な善の反対）とは対照的に、悪いものの公平な分担と呼ばれることがよくあります。別名は、汚い仕事の問題です。同じリソースが、状況に応じて良いことも悪いこともあります。たとえば、分割するリソースが家の裏庭であるとします。相続財産を分割する状況では、この庭は良いものと見なされます。なぜなら、各相続人はできるだけ多くの土地を持ちたいと考えるため、これはケーキカットの問題です。しかし、芝刈りなどの家事を分担する状況では、この庭は悪いものと見なされます。なぜなら、各子供はおそらく芝刈りする土地をできるだけ少なくしたいと考えるため、これは家事カットの問題です。

公平なケーキカットの結果の一部は、家事カットのシナリオに簡単に変換できます。たとえば、分割と選択の手順は、両方の問題で同様に機能します。パートナーの 1 人がリソースを、自分にとって等しい 2 つの部分に分割し、もう 1 人のパートナーが自分にとって「より良い」部分を選択します。唯一の違いは、「より良い」がケーキカットでは「大きい」ことを意味し、家事カットでは「小さい」ことを意味することです。ただし、すべての結果が簡単に変換できるわけではありません。

家事分担における比例分割の定義は、ケーキカットにおける定義の鏡像です。各パートナーは、自分の個人的な不効用関数に従って、最大で合計価値の価値がある部分を受け取る必要があります(ここで、 はパートナーの合計数です)。 ${\displaystyle i}$${\displaystyle X_{i}}$ ${\displaystyle 1/n}$${\displaystyle n}$

${\displaystyle \forall i:V_{i}(X_{i})\leq V_{i}(全体)/n}$

比例ケーキカットのプロトコルのほとんどは、家事カットに簡単に変換できます。例:

• 最後の縮小プロトコルを使用するには、エージェントに、自分にとってちょうど価値のあるピースをカットするように依頼します。他のエージェントがこのピースが小さすぎると感じた場合は、自分にとってちょうど価値のあるピースになるまで拡大することができます。これを繰り返します。「最後の拡大者」は、自分と少なくとも他のエージェントにとってちょうど価値のあるピースを受け取ります。${\displaystyle 1/n}$${\displaystyle 1/n}$${\displaystyle 1/n}$${\displaystyle 1/n}$
• Even-Paz プロトコルを使用するには、各エージェントに半分の値の線をマークしてもらい、すべての線が平行であることを確認します。ケーキを線の中央で切り、エージェントを 2 つのグループに分け、各半分に、その線を含まないピースを再帰的に分割させます。${\displaystyle n/2}$

公平な分割と正確な分割の手順は、等しい価値を保証するため、ケーキと家事の両方に同様に有効です。一例として、オースティンのムービングナイフ手順があります。これは、各パートナーに、合計の ちょうど 1/ nとして評価されるピースを保証します。

家事の分担における嫉妬のなさの定義は、ケーキの切り分けにおける定義と正反対です。つまり、各パートナーは、自分の個人的な不効用関数に応じて、最大でも他のピースと同じだけの価値があるピースを受け取るべきです 。 ${\displaystyle i}$${\displaystyle X_{i}}$

${\displaystyle \forall i,j:V_{i}(X_{i})\leq V_{i}(X_{j})}$

パートナーが 2 人の場合、分割と選択によって、うらやましがられることのない雑用削減が実現します。しかし、パートナーが 3 人以上の場合、状況ははるかに複雑になります。主な難しさは、トリミング、つまり、ピースを別のピースと同等にするためにトリミングするアクション (セルフリッジ-コンウェイ プロトコルなどで行われる) にあります。このアクションは、雑用削減シナリオに簡単に変換できません。

レザ・オスクイは、3人のパートナーのための雑用削減手順を最初に提案した人物である。彼の研究は正式には出版されていないが、^[2]の73～75ページで説明されている。これはセルフリッジ・コンウェイ・プロトコルに似ているが、より複雑で、5回のカットではなく9回のカットを必要とする。

以下では、パートナーは Alice、Bob、Carl と呼ばれます。

ステップ 1。アリスは、自分の目に等しい 3 つのピースに仕事を切り分けます (これは、セルフィッジ-コンウェイ プロトコルの最初のステップでもあります)。ボブとカールは、最小のピースを指定します。簡単なケースは、両者が同意しない場合です。その場合、各パートナーに最小のピースを渡せば完了です。難しいケースは、両者が同意する場合です。ボブとカール両方が最小と見なすピースを X1、他の 2 つのピースを X2 と X3 と呼びましょう。

ステップ 2。ボブとカールに、X2 と X3 の各ピースを X1 と同じサイズにするためには、ピースをどこでカットする必要があるかをマークするように依頼します。いくつかのケースを検討します。

ケース 1.ボブのトリムは弱いです。つまり、ボブが X2 を X2' に、X3 を X3' にトリムして、ボブにとって X2' と X3' の両方が X1 と同じ大きさになるようにすると、カールは X1 がまだ最小のピースであると考えます。つまり、X2' と X3' よりも弱い大きさです。すると、次の部分分割はエンヴィフリーになります。

• カールはX1を獲得します。
• アリスは X2' と X3' のうち小さい方を取得します (どちらもアリスにとっては X1 より小さいです)。
• ボブはアリスが取らなかったピースを手に入れます (ボブにとっては両方とも X1 に等しい)。

ここで、トリミング E2 と E3 を分割する必要があります。トリミングごとに、次の処理が実行されます。

• ボブはそれを3等分に切ります。
• エージェントは、カール、アリス、ボブの順にピースを選択します。

カールは最初に選んだので嫉妬しません。ボブは切ったので嫉妬しません。アリスはカールに対して（マイナスの）優位性があったので嫉妬しません。最初のステップでは、カールは X1 を取り、アリスは X1 より最大 (E2,E3) 小さいピースを取り、最後のステップでは、アリスは最大で (E2+E3)/2 の価値がある 2 つのピースを取りました。

ケース 2。カールのトリムは弱くなります。つまり、カールが X2 を X2' に、X3 を X3' にトリムして、カールにとって X2' と X3' の両方が X1 と同じ大きさになるようにすると、ボブは X1 がまだ最小のピースであると考えます。つまり、X2' と X3' よりも弱く小さいということです。次に、ボブとカールの役割を入れ替えて、ケース 1 のように進めます。

ケース 3。ボブのトリムは X2 で弱く、カールのトリムは X3 で弱くなります。つまり、ボブが X2 を X2' にトリムして X1 と等しくし、カールが X3 を X3' にトリムして X1 と等しくした場合、次のようになります。

• カールの場合: X2' >= X1 = X3'
• ボブの場合: X3' >= X1 = X2'

したがって、次の部分分割は羨望の的になりません。

• アリスは X2' と X3' のうち小さい方を取得します (どちらもアリスにとっては X1 より小さいです)。
• ボブは、X2'（アリスが取得しなかった場合）またはX1（そうでない場合）のいずれかを取得します。
• カールは、X3' (アリスが取っていなかった場合) または X1 (そうでない場合) のいずれかを取得します。

トリミング E2 と E3 は、ケース 1 と同様の方法で分割されます。

Oskui 氏は、次の動くナイフの手順をケーキカットから雑用カットに変換する方法も示しました。

• ストロムクイストのムービングナイフ手順
• 回転ナイフ手術^{[2] ：77–78}

ピーターソンとスー^[3]は、3人のパートナーに対して異なる手順を提案した。これはオスクイの手順よりも単純で対称的だが、動くナイフの手順に依存しているため離散的ではない。彼らの主要なアイデアは、雑用を6つの部分に分割し、各パートナーに、他のプレイヤーが受け取るピースと同じくらい小さいと思われるピースを2つずつ渡すというものである。

ステップ 1。 羨ましがられないケーキカット方法を使用して、仕事を 3 つに分割し、各ピースを最も大きいと感じたプレイヤーに割り当てます。

ステップ2。

• オースティンのムービングナイフ法を使用して、ピース 1 を、パートナー 1 と 2 が等しいとみなす 2 つのスライスに分割します。パートナー 3 に、自分にとって小さい方のスライスを選ばせ、もう一方のスライスをパートナー 2 に渡します。
• 同様に、ピース 2 をパートナー 2 と 3 が等しいとみなす 2 つのスライスに分割し、パートナー 1 に小さいスライスを選択させ、もう 1 つのスライスをパートナー 3 に渡します。
• 同様に、ピース 3 を、パートナー 3 と 1 が等しいとみなす 2 つのスライスに分割し、パートナー 2 に小さいスライスを選択させ、もう 1 つのスライスをパートナー 1 に渡します。

分析。パートナー 1 は 2 つのスライスを持っています。1 つはピース 2 から、もう 1 つはピース 3 からです。パートナー 1 の目には、ピース 2 からのスライスはパートナー 3 に渡されたスライスよりも小さく、ピース 3 からのスライスはパートナー 2 に渡されたスライスよりも小さく見えます。さらに、ピース 1 はピース 2 とピース 3 の両方よりも大きいため (ステップ 1 による)、これらのスライスは両方ともピース 1 のスライスよりも小さくなります。したがって、パートナー 1 は自分の取り分が他の 2 つの取り分よりも (弱く) 小さいと考えています。同じ考慮がパートナー 2 と 3 にも当てはまります。したがって、この分割は嫉妬の影響を受けません。

ピーターソンとスーは、連続手続きを4人のパートナーにまで拡大した。^[3]

5人以上のパートナーに対する離散的手順の存在は未解決の問題であったが、2009年にピーターソンとスーがn人のパートナーに対する手順を発表した。^[4]これはブラムス・テイラー手順に類似しており、取り返しのつかない優位性という同じ考え方を使用している。彼らはトリミングの代わりに、予備からの追加を使用している。

ピーターソンとスーは、4人の家事分担のためのムービングナイフ手順を提示した。デガニら^[5]は、任意の数のエージェント間の家事分担のための最初の離散的かつ境界付き羨望のないプロトコルを提供した。

次の手順は、切断されたピースのある不良ケーキを分割するために適用できます。

• ロバートソン・ウェッブ回転ナイフ法^{[2] : 演習5.10}
• ストロムクイスト移動ナイフ法^{[2] ：演習5.11}
• シモンズ–スー プロトコル。シモンズはもともと、スペルナーの補題に基づいて、連結ピースによる近似的な羨望のないケーキカットのプロトコルを開発しました。スーは、双対補題を使用して、同様のプロトコルが近似的な羨望のない家事分担に使用できることを示しました。特に、連結ピースによる羨望のない家事分担が常に存在することを示しています。

ハイドリヒとヴァン・ステー^[6]は、ピースをつなげる必要がある場合の家事分担の 公平性の代償を計算している。

気候変動の削減のための作業と費用を国家間で分担するために、分担手順を使用することもできるかもしれない。国家間の道徳や協力を得ることには問題が生じる。しかし、分担手順を使用すると、国家間の作業を分割して監督するための超国家的な機関の必要性が軽減される。^[7]

家事分担のもう一つの用途は、賃貸の調和問題です。

• 羨望の的にならないケーキカット
• 悪い（経済）
• レンタルハーモニー