今回はゲーム理論にまつわる
プログラミング小噺です。

解説動画はこちら



ブライスのパラドックスとは

今回はプログラミングにまつわるものの小話です。


移動時間の短縮を目的としてネットワーク中に新たに
最短流路を作ったにもかかわらず、移動時間の短縮どころか
逆に移動時間が増加する場合があるという
交通工学におけるパラドックスのことです。


Start -  End の経路をドライバーが移動する事を考えます。
A,B2つのルートが存在します。




この状態ではA,Bルートともに
かかる時間は80分になっています。




ここで新たなルート A - B を作ります。
ここを通ると元々Start - End を80分で行けていたところが
70分に短縮されそうですが



みんな一番時間の掛からないルートを通ろうとして
逆に時間が掛かるようになっていまいます。



実際にこんな事になっていた道路が有ったようです。

この現象における重要なポイントは
ということです。

他のドライバーの行動を考えずに自身が最短経路を辿ろうとすると
逆に最適な状態にならない、というのがこのパラドックスにおける
重要なポイントです。

この考え方は、さまざまな分野で応用されています。

送電網
通信網
スポーツのチーム編成
選挙の投票 etc


プログラミングの分野でも表立って見えないですが
最適な状態を目指すために色々な所で使われています。

分散システムのリソース配分の最適化
レコメンドエンジンの推薦システム
広告配信のオークション
etc






今回はプログラミングに直接的には関わらないけど
裏ではすごく重要な考え方である
ブライスのパラドックスについて
お伝えしました。

今日はここまでです
それでは。

タグ ：

#プログラミング

#ゲーム理論

#ブライスのパラドックス

#パレート最適

#ナッシュ均衡