品物とお金の公平な分配

アイテムとお金の公平な割り当ては、公平なアイテム割り当て問題の一種で、割り当てプロセス中に参加者の一部にお金を与えたり受け取ったりすることができます。お金がなければ、分割できないアイテムを公平に割り当てることは不可能です。たとえば、アイテムが 1 つと人が 2 人いて、アイテムを 1 人にすべて渡さなければならない場合、割り当てはもう 1 人に対して不公平になります。以下で説明するように、金銭による支払いによって公平性を実現できます。

2 つのエージェントと 1 つのアイテムを使用する場合、次の単純なアルゴリズム (カット アンド チョイスのバリエーション) を使用して公平性を実現できます。

• アリスは、その商品に支払ってもよいと思う価格p を言います。
• ジョージは、商品を受け取ってp を支払うか、商品をアリスに残してアリスがp を支払うかを選択します。

このアルゴリズムは、常に羨望のない割り当てを生成します。エージェントが準線型効用を持つ場合、つまり、効用がアイテムの価値と彼らが持っている金額の合計である場合、割り当ても比例します。ジョージがアリスの価格が低いと考える場合（ pよりも多く支払う意思がある場合）、彼はアイテムを受け取ってp を支払い、彼の効用は正であるため、アリスを羨ましがりません。アリスも、ジョージの効用が（彼女の目には）0であるため、ジョージを羨ましがりません。同様に、ジョージがアリスの価格が高いと考える場合（p以上を支払う意思がある場合）、彼はアイテムをアリスに残し、アリスの効用が彼の目には負であるため、羨ましがりません。

支払われたお金p は、後でプレイヤー間で均等に分割できます。これは、均等な金銭移転は相対的な効用に影響を与えないためです。すると、実質的に、買い側のエージェントは売り手側のエージェントにp /2 を支払うことになります。各エージェントの合計効用は、そのアイテムに対する効用の少なくとも 1/2 になります。エージェントが異なる権利を持っている場合、支払われたお金p は、権利に応じてパートナー間で分割する必要があります。

この単純なアイデアを 2 人以上のプレイヤーやより複雑な設定に拡張するさまざまな研究があります。これらの研究における主な公平性の基準は、嫉妬のなさです。さらに、一部の研究では、善意の第三者が割り当てを補助する意思があるが、嫉妬のなさを条件に補助額を最小限に抑えたいと考えている設定を考慮しています。この問題は、最小補助羨望のない割り当てと呼ばれます。

ユニット需要エージェントは最大で 1 つのアイテムに関心があります。

この設定の特殊なケースは、アパートの部屋を入居者間で分割する場合です。これは、次の 3 つの要件によって特徴付けられます: (a) エージェントの数はアイテムの数と等しい、(b) 各エージェントは正確に 1 つのアイテム (部屋) を取得する必要がある、(c) エージェントが支払う合計金額は、アパートの合計家賃を表す固定定数と等しくなければならない。これは、賃貸調和問題として知られています。

一般に、経済学の文献では、各エージェントがバンドル (バンドルとは、オブジェクトと一定額のお金のペア) に対して効用関数を持つと想定するのが一般的です。効用関数は、連続的で、お金に対して増加する必要があります。お金に対して線形である必要はありませんが、「アルキメデス的」である必要があります。つまり、 2 つのオブジェクトjとkごとに、オブジェクトjとV を加えた効用がオブジェクトkの効用よりも大きくなるような値V が存在します (または、オブジェクトjを無料で取得する効用は、オブジェクトk を取得してV を支払う効用よりも大きくなります)。準線形効用はアルキメデス的効用の特殊なケースであり、Vは 2 つのオブジェクト間の最大価値差 (同じエージェントの場合) です。

スヴェンソン^[1]は、すべてのエージェントがアルキメデス的である場合、嫉妬のない割り当てが存在し、それがパレート最適であることを初めて証明した。

デマンジュ、ゲイル、ソトマイヨール^[2]は、単位需要エージェントに対する金銭的支払いを用いて羨望のない割り当てを実現する自然な上昇オークションを示した。

マスキン^{[3]は、総貨幣賦存量が(} n-1 ) Vより大きい場合、パレート最適な羨望のない配分が存在することを証明した。証明には競争均衡が用いられる。

( n -1) Vの補助金が必要になる場合があることに注意してください。すべてのエージェントが1つのオブジェクトをVと評価し、他のオブジェクトを0と評価する場合、嫉妬のなさは、オブジェクトを受け取らないエージェントごとに Vの補助金を必要とします。

蓼沼とトムソン^[4]は、嫉妬のない割り当て規則のいくつかの一貫性特性を研究している。

アラゴネス^[5]は、嫉妬のなさに必要な補助金の最小額を特徴づけています。この最小補助金を達成する割り当てはほぼ一意です。つまり、オブジェクトとエージェントを組み合わせる方法は1つしかなく、すべてのエージェントはすべての最小補助金割り当て間で無差別です。これは、アルカン、デマンジュ、ゲイルの「マネー・ロールズ解」と呼ばれる解と一致します。^[6] これは、最大重みマッチングを見つけ、次に特定の誘導グラフで最短経路を見つけることで、多項式時間で見つけることができます。

Klijn ^{[7] は、}同じ設定で別の多項式時間アルゴリズムを提示しています。彼のアルゴリズムは、与えられた割り当てを羨望フリーにするサイドペイメントの多面体を使用します。この多面体は、元の割り当てがパレート効率的である場合に限り、空ではありません。無向羨望グラフの連結性は、この多面体の極値点を特徴付けます。これは、羨望フリーの極値割り当てを見つける方法を意味します。

添加剤エージェントは複数のオブジェクトを受け取る可能性があるため、割り当ての問題はより複雑になり、割り当ての可能性がさらに多くなります。

品物とお金の公平な分配のための最初の手順は、ブロニスワフ・クナスターによって発明され、ヒューゴ・シュタインハウスによって公開されました。^{[8] [9]}このオークションは、品物ごとに次のように機能します。

• 各エージェントはアイテムに対して入札を提出します。
• 最高額入札者にアイテムが与えられます（同点の場合は任意で決定します）。
• 勝者は入札額の( n -1)/ nを支払う。
• 他のエージェントはそれぞれ入札額の1/ nを受け取ります。
• 最高額の入札者が勝者となるため、非負の余剰が生じ、余剰はエージェント間で均等に分配されます。

各エージェントの効用は、そのエージェントがオブジェクトのセット全体に与える価値の少なくとも1/ nであるため、割り当ては比例します。^[10]さらに、割り当ては効用の合計を最大化するため、パレート効率的です。

ナスターのオークションは戦略性がない。一部の研究者は、エージェントが戦略的にプレイする場合のパフォーマンスを分析した。

• エッセン^[11]は、均衡配分は依然としてパレート効率的であるが、事後的には比例的ではない可能性があることを証明している。しかし、平均的には、エージェントは全員が正直であるのと同じ結果を受け取る。つまり、メカニズムは事前的には比例的である。
• フラグネリとマリーナ^[12]は、リスクを限りなく回避するエージェントであっても、他のエージェントの申告に関係なく、共同で評価を誤って報告することで安全な利益を得ることができることを示している。

ナスターオークションは無線チャンネルの公平な割り当てに適応している。^[13]

マティアス・G・レイス^[14]は、ナスターのオークションのバリエーションとして「調整ナスター」というオークションを提案した。ナスターのオークションと同様に、各アイテムは最高入札者に与えられる。しかし、支払額は異なる。支払額は次のように決定される。

• アイテムを落札した各エージェントは、そのアイテムに対する入札額を支払います。
• エージェントが支払う合計金額は、入札額に応じてエージェント間で分配されます。

Knaster のオークションと Raith のオークションの違いを説明するために、次の値を持つ 2 つのアイテムと 2 つのエージェントがある設定を考えてみましょう。

両方のオークションで、ジョージは両方の品物を勝ち取りましたが、支払いは異なります。

• ナスターのオークションでは、ジョージが 90 を支払い、アリスが 10 を受け取り、差額の 80 が均等に分割されるため、純効用は 50、130 になります。
• レイスのオークションでは、ジョージは 180 を支払い、それが 20:180 = 1:9 の比率で分割されます。つまり、アリスは 18 を受け取り、ジョージは 162 を受け取ります。支払いは、各アイテムごとにではなく、すべてのアイテムに対して一度に計算されることに注意してください。

人間を対象とした実験では、^[15]参加者は分割選択や比例ナスター（勝者が敗者に勝利金の1/nを支払う変種。上記の例では、ジョージはアリスに90を支払い、純効用は90、90）よりもレイスのオークション（調整ナスター）を好むことがわかった。

Haake、Raith、Su ^{[16] は}補償手順を提示しています。彼らの手順では、アイテムのバンドルが匿名である限り (パートナーをそのアイデンティティに基づいて区別しない)、任意の制約を許します。たとえば、制約がまったくないこともあれば、「各パートナーは少なくとも一定数のアイテムを受け取る必要がある」、または「いくつかのアイテムはバンドルされている必要がある」(たとえば、接続されたままでなければならない土地区画であるため) などの制約もあります。「アイテム」には、正の効用と負の効用の両方があります。パートナーには「資格要件」があり、入札の合計が少なくとも総コストである必要があります。手順は次の手順で動作します。

1. 最大合計 (功利主義) 割り当てを見つけます。これは、アイテムのバンドルに対する制約を満たす、効用の合計が最も高い割り当てです。制約がない場合、各アイテムを最も高い評価を持つパートナーに提供する割り当てが最大合計です。制約がある場合 (「パートナーごとに少なくとも 1 つのアイテム」など)、最大合計割り当てを見つけるのがより困難になる可能性があります。
2. 各パートナーから、割り当てられたバンドルの価値を請求します。これにより、初期の資金プールが作成されます。
3. 初期プールからコストを支払います。すべてのパートナーが資格要件を満たしている場合は、プール内の資金は十分であり、余剰金が残る可能性があります。
4. 嫉妬深い相手に補償することで嫉妬をなくします。補償は最大でラウンドで行われます。手順は完全に説明されており、どの補償をどのような順序で行うべきかが明確に示されています。さらに、コンピューターのサポートなしで実行できるほど簡単です。${\displaystyle n-1}$
5. すべてのラウンドで行われた補償の合計は、嫉妬をなくすために必要な最小の合計であり、余剰を超えることはありません。余剰が残った場合は、各パートナーに同額を与えるなど、嫉妬を生まない方法で分割できます (この論文では、「より公平」であると考えられる他のオプションについても説明しています)。

項目が多く、制約が複雑な場合、最初のステップである最大和割り当ての検出は、コンピュータなしでは計算が難しい場合があります。この場合、補償手順は任意の割り当てから開始される可能性があります。この場合、手順は、羨望サイクルを含む割り当てで終了する可能性があります。これらのサイクルは、羨望グラフ手順のように、バンドルをサイクルに沿って移動することで削除できます。これにより、ユーティリティの合計が確実に増加します。したがって、制限された回数の反復の後、最大和割り当てが見つかり、手順は上記のように続行して羨望のない割り当てを作成できます。

補償手続きでは、一部のパートナーにマイナスの支払いを請求する場合があります（つまり、パートナーにプラスの金額を支払うことになります）。著者は次のように述べています。

「我々は、個人が他のメンバーから商品の束を受け取るために報酬を受け取る可能性を排除しません。公平な分配の文脈では、これはまったく問題ではないと考えています。実際、グループがメンバーの誰も排除したくない場合は、グループがメンバーに望まない束を受け取ったことを補助しない理由は何もありません。さらに、資格要件は、補助が、分配されるオブジェクトの完全なセットに対するプレーヤーの評価が不十分であることの結果ではないことを保証します。」^{[16] : 746}

いくつかの研究では、善意の第三者が配分を補助する意思はあるが、羨望の無いことを条件に補助額を最小限に抑えたいと考えていると仮定しています。この問題は、最小補助羨望無し配分と呼ばれます。

ハルパーンとシャー^[17]は、一般的な品目配分設定における補助金最小化を研究している。彼らは2つのケースを検討している。

1. 割り当ては事前に与えられます。この場合、そのバンドルをエージェントに再割り当てするたびに効用の合計が最大化される場合にのみ、その割り当ては「羨望の影響を受けない」状態になります。また、羨望グラフにサイクルがない場合にも限ります。最小限の補助金で羨望のない価格は、重み付き羨望グラフを作成し、各エージェントiに、 iから発する経路の最大重みに等しい価格を与えることで、強多項式時間で計算できます。各経路の重みは、最大でm項の合計です。各項は、あるエージェントのある財に対する価値です。特に、各エージェントの各財の価値が最大でVの場合、各経路の重みは最大でmVです。1 つのエージェントが補助金をゼロにするように価格を下げることは常に可能なので、最大で ( n -1) mVの補助金で羨望のない割り当てが常に存在することになります。この補助金は、たとえばすべての商品が同一であり、1 人の代理人がそれらすべてを取得する場合などに必要になることがあります。
2. 配分は選択できる。この場合、以下の場合 には（ n -1）Vの補助金で十分である。
   • エージェントの評価がバイナリ（0 または 1）の場合、最大積割り当てまたはレキシミン最適割り当ては最大で ( n -1) V の補助金が必要となり、多項式時間で見つけることができます。EF を達成するために必要な最小補助金を計算することは、嫉妬のない割り当ての存在を確認することとチューリング同等であり、無駄のない割り当てに制限すると NP 困難になります。
   • すべてのエージェントが同じ加法的評価を持っている場合、すべての割り当ては羨望の影響を受けない。最大 ( n -1) V の補助金を必要とする割り当ては、多項式時間で見つけることができます。割り当てが補助金を最小化するのは、任意のエージェントの最大効用を最小化する場合のみです。このような割り当ての計算は NP 困難であり、最大積アルゴリズムで解決できます。
   • エージェントが 2 人いる場合、特定のエージェント順序によるラウンドロビン項目割り当てにより、補助金が最大Vで羨望の影響を受けない割り当てが見つかります。

Brustle、Dippel、Narayan、Suzuki、Vetta ^[18]は、必要な補助金の上限を改善した。

• 加法的な評価では、エージェント 1 人あたり最大V、一般に最大 ( n -1) Vの補助金で十分です。さらに、この境界を達成する割り当てがあり、これは EF1 でバランスが取れています (割り当てられたバンドルの基数は最大で 1 つの財だけ異なります)。これは、エージェントとオブジェクトの二部グラフで最大重みのマッチングを反復的に見つけるという単純なアルゴリズムによって、多項式時間で計算できます。
• 一般的な単調な評価では、エージェントあたり最大 2( n -1) V、最大 O( n ² V ) の補助金が常に十分です。特に、必要な補助金はオブジェクトの数に依存しません。この制限を達成する割り当ては、値クエリを使用して多項式時間で計算できます。

カラギアニスとイオアニディス^[19]は補助金を最小化する計算問題を研究している。

• エージェントの数が一定である場合、彼らは必要な精度内で補助金の最小額を近似するアルゴリズムを提示しています。任意のε > 0 に対して、最大 の補助金による割り当てを見つけます。ここで、S はエージェントがすべてのオブジェクトに割り当てる最大値です。アルゴリズムは動的プログラミングを使用し、時間 で実行されます。${\displaystyle OPT+\varepsilon \cdot S}$${\displaystyle O((m/\varepsilon )^{n^{2}+1})}$
• エージェントの数が可変の場合、簡単な近似アルゴリズムで が達成されます。しかし、 nに依存しない近似係数の達成は困難です。補助金が最大 の割り当てを計算するのは NP 困難です。証明は、各頂点が正確に 2 回出現する最大3 次元マッチングの制限された変形からの簡約によって行われます。${\displaystyle OPT+(n-1)\cdot S}$${\displaystyle OPT+3\cdot 10^{-4}\cdot S}$

補助金付きの羨望のない割り当ては、各エージェントから固定額が取られる場合、羨望のないままであることに注意してください。したがって、同様の方法を使用して、補助金のない割り当てを見つけることができます。

• 各エージェントに平均支払額を請求すると、羨望の的にならない配分となり、予算のバランスも取れます。補助金を最小限に抑えることは、個々のエージェントが支払う最大額を最小限に抑えることと同じです。
• すべてのエージェントが支払う合計金額を最小限に抑えながら、負の補助金（税金）を使用することも可能です。

アルカン、デマンジュ、ゲイル^[6]は、お金の量が十分に大きい場合、嫉妬のない配分が常に存在することを示しました。これは、アイテムの評価がマイナスになる場合でも当てはまります。

Meertens、Potters、Reijnierse ^[20]は、評価に関する非常に緩やかな仮定（必ずしも準線形ではない）の下で、嫉妬のないパレート最適な配分が存在することを証明している。

Cavallo ^{[21] は}、嫉妬のなさ、比例性、効率性 (福祉) という伝統的な二項基準を、0 から 1 の範囲の程度を示す尺度に一般化しています。標準的な公平な分割設定では、配分効率の高いメカニズムの下では、最悪の福祉率は 0 で、不均衡率は 1 です。言い換えれば、最悪の結果は可能な限り悪いということです。彼は、公平な分割設定のスペクトル全体にわたって、高い福祉、低い嫉妬、低い不均衡性を実現するメカニズムを探しています。VCGメカニズムは満足のいく候補ではありませんが、 Bailey ^[22]とCavallo ^[23]の再分配メカニズムは満足のいく候補です。

買い手に商品を販売する場合、支払額は事前に決まっておらず、売り手の収益または社会福祉を最大化することが目標です。ただし、羨望の影響を受けないことが条件となります。さらに、商品の数はエージェントの数と異なる場合があり、一部の商品は破棄される可能性があります。これは羨望のない価格設定問題として知られています。

多くの場合、公平性以外にも達成しなければならない目的があります。例えば、エージェントにタスクを割り当てる際には、嫉妬を避けることと、メイクスパン（最後のエージェントの完了時間）を最小化することの両方が必要です。Mu'alemは、嫉妬のないことを保証する最適化問題の一般的なフレームワークを提示し、金銭の支払いを使用して公平なアイテムの割り当てを自然に拡張します。^[24]

アジズ^[25]は、金銭移転を利用して、羨望のない公平な配分を達成することを目指している。彼は、加法的な正の効用だけでなく、正か負かを問わず、超加法的な効用についても研究している。

• 超加法効用の場合、羨望のなさ、公平性、予算均衡（予算均衡を補助金と交換するのは簡単）を実現する多項式時間アルゴリズムが存在します。
• 特定の割り当てが EFEQ に変換可能な場合、それを EF+EQ にするために必要な最小の補助金は線形時間で見つけることができます。
• 補助金が最小で EFEQ に変換可能な割り当てを見つけることは NP 困難であり、正の係数内で近似することはできません。これは、EF 割り当て (補助金が 0 必要) の存在を確認することが NP 困難であるためです。
• 最大 ( n -1) mVの補助金は常に十分であり、割り当てが与えられるかどうかに関係なく必要になる場合があります。

• 羨望のないアイテム割り当て- 金銭の移転のない設定。
• ^[26]