市場均衡計算

市場均衡計算（競争均衡計算または清算価格計算とも呼ばれる）は、経済学とコンピュータサイエンスの交差点における計算問題です。この問題への入力は、リソースの集合とエージェントの集合で構成される市場です。市場には、フィッシャー市場やアロー・デブリュー市場など、分割可能または分割不可能なリソースを持つさまざまな種類の市場があります。必要な出力は、価格ベクトル（各リソースの価格）と割り当て（各エージェントのリソースバンドル）で構成される競争均衡です。これにより、各エージェントは、予算を与えられた場合に（自分にとって）可能な限り最良のバンドルを取得し、市場が清算されます（すべてのリソースが割り当てられます）。

市場均衡の計算は、競争均衡が常にパレート効率的であるという事実により興味深いものです。すべての買い手の収入が等しいフィッシャー市場の特殊なケースは特に興味深いものです。なぜなら、この設定では競争均衡は嫉妬フリーでもあるからです。したがって、市場均衡の計算は、公平かつ効率的な割り当てを見つける方法です。

市場均衡計算への入力は、以下の要素から構成される: [ 1 ^{] : chap.5}

1. 事前に指定された供給量を持つリソースのセット。リソースは分割可能(この場合、供給量は 1 に正規化されます) または分割不可能です。 ${\displaystyle m}$
   • バンドルはベクトル で表されます。ここで はリソース の量です。リソースが分割できない場合、すべてのx _jは整数です。リソースが分割可能な場合、x _{j は}任意の実数（通常は [0,1] に正規化されます）になります。${\displaystyle \mathbf {x} =x_{1},\dots ,x_{m}}$${\displaystyle x_{j}}$${\displaystyle j}$
2. エージェントの集合。各エージェントにはバンドルに対する選好関係があり、これは効用関数によって表すことができます。エージェントの効用関数は で表されます。${\displaystyle n}$ ${\displaystyle i}$${\displaystyle u_{i}}$
3. 各エージェントの初期寄付金。
   • フィッシャー市場では、賦課金は「不換紙幣」の予算です。これは市場外では価値のないお金であり、したがって効用関数には入りません。エージェントはお金だけを持っているため、買い手と呼ばれることがよくあります。${\displaystyle B_{i}}$
   • Arrow-Debreu 市場では、賦存量は任意の束です。このモデルでは、エージェントは買い手と売り手の両方になることができます。${\displaystyle \mathbf {e} ^{i}}$

必要な出力には次の要素が含まれている必要があります。

1. 価格ベクトル ; 各リソースの価格。バンドルの価格は 内のリソースの価格の合計であるため、バンドルの価格は です。${\displaystyle \mathbf {p} =p_{1},\dots ,p_{m}}$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {p} \cdot \mathbf {x} =\sum _{j=1}^{m}p_{j}\cdot x_{j}}$
2. 割り当て-各エージェントiのバンドル。${\displaystyle \mathbf {x} ^{i}}$

出力は次の要件を満たす必要があります。

1. バンドルは iにとって手頃な価格である 必要があります。つまり、その価格はエージェントiの寄付金の価格以下である必要があります。 ${\displaystyle \mathbf {x} ^{i}}$
   • フィッシャー市場では、これは次のことを意味します 。${\displaystyle \mathbf {p} \cdot \mathbf {x} ^{i}\leq B_{i}}$
   • Arrow-Debreu 市場では、これは次のことを意味します 。${\displaystyle \mathbf {p} \cdot \mathbf {x} ^{i}\leq \mathbf {p} \cdot \mathbf {e} ^{i}}$
2. バンドルは i :の需要集合 内にある必要があります。これは、供給に関係なく、すべての手頃な価格のバンドルの中でエージェントの効用を最大化するバンドルの集合として定義されます。たとえば、フィッシャー市場では次のようになります。${\displaystyle \mathbf {x} ^{i}}$${\displaystyle \mathbf {x} ^{i}\in {\text{Demand}}_{i}(\mathbf {p} )}$${\displaystyle {\text{Demand}}_{i}(\mathbf {p} ):=\arg \max _{\mathbf {p} \mathbf {x} \leq B_{i}}u_{i}(\mathbf {x} )}$
3. 市場が均衡化する、つまりすべての資源が割り当てられる。対応する価格は市場均衡価格と呼ばれる。

これらの要件を満たす価格と配分は、競争均衡( CE) または市場均衡と呼ばれ、価格は均衡価格または清算価格とも呼ばれます。

市場均衡の計算は、エージェントの効用関数に関するさまざまな仮定の下で研究されてきました。

• 凹面性: 最も一般的な仮定 (Fisher と Arrow&Debreu による) は、エージェントの効用が凹関数である、つまり、収穫逓減を示すというものです。
• 同次性: 場合によっては、効用は同次関数であると仮定されます。これには特に、代替の弾力性が一定である効用が含まれます。
• 分離可能性: バンドルの効用がバンドル内の個々のリソースの効用の合計である場合、効用関数は分離可能と呼ばれます。${\displaystyle u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}(x_{j})}$
• 区分線形性は分離可能性の特殊なケースであり、個々のリソースの効用関数はx jの区分線形関数になります。${\displaystyle u_{i,j}(x_{j})}$
• 線形性はさらに特殊なケースで、個々のリソースの効用関数は線形関数です。つまり、 であり、 は定数です。${\displaystyle u_{i}(\mathbf {x} )=\sum _{j=1}^{m}u_{i,j}\cdot x_{j}}$${\displaystyle u_{i,j}}$

区分線形かつ凹状の効用は PLC と呼ばれることが多く、分離可能な場合は SPLC と呼ばれます。

スカーフ^{[2]は、スペルナーの補題（}フィッシャーマーケットを参照）を用いてCEの存在を初めて示した。彼はまた、近似CEを計算するアルゴリズムも提示した。

メリル^[3]は近似CEのための拡張アルゴリズムを提示した。

Kakade、Kearns、Ortiz ^[4]は、エージェントがグラフ上に配置され、取引が隣接するエージェント間でのみ発生する一般化されたArrow-Debreu市場における近似CEのアルゴリズムを提示した。彼らは非線形効用を考慮した。

ニューマンとプリマック^{[5]は、線形効用を持つアロー・デブリュー市場でCEを見つけるための}楕円体法の2つの変種を研究した。彼らは、内接楕円体法が外接楕円体法よりも計算効率が高いことを証明した。

場合によっては、近似CEを計算することはPPAD困難です。

• DevanurとKannan ^[6]は、PLCユーティリティの特殊なケースであるレオンチェフユーティリティを使用して、Arrow-Debreu市場でPPAD困難性を証明した。
• Chen、Dai、Du、Teng ^[7]は、SPLC効用を持つArrow-Debreu市場におけるPPAD困難性を証明した。彼らの証明は、PPADがPに含まれない限り、この市場均衡問題にはFPTASが存在しないということを示している。
• ChenとTeng ^[8]は、 SPLCユーティリティを用いたフィッシャー市場におけるPPAD困難性を証明した。
• Chaudhury、Garg、McGlaughlin、Mehta ^[9]は、CEの存在を保証する特定の条件下でも、バッドと線形効用を持つ交換（Arrow-Debreu）市場でPPAD困難性を証明した。

Devanur、Papadimitriou、Saberi、Vazirani ^[10]は、線形効用関数を持つフィッシャー市場の均衡を正確に計算する多項式時間アルゴリズムを提示した。彼らのアルゴリズムは、KKT条件と凸計画の拡張設定で主双対パラダイムを使用する。彼らのアルゴリズムは弱多項式である。つまり、最大フロー問題を解き、したがって時間 で実行される 。ここで、u _maxとB _{max は}それぞれ最大効用と予算である。 ${\displaystyle O((n+m)^{5}\log(u_{\max })+(n+m)^{4}\log {B_{\max }})}$ ${\displaystyle O((n+m)^{8}\log(u_{\max })+(n+m)^{7}\log {B_{\max }})}$

オーリン^[11]は、線形効用を持つフィッシャー市場モデルの改良アルゴリズムを提示した。このアルゴリズムは の時間で実行される。 その後、彼はこのアルゴリズムを強多項式時間で実行されるように改良した。${\displaystyle O((n+m)^{4}\log(u_{\max })+(n+m)^{3}B_{\max })}$${\displaystyle O((m+n)^{4}\log(m+n))}$

DevanurとKannan ^[6]は、凹型の効用関数を持つArrow-Debreu市場のアルゴリズムを提示した。このアルゴリズムでは、すべてのリソースが財である（効用は正である）。

• 効用が SPLC で、nまたはmのいずれかが定数の場合、そのアルゴリズムは他のパラメータに関して多項式です。この手法では、一定数の超平面を使用して可能な価格の空間をセルに分解し、各セルで各購入者の限界効用しきい値がわかるようにします ( nとm の両方が変数の場合、多項式アルゴリズムが存在するかどうかは未解決のままです)。
• ユーティリティが PLC (必ずしも分離可能ではない) で、mが定数の場合、そのアルゴリズムはnの多項式です。mとn の両方が変数の場合、 PLC ユーティリティの特殊なケースであるレオンチェフ ユーティリティの場合でも、 CE を見つけることはPPAD 困難です ( nが定数でmが変数の場合、多項式アルゴリズムが存在するかどうかは未解決のままでした)。

Codenotti、McCune、Penumatcha、Varadarajan ^[12]は、代替の弾力性が少なくとも1/2である CES効用を持つArrow-Debreuマークのアルゴリズムを提示した。

Bogomolnaia と Moulin、および Sandomirskiy と Yanovskaia は、バッド (負の効用を持つアイテム) ^[13]と、グッズとバッドが混在するフィッシャー市場における CE の存在と特性を研究しました^[14] 。グッズの設定とは対照的に、リソースがバッドの場合、CE は線形効用であっても凸最適化問題を解決しません。CE の割り当ては、実行可能な効用セットのパレート境界上の効用の積の極小値、極大値、および鞍点に対応します。CE ルールは多値になります。この研究は、そのような市場で CE を見つけるアルゴリズムに関するいくつかの研究につながりました。

• BranzeiとSandomirskiy ^[15]は、バッドと線形効用を持つフィッシャー市場ですべてのCEを見つけるアルゴリズムを提示した。彼らのアルゴリズムは、nまたはmのいずれかが固定されている場合、強多項式時間で実行される。彼らのアプローチは、3つのアイデアを組み合わせたものである。PO割り当てのすべての消費グラフを多項式時間でリストできること、特定の消費グラフに対して、明示的な式を使用してCE候補を構築できること、最大フロー計算を使用して特定の割り当てがCEであるかどうかを確認できることである。
• ガーグとマクグローリン^{[16]は、混合マナと線形効用を持つフィッシャー市場におけるすべてのCEを計算するアルゴリズムを提示した。彼らのアルゴリズムは、} nまたはmのいずれかが固定されている場合、多項式時間で実行される。
• Chaudhury、Garg、McGlaughlin、Mehta ^{[17] は、}混合マナ効用と SPLC 効用を持つフィッシャー市場で単一の CE を計算するアルゴリズムを提示しました。彼らのアルゴリズムは単体型で、Lemkeのスキームに基づいています。その最悪のケースの実行時間は多項式ではありませんが (問題は財があっても PPAD 困難です^[8] )、ランダムインスタンスでは高速に実行されます。また、問題が PPAD であり、解が有理値であり、解の数が奇数であることが証明されています。彼らのアルゴリズムは、すべての効用が負である特殊なケースでは多項式時間で実行されます。

nとm の両方が変数の場合、問題は計算上困難になります。

• Chaudhury、Garg、McGlaughlin、Mehta ^{[9] : Thm.3 は}、バッドと線形効用を持つフィッシャー市場では、CE が存在するかどうかを判断するのは NP 困難であることを示しています。同じ困難さは、δ>0 の任意の値に対して (11/12+δ)-CE を見つけることにも当てはまり、所得が等しい場合でも当てはまります。彼らはまた、グラフの連結性に基づいて、CE が存在するための十分な条件を証明しています。この条件では、CE は常に存在しますが、それを見つけることは PPAD 困難です。^{[9] : Thm.5}

効用が線形の場合、エージェントiの1 ドル当たりの価値(BPB または1 コイン当たりの効用とも呼ばれる) は、 iの効用を支払価格で割ったものとして定義されます。単一リソースの BPB は で 、合計 BPB は です。 ${\displaystyle bpb_{i,j}:={\frac {u_{i,j}}{p_{j}}}}$${\displaystyle bpb_{i,total}:={\frac {\sum _{j=1}^{m}u_{i,j}\cdot x_{i,j}}{B_{i}}}}$

線形効用を持つフィッシャー市場でCEを見つけるための重要な観察は、任意のCEと任意のエージェントiにおいて次のようになることである。^[1]

• 合計 BPB は、個々のリソースからの BPB よりもわずかに大きくなります 。${\displaystyle \forall j:bpb_{i,j}\leq bpb_{i,total}}$
• エージェントi は、最大可能な BPB、つまり のリソースのみを消費します。${\displaystyle \forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}}$

すべての製品には潜在的な購入者（の購入者）がいると仮定します。すると、上記の不等式は、つまりすべての価格が正であることを意味します。 ${\displaystyle j}$${\displaystyle i}$${\displaystyle u_{i,j}>0}$${\displaystyle p_{j}>0}$

セル分解^{[6] は、}超平面またはより一般的には多項式面によって、価格の可能性のある空間を小さな「セル」に分割するプロセスです。セルは、各面のどの側にあるかを指定することによって定義されます (多項式面の場合、セルは半代数集合とも呼ばれます)。各セルについて、市場均衡価格ベクトル (つまり、市場均衡割り当てが存在するセル内の価格) を見つけるか、セルに市場均衡価格ベクトルが含まれていないことを確認します。課題は、次の特性を持つ分解を見つけることです。 ${\displaystyle \mathbb {R} _{+}^{m}}$

• セルの総数は入力のサイズの多項式です。これは、k 個の超平面の任意の集合が空間をセルに分割するという事実を利用しています。^{[6] : Thm.2} mが固定されている場合、これは多項式です。さらに、最大次数dのk 個の多項式面の任意の集合は、空間を空でないセルに分割し、出力サイズに線形の時間で列挙できます。^[18]${\displaystyle \mathbb {R} _{+}^{m}}$${\displaystyle O(k^{m})}$${\displaystyle O(k^{m+1}\cdot d^{O(m)})}$
• 各セルの市場均衡価格ベクトルを見つけることは、例えば線形計画法を使用して多項式時間で実行できます。

すべてのエージェントの効用が同次関数である場合、フィッシャーモデルの均衡条件は、アイゼンバーグ-ゲール凸計画と呼ばれる凸最適化プログラムの解として記述できます。^{[19]このプログラムは、購入者の効用の}加重幾何平均を最大化する割り当てを見つけます。ここで、重みは予算によって決定されます。同様に、効用の対数の加重算術平均を最大化します。

最大化${\displaystyle \sum _{i=1}^{n}\left(B_{i}\cdot \log {(u_{i})}\right)}$

以下を条件とします:

非負数量: すべての購入者と製品について:${\displaystyle i}$${\displaystyle j}$${\displaystyle x_{i,j}\geq 0}$

十分な供給：すべての製品について：${\displaystyle j}$${\displaystyle \sum _{i=1}^{n}x_{i,j}\leq 1}$

(供給量は 1 に正規化されるため)。

この最適化問題は、Karush-Kuhn-Tucker条件（KKT）を使用して解くことができます。これらの条件は、価格として解釈できるラグランジュ乗数を導入します。アイゼンバーグ-ゲール計画を最大化するすべての割り当てにおいて、すべての購入者は要求されたバンドルを受け取ります。つまり、アイゼンバーグ-ゲール計画の解は市場均衡を表します。^{[1] ：141–142}${\displaystyle p_{1},\dots ,p_{m}}$

同次効用の特殊なケースは、すべての買い手が線形効用関数を持つ場合です。各リソースには潜在的な買い手、つまりそのリソースから正の効用を引き出す買い手がいると仮定します。この仮定の下では、市場均衡価格が存在し、一意です。証明はアイゼンバーグ-ゲール計画に基づいています。KKT 条件は、最適解 (割り当てと価格) が次の不等式を満たすことを意味します。 ${\displaystyle x_{i,j}}$${\displaystyle p_{j}}$

1. すべての価格は負ではありません: 。${\displaystyle p_{j}\geq 0}$
2. 製品の価格が正の場合、その製品の供給はすべて枯渇します。${\displaystyle p_{j}>0\implies \sum _{i=1}^{n}x_{i,j}=1}$
3. 合計 BPB は、個々のリソースからの BPB よりもわずかに大きくなります 。${\displaystyle \forall j:bpb_{i,j}\leq bpb_{i,total}}$
4. エージェントi は、最大可能な BPB、つまり のリソースのみを消費します。${\displaystyle \forall j:x_{i,j}>0\implies bpb_{i,j}=bpb_{i,total}}$

すべての製品には潜在的な買い手、つまり の買い手がいると仮定します。すると、不等式 3 は、つまりすべての価格が正であることを意味します。すると、不等式 2 はすべての供給が枯渇していることを意味します。不等式 4 はすべての買い手の予算が枯渇していることを意味します。つまり、市場はクリアされます。対数関数は厳密に凹関数であるため、均衡配分が複数ある場合、両方の配分で各買い手が得る効用は同じでなければなりません (買い手の効用の減少は、別の買い手の効用の増大によって補うことはできません)。これは、不等式 4 とともに、価格が一意であることを意味します。^{[1] : 107}${\displaystyle j}$${\displaystyle i}$${\displaystyle u_{i,j}>0}$${\displaystyle p_{j}>0}$

Vazirani ^{[1] : 109–121 は、}線形フィッシャー市場で均衡価格と配分を見つけるアルゴリズムを発表しました。このアルゴリズムは、上記の条件 4 に基づいています。この条件は、均衡状態では、すべての購入者が最大の BPB をも​​たらす製品のみを購入することを意味します。現在の価格で最大の BPB をも​​たらす製品が購入者に「好まれる」とします。価格ベクトルが与えられた場合、各エッジの容量がそのエッジを「流れる」合計金額を表すフロー ネットワークを構築します。ネットワークは次のようになります。

• ソースノードsがあります。
• 各製品にはノードがあり、sから各製品jへのエッジがあり、容量があります（これは、供給が 1 に正規化されているため、製品jに費やせる最大金額です）。${\displaystyle p_{j}}$
• 各購入者ごとにノードがあり、購入者が製品を気に入った場合（現在の価格で）、製品から購入者へのエッジが無限の容量で存在します。
• ターゲットノードtがあり、各購入者iからtへのエッジがあり、容量はiの最大支出です。${\displaystyle B_{i}}$

価格ベクトルp は、2 つのカット ({s},V\{s}) と (V\{t},{t}) が最小カットである場合にのみ、均衡価格ベクトルになります。したがって、均衡価格ベクトルは次のスキームを使用して見つけることができます。

• 均衡価格を下回ることが保証されている非常に低い価格から始めます。これらの価格では、購入者にはいくらかの予算が残ります (つまり、最大フローはtへのノードの容量に達しません)。
• すべての予算が使い果たされるまで、継続的に価格を上げ、それに応じてフロー ネットワークを更新します。

この問題を弱多項式時間で解くアルゴリズムがあります。

最近、Gao、Peysakhovich、Kroer ^[20]は市場均衡のオンライン計算アルゴリズムを提示した。

• 効率的で嫉妬のない分割
• 効率的でほぼ公平なアイテムの割り当て