平等な所得からの競争均衡のおおよその計算

平等所得からの近似競争均衡（A-CEEI ）は、公平な品目割り当ての手順です。これはエリック・バディッシュによって開発されました。^[1]

CEEI (平等所得からの競争均衡) は、分割可能なリソースを公平に分割するための基本ルールです。次の仮想プロセスの結果に従ってリソースを分割します。

• 各エージェントは 1 単位の不換紙幣を受け取ります。これが CEEI の平等所得の部分です。
• エージェントは、市場が競争均衡に達するまで自由に取引します。これは価格ベクトルと割り当てであり、(a) 割り当てられた各バンドルは、そのエージェントの収入を考慮するとエージェントにとって最適であり、エージェントは同じ収入でより良いバンドルを購入することはできません。(b) 市場は均衡し、すべての割り当ての合計は、最初の保有量と正確に等しくなります。

均衡配分は、嫉妬がなく、パレート効率的であることが証明されています。さらに、エージェントが線形効用関数を持つ場合、CEEI 配分を効率的に計算できます。

残念ながら、不可分性がある場合、CEEI が常に存在するとは限らないため、公平なアイテム割り当てに直接使用することはできません。ただし、近似することは可能であり、近似には優れた公平性、効率性、戦略的特性があります。

A-CEEI は、エージェントがアイテムのバンドルをランク付けする方法を知っていることだけを前提としています。ランク付けは弱加法的である必要はなく、単調である必要もありません。

パラメータ付きの A-CEEI は、次の仮想プロセスの結果に応じてリソースを分割します。 ${\displaystyle \alpha ,\beta }$

• 近似 EI: 各エージェントは 1 から の間の収入を受け取ります。各エージェントの正確な収入はランダムに決定することも、勤続年数によって決定することもできます (年長者はわずかに高い収入を得ることができます)。${\displaystyle 1+\beta }$
• 近似 CE: 価格ベクトルと割り当てが計算され、(a) 割り当てられた各バンドルがエージェントの予算を考慮すればそのエージェントにとって最適であり、(b) 市場が「ほぼ」クリアされる、つまりすべての割り当ての合計と初期保有額の間のユークリッド距離が最大 になります。${\displaystyle \alpha}$

Budish は、任意の に対して、異なるアイテム タイプの数とエージェントが受け取る可能性のある異なるアイテムの数の間の最小値に依存する -CEEI が存在することを証明します。${\displaystyle \beta >0}$${\displaystyle \alpha ,\beta }$${\displaystyle \alpha}$

割り当ては次のプロパティを満たします。

• 1 つの項目を除いて羨望のない項目 (羨望のない項目の割り当てを参照)。
• ${\displaystyle (n+1)}$-最大最小シェア保証。
• 割り当てられた品目に関するパレート効率。つまり、エージェント間ではパレート改善取引は行われませんが、エージェントとマーケットメーカーの間にはパレート改善トレーダーが存在する可能性があります。

さらに、A-CEEI メカニズムは「大規模」には戦略不変です。つまり、エージェントの数が多い場合、各エージェントは価格にわずかな影響しか及ぼさないため、エージェントは価格受容者として機能します。その場合、メカニズムが価格に基づいて最適なバンドルを提供できるため、各エージェントが真の評価を報告することが最適です。

A-CEEIの割り当ては計算が難しく、PPAD完全である。^[2]

ただし、現実的な規模の問題では、A-CEEI は 2 レベルの検索プロセスを使用して計算できます。

1. マスターレベル: センターはタブー検索を使用して価格を提案します。
2. エージェント レベル:混合整数計画を解いて、現在の価格でのエージェントの需要を見つけます。

エージェントレベルのプログラムはすべてのエージェントに対して並列に実行できるため、この方法はプロセッサの数に応じてほぼ最適にスケーリングされます。^[3]

この仕組みは、ペンシルバニア大学ウォートン校のコースに学生を割り当てるタスクのために検討されてきた。 ^[4]

最大ナッシュ福祉（MNW）アルゴリズムは、エージェントの効用を最大化する配分を見つける。これはいくつかの点でA-CEEIに似ている：^[5]

• どちらのアルゴリズムも、EF-except-1 割り当てを見つけます。
• どちらのアルゴリズムも、最大最小シェア保証を近似します。

ただし、A-CEEI にはいくつかの利点があります。

• これは、サブモジュラー関数だけでなく、任意のユーティリティ関数で動作します。好みの単調性さえも必要としません。
• これは順序入力で機能します。エージェントは、アイテムの数値評価ではなく、バンドル全体のランキングを報告することのみが必要です。
• それは「大規模」な戦略の証明です。

反対に、A-CEEI にはいくつかの欠点があります。

• 割り当てられる品目には近似誤差があり、一部の品目は需要過剰または供給過剰になる可能性があります。^[6]
• 特に、返された割り当てはパレート効率的ではなく、一部の項目は未割り当てのままになります (割り当てられた項目に関してのみパレート効率的です)。

A-CEEIの近似誤差は、異なるアイテムの数に応じて大きくなりますが、プレイヤーの数や各アイテムのコピー数に応じて大きくなることはありません。したがって、A-CEEIは、エージェントの数が多く、各アイテムのコピーが多い場合に適しています。典型的な適用例は、エージェントが学生で、アイテムがコース内のポジションである場合です。^[6]

対照的に、相続分割など、エージェントが少なく、個別の項目が多い場合は、MNW の方が適しています。

A-CEEI（および一般的なCEEI）は、競争均衡の概念に関連していますが、同一ではありません。

• 競争均衡 (CE) は記述的概念であり、価格が安定し、需要が供給に等しくなる自由市場の状況を説明します。
• CEEI は規範的な概念であり、人々の間で商品を分配するためのルールを説明します。

• 組み合わせオークション