Concept in economics and game theory
無政府状態の代償 （ PoA ） [ 1]は、 経済学 と ゲーム理論 における概念であり、 システムの 効率がエージェントの 利己的な 行動によってどの程度低下するかを測定するもの です。これは、さまざまなシステムや効率の概念に拡張できる一般的な概念です。たとえば、ある都市の交通システムと、多くのエージェントが最初の場所から目的地まで移動しようとしている場合を考えてみましょう。ここで、効率とは、エージェントが目的地に到達するまでの平均時間を意味します。「集中型」ソリューションでは、中央機関が各エージェントに平均移動時間を最小化するためにどの経路を取るべきかを指示できます。「分散型」バージョンでは、各エージェントが独自の経路を選択します。無政府状態の代償は、2つのケースの平均移動時間の比率を測定します。
通常、システムは ゲーム としてモデル化され、効率は結果の何らかの関数（例：ネットワークの最大遅延、交通システムの混雑、オークションにおける社会福祉など）として表されます。エージェントの利己的行動をモデル化するために、さまざまな均衡の概念を使用できますが、最も一般的なのは ナッシュ均衡 です。ナッシュ均衡のさまざまなフレーバーにより、無政府状態の価格の概念のバリエーションが生まれ、 純粋無政府状態の価格 （決定論的均衡の場合）、 混合無政府状態の価格 （ランダム化均衡の場合）、 ベイズ・ナッシュ無政府状態の価格（不完全情報ゲームの場合）などがあります。ナッシュ均衡以外の解の概念は 、沈没の価格 などのバリエーションにつながります 。 [2]
「アナーキーの代償」という用語は、 エリアス ・クツピアス と クリストス・パパディミトリウによって初めて使用されました [1] [3]。 しかし、均衡の非効率性を測定するという概念はより古いものです。 [4] 現在の形の概念は、 近似アルゴリズムにおける「近似比率」、または オンラインアルゴリズム における「競争比率」に相当するものとして設計されました。これは、アルゴリズム的なレンズを用いてゲームを分析するという現在のトレンド（ アルゴリズムゲーム理論 ）の文脈に即しています 。
数学的な定義 プレイヤーの集合、 各プレイヤーの 戦略集合、そして効用 （ここで は結果集合とも呼ばれる）によって定義される ゲームを考えてみましょう 。各結果の効率性を表す尺度を厚生関数 と定義することができます 。自然な候補としては、プレイヤーの効用の合計（功利主義的目的）、 最小効用（公平性または平等主義的目的）、 …など、分析対象の特定のゲームにとって意味があり、最大化が望ましい任意の関数が挙げられます。 G = ( N , S , u ) {\displaystyle G=(N,S,u)} N {\displaystyle N} S i {\displaystyle S_{i}} u i : S → R {\displaystyle u_{i}:S\rightarrow \mathbb {R} } S = S 1 × . . . × S n {\displaystyle S=S_{1}\times ...\times S_{n}} Welf : S → R {\displaystyle \operatorname {Welf} :S\rightarrow \mathbb {R} } Welf ( s ) = ∑ i ∈ N u i ( s ) , {\displaystyle \operatorname {Welf} (s)=\sum _{i\in N}u_{i}(s),} Welf ( s ) = min i ∈ N u i ( s ) , {\displaystyle \operatorname {Welf} (s)=\min _{i\in N}u_{i}(s),}
均衡状態にある戦略の集合（例えば、 ナッシュ均衡 の集合）を部分集合として定義することができます 。そして、無政府状態の価格は、最適な「集中型」解と「最悪の均衡」の比として定義されます。 E q u i l ⊆ S {\displaystyle Equil\subseteq S}
P o A = max s ∈ S Welf ( s ) min s ∈ E q u i l Welf ( s ) {\displaystyle PoA={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\min _{s\in Equil}\operatorname {Welf} (s)}}}
関数測定効率が、私たちが「最大化」したい「福祉」ではなく、 私たちが「最小化」したい「コスト関数」（ネットワークの遅延など）である場合、私たちは（近似アルゴリズムの慣例に従って）次のように使用します。 Cost : S → R {\displaystyle \operatorname {Cost} :S\rightarrow \mathbb {R} }
P o A = max s ∈ E q u i l Cost ( s ) min s ∈ S Cost ( s ) {\displaystyle PoA={\frac {\max _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}
関連する概念として、 最適な「集中型」ソリューションと「最良の均衡」の比率を測定する「 安定の価格 （ PoS ）」があります。
P o S = max s ∈ S Welf ( s ) max s ∈ E q u i l Welf ( s ) {\displaystyle PoS={\frac {\max _{s\in S}\operatorname {Welf} (s)}{\max _{s\in Equil}\operatorname {Welf} (s)}}}
あるいはコスト関数の場合：
P o S = min s ∈ E q u i l Cost ( s ) min s ∈ S Cost ( s ) {\displaystyle PoS={\frac {\min _{s\in Equil}\operatorname {Cost} (s)}{\min _{s\in S}\operatorname {Cost} (s)}}}
それは定義から 分かります。ゲーム理論的な制約による効率の低下は、「PoS」と「PoA」の中間にあると予想されます。 1 ≤ P o S ≤ P o A {\displaystyle 1\leq PoS\leq PoA}
例
囚人のジレンマ 次のコスト マトリックスで表される、 囚人のジレンマ と呼ばれる 2x2 ゲームを考えます。
協力する 欠陥 協力する 1、1 7 , 0 欠陥 0 , 7 5、5
そして、費用関数を とします。 ここで、最悪（そして唯一の） ナッシュ均衡は 、両方のプレイヤーが裏切った場合であり、その結果生じる費用は となります 。しかし、社会福祉が最も高くなるのは両者が協力した場合であり、その場合の費用は となります 。したがって、このゲームのPoAは となります 。 C ( s 1 , s 2 ) = u 1 ( s 1 , s 2 ) + u 2 ( s 1 , s 2 ) . {\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2}).} C e q u i l = 5 + 5 = 10 {\displaystyle C_{equil}=5+5=10} C m i n = 1 + 1 = 2 {\displaystyle C_{min}=1+1=2} C e q u i l / C m i n = 10 / 2 = 5 {\displaystyle C_{equil}/C_{min}=10/2=5}
ゲームには固有のナッシュ均衡があるため、PoS は PoA と等しく、これも 5 です。
ジョブスケジューリング より自然な例として、 ジョブスケジューリング が挙げられます。プレイヤーが複数存在し 、それぞれが実行するジョブを持っています。プレイヤーは、 ジョブを実行するマシンを1つ選択できます。「The Price of Anarchy」では、マシンの選択が中央集権的に指示される状況と、各プレイヤーが自分のジョブを最も速く実行できるマシンを選択する状況を比較しています。 N {\displaystyle N} M {\displaystyle M}
各マシンには速度があり、 各ジョブには重みがあります 。プレイヤーはジョブを実行するマシンを選択します。したがって、各プレイヤーの戦略は以下のとおりです。 マシンの 負荷を 次のように 定義します。 s 1 , … , s M > 0. {\displaystyle s_{1},\ldots ,s_{M}>0.} w 1 , … , w N > 0. {\displaystyle w_{1},\ldots ,w_{N}>0.} A i = { 1 , 2 , … , M } . {\displaystyle A_{i}=\{1,2,\ldots ,M\}.} j {\displaystyle j}
L j ( a ) = ∑ i : a i = j w i s j . {\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.} プレイヤーのコストは 、選択したマシンの負荷、すなわち、均等化コスト関数 （ここでは メイクスパン と呼ぶ）を考慮する 。 i {\displaystyle i} c i ( a ) = L a i ( a ) , {\displaystyle c_{i}(a)=L_{a_{i}}(a),} MS ( a ) = max j L j ( a ) {\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)}
我々は、純粋ナッシュ均衡と 混合ナッシュ 均衡という2つの均衡概念を考察する 。混合PoA ≥ 純粋PoAであることは明らかである。なぜなら、任意の純粋ナッシュ均衡は混合ナッシュ均衡でもあるからである（この不等式は厳密になることもある。例えば 、、、、 の場合 、混合戦略は 平均メイクスパン1.5を達成するが、この設定における任意の純粋戦略PoAは である ）。まず、純粋ナッシュ均衡が存在することを論じる必要がある。 N = 2 {\displaystyle N=2} w 1 = w 2 = 1 {\displaystyle w_{1}=w_{2}=1} M = 2 {\displaystyle M=2} s 1 = s 2 = 1 {\displaystyle s_{1}=s_{2}=1} σ 1 = σ 2 = ( 1 / 2 , 1 / 2 ) {\displaystyle \sigma _{1}=\sigma _{2}=(1/2,1/2)} ≤ 4 / 3 {\displaystyle \leq 4/3}
主張 。各ジョブスケジューリングゲームには、少なくとも1つの純粋戦略ナッシュ均衡が存在する。
証明 。社会的に最適な行動プロファイル を取り上げます 。これは、メイクスパンが最小となる行動プロファイルを意味します。しかし、これだけでは十分ではありません。このような行動プロファイルは複数存在し、様々な負荷分布（すべて最大負荷は同じ）につながる可能性があります。これらのプロファイルの中から、2番目に大きい負荷が最小となるものに限定します。ここでも、一連の可能な負荷分布が得られ、これを 番目に大きい（つまり、最小の）負荷まで繰り返します。この負荷分布では、負荷の分布は1つしか存在できません（順列を除いて一意です）。これは、 辞書式 最小ソート済み負荷ベクトル とも呼ばれます。 a ∗ {\displaystyle a^{*}} M {\displaystyle M}
これは純粋戦略ナッシュ均衡であると主張する。矛盾から推論すると、あるプレイヤーが マシン から マシン へ移動することで厳密に改善できると仮定する。これは 、移動後 のマシン の増加した負荷が、 移動前のマシン の負荷よりも依然として小さいことを意味する。マシン の負荷は 移動の結果として減少するはずであり、他のマシンは影響を受けないため、これは新しい構成によって分布内で 番目に大きい（または上位にランク付けされた）負荷が確実に減少することを意味する。しかし、これは の 辞書式最小性という仮定に違反する 。QED i {\displaystyle i} j {\displaystyle j} k {\displaystyle k} k {\displaystyle k} j {\displaystyle j} j {\displaystyle j} j {\displaystyle j} a {\displaystyle a}
を主張します 。各ジョブスケジューリングゲームについて、純粋なPoAは最大で です 。 M {\displaystyle M}
証明 任意 の混合戦略ナッシュ均衡において得られる厚生を 次のよう
に上限値で定めることは容易である。 σ {\displaystyle \sigma }
w ( σ ) ≤ ∑ i w i max j s j . {\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.} 説明を分かりやすくするために、純粋戦略の行動プロファイルを考えてみましょう 。明らかに a {\displaystyle a}
w ( a ) ≥ ∑ i w i ∑ j s j ≥ ∑ i w i M ⋅ max j s j . {\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 w ( σ ) {\displaystyle w(\sigma )} w ( a ) {\displaystyle w(a)}
利己的なルーティング
ブラエスのパラドックス 右の図に示すような道路網を考えてみましょう。この道路では 4000 人のドライバーがスタート地点からエンド地点まで移動します。スタート–A 道路の移動時間 (分) は、旅行者数 (T) を 100 で割った値で、スタート–B 道路では定数 45 分です (向かい側の道路も同様)。破線の道路がない場合 (つまり交通網には合計 4 本の道路がある)、スタート–A–エンド ルートを ドライバーで運転するのに必要な時間は になります 。スタート–B–エンド ルートをドライバーで運転するのに必要な時間は になります 。4000 人のドライバーがいるため、 という事実を使用して、 システムが均衡状態にあるとき という事実を導き出すことができます。したがって、各ルート には 数分かかります。どちらかのルートの所要時間が短い場合、ナッシュ均衡にはなりません。合理的なドライバーであれば、長いルートから短いルートに切り替えるでしょう。 a {\displaystyle a} a 100 + 45 {\displaystyle {\tfrac {a}{100}}+45} b {\displaystyle b} b 100 + 45 {\displaystyle {\tfrac {b}{100}}+45} a + b = 4000 {\displaystyle a+b=4000} a = b = 2000 {\displaystyle a=b=2000} 2000 100 + 45 = 65 {\displaystyle {\tfrac {2000}{100}}+45=65}
ここで、破線 A–B が約 0 分という極めて短い移動時間の道路だとします。道路が開通し、1 人のドライバーが Start–A–B–End を試みたとします。驚いたことに、所要時間は 数分で、約 25 分も節約できたことになります。まもなく、4,000 人のドライバーのうちさらに多くのドライバーがこの新しいルートを試します。所要時間は 40.01 から増加し続けます。新しいルートを試みるドライバーの数が 2,500 人に達し、1,500 人はまだ Start–B–End ルートを使用しているため、所要時間は 数分になり、元のルートと比べて改善されません。一方、これら 1,500 人のドライバーは数分に減速され 、20 分の増加となりました。彼らも A を経由する新しいルートに切り替える必要があるため、今では 数分しかかかりません。どのドライバーも A–End または Start–B を移動すると 85 分かかるため、これらのルートを移動するインセンティブはありません。したがって、横断ルートの開通は、全員による不可逆的な変更を引き起こし、全員が当初の 65 分ではなく 80 分を費やすことになります。すべてのドライバーが A-B パスを使用しないことに同意するか、そのルートが閉鎖された場合、すべてのドライバーは 15 分の移動時間の短縮という恩恵を受けることになります。 2000 100 + 2001 100 = 40.01 {\displaystyle {\tfrac {2000}{100}}+{\tfrac {2001}{100}}=40.01} 2500 100 + 4000 100 = 65 {\displaystyle {\tfrac {2500}{100}}+{\tfrac {4000}{100}}=65} 45 + 4000 100 = 85 {\displaystyle 45+{\tfrac {4000}{100}}=85} 4000 100 + 4000 100 = 80 {\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}
一般化ルーティング問題 Braess のパラドックスで導入されたルーティング問題は、同じグラフを同時に横断する多くの異なるフローに一般化できます。
定義（一般化フロー） 。 、、 を上で定義したとおりとし、各量を 内の異なるノードのペアに 通すとします 。 フローと は、から に至る各 パス に実数の非負数を 割り当てることで定義され 、次の制約が満たされます。 G = ( V , E ) {\displaystyle G=(V,E)} L {\displaystyle L} w {\displaystyle w} R = { r 1 , r 2 , … , r k , | r i > 0 } {\displaystyle R=\{r_{1},r_{2},\dots ,r_{k},\;|\;r_{i}>0\}} Γ = { ( s 1 , t 1 ) , ( s 2 , t 2 ) , … , ( s k , t k ) } ⊆ ( V × V ) {\displaystyle \Gamma =\{(s_{1},t_{1}),(s_{2},t_{2}),\dots ,(s_{k},t_{k})\}\subseteq (V\times V)} f Γ , R {\displaystyle f_{\Gamma ,R}} p ↦ ℜ {\displaystyle p\mapsto \Re } p {\displaystyle p} s i {\displaystyle s_{i}} t i {\displaystyle t_{i}} ∈ Γ {\displaystyle \in \Gamma }
∑ p : s i → t i f p = r i ∀ ( s i , t i ) ∈ Γ . {\displaystyle \sum _{p:\,s_{i}\rightarrow t_{i}}{f_{p}}=r_{i}\;\;\forall (s_{i},t_{i})\in \Gamma .} 特定のエッジを通過する流れは 次のように定義される。 G {\displaystyle G}
f e , Γ , R = ∑ p : e ∈ p f p . {\displaystyle f_{e,\Gamma ,R}=\sum _{p:\,e\in p}{f_{p}}.} 簡潔にするために、文脈から明らかな 場合は 書きます。 f e {\displaystyle f_{e}} Γ , R {\displaystyle \Gamma ,R}
定義（ナッシュ均衡フロー） 。フローは、 次の場合 に限り ナッシュ 均衡 フロー である。 f Γ , R {\displaystyle f_{\Gamma ,R}} ∀ ( s i , t i ) ∈ Γ {\displaystyle \forall (s_{i},t_{i})\in \Gamma } ∀ p , q {\displaystyle \forall p,q} s i {\displaystyle s_{i}} t i {\displaystyle t_{i}}
f p > 0 ⇒ ∑ e ∈ p l e ( f e ) ≤ ∑ e ∈ q l e ( f e ) . {\displaystyle f_{p}>0\Rightarrow \sum _{e\in p}{l_{e}(f_{e})}\leq \sum _{e\in q}{l_{e}(f_{e})}.} この定義は、正規形ゲームにおける混合戦略ナッシュ均衡のサポートについて述べたことと密接に関連しています。
定義（フローの条件付き福祉） と を、 同じ集合 と に関連付けられた における 2つのフローとする 。以下では、表記を明瞭にするため、添え字を省略する。 によって生じる遅延を グラフに固定すると仮定する。 に関する の 条件付き福祉は 次のように定義される。 f Γ , R {\displaystyle f_{\Gamma ,R}} f Γ , R ∗ {\displaystyle f_{\Gamma ,R}^{*}} G {\displaystyle G} Γ {\displaystyle \Gamma } R {\displaystyle R} f {\displaystyle f} f ∗ {\displaystyle f^{*}} f {\displaystyle f}
w f ( f ∗ ) = ∑ e ∈ E f e ∗ ⋅ l e ( f e ) {\displaystyle w^{f}(f^{*})=\sum _{e\in E}{f_{e}^{*}\cdot l_{e}(f_{e})}} 事実 1 . ナッシュ均衡フロー と他の任意のフロー が
与えられた場合 、 f {\displaystyle f} f ∗ {\displaystyle f^{*}} w ( f ) = w f ( f ) ≤ w f ( f ∗ ) {\displaystyle w(f)=w^{f}(f)\leq w^{f}(f^{*})}
証明（背理法） . と仮定する 。定義により、 w f ( f ∗ ) < w f ( f ) {\displaystyle w^{f}(f^{*})<w^{f}(f)}
∑ i = 1 k ∑ p : s i → t i f p ∗ ⋅ ∑ e ∈ p l e ( f e ) < ∑ i = 1 k ∑ p : s i → t i f p ⋅ ∑ e ∈ p l e ( f e ) {\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})} 。 とは 同じ集合に関連付けられている ので 、 f {\displaystyle f} f ∗ {\displaystyle f^{*}} Γ , R {\displaystyle \Gamma ,R}
∑ p : s i → t i f p = ∑ p : s i → t i f p ∗ = r i ∀ i . {\displaystyle \sum _{p:s_{i}\rightarrow t_{i}}f_{p}=\sum _{p:s_{i}\rightarrow t_{i}}f_{p}^{*}=r_{i}\;\;\forall i.} したがって、 、 、 と なるような から への 1 組のパス と 2 つのパスが存在する必要があります。 ( s i , t i ) {\displaystyle (s_{i},t_{i})} p , q {\displaystyle p,q} s i {\displaystyle s_{i}} t i {\displaystyle t_{i}} f p ∗ > f p {\displaystyle f_{p}^{*}>f_{p}} f q ∗ < f q {\displaystyle f_{q}^{*}<f_{q}}
∑ e ∈ p l e ( f e ) < ∑ e ∈ q l e ( f e ) . {\displaystyle \sum _{e\in p}l_{e}(f_{e})<\sum _{e\in q}l_{e}(f_{e}).} 言い換えれば、フローが よりも低い厚生を達成できるのは、 から への異なるコストを持つ 2つの経路があり 、 が の フローの一部を高コストの経路から低コストの経路へ迂回させる場合のみです。この状況は、 が ナッシュ均衡フローである という仮定と明らかに矛盾します 。QED f ∗ {\displaystyle f^{*}} f {\displaystyle f} s i {\displaystyle s_{i}} t i {\displaystyle t_{i}} f ∗ {\displaystyle f^{*}} f {\displaystyle f} f {\displaystyle f}
事実 1 では、集合 上に特定の構造を想定していないことに注意してください 。 L {\displaystyle L}
事実 2 . 任意の 2 つの実数とが与えられる と 、 x {\displaystyle x} y {\displaystyle y} x ⋅ y ≤ x 2 + y 2 / 4 {\displaystyle x\cdot y\leq x^{2}+y^{2}/4}
証明 . これは真の不等式を表す別の方法です 。 QED ( x − y / 2 ) 2 ≥ 0 {\displaystyle (x-y/2)^{2}\geq 0}
定理 .線形遅延を伴う 一般化ルーティング問題の純粋な PoAは . ( G , L ) {\displaystyle (G,L)} ≤ 4 / 3 {\displaystyle \leq 4/3}
証明 。この定理は、任意のナッシュ均衡フロー に対して 、 が他の任意のフローである、ということと等価である。定義により 、 f {\displaystyle f} w ( f ) ≤ ( 4 / 3 ) ⋅ min f ∗ { w ( f ∗ ) } {\displaystyle w(f)\leq (4/3)\cdot \min _{f^{*}}\{w(f^{*})\}} f ∗ {\displaystyle f^{*}}
w f ( f ∗ ) = ∑ e ∈ E f e ∗ ( a e ⋅ f e + b e ) {\displaystyle w^{f}(f^{*})=\sum _{e\in E}f_{e}^{*}(a_{e}\cdot f_{e}+b_{e})} = ∑ e ( a e f e f e ∗ ) + ∑ e ∈ E f e ∗ b e . {\displaystyle =\sum _{e}(a_{e}f_{e}f_{e}^{*})+\sum _{e\in E}f_{e}^{*}b_{e}.} 事実2を使うと、
w f ( f ∗ ) ≤ ∑ e ∈ E ( a e ⋅ ( ( f e ∗ ) 2 + ( f e ) 2 / 4 ) ) + ∑ e ∈ E f e ∗ ⋅ b e {\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}} = ( ∑ e ∈ E a e ( f e ∗ ) 2 + f e ∗ b e ) + ∑ e ∈ E a e ( f e ) 2 / 4 {\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} ≤ w ( f ∗ ) + w ( f ) 4 , {\displaystyle \leq w(f^{*})+{\frac {w(f)}{4}},} 以来
( 1 / 4 ) ⋅ w ( f ) = ( 1 / 4 ) ⋅ ∑ e ∈ E f e ( a e f e + b e ) {\displaystyle (1/4)\cdot w(f)=(1/4)\cdot \sum _{e\in E}f_{e}(a_{e}f_{e}+b_{e})} = ( 1 / 4 ) ⋅ ∑ e ∈ E ( f e ) 2 + ( 1 / 4 ) ⋅ ∑ e ∈ E f e b e ⏟ ≥ 0 . {\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 w f ( f ∗ ) ≤ w ( f ∗ ) + w ( f ) / 4 {\displaystyle w^{f}(f^{*})\leq w(f^{*})+w(f)/4}
証明では、関数が 線形であるという仮定を多用していることに注意してください。実際には、より一般的な事実が成り立ちます。 L {\displaystyle L}
定理 . グラフと次数 の多項式遅延関数と非負係数を持つ 一般化ルーティング問題が与えられた場合 、純粋なPoAは です 。 G {\displaystyle G} d {\displaystyle d} ≤ d + 1 {\displaystyle \leq d+1}
PoAは とともに成長できることに注意する 。単位フローを仮定した次の図の例を考えてみよう。ナッシュ均衡フローの社会厚生は1である。しかし、 のときに社会厚生が最大となる。 この場合、 d {\displaystyle d} x = 1 − 1 / d + 1 {\displaystyle x=1-1/{\sqrt {d+1}}}
w = ( 1 − 1 d + 1 ) d ⋅ ( 1 − 1 d + 1 ) + 1 ⋅ 1 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}}}} = ( ( 1 − 1 d + 1 ) d + 1 ) d + 1 + 1 d + 1 {\displaystyle =\left(\left(1-{\frac {1}{\sqrt {d+1}}}\right)^{\sqrt {d+1}}\right)^{\sqrt {d+1}}+{\frac {1}{\sqrt {d+1}}}} ≤ e − d + 1 + 1 d + 1 . {\displaystyle \leq e^{-{\sqrt {d+1}}}+{\frac {1}{\sqrt {d+1}}}.} この量は、 無限大に近づくとゼロに近づきます。 d {\displaystyle d}
さらなる結果 PoAの上限は、ゲームがいわゆる 平滑性 不等式を満たすことが示されれば得られる。より正確には、コスト最小化ゲームが ( λ , μ )-平滑性 （λ≥0かつμ<1）を持つとは、不等式が成り立つことを意味する。
∑ i = 1 n C i ( a i ∗ , a − i ) ≤ λ C ( a ∗ ) + μ C ( a ) {\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]
参照
参考文献 ^ ab Koutsoupias, Elias; Papadimitriou, Christos (2009年5月). 「最悪ケース均衡」. Computer Science Review . 3 (2): 65– 69. doi :10.1016/j.cosrev.2009.04.003. 2016年3月13日時点のオリジナルよりアーカイブ。 2010年9月12日 閲覧 。 ^ M. ゴーマンス、V. ミラークニ、A. ベッタ、 シンクの平衡と収束 、FOCS 05 ^ Chung, Christine; Ligett, Katrina; Pruhs, Kirk; Roth, Aaron (2008), Monien, Burkhard; Schroeder, Ulf-Peter (eds.), "The Price of Stochastic Anarchy" , Algorithmic Game Theory , vol. 4997, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 303– 314, doi :10.1007/978-3-540-79309-0_27, ISBN 978-3-540-79308-3 、 2023年12月29日 閲覧 ^ P. Dubey. ナッシュ均衡の非効率性. Math. Operat. Res., 11(1):1–8, 1986 ^ ラフガーデン、ティム (2015年11月2日). 「アナーキーの代償の本質的な堅牢性」 . ACMジャーナル . 62 (5): 1– 42. doi :10.1145/2806883. ISSN 0004-5411. ^ Phillips, Matthew; Marden, Jason R. (2018年7月). 「凹型コストシェアリングゲームにおける設計トレードオフ」. IEEE Transactions on Automatic Control . 63 (7): 2242– 2247. Bibcode :2018ITAC...63.2242P. doi :10.1109/tac.2017.2765299. ISSN 0018-9286. S2CID 45923961. ^ シートン、ジョシュア・H.、ブラウン、フィリップ・N. (2023). 「アナーキーの代償の本質的脆弱性について」. IEEE Control Systems Letters . 7 : 3573–3578 . Bibcode :2023ICSL....7.3573S. doi :10.1109/LCSYS.2023.3335315. ISSN 2475-1456.
さらに読む
コア コンセプト ゲーム 数学 ツール 検索 アルゴリズム 主要人物
