ブレスのパラドックス

ブライスのパラドックスとは、道路網に1本以上の道路を追加すると、その道路を通る交通の流れが全体的に遅くなるという観察である。このパラドックスは1920年にアーサー・ピグーによって最初に発見され、^[1]後に1968年にドイツの数学者ディートリッヒ・ブライスにちなんで命名された。 ^[2]

このパラドックスは、電力網や生物系にも類似点があるかもしれない。理論上は、機能不全のネットワークを改善するには、その一部を取り除くことが効果的だと示唆されている。このパラドックスは、既存の主要道路を閉鎖すると 交通の流れが改善される例を説明するために使われてきた。

ドイツのルール大学の数学者ディートリッヒ・ブライスは、交通モデル化に取り組んでいたとき、新しい道路を追加すると道路網の流れが妨げられる可能性があることに気付きました。彼の考えは、各ドライバーがどのルートが最も速いかについて最適な利己的な決定を下す場合、ドライバーが可能な限り最短の移動時間を得るために近道が頻繁に選択される可能性があるというものでした。より正式には、ブライスの発見の背後にある考えは、ナッシュ均衡がネットワーク全体の最良の流れと一致しない可能性があるというものです。^[3]

このパラドックスは次のように述べられています。

「道路網の各地点について、そこから出発する車の数と目的地が与えられているとします。これらの条件下で、交通流の分布を推定します。ある通りが他の通りよりも好ましいかどうかは、道路の質だけでなく、交通流の密度にも左右されます。すべてのドライバーが自分にとって最も好ましいと思われる経路を取れば、結果として生じる走行時間は最小限である必要はありません。さらに、道路網の拡張によって交通が再配分され、個々の走行時間が長くなる可能性があることが例で示されています。」

移動体が利己的に経路を選択するときにネットワークに余分な容量を追加すると、全体的なパフォーマンスが低下する場合があります。これは、そのようなシステムのナッシュ均衡が必ずしも最適ではないためです。ネットワークの変更により、新しいゲーム構造が誘発され、（マルチプレイヤー）囚人のジレンマにつながります。ナッシュ均衡では、ドライバーには経路を変更するインセンティブがありません。システムがナッシュ均衡ではない間、個々のドライバーは経路を変更することで、それぞれの移動時間を改善できます。Braess のパラドックスの場合、ドライバーは全体的なパフォーマンスが低下しても、ナッシュ均衡に達するまで経路を切り替え続けます。

待ち時間関数が線形である場合、エッジを追加しても平衡時の合計移動時間が4/3以上悪化することはありません。^[4]

1983年、スタインバーグとザングウィルは、合理的な^{[第三者ソースが必要]}仮定の下で、一般的な交通ネットワークに新しいルートが追加されたときにブライスのパラドックスが発生する必要十分条件を示しました。（彼らの結果は、単一のリンクを追加する場合だけでなく、すべての新しいルートの追加に適用されることに注意してください。）結果として、彼らは、ランダムに新しいルートが追加されたときにブライスのパラドックスが発生する可能性は発生しない可能性とほぼ同じであると結論付けました。^[5]

ブレイスのパラドックスは道路網の縮小の場合にも当てはまり、個人の通勤時間の短縮につながる可能性がある。^[6]

韓国のソウルでは、清渓川修復事業の一環として高速道路が撤去された後、市内の交通が加速した。 ^[7]ドイツのシュトゥットガルトでは、1969年に道路網に投資された後、新しく建設された道路の一部が再び交通閉鎖されるまで、交通状況は改善しなかった。^[8] 1990年には、ニューヨーク市マンハッタンの42番街がアースデイのために一時的に閉鎖され、その地域の渋滞が緩和された。^[9] 2008年にユン、ガストナー、ジョンは、ボストン、ニューヨーク市、ロンドンで実際に渋滞が発生する可能性のある特定のルートを実演し、予測される移動時間を短縮するために閉鎖できる道路を指摘した。^[10] 2009年、ニューヨークはタイムズスクエアとヘラルドスクエアのブロードウェイを閉鎖する実験を行い、交通の流れが改善され、歩行者広場が恒久的に設置された。^[11]

2012年、イル・ド・フランス計画開発研究所のポール・ルクロアート氏は、「当初の懸念にもかかわらず、主要道路の撤去は、初期調整以上の交通状況の悪化を引き起こしません。交通の移行は限られており、予想を下回っています」と書いています。^[6]彼はまた、一部の自家用車による移動（および関連する経済活動）は公共交通機関に移行されず、単に消えてしまう（「蒸発」する）と指摘しています。^[6]

同じ現象は、道路閉鎖が都市計画の一環ではなく、事故の結果であった場合にも観察されました。2012年にルーアンでは橋が火災で破壊されました。その後2年間で他の橋の使用が増えましたが、橋を渡る車の総数は減少しました。^[6]

2012年、マックスプランク動力学・自己組織化研究所の科学者たちは、計算モデルを通じて、発電が分散化された送電ネットワークでこの現象が発生する可能性があることを実証しました。^[12]

2012年、Institut Néel（フランスCNRS）、INP（フランス）、IEMN（フランスCNRS）、UCL（ベルギー）の国際研究者チームがPhysical Review Letters ^{[13]に、Braessのパラドックスが}メソスコピック電子システムで発生する可能性があることを示す論文を発表しました。特に、ナノスケールのネットワークに電子の経路を追加すると、逆説的にその伝導度が低下することを示しました。これは、シミュレーションと走査ゲート顕微鏡を使用した低温での実験の両方で示されました。

バネとロープを使ったモデルは、吊り下げられた重りが、吊り下げシステムの張られたロープが切断されたにもかかわらず、高さを上昇できることを示しており、元のブライスのパラドックスと同じ数学的構造に従っています。^[14]

2 つの同一のバネを短いロープで直列に接続すると、バネ定数の合計は各バネの半分になり、一定の重量を吊るすと大きく伸びます。長いロープを 2 本たるませて、上部バネの下端を吊るした重量 (下部バネの下端) に、下部バネの上端を吊り下げ点 (上部バネの上端) に接続した場合も、この状態は変わりません。ただし、短いロープを切ると、長いロープが張って、2 つのバネが (機械的な意味で) 互いに平行になります。バネ定数の合計は各バネの 2 倍になり、長いロープの長さがそれほど長くない場合は、短いロープを切る前と比べて吊るした重量が実際に高くなります。

吊り下げシステムで張られたロープ (短いロープ) を切断したにもかかわらず、吊り下げられた重量が上昇するという事実は直感に反しますが、フックの法則とバネが直列および並列で機能する方法から導き出されます。

アディルソン・E・モッターと共同研究者は、ブライスのパラドックスの結果が生物系や生態系で頻繁に発生する可能性があることを実証した。^[15]モッターは、混乱したネットワークの一部を除去することでネットワークを救済できる可能性があると示唆している。絶滅危惧種の食物網の資源管理では、多くの種が次々と絶滅する可能性があるが、絶滅の危機に瀕した種をネットワークから選択的に除去することは、原理的には、さらなる絶滅の連鎖を防ぐという肯定的な結果をもたらす可能性がある。^[16]

バスケットボールでは、チームは得点までの経路のネットワークとみなすことができ、経路ごとに効率が異なり、スター選手がチーム全体の効率を低下させる可能性があると示唆されている。これは、道路網を通る移動時間全体を増加させる近道の使いすぎに似ている。得点の最大効率化のための提案された解決策は、スター選手がチームメイトとほぼ同じ数のシュートを打つことである。しかし、このアプローチは、元の論文で指摘されているように、確固とした統計的証拠によって裏付けられていない。^[17]

ブレイスのパラドックスは、レイヤー2ネットワークとしても知られるブロックチェーン決済チャネルネットワークで現れることが示されています。^[18]決済チャネルネットワークは、ブロックチェーンネットワークのスケーラビリティ問題に対する解決策を実装し、ブロックチェーンに記録することなく高レートの取引を可能にします。このようなネットワークでは、ユーザーはチャネルの両側に資金をロックすることでチャネルを確立できます。取引は、支払人と受取人を直接接続するチャネルを介して実行されるか、中間ユーザーがいくらかの手数料を要求するチャネルのパスを介して実行されます。

直感的には、新しいチャネルを開くとルーティングの柔軟性が高まりますが、新しいチャネルを追加すると手数料が高くなる可能性があり、同様に既存のチャネルを閉じると手数料が下がる可能性があります。この論文では、パラドックスの条件、パラドックスを緩和する方法、および実証分析を含む理論的分析を提示し、パラドックスの実際の出現とビットコインのライトニングネットワークへの影響を示しました。

右の図のような道路網を考えてみましょう。この道路では、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}$

端を運転する各人の移動時間が等しいと仮定すると、常に均衡が存在します。

を、人々がその辺を利用するときに、辺に沿って移動する各人の移動時間の式とします。人々が辺に沿って運転している交通グラフがあるとします。 、のエネルギーを次のように します。${\displaystyle L_{e}(x)}$${\displaystyle e}$${\displaystyle x}$${\displaystyle x_{e}}$${\displaystyle e}$${\displaystyle e}$${\displaystyle E(e)}$

${\displaystyle \sum _{i=1}^{x_{e}}L_{e}(i)=L_{e}(1)+L_{e}(2)+\cdots +L_{e}( x_{e})}$

( とします)。トラフィック グラフの総エネルギーを、グラフ内のすべてのエッジのエネルギーの合計とします。 ${\displaystyle x_{e}=0}$${\displaystyle E(e)=0}$

総エネルギーを最小化する経路を選択します。経路の選択肢は有限数あるため、このような選択が存在するはずです。それが均衡になります。

矛盾を避けるために、これが当てはまらないと仮定します。すると、ルートを変更して移動時間を改善できるドライバーが少なくとも 1 人存在します。元のルートが で、新しいルートが であると仮定します。を交通グラフの総エネルギーとし、ルートが削除されたときに何が起こるかを考えます。各エッジのエネルギーはだけ減少し、したがっては だけ減少します。これは、元のルートを取るのに必要な総移動時間です。次に新しいルートが追加されると、総エネルギーは新しいルートを取るのに必要な総移動時間だけ増加します。新しいルートは元のルートよりも短いため、は元の構成に比べて減少する必要があり、元のルート セットが総エネルギーを最小化したという仮定と矛盾します。 ${\displaystyle e_{0},e_{1},\ldots ,e_{n}}$${\displaystyle e'_{0},e'_{1},\ldots ,e'_{m}}$${\displaystyle E}$${\displaystyle e_{0},e_{1},...e_{n}}$${\displaystyle e_{i}}$${\displaystyle L_{e_{i}}(x_{e_{i}})}$${\displaystyle E}$${\textstyle \sum _{i=0}^{n}L_{e_{i}}(x_{e_{i}})}$${\displaystyle e'_{0},e'_{1},\ldots ,e'_{m}}$${\displaystyle E}$${\displaystyle E}$

したがって、総エネルギーを最小化する経路の選択は均衡です。

上記の証明は、最適応答ダイナミクスと呼ばれる手順の概要を示しています。この手順は、線形交通グラフの均衡点を見つけ、有限数のステップで終了します。アルゴリズムが「最適応答」と呼ばれるのは、アルゴリズムの各ステップでグラフが均衡点に達していない場合、一部のドライバーが他のすべてのドライバーの戦略に対して最適な応答を持ち、その応答に切り替えるためです。

最良応答ダイナミクスの疑似コード:

P をある交通パターンと
します。Pが平衡状態にない場合: P内の各ドライバーdについて、 Pの
    潜在エネルギーeを計算します。d
        が利用できる各代替パスpについて、
    n < eの場合、 dが経路pを取るときのパターンの
            ポテンシャルエネルギーnを計算します。
             Pを
                修正してdがパスpを
取るようにし、最上位を続行する

各ステップで、ある特定のドライバーが別のパス (「最適な応答」) を取ることでより良い結果が得られる場合、そうすることでグラフのエネルギーが厳密に減少します。どのドライバーも最適な応答を示さない場合、グラフは平衡状態にあります。グラフのエネルギーは各ステップで厳密に減少するため、最適な応答ダイナミクス アルゴリズムは最終的に停止する必要があります。

旅行時間関数が線形である場合、つまり何らかの場合、エネルギー最小化均衡における交通は最悪の場合、社会的に最適な交通の2倍悪くなります。^[19]${\displaystyle L_{e}(x)=a_{e}x+b_{e}}$${\displaystyle a_{e},b_{e}\geq 0}$

証明:を、関連するエネルギーと総移動時間を持つ交通構成とします。各エッジについて、エネルギー は等差数列の合計であり、等差数列の合計の公式を使用すると、 であることがわかります。が社会的に最適な交通流で、 がエネルギーを最小化する交通流である場合、不等式は であることを意味します。 ${\displaystyle Z}$${\displaystyle E(Z)}$${\displaystyle T(Z)}$${\displaystyle E(Z)\leq T(Z)\leq 2E(Z)}$${\displaystyle Z_{o}}$${\displaystyle Z_{e}}$${\displaystyle T(Z_{e})\leq 2E(Z_{e})\leq 2E(Z_{o})\leq 2T(Z_{o})}$

したがって、エネルギーを最小化する均衡の総移動時間は、最適な流れの場合よりも最大で 2 倍悪くなります。

Mlichtaich ^{[20]は、ネットワークが}直列並列グラフでない場合にのみ、Braessのパラドックスが発生する可能性があることを証明した。

• ダウンズ・トムソンのパラドックス – 道路網の改善に関連する交通工学のパラドックス
• ジェヴォンズのパラドックス – 効率化は需要の増加につながる
• マルケッティ定数 – 平均通勤時間
• ルイス・モグリッジの立場 – 道路交通理論
• 混雑ゲームにおける無秩序の代償- 混雑の外部性によって引き起こされる効率性の低下の定量分析。

• ブラス、D. (1969)。 「Über ein Paradoxon aus der Verkehrsplanung」[交通計画のパラドックスについて] (PDF)。Unternehmensforschung (ドイツ語)。12 : 258–268。（ナガーニー＆ワコルビンガーによる翻訳）
• カタリーナ・ベラガ＝ウェルビツキー：「Das Paradoxon von Braess in erweiterten Wheatstone-Netzen mit M/M/1-Bedienen」ISBN 3-89959-123-2 
• Braess 1968 の記事のドイツ語から英語への翻訳は、D. Braess、A. Nagurney、T. Wakolbinger による記事「交通計画のパラドックスについて」として、2005 年、Transportation Science 誌第 39 巻、446 ～ 450 ページに掲載されています。詳細情報は、2011 年 9 月 27 日にWayback Machineにアーカイブされています。
• アーヴァイン、AD（1993）。「ブライスのパラドックスはニューカムの問題をいかに解決するか」。国際科学哲学研究。7 （2 ）：141-160。doi ：10.1080/02698599308573460。
• Steinberg, R.; Zangwill, WI (1983). 「Braess のパラドックスの蔓延」.交通科学. 17 (3): 301. doi :10.1287/trsc.17.3.301.
• Rapoport, A.; Kugler, T.; Dugar, S.; Gisches, EJ (2009). 「混雑した交通ネットワークにおける経路の選択: Braess パラドックスの実験的検証」(PDF) . Games and Economic Behavior . 65 (2): 538–571. doi :10.1016/j.geb.2008.02.007.
• T. ラフガーデン。「無政府状態の代償」。MIT プレス、マサチューセッツ州ケンブリッジ、2005 年。

ウィキメディア・コモンズには、 Braess のパラドックスに関連するメディアがあります。

• ソフトウェアテストのパラドックス (2005 年 12 月) 直接リンク
• ディートリッヒ・ブライスのホームページ
• 道路網のパラドックス
• スプリングパラドックス、スティーブ・モールドによるYouTube動画。ブライスのパラドックスと、それと密接に関連するスプリングパラドックスについて説明しています。