非線形計画問題と potential game

Sandholm(2002)の面白い点．
==========
利用者均衡(UE: User Equilibrium)配分問題は等価な非線形計画問題[ENLP]として再定式化できる．この[ENLP]の目的関数(の正負を反転したもの) F(x) を potential function とする potential game [F] を考えるとき，[F]の Nash 均衡状態とはUE状態に他ならない．

このとき，potential game に対する以下の補題を用いれば，UE は利用者全てが「完全合理的で他の利用者の行動を完全に予測可能」でなくても，より自然な仮定の下で各利用者が myopic に行動を変化させた結果として実現することが保証される．

補題 1: potential game [F] について admissible な動学Δx(x) によって生成される解：
x⁽ⁿ⁺¹⁾=x⁽ⁿ⁾+Δx(x⁽ⁿ⁾)
のパス{x⁽¹⁾, x⁽²⁾, ...}は [F] の Nash 均衡（の一つ）に収束する．

ここで，ある動学 Δx(x) が potential game [F] に対して admissible であるためには

0. Δx は Lipschetz 連続である．
1. x が解であり，かつそのときに限り Δx(x) = 0．
2. Δx(x) の要素の総和は0である．
3. xi=0ならば Δxi(x)≧0．
4. x が解でない限り，Δx　とpotential function F(x) の勾配 ∇F の内積は厳密に正である．

という条件が必要十分である．
=======

以下は長江の放言．

この admissible であるための条件のうち，2.と3.は，生成されるすべての解{x⁽¹⁾, x⁽²⁾, ...}がフロー保存則を満足することを意味しており，4)は，ΔxとΔFのなす角が90度以下であることを意味している．従って，Δx(x⁽ⁿ⁾) は，元の非線形計画問題[ENLP]を繰り返し計算で解くときの x⁽ⁿ⁾における許容降下方向に他ならない．

そう考えると，調整ダイナミクス Δx を非線形計画問題[ENLP]を群知能的に解くための各エージェントに対するルールとして解釈することもできるような．

書くのに時間かかったくせにオチが弱い．

Sandholm, W. H. (2002) Evolutionary Implementation and Congestion Pricing, The Review of economic studies Vol.69(3), pp.667-689.