無秩序の代償

無政府状態の代償( PoA ) [ ^1]は経済学とゲーム理論の概念であり、エージェントの利己的な行動によってシステムの効率がどの程度低下するかを測定します。これは、さまざまなシステムや効率の概念に拡張できる一般的な概念です。たとえば、都市の交通システムと、ある最初の場所から目的地まで移動しようとしている多くのエージェントを考えてみましょう。ここで、効率とは、エージェントが目的地に到着するまでの平均時間を意味します。「集中型」ソリューションでは、中央の機関が各エージェントに平均移動時間を最小化するためにどの経路を取るべきかを指示できます。「分散型」バージョンでは、各エージェントが独自の経路を選択します。無政府状態の代償は、2 つのケースの平均移動時間の比率を測定します。

通常、システムはゲームとしてモデル化され、効率は結果の何らかの関数です（例：ネットワークの最大遅延、輸送システムの混雑、オークションの社会的厚生など）。エージェントの利己的な行動をモデル化するために、さまざまな均衡の概念を使用できますが、最も一般的なのはナッシュ均衡です。ナッシュ均衡のさまざまなフレーバーにより、無政府状態の価格の概念のバリエーションが生まれ、純粋無政府状態の価格（決定論的均衡の場合）、混合無政府状態の価格（ランダム化均衡の場合）、ベイズ–ナッシュ無政府状態の価格（不完全情報ゲームの場合）などになります。ナッシュ均衡以外のソリューションの概念は、沈没の価格などのバリエーションにつながります。^[2]

「無政府状態の代償」という用語は、エリアス・クツピアスとクリストス・パパディミトリウによって初めて使用されましたが、^{[1] [3]}均衡の非効率性を測定するというアイデアはもっと古いものです。^{[4]現在の形の概念は、}近似アルゴリズムの「近似比率」やオンラインアルゴリズムの「競争比率」の類似物となるように設計されました。これは、アルゴリズムのレンズを使用してゲームを分析する現在の傾向（アルゴリズムゲーム理論）に沿ったものです。

プレイヤーの集合、各プレイヤーの戦略集合、効用（結果集合とも呼ばれる）によって定義されるゲームを考えてみましょう 。各結果の効率性の尺度を定義でき、これを福祉関数と呼びます。自然な候補としては、プレイヤーの効用の合計（功利主義目的）、最小効用（公平性または平等主義目的）、…、または分析対象の特定のゲームにとって意味があり、最大化することが望ましい任意の関数が挙げられます。 ${\displaystyle G=(N,S,u)}$${\displaystyle N}$${\displaystyle S_{i}}$${\displaystyle u_{i}:S\rightarrow \mathbb {R} }$${\displaystyle S=S_{1}\times ...\times S_{n}}$${\displaystyle \operatorname {Welf} :S\rightarrow \mathbb {R} }$${\displaystyle \operatorname {Welf} (s)=\sum _{i\in N}u_{i}(s),}$${\displaystyle \operatorname {Welf} (s)=\min _{i\in N}u_{i}(s),}$

均衡状態にある戦略の集合（たとえば、ナッシュ均衡の集合）をサブセットとして定義することができます。無政府状態の価格は、最適な「集中型」ソリューションと「最悪の均衡」の比率として定義されます。 ${\displaystyle Equil\subseteq S}$

${\displaystyle PoA={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\min _{s\in Equil}\operatorname {Welf} (s)}}}$

関数測定効率が、最大化したい「福祉」ではなく、最小化したい「コスト関数」（ネットワークの遅延など）である場合は、次のように使用します（近似アルゴリズムの慣例に従います）。 ${\displaystyle \operatorname {コスト} :S\rightarrow \mathbb {R} }$

${\displaystyle PoA={\frac {\max _{s\in Equil}\operatorname {コスト} (s)}{\min _{s\in S}\operatorname {コスト} (s)}}}$

関連する概念として、最適な「集中型」ソリューションと「最良の均衡」の比率を測定する 安定価格（PoS ）があります。

${\displaystyle PoS={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\max _{s\in Equil}\operatorname {Welf} (s)}}}$

またはコスト関数の場合:

${\displaystyle PoS={\frac {\min _{s\in Equil}\operatorname {コスト} (s)}{\min _{s\in S}\operatorname {コスト} (s)}}}$

それは定義から わかります。ゲーム理論上の制約による効率の低下は、「PoS」と「PoA」の間のどこかにあると予想されます。${\displaystyle 1\leq PoS\leq PoA}$

次のコスト マトリックスで表される、 囚人のジレンマと呼ばれる 2x2 ゲームを考えます。

そしてコスト関数を とします。ここで、最悪（かつ唯一の）ナッシュ均衡は、両方のプレイヤーが裏切った場合であり、その結果生じるコストはです。ただし、社会福祉が最も高くなるのは両方が協力した場合であり、その場合のコストは です。したがって、このゲームの PoA は になります。 ${\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).}$${\displaystyle C_{equil}=5+5=10}$${\displaystyle C_{min}=1+1=2}$${\displaystyle C_{equil}/C_{min}=10/2=5}$

ゲームには固有のナッシュ均衡があるため、PoS は PoA と等しく、これも 5 です。

より自然な例は、ジョブ スケジューリングの例です。プレイヤーがいて、それぞれが実行するジョブを持っています。プレイヤーは、ジョブを実行するマシンを 1 つ選択できます。The Price of Anarchy では、マシンの選択が中央から誘導/指示される状況と、各プレイヤーが自分のジョブを最も速く実行できるマシンを選択する状況を比較しています。 ${\displaystyle N}$${\displaystyle M}$

各マシンには速度があり、 各ジョブには重みがあります。プレイヤーはジョブを実行するマシンを選択します。したがって、各プレイヤーの戦略は、マシンの負荷を次のように 定義します。${\displaystyle s_{1},\ldots ,s_{M}>0.}$${\displaystyle w_{1},\ldots ,w_{N}>0.}$${\displaystyle A_{i}=\{1,2,\ldots ,M\}.}$${\displaystyle j}$

${\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.}$

プレイヤーのコストは、つまり、選択したマシンの負荷です。ここでは、メイクスパンと呼ばれる平等主義コスト関数を考慮します。${\displaystyle i}$${\displaystyle c_{i}(a)=L_{a_{i}}(a),}$${\displaystyle {\mbox{M​​S}}(a)=\max _{j}L_{j}(a)}$

ここでは、純粋ナッシュ均衡と混合ナッシュ均衡という 2 つの均衡概念について検討します。任意の純粋ナッシュ均衡は混合ナッシュ均衡でもあるため、混合 PoA ≥ 純粋 PoA であることは明らかです (この不等式は厳密になる場合があります。たとえば、、、、の場合、混合戦略は平均メイクスパンが 1.5 になりますが、この設定での任意の純粋戦略 PoA は です)。まず、純粋ナッシュ均衡が存在することを論じる必要があります。 ${\displaystyle N=2}$${\displaystyle w_{1}=w_{2}=1}$${\displaystyle M=2}$${\displaystyle s_{1}=s_{2}=1}$${\displaystyle \sigma _{1}=\sigma _{2}=(1/2,1/2)}$${\displaystyle \leq 4/3}$

主張。各ジョブスケジューリングゲームには、少なくとも 1 つの純粋戦略ナッシュ均衡が存在します。

証明。社会的に最適なアクション プロファイルを採用します。これは、単にメイクスパンが最小となるアクション プロファイルを意味します。ただし、これだけでは十分ではありません。このようなアクション プロファイルは複数存在し、さまざまな負荷分布 (すべて最大負荷は同じ) につながる可能性があります。これらのプロファイルの中から、2 番目に大きい負荷が最小となるプロファイルにさらに限定します。これにより、一連の可能な負荷分布が生成され、 番目に大きい (つまり、最小の) 負荷まで繰り返します。この負荷分布では、負荷の分布は 1 つしか存在できません (順列を除いて一意)。これは、辞書式最小ソート済み負荷ベクトル とも呼ばれます。${\displaystyle a^{*}}$${\displaystyle M}$

これは純粋戦略ナッシュ均衡であると主張する。矛盾から推論すると、あるプレイヤーがマシンからマシンへ移動することで厳密に改善できると仮定する。これは、移動後のマシンの増加した負荷が、移動前のマシンの負荷よりもまだ小さいことを意味する。マシンの負荷は移動の結果として減少するはずであり、他のマシンは影響を受けないため、これは新しい構成によって分布の 番目の最大 (または上位ランク) の負荷が確実に減少することを意味する。ただし、これは の想定された辞書式最小性に違反する。QED${\displaystyle i}$${\displaystyle j}$${\displaystyle k}$${\displaystyle k}$${\displaystyle j}$${\displaystyle j}$${\displaystyle j}$${\displaystyle a}$

主張。各ジョブ スケジューリング ゲームについて、純粋な PoA は最大で です。 ${\displaystyle M}$

証明任意の 混合戦略ナッシュ均衡で得られる厚生を次のように上限値で表すことは簡単である。${\displaystyle \sigma}$

${\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.}$

説明をわかりやすくするために、純粋戦略の行動プロファイルを考えてみましょう。明らかに ${\displaystyle a}$

${\displaystyle w(a)\geq {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geq {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.}$

上記は社会的最適にも当てはまるので、比率を比較すると主張が証明されます。QED${\displaystyle w(\sigma )}$${\displaystyle w(a)}$

右の図のような道路網を考えてみましょう。この道路では、4000 人のドライバーがスタート地点からエンド地点まで移動します。スタート–A 道路の移動時間は、旅行者数 (T) を 100 で割った値 (分) で、スタート–B 道路の移動時間は定数の 45 分です (向かい側の道路も同様)。破線の道路がない場合 (つまり、交通網には合計 4 つの道路がある)、スタート–A–エンド ルートをドライバーで運転するのに必要な時間は になります。スタート–B–エンド ルートをドライバーで運転するのに必要な時間は になります。ドライバーが 4000 人いるので、 という事実を使用して、システムが均衡状態にあるときという事実を導き出すことができます。したがって、各ルートには数分かかります。どちらかのルートの所要時間が短い場合、ナッシュ均衡ではありません。合理的なドライバーは、長いルートから短いルートに切り替えるでしょう。 ${\displaystyle a}$${\displaystyle {\tfrac {a}{100}}+45}$${\displaystyle b}$${\displaystyle {\tfrac {b}{100}}+45}$${\displaystyle a+b=4000}$${\displaystyle a=b=2000}$${\displaystyle {\tfrac {2000}{100}}+45=65}$

ここで、破線 A–B が、移動時間が約 0 分と極めて短い道路であるとします。道路が開通し、1 人のドライバーが開始–A–B–終了を試みたとします。驚いたことに、所要時間は数分で、約 25 分の節約になります。すぐに、4,000 人のドライバーのうちさらに多くのドライバーがこの新しいルートを試します。所要時間は 40.01 から増加し続けます。新しいルートを試みるドライバーの数が 2,500 人に達し、1,500 人はまだ開始–B–終了ルートにいるため、所要時間は数分になり、元のルートと比べて改善されません。一方、これら 1,500 人のドライバーは数分に遅くなり、20 分の増加になります。彼らも A を経由する新しいルートに切り替える必要があるため、今では数分しかかかりません。どのドライバーも A 終了または開始–B を移動しようとすると 85 分かかるため、誰もこれらのルートを移動するインセンティブがありません。したがって、横断ルートの開通は、全員による不可逆的な変更を引き起こし、全員が当初の 65 分ではなく 80 分を費やすことになります。すべてのドライバーが A-B パスを使用しないことに同意した場合、またはそのルートが閉鎖された場合、すべてのドライバーは移動時間を 15 分短縮することで恩恵を受けることになります。 ${\displaystyle {\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01}$${\displaystyle {\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65}$${\displaystyle 45+{\tfrac {4000}{100}}=85}$${\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}$

Braess のパラドックスで導入されたルーティング問題は、同じグラフを同時に横断する多くの異なるフローに一般化できます。

定義（一般化されたフロー）。、、を上で定義したとおりとし、量を内の各ノードの異なるペアにルーティングするとします。フローは、からへの各パスに実数の非負数を割り当てることで定義され、制約は次のよう になります。${\displaystyle G=(V,E)}$${\displaystyle L}$${\displaystyle w}$${\displaystyle R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}}$${\displaystyle \Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)}$ ${\displaystyle f_{\Gamma,R}}$${\displaystyle p\mapsto \Re}$ ${\displaystyle p}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$ ${\displaystyle \in \Gamma }$

${\displaystyle \sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma .}$

の特定のエッジを通過する流れは次のように定義されます。 ${\displaystyle G}$

${\displaystyle f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}.}$

簡潔にするために、文脈から明らかな 場合は書きます。${\displaystyle f_{e}}$${\displaystyle \Gamma ,R}$

定義（ナッシュ均衡フロー）フローはナッシュ均衡フローであるためには、からまでが${\displaystyle f_{\Gamma ,R}}$${\displaystyle \forall (s_{i},t_{i})\in \Gamma }$${\displaystyle \forall p,q}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$

${\displaystyle f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leq \sum _{e\in q}{l_{e}(f_{e})}.}$

この定義は、正規形ゲームにおける混合戦略ナッシュ均衡のサポートについて述べたことと密接に関連しています。

定義（フローの条件付き福祉） と を、同じ集合 と に関連付けられたの2つのフローとします。以下では、表記を明確にするために下付き文字を省略します。 によって誘発される遅延をグラフに固定すると仮定します。に対する の条件付き福祉は次のように定義されます。 ${\displaystyle f_{\Gamma ,R}}$${\displaystyle f_{\Gamma ,R}^{*}}$${\displaystyle G}$${\displaystyle \Gamma }$${\displaystyle R}$${\displaystyle f}$${\displaystyle f^{*}}$${\displaystyle f}$

${\displaystyle w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}}$

事実 1 . ナッシュ均衡フローおよび他の任意のフローが与えられた場合、${\displaystyle f}$${\displaystyle f^{*}}$${\displaystyle w(f)=w^{f}(f)\leq w^{f}(f^{*})}$

証明（背理法による） . と仮定する。定義により、 ${\displaystyle w^{f}(f^{*})<w^{f}(f)}$

${\displaystyle \sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}\cdot \sum _{e\in p}l_{e}(f_{e})<\sum _{i=1}^{k}\sum _{p:s_{i}\rightarrow t_{i}}f_{p}\cdot \sum _{e\in p}l_{e}(f_{e})}$。

とは同じ集合に関連付けられているので、 ${\displaystyle f}$${\displaystyle f^{*}}$${\displaystyle \Gamma ,R}$

${\displaystyle \sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i.}$

したがって、からへのパスのペアが2つ存在し、、、および ${\displaystyle (s_{i},t_{i})}$${\displaystyle p,q}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$${\displaystyle f_{p}^{*}>f_{p}}$${\displaystyle f_{q}^{*}<f_{q}}$

${\displaystyle \sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).}$

言い換えれば、フローがより低い福祉を達成できるのは、から への異なるコストを持つ 2 つの経路があり、 が のフローの一部を高コストの経路から低コストの経路に再ルーティングする場合のみです。この状況は、 がナッシュ均衡フローであるという仮定と明らかに矛盾しています。QED${\displaystyle f^{*}}$${\displaystyle f}$${\displaystyle s_{i}}$${\displaystyle t_{i}}$${\displaystyle f^{*}}$${\displaystyle f}$${\displaystyle f}$

事実 1 では、集合 上の特定の構造を想定していないことに注意してください。 ${\displaystyle L}$

事実 2.任意の 2 つの実数とが与えられると 、${\displaystyle x}$${\displaystyle y}$${\displaystyle x\cdot y\leq x^{2}+y^{2}/4}$

証明。これは真の不等式を表現する別の方法です。QED${\displaystyle (x-y/2)^{2}\geq 0}$

定理.線形遅延を伴う一般化ルーティング問題の純粋な PoA はです。 ${\displaystyle (G,L)}$${\displaystyle \leq 4/3}$

証明この定理は、各ナッシュ均衡フロー に対して、（ は他の任意のフロー） となることと同等であることに注意してください。定義により、 ${\displaystyle f}$${\displaystyle w(f)\leq (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}}$${\displaystyle f^{*}}$

${\displaystyle w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})}$

${\displaystyle =\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.}$

事実2を使うと、

${\displaystyle w^{f}(f^{*})\leq \sum _{e\in E}\left(a_{e}\cdot \left((f_{e}^{*})^{2}+(f_{e})^{2}/4\right)\right)+\sum _{e\in E}f_{e}^{*}\cdot b_{e}}$

${\displaystyle =\left(\sum _{e\in E}a_{e}(f_{e}^{*})^{2}+f_{e}^{*}b_{e}\right)+\sum _{e\in E}a_{e}(f_{e})^{2}/4}$

${\displaystyle \leq w(f^{*})+{\frac {w(f)}{4}},}$

以来

${\displaystyle (1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})}$

${\displaystyle =(1/4)\cdot \sum _{e\in E}(f_{e})^{2}+\underbrace {(1/4)\cdot \sum _{e\in E}f_{e}b_{e}} _{\geq 0}.}$

結論として、事実1を用いて命題を証明することができます。QED${\displaystyle w^{f}(f^{*})\leq w(f^{*})+w(f)/4}$

証明では、関数が線形であるという仮定を広範に使用していることに注意してください。実際には、より一般的な事実が当てはまります。 ${\displaystyle L}$

定理. グラフと次数 の多項式遅延関数を持つ一般化されたルーティング問題が与えられ、係数が非負の場合、純粋な PoA は です。 ${\displaystyle G}$${\displaystyle d}$${\displaystyle \leq d+1}$

PoAは とともに成長できることに注意する。単位フローを仮定した次の図の例を考えてみよう。ナッシュ均衡フローの社会的厚生は1である。しかし、 のときに最も厚生が良くなる。その場合、 ${\displaystyle d}$${\displaystyle x=1-1/{\sqrt {d+1}}}$

${\displaystyle w=\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{d}\cdot \left(1-{\frac {1}{\sqrt {d+1}}}\right)+1\cdot {\frac {1}{\sqrt {d+1}}}}$

${\displaystyle =\left(\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{\sqrt {d+1}}\right)^{\sqrt {d+1}}+{\frac {1}{\sqrt {d+1}}}}$

${\displaystyle \leq e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.}$

この量は、無限大に近づくとゼロに近づきます。 ${\displaystyle d}$

PoAの上限は、ゲームがいわゆる滑らかさ不等式を満たすことが示されれば得られる。より正確には、コスト最小化ゲームは、不等式が満たされる場合、 ( λ , μ )滑らか（λ≥0かつμ<1）である。

${\displaystyle \sum _{i=1}^{n}C_{i}\left(a_{i}^{*},a_{-i}\right)\leq \lambda C\left(a^{*}\right)+\mu C(a)}$

は任意の結果aとa *に対して成り立つ。この場合、PoAはλ /(1 − μ )で上限が定められる。^[5]

凹状のコスト関数を持つコストシェアリングゲームの場合、無政府状態のコストを最適化し、次に安定のコストを最適化する最適なコストシェアリングルールは、まさにシャプレー値のコストシェアリングルールです。^[6]（対称的なステートメントは、凸状の効用関数を持つ効用シェアリングゲームでも同様に有効です。）メカニズム設計では、これはシャプレー値のソリューションの概念がこれらのゲームセットに最適であることを意味します。

さらに、これらの（有限）ゲームでは、PoA境界を達成するすべての均衡は脆弱であることが証明されており、これはエージェントが均衡行動とシステム最適な結果で追求する行動との間に無関心の状態を示すという意味で脆弱である。^[7]

• オークションにおける無政府状態の値段
• 混雑ゲームにおける無秩序の代償
• 安定の代償
• コモンズの悲劇
• 競争的な施設配置ゲーム- 無秩序の代償が小さいゲーム。

• Tim Roughgarden と Eva Tardos、「均衡の非効率性入門」。Vazirani , Vijay V.、Nisan, Noam、Roughgarden, Tim、Tardos, Éva (2007) の第 17 章。アルゴリズム ゲーム理論( PDF)。ケンブリッジ、イギリス: Cambridge University Press。ISBN 0-521-87282-0。。
• ティム・ラフガーデン（2005年）。 『利己的なルーティングと無政府状態の代償』MIT Press。ISBN 0-262-18243-2。

• ファビオ・クニアル『無政府状態の代償』