嫉妬の最小化

コンピュータサイエンスとオペレーションズリサーチにおいて、羨望最小化問題とは、羨望の量が可能な限り小さくなるよう に、アイテムに対する異なる評価を持つエージェント間で個別のアイテムを割り当てる問題です。

理想的には、公平性の観点から、羨望のないアイテム割り当て、つまり、どのエージェントも他のエージェントを羨望しない割り当てを見つけたいものです。つまり、どのエージェントも、他のエージェントに割り当てられたバンドルを好みません。ただし、分割できないアイテムの場合、これは不可能な場合があります。この不可能性に対処する 1 つの方法は、問題を最適化問題に変換することです。最適化問題では、損失関数は羨望の量を表す関数です。一般に、この最適化問題はNP 困難です。羨望のない割り当てが存在するかどうかを判断することさえ、分割問題と同等であるためです。ただし、実際には良い結果を生む最適化アルゴリズムがあります。

最小化のための目的関数 (羨望の量) を定義する方法はいくつかあります。そのいくつかを次に示します。

• 嫉妬深いエージェントの数;
• 羨望関係の数（羨望グラフの辺）
• 割り当てXにおけるjに対するiの羨望率の最大羨望率は次のように定義されます: ; したがって、 i がj を羨望しない場合は比率は 1 になり、i がj を羨望する場合は比率が大きくなります。 ${\displaystyle {\text{EnvyRatio}}(X,i,j):=\max \left(1,{u_{i}(X_{j}) \over u_{i}(X_{i})}\right)}$
  • 同様に、羨望比率の合計、またはその積を考慮することもできます。
• 嫉妬の差の最大値、合計、または積。

一般的な評価では、最大羨望率を最小化する決定論的アルゴリズムは、最悪の場合、商品の数の指数関数的な数のクエリを必要とする。^{[1] : 3}

加法および同一評価の場合：^{[1] ：4～6}

• 次の貪欲アルゴリズムは、最大羨望率が最適値の1.4倍以下になる割り当てを見つけます。^[2]
  1. 項目を値の降順で並べ替えます。
  2. アイテムがまだある場合は、合計値が最小のエージェントに次のアイテムを渡します。
• 最大羨望比を最小化するPTASがあります。さらに、プレイヤー数が一定の場合は、FPTASがあります。

加法的な評価と異なる評価の場合：^[3]

• エージェントの数が入力の一部である場合、P = NP でない限り、多項式時間で 1.5 よりも優れた近似係数を取得することは不可能です。
• エージェントの数が一定（入力の一部ではない）の場合、最大羨望比率と羨望比率の積を最小化するFPTASが存在します。
• エージェントの数がアイテムの数と等しい場合、多項式時間アルゴリズムが存在します。

場合によっては、嫉妬を最小化する割り当てを分散的に計算する必要があります。つまり、各エージェントは、結果の割り当てが一貫していることを保証する方法で、独自の割り当てを計算する必要があります。この問題は、次のように非対称分散制約最適化問題 (ADCOP) として提示することで解決できます。^[4]

• 各エージェントiとアイテムjにバイナリ変数v _{ij を}追加します。エージェントがアイテムを取得した場合、変数の値は「1」になり、そうでない場合は「0」になります。変数はエージェントiが所有します。
• 各アイテムが最大 1 つのエージェントに与えられるという制約を表現するには、同じアイテムに関連する 2 つの異なる変数ごとにバイナリ制約を追加します。2 つの変数が同時に「1」の場合はコストが無限大になり、それ以外の場合はコストがゼロになります。
• すべてのアイテムを割り当てる必要があるという制約を表現するには、各アイテムにn項制約 ( nはエージェントの数) を追加します。このアイテムに関連する変数が 1 でない場合は、コストは無限大になります。

この問題は、次の局所探索アルゴリズムを使用して解決できます。^[4]

• すべてのエージェントは辞書式に並べられます (例: 名前またはインデックス順)。
• 各エージェントは変数を辞書順に並べます。
• 各エージェントは、より高い優先度を持つエージェントに割り当てられなかったアイテムを順番に要求します (「要求」とは、エージェントが対応する変数に「1」を割​​り当てることを意味します)。
• エージェントがすべての変数 (1 または 0) を割り当てた後、結果の割り当てを辞書式順序で次のエージェントに送信します。
• エージェントは、現在の割り当てに対する羨望の評価をメッセージで相互に送信します。
• 他のエージェントから羨望の評価を受け取った後、エージェントは変数をバックトラックすることを決定する場合があります。バックトラックする変数がなくなった場合、エージェントは前のエージェントに戻ることができます。最初のエージェントが最初の変数をバックトラックすると、検索は終了し、最適な割り当てが見つかります。

割り当てるアイテムが一度にすべて利用可能ではなく、オンラインで時間をかけて到着する場合があります。到着した各アイテムは、すぐに割り当てる必要があります。例として、食品の寄付を受け取り、それを慈善団体にすぐに割り当てなければならないフードバンクの問題が挙げられます。

Benade、Kazachkov、Procaccia、および Psomas ^{[5] は、各アイテムの値が [0,1] になるように評価が正規化される、最大}羨望差を最小化する問題を考察しています。この設定のオフライン版では、最大羨望差が 1 になる割り当てを簡単に見つけることができることに注意してください (このような割り当ては EF1 と呼ばれます。詳細については、羨望のないアイテム割り当てを参照してください)。ただし、オンライン版では、羨望差はアイテムの数とともに増加します。彼らは、 T個のアイテムの後の羨望が であるアルゴリズムを示しています。Jiang、Kulkarni、および Singla ^{[6] は、}オンラインの 2 次元不一致最小化 のアルゴリズムを使用して、羨望の境界を改善しています。 ${\displaystyle O({\sqrt {T/n}})}$

嫉妬の最小化が研究された他の設定は次のとおりです。

• 最適な税金^[7 ]
• 学校選択^[8 ]