アナーキーの代償(price of anarchy)とは、各参加者が自分の費用だけを考えて選んだ均衡のうち最悪のものの社会費用を、全体で最小にした費用で割った比である。利用者を連続量とみなす経路選択では、遅れが非負の係数の 1 次関数なら網の形によらず比は $4/3$ 以下で、平行な 2 辺の Pigou の網で $4/3$ に等しくなる。一般の遅れの関数の族でも比は Pigou 型の 2 辺の網の比の上限で抑えられ、次数 $d$ 以下の非負の係数の多項式ではその上限が $d\to\infty$ で $d/\log d$ 程度に増える。有限人数のゲームでは滑らかさの不等式から上界が得られ、粗い相関均衡まで同じ上界が成り立ち、1 次の遅れの有限人数の経路選択では比は $5/2$ 以下である。
前提知識: Nash均衡, Braessのパラドックス, 相関均衡
アナーキーの代償(price of anarchy)は、各参加者が自分の費用だけを考えて行動した結果(均衡)の社会全体の費用が、全体で協調したときの最小の費用の何倍になりうるかを測る比で、最悪の均衡の費用を最適な費用で割った値 として定める。E. Koutsoupias と C. Papadimitriou が 1999 年に導入し、名前は Papadimitriou による(KP99。帰属は KP17 第 8 章の注、p. 164 による)。
この比の大きさは、ゲームの細部よりも費用の関数の形で決まることが多い。代表的な結果は、利用者を連続量とみなす経路選択(Braessのパラドックス の Wardrop の模型)で、遅れが非負の係数の 1 次関数なら、網の形によらず比が $\frac43$ 以下になることである(T. Roughgarden と É. Tardos)。この記事では、この定理を証明し、一般の遅れの関数での上界(Pigou の上界)、需要を 2 倍にした最適流との比較、有限人数のゲームでの「滑らかさ」による上界と、その相関均衡への拡張を扱う。
$N$ 人の参加者 $i=1,\dots,N$ が、空でない有限集合 $A_i$ から行動 $a_i$ を選ぶとする。$A:=A_1\times\cdots\times A_N$ とし、参加者 $i$ の費用を $C_i\colon A\to[0,\infty)$ とする。$a\in A$ の第 $i$ 成分を $b\in A_i$ に替えた組を $(b,a_{-i})$ と書く。
定義から $1\le\mathrm{PoS}\le\mathrm{PoA}$ である。アナーキーの代償は最悪の均衡、安定性の代償は最良の均衡を測る(後者の用語は Anshelevich らによる。KP17 第 8 章の注、p. 165)。
利用者が連続量の経路選択では、Braessのパラドックス の記号(品種 $j$ の交通量 $r_j$、流れ $f$、辺の流れ $F_e$、遅れ $\ell_e$、最小の遅れ $d_j(f)$、総費用 $C(f)=\sum_eF_e\ell_e(F_e)$)を使う。遅れの関数が連続で広義単調増加なら、Wardrop 均衡は存在し、その総費用は均衡によらない(Braessのパラドックス の定理「均衡の特徴づけ・存在・一意性」)。そこで、$f$ を Wardrop 均衡、$f^*$ を最適流として、アナーキーの代償を $C(f)/C(f^*)$ と定める($C(f^*)>0$ とする)。
$s$ から $t$ への平行な 2 辺があり、遅れが $\ell_1(x)=x$、$\ell_2(x)=1$、交通量が $1$ とする。辺 1 の流れを $x$ とすると、$x< 1$ なら辺 2 は使われていてその遅れ $1$ は辺 1 の遅れ $x$ より大きいので均衡でない。$x=1$ では両方の遅れが $1$ で均衡であり、総費用は $1$ である。最適流は $x^2+(1-x)$ を最小にする $x=\frac12$ で、総費用は $\frac34$ である。よってアナーキーの代償は $\frac43$ である。KP17 Example 8.1.2(pp. 150–151)の例で、名前は A. C. Pigou の 1920 年の本による(同 第 8 章の注、p. 164)。
主定理の証明は、Braessのパラドックス の補題「変分不等式による言い換え」と同じ次の不等式から始まる。$f$ を Wardrop 均衡、$g$ を任意の流れとし、その辺の流れを $G_e$ とすると
$$
\sum_eF_e\,\ell_e(F_e)\le\sum_eG_e\,\ell_e(F_e)\qquad(1)
$$
である。実際、右辺は $\sum_Pg_P\,\ell_P(f)$ に等しく、$\ell_P(f)\ge d_j(f)$($P$ は品種 $j$ の路)から $\sum_jr_jd_j(f)=C(f)$ 以上である。(1) は「遅れを均衡の値に固定すれば、どの流れも均衡より速くはならない」と読める。
利用者が連続量の経路選択(品種は何個でもよい)で、各辺の遅れが $\ell_e(x)=a_ex+b_e$($a_e,b_e\ge0$)であるとする。$f$ が Wardrop 均衡なら、どの流れ $g$ についても
$$
C(f)\le\frac43\,C(g)
$$
である。とくにアナーキーの代償は $\frac43$ 以下で、ex-poa-pigou によりこの上界は改善できない。
単一品種の場合が KP17 Theorem 8.1.8(p. 153)で、品種が複数の場合は同書の Exercise 8.1(pp. 165–166)にあたる。定理は Roughgarden–Tardos(RT02)によるもので、ここで与えた証明は Correa–Schulz–Stier-Moses による(KP17 第 8 章の注、p. 165)。
$b_e=0$(遅れが流れに比例する)ならアナーキーの代償は $1$、すなわち均衡は最適流である。実際 (1) と $xy\le\frac{x^2+y^2}2$ から
$$
C(f)\le\sum_ea_eG_eF_e\le\frac12\sum_ea_eG_e^2+\frac12\sum_ea_eF_e^2=\frac12C(g)+\frac12C(f)
$$
となり、$C(f)\le C(g)$ である(KP17 Remark 8.1.9 と Exercise 8.3、pp. 153・166)。比 $\frac43$ には、流れによらない遅れ $b_e$ が要る。
thm-poa-affine の仮定のもとで、網 $G$ に辺を足した網を $H$ とする(共通の辺の遅れと品種は同じ)。$H$ の均衡の総費用は $G$ の均衡の総費用の $\frac43$ 倍以下である。
$H$、$G$ の均衡を $f_H$、$f_G$、最適流を $f_H^*$、$f_G^*$ とする。thm-poa-affine と、辺を足しても最適流の総費用が増えないこと(Braessのパラドックス の命題「辺を足しても最適流の総費用は増えない」)から $C(f_H)\le\frac43C(f_H^*)\le\frac43C(f_G^*)\le\frac43C(f_G)$ である。$\square$
単一品種の場合が KP17 Corollary 8.1.10(p. 153)である。Braessのパラドックス の例(近道の遅れが $0$)では総費用が $\frac32$ から $2$ になり、比はちょうど $\frac43$ である。
遅れの関数の族 $\mathcal L$(どれも連続、広義単調増加で $0$ 以上)に対し
$$
\alpha(\mathcal L):=\sup\Bigl\{\frac{r\,\ell(r)}{x\,\ell(x)+(r-x)\,\ell(r)}\ \Bigm|\ \ell\in\mathcal L,\ r>0,\ \ell(r)>0,\ 0\le x\le r\Bigr\}
$$
とおく(上の集合が空なら $\alpha(\mathcal L):=1$)。$x=r$ で比は $1$ なので $\alpha(\mathcal L)\ge1$ である。分母は $(r-x)\ell(r)\ge0$ と $x\ell(x)\ge0$ の和で、$x< r$ なら正、$x=r$ なら $r\ell(r)>0$ である。$\alpha(\mathcal L)$ は、辺 1 に遅れ $\ell$、辺 2 に定数の遅れ $\ell(r)$ を置いた交通量 $r$ の Pigou 型の網のアナーキーの代償の上限である(下の証明の 2)。
$\alpha:=\alpha(\mathcal L)< \infty$ とする。
1:まず、$\ell\in\mathcal L$ と $x,r\ge0$ について
$$
x\,\ell(r)\le x\,\ell(x)+\Bigl(1-\frac1\alpha\Bigr)r\,\ell(r)\qquad(2)
$$
を示す。$\ell(r)=0$ なら左辺は $0$ で、右辺は $0$ 以上である。$x\ge r$ なら $\ell(x)\ge\ell(r)$ なので $x\ell(r)\le x\ell(x)$ で、(2) が成り立つ。$x< r$ かつ $\ell(r)>0$ なら $r>0$ で、$\alpha$ の定義から $r\ell(r)\le\alpha\bigl(x\ell(x)+(r-x)\ell(r)\bigr)$ であり、両辺を $\alpha$ で割って移項すると (2) になる。
各辺で $x=G_e$、$r=F_e$ として (2) を足し、(1) と合わせると
$$
C(f)\le\sum_eG_e\,\ell_e(F_e)\le\sum_eG_e\,\ell_e(G_e)+\Bigl(1-\frac1\alpha\Bigr)\sum_eF_e\,\ell_e(F_e)=C(g)+\Bigl(1-\frac1\alpha\Bigr)C(f)
$$
となり、$C(f)\le\alpha\,C(g)$ を得る。
2:$\beta< \alpha$ なので、定義の集合の中に、比が $\beta$ より大きい $\ell$、$r$、$x$ がある。$s$ から $t$ への平行な 2 辺に遅れ $\ell$ と定数 $\ell(r)$ を置き、交通量を $r$ とする。全部を辺 1 に流すと、辺 1 の遅れは $\ell(r)$ で辺 2 と等しいので均衡で、総費用は $r\ell(r)$ である。辺 1 に $x$、辺 2 に $r-x$ を流すと総費用は $x\ell(x)+(r-x)\ell(r)$ なので、最適流の総費用はこれ以下である。よってアナーキーの代償は $\beta$ より大きい。$\square$
単一品種の形が KP17 Definition 8.1.13 と Theorem 8.1.15(pp. 155–156)で、そこでは交通量 $r$ ごとの量 $A_r(\mathcal L)$ で述べられている。凸性の仮定のもとで Roughgarden が示し、Correa–Schulz–Stier-Moses がその仮定を外した(同 第 8 章の注、p. 165)。(2) を各辺で足し合わせるだけで網の形が消えるので、上界は網によらない。
1 次関数の族では、$\ell(x)=ax+b$ の分母は $x=\frac r2$ で最小値 $\frac34ar^2+br$ をとるので、比は $\frac{ar^2+br}{\frac34ar^2+br}\le\frac43$ であり、$\alpha=\frac43$ である。thm-poa-affine はこの特別な場合でもある。
$d\ge1$ とし、$\mathcal L_d$ を、次数 $d$ 以下で係数がすべて $0$ 以上の多項式の全体とする。このとき
$$
\alpha(\mathcal L_d)=\alpha_d:=\Bigl(1-d\,(d+1)^{-(d+1)/d}\Bigr)^{-1}
$$
であり、$\alpha_1=\frac43$、$\alpha_2=\frac{3\sqrt3}{3\sqrt3-2}\approx1.6258$、$\alpha_3\approx1.8956$ である。$\alpha_d$ は $d$ について増加し、$d\to\infty$ で $\alpha_d\sim\frac d{\log d}$ である。
$k\ge0$ について $m_k:=\min_{0\le y\le1}\bigl(y^{k+1}+1-y\bigr)$ とおく。$y^{k+2}\le y^{k+1}$ なので $m_{k+1}\le m_k$ で、$m_0=1$ である。$k\ge1$ では $y^{k+1}+1-y$ の導関数 $(k+1)y^k-1$ は $y_k:=(k+1)^{-1/k}$ でだけ $0$ になり、そこで最小なので $m_k=1+y_k\bigl(\frac1{k+1}-1\bigr)=1-k(k+1)^{-(k+1)/k}=\alpha_k^{-1}$ である。
$\ell(x)=\sum_{k=0}^dc_kx^k$($c_k\ge0$)、$r>0$、$\ell(r)>0$、$0\le x\le r$ とし、$x=ry$ とおく。分母は $\sum_kc_kr^{k+1}\bigl(y^{k+1}+1-y\bigr)\ge\sum_kc_kr^{k+1}m_k\ge m_d\sum_kc_kr^{k+1}=m_d\,r\ell(r)$ なので、比は $m_d^{-1}=\alpha_d$ 以下である。$\ell(x)=x^d$、$r=1$、$x=y_d$ で比はちょうど $\alpha_d$ になる。$m_k$ が減少するので $\alpha_d$ は増加する。漸近形は、$(d+1)^{-1/d}=1-\frac{\log(d+1)}d+O\bigl(\frac{(\log d)^2}{d^2}\bigr)$ から $m_d=\frac{\log(d+1)}d+\frac1{d+1}+O\bigl(\frac{(\log d)^2}{d^2}\bigr)\sim\frac{\log d}d$ となることによる。$\square$
KP17 Figure 8.6(p. 154)は、Pigou 型の網で辺 1 の遅れを $x^d$ にしたときの比を $d=2$ でおよそ $1.6$、$d=3$ でおよそ $1.9$ とし、$d\to\infty$ での漸近形を $d/\ln d$ としている。遅れの次数が上がるほど、均衡は最適から離れうる。
どんな遅れの関数でも、アナーキーの代償は「交通量を 2 倍にすること」で償える。
遅れの関数は連続で広義単調増加で $0$ 以上とする。$f$ を交通量 $r_j$ の Wardrop 均衡、$g$ を同じ網で交通量を $2r_j$ にした任意の流れとすると、$C(f)\le C(g)$ である。
各辺で $G_e\bigl(\ell_e(F_e)-\ell_e(G_e)\bigr)\le F_e\,\ell_e(F_e)$ を示す。$G_e\le F_e$ なら、$\ell_e(G_e)\ge0$ から左辺は $G_e\ell_e(F_e)\le F_e\ell_e(F_e)$ 以下である。$G_e>F_e$ なら $\ell_e(F_e)\le\ell_e(G_e)$ で左辺は $0$ 以下である。$e$ について足すと $\sum_eG_e\ell_e(F_e)\le C(g)+C(f)$ である。一方 $g$ は品種 $j$ に $2r_j$ を流し、その路の遅れ($f$ で測る)はどれも $d_j(f)$ 以上なので、$\sum_eG_e\ell_e(F_e)=\sum_Pg_P\ell_P(f)\ge\sum_j2r_jd_j(f)=2C(f)$ である。合わせて $2C(f)\le C(g)+C(f)$ を得る。$\square$
単一品種の場合が KP17 Theorem 8.1.16(p. 156)で、定理は Roughgarden–Tardos による(同 第 8 章の注、p. 165)。各辺の容量を 2 倍にすれば中央の制御がなくても足りる、とも読める(同 Remark 8.1.17)。
利用者が有限人なら、1 人の変更が費用を変えるので、上の (1) は使えない。代わりに、均衡の各人が「最適な組での自分の行動」に替える場合と比べる。
純粋 Nash 均衡(1 点に集中した分布)は粗い相関均衡である。相関均衡 は、その記事の命題「外れ方の関数による言い換え」で外れ方を定数の写像に限った条件(利得を $-C_i$ とする)を満たすので、粗い相関均衡である。混合戦略の Nash 均衡も、独立な分布として相関均衡なので粗い相関均衡である。
$(\lambda,\mu)$ 滑らかなゲームの粗い相関均衡 $p$ について
$$
\mathbb E_p[\mathrm{SC}(a)]\le\frac\lambda{1-\mu}\,\mathrm{OPT}
$$
である。とくに純粋 Nash 均衡、混合戦略の Nash 均衡、相関均衡のアナーキーの代償はどれも $\frac\lambda{1-\mu}$ 以下である。
粗い相関均衡の条件で $b=a_i^*$ とし、$i$ について足すと、滑らかさの不等式の期待値をとって
$$
\mathbb E_p[\mathrm{SC}(a)]=\sum_i\mathbb E_p[C_i(a)]\le\mathbb E_p\Bigl[\sum_iC_i(a_i^*,a_{-i})\Bigr]\le\lambda\,\mathrm{OPT}+\mu\,\mathbb E_p[\mathrm{SC}(a)]
$$
である。$1-\mu>0$ で割ればよい。$\square$
KP17 Definition 8.4.5 と Theorem 8.4.7(pp. 162–163)にあり、枠組みは Roughgarden による(Rou09。帰属は KP17 第 8 章の注、p. 165)。同書の Theorem 8.4.7 (3) は、各参加者が後悔が $o(T)$ の学習の手続きで $T$ 回繰り返し遊ぶとき、社会費用の時間平均にも同じ上界が $o(1)$ の誤差つきで成り立つことを示している。
有限人数の経路選択:有向グラフで、参加者 $i$ が自分の出発点から到着点への単純な有向路 $a_i$ を選び、辺 $e$ を $n_e(a)$ 人が使うとき 1 人あたりの遅れを $\ell_e(n)=p_en+q_e$($p_e,q_e\ge0$)、$C_i(a):=\sum_{e\in a_i}\ell_e(n_e(a))$ とする。これは ポテンシャルゲーム の混雑ゲームの例なので、純粋 Nash 均衡がある。
このゲームは $(\frac53,\frac13)$ 滑らかであり、粗い相関均衡(とくに純粋 Nash 均衡)のアナーキーの代償は $\frac52$ 以下である。
まず、$0$ 以上の整数 $m,n$ について $m(n+1)\le\frac53m^2+\frac13n^2$、すなわち $5m^2+n^2-3m(n+1)\ge0$ を示す。$m=0$ なら $n^2\ge0$、$n=0$ なら $m(5m-3)\ge0$($m$ は $0$ か $1$ 以上の整数)、$m=n=1$ なら $0$ である。それ以外では $m+n\ge3$ で、$5m^2+n^2-3m(n+1)=(2m-n)^2+m(m+n-3)\ge0$ である。
$a^*$ を最適な組、$a$ を任意の組とし、$n_e:=n_e(a)$、$n_e^*:=n_e(a^*)$ とおく。参加者 $i$ が $a_i^*$ に替えると、$a_i^*$ の各辺の利用者は高々 $n_e+1$ 人なので $C_i(a_i^*,a_{-i})\le\sum_{e\in a_i^*}\bigl(p_e(n_e+1)+q_e\bigr)$ である。$i$ について足すと、各辺 $e$ は $n_e^*$ 回数えられるので
$$
\sum_iC_i(a_i^*,a_{-i})\le\sum_e\Bigl(p_en_e^*(n_e+1)+q_en_e^*\Bigr)\le\sum_e\Bigl(\frac53p_e(n_e^*)^2+\frac13p_en_e^2+q_en_e^*\Bigr)
$$
である。$\mathrm{SC}(a^*)=\sum_en_e^*(p_en_e^*+q_e)$、$\mathrm{SC}(a)=\sum_en_e(p_en_e+q_e)\ge\sum_ep_en_e^2$ なので、右辺は $\frac53\mathrm{SC}(a^*)+\frac13\mathrm{SC}(a)$ 以下である。thm-poa-smooth により上界は $\frac{5/3}{1-1/3}=\frac52$ である。$\square$
KP17 Claim 8.4.2、Lemma 8.4.3、Theorem 8.4.4、Remark 8.4.6(pp. 161–162)にあり、同書は §8.4 の結果を Christodoulou–Koutsoupias と Awerbuch–Azar–Epstein に帰している(第 8 章の注、p. 165)。
頂点 $u,v,w$ の有向グラフで、辺 $uv$、$uw$、$vw$、$wv$ の遅れを $\ell(n)=n$、辺 $vu$、$wu$ の遅れを $0$ とする。4 人の参加者が、それぞれ $u\to v$、$u\to w$、$v\to w$、$w\to v$ を移動する(KP17 Figure 8.11、p. 160。頂点の名を替えてある)。各参加者の単純な路は、直通の辺と、2 本の辺の路(順に $u\,w\,v$、$u\,v\,w$、$v\,u\,w$、$w\,u\,v$)の 2 本である。
どの路も遅れ $\ell(n)=n$ の辺を少なくとも 1 本含むので、各人の費用は $1$ 以上である。全員が直通の辺を使うと各辺の利用者は 1 人で、費用は各 $1$、社会費用は $4$ であり、これが最小である。一方、全員が 2 本の辺の路を使うと、$uv$ と $uw$ の利用者が 2 人、$vw$ と $wv$ が 1 人で、費用は順に $3,3,2,2$、社会費用は $10$ である。直通に替えると、1 人目は $uv$ が 3 人になって費用 $3$、2 人目も $3$、3 人目は $vw$ が 2 人になって $2$、4 人目も $2$ で、誰も費用を下げられない。よって純粋 Nash 均衡で、比は $\frac{10}4=\frac52$ である。
| 外した仮定 | 例 | 成り立たなくなる結論 |
|---|---|---|
| 遅れが 1 次関数(thm-poa-affine) | Pigou の網で $\ell_1(x)=x^2$、$\ell_2\equiv1$ | アナーキーの代償が $\alpha_2\approx1.6258>\frac43$ |
| 利用者が連続量(thm-poa-affine) | ex-poa-atomic | アナーキーの代償が $\frac52>\frac43$ |
| $\mathcal L$ が定数関数を含む(thm-poa-pigou の 2) | $\mathcal L=\{ax\mid a\ge0\}$ | $\alpha(\mathcal L)=\frac43$ だが、この族のどの網でもアナーキーの代償は $1$ |
| 交通量を 2 倍にする(thm-poa-demand) | Pigou の網で $\ell_1(x)=x^{10}$、$\ell_2\equiv1$、比較する流れの交通量を $\frac32$ 倍にする | 交通量 $\frac32$ の流れで総費用が約 $0.78473$ になり、交通量 $1$ の均衡の総費用 $C(f)=1$ を下回る |
$\ell_1(x)=x^2$:$\ell_1$ は連続で単調増加だが 1 次でない。全部を辺 1 に流すと両辺の遅れが $1$ で均衡、総費用は $1$ である。辺 1 に $y=3^{-1/2}$ を流すと総費用は $y^3+1-y=1-\frac2{3\sqrt3}\approx0.61510$ で、prop-poa-polynomial の $m_2$ に等しい。比は $\alpha_2\approx1.6258$ である。
比例する遅れ:$\ell_e(x)=a_ex$ は定数関数を含まない族である。thm-poa-affine の後で示したとおり均衡は最適流なので、アナーキーの代償は $1$ である。一方、$\ell(x)=x$、$r=1$、$x=\frac12$ で比は $\frac43$ なので $\alpha(\mathcal L)=\frac43$ である。
交通量 $\frac32$ 倍:交通量 $1$ の均衡は全部を辺 1 に流すもので、総費用は $1$ である。交通量 $\frac32$ で、辺 1 に $y=11^{-1/10}\approx0.78679$、辺 2 に $\frac32-y$ を流すと、総費用は $y^{11}+\frac32-y\approx0.78473$ で、$1$ より小さい。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 均衡を 1 つ求めて最適と比べればよい | 有限人数では均衡ごとに費用が違い、アナーキーの代償は最悪の均衡で測る | ex-poa-atomic の均衡の社会費用は $4$ と $10$ |
| 上界 $\frac43$ は網が小さいときの話である | 網の形によらない | thm-poa-pigou の証明は辺ごとの不等式の和 |
| 有限人数でも上界は $\frac43$ である | 1 次の遅れでも $\frac52$ まで悪くなる | prop-poa-atomic、ex-poa-atomic |
| アナーキーの代償が大きいと均衡は必ず悪い | 最良の均衡は安定性の代償で測り、ずっと良いことがある | ex-poa-atomic では最適な組も均衡 |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する