Selfish Routing and the Price of Anarchy

Slides:



Advertisements
Similar presentations
組合せ最適化輪講 2.3 連結性 川原 純. 2.3 連結性 内容 – グラフ上の節点をすべてたどるアルゴリズム 計算機上でのグラフの表現 – 強連結成分を求めるアルゴリズム トポロジカル順序を求める方法も – k- 連結、 k- 辺連結について – 2- 連結グラフの耳分解について.
Advertisements

HBSP モデル上での 行列積を求めるアルゴリ ム 情報論理工学 吉岡健太.
統計学 第3回 西山. 第2回のまとめ 確率分布=決まっている分布の 形 期待値とは平均計算 平均=合計 ÷ 個数から卒業! 平均=割合 × 値の合計 同じ平均値でも 同じ分散や標準偏差でも.
到着時刻と燃料消費量を同時に最適化する船速・航路計画
情報システム ネットワークフロー.
第 4 章 : 一般回路の定理 4.5 可逆の理 可逆の理 キーワード : 可逆の理を理解する. 学習目標 :
コンピュータビジョン特論B - Graph Cuts - 永橋知行.
オンライン学習 Prediction Learning and Games Ch2
2009/12/4 グラフ (2) 第10講: 平成21年12月4日 (金) 4限 E252教室 コンピュータアルゴリズム.
ネットワーク理論講義補助資料 Text. 組合せ最適化とアルゴリズム 4.5 節 主・双対法 pp
    有限幾何学        第8回.
初級ミクロ経済学 -生産者行動理論- 2014年10月20日 古川徹也 2014年10月20日 初級ミクロ経済学.
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
An Algorithm for Enumerating Maximal Matchings of a Graph
アルゴリズムイントロダクション第5章( ) 確率論的解析
組合せ最適化 輪講 第1回 ERATO研究員 川原 純.
Extremal Combinatrics Chapter 4
Reed-Solomon 符号と擬似ランダム性
神奈川大学大学院工学研究科 電気電子情報工学専攻
「データ学習アルゴリズム」 第3章 複雑な学習モデル 3.1 関数近似モデル ….. … 3層パーセプトロン
JAG Regional Practice Contest 2012 問題C: Median Tree
第2回 内容 ハノイの塔―無向グラフと有向グラフ 教科書の 1.3 節 pp.7-12 参照
Bias2 - Variance - Noise 分解
Paper from PVLDB vol.7 (To appear in VLDB 2014)
リンクパワーオフによる光ネットワークの省電力化
「データ学習アルゴリズム」 第2章 学習と統計的推測 報告者 佐々木 稔 2003年5月21日 2.1 データと学習
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
Selfish Routing and the Price of Anarchy 第2回
Selfish routing 川原 純.
計算量理論輪講 岩間研究室 照山順一.
不安定な補償器を用いた 低剛性・高慣性比の 二慣性ねじり振動系における 外乱抑制制御性能の改善
A First Course in Combinatorial Optimization Chapter 3(前半)
早わかりアントコロニー最適化 (ACO: Ant Colony Optimization)
二分探索木によるサーチ.
チューリング機械 状態の有限集合 ヘッドの方向を表す。 L:1コマ左へ R:1コマ右へ テープ記号の有限集合 入力記号の有限集合 動作関数
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
情報学研究科 通信情報システム専攻 小野寺研究室 M1 奥村 佳弘
割当て問題 • 割当問題の記法・定式化 • 拡張 • 特殊ケース(マッチング) • 3種類のものを割当てる問題.
第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム
論文紹介 Query Incentive Networks
ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究
ネットワーク理論 Text. Part 3 pp 最短路問題 pp 最大流問題 pp.85-94
プロセス制御工学 7.多変数プロセスの制御 京都大学  加納 学.
7.4 Two General Settings D3 杉原堅也.
トーリックイデアルの グレブナ基底を求める アルゴリズム – F4およびF5 –
§ , How Bad Is Selfish Routing?
Extractor D3 川原 純.
Selfish Routing and the Price of Anarchy 4.3
計算量理論輪講 chap5-3 M1 高井唯史.
A First Course in Combinatorial Optimization Chapter
あるルーティングゲームの 最適戦略について
2016年度 有限幾何学 中間試験 問1 次のグラフを描け.(描けない場合は理由を述べよ) 各20点
第4章 データ構造 p.82 [誤] ハミルトニアン経路問題  [正] ハミルトン閉路問題 p.82,83 [誤] セールスパーソン問題
コンピュータ応用B 第3週の要点 第1章 データを抽出し集計する.
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
Selfish Routing 4章前半 岡本 和也.
第9章 学習アルゴリズムとベイズ決定側 〔3〕最小2乗法とベイズ決定側 発表:2003年7月4日 時田 陽一
大規模ネットワークに対する 実用的クラスタ発見アルゴリズムの開発
Max Cut and the Smallest Eigenvalue 論文紹介
7.8 Kim-Vu Polynomial Concentration
アルゴリズムとデータ構造 第2章 リスト構造 5月24日分
ヒープソート.
卒業研究 Treedecompositionを生成するヒューリスティックアルゴリズムの幅に関する評価実験
卒業研究 木分解ヒューリスティック アルゴリズムの性能評価実験 ~アルゴリズムの改良の考察と そのプログラム作成~
長岡技術科学大学 大学院 工学研究科 機械創造工学専攻 髙山 誠 指導教員 小林 泰秀 准教授
第4章 空間解析 2.ネットワーク分析 (2) 最大流問題
グラフの帯域幅連続多重彩色 を求めるアルゴリズム (Bandwidth Consective Multicolorings of Graphs) 西関研究室 西川和秀.
1 ひとりにしてくれ数 東北大学 大学院情報科学研究科 ◎鈴木 顕 内澤 啓 国立情報学研究所 情報学プリンシプル研究系 宇野 毅明.
Presentation transcript:

Selfish Routing and the Price of Anarchy 川原 純

かかります。車全体の平均遅延を最小にするために、 1.1 selfish routing とは (利己的ルーティング) 車でA町まで向かう途中… A町に行くには2つの道があります。 左の道は 30分 右の道は 50分 かかります。車全体の平均遅延を最小にするために、 あなたは右へ行ってください。 どちらへ行きますか? おせっかいなカーナビ

} 1.1 selfish routing とは 重要な事実 人は皆、自分にかかるコストを最小にするように動く selfish この差を (利己的ルーティング) 重要な事実 人は皆、自分にかかるコストを最小にするように動く selfish この差を 社会的繁栄の損失 とよぶ 神様が交通整理したときの平均遅延時間 人が利己的に動いたときの平均遅延時間 } selfish routing による社会的繁栄の損失を評価し、 なるべく損失を抑えるネットワークの設計が目標 交通網、コンピュータ ネットワークなど

1.2 研究の動機付けとなる2つの例題 ピゴーの例題 [Pigou, 1920] ブライスのパラドックス  [Braess, 1968]

1.2.1 ピゴーの例題 A町からB町まで行く道が2つある 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分

1.2.1 ピゴーの例題 10台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分

1.2.1 ピゴーの例題 10台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分 全車が下の道を選ぶ 簡単のため、この場合は全車が10分かかるとする

1.2.1 ピゴーの例題 60台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分

1.2.1 ピゴーの例題 60台 広いが、長い道 一律に60分かかる A B 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分 全車が下の道を選ぶ 平均時間は 60 分

1.2.1 ピゴーの例題 神様が交通整理をするなら selfish な振る舞いは社会的に最適であるとは限らない 30台 60台 広いが、長い道 一律に60分かかる A B 30台 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分 平均遅延時間 = 60 × 0.5 + 30 × 0.5 = 45 分

ナッシュフロー 30台 90台 広いが、長い道 広いが、長い道 一律に60分かかる A B 60台 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分 どちらを通っても60分かかる。 このようなバランスされた状態をナッシュ均衡と呼ぶ このフローをナッシュフローと呼ぶ 詳しい定義は2章で

無秩序さの代償 60台 広いが、長い道 一律に60分かかる A B 60台 狭いが、短い道 車の台数に比例した 時間がかかる 1台:1分 神様が交通整理すると45分のところ、60分かかる場合、 この比 60/45 = 1.333 を無秩序さの代償 (price of anarchy) と呼ぶ 詳しい定義は2章で

1.2.1 ピゴーの例題 以降、交通の総量は 1 と仮定 枝のコスト関数を c(x) で表す c(x) = 1 A B c(x) = x

1.2.2 ブライスのパラドックス 次のようなネットワークを考える c(x) = x v c(x) = 1 s t c(x) = 1 w

1.2.2 ブライスのパラドックス selfish な場合 c(x) = x v c(x) = 1 0.5 s t 0.5 c(x) = 1 w c(x) = x 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5

1.2.2 ブライスのパラドックス selfish な場合 社会的に最適な場合 c(x) = x v c(x) = 1 c(x) = x v 0.5 0.5 s t s t 0.5 0.5 c(x) = 1 w c(x) = x c(x) = 1 w c(x) = x 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5

1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v 0.5 s t c(x) = 0 0.5 c(x) = 1 w c(x) = x 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5

1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v 0.5 s c(x) = 0 t 0.5 c(x) = 1 w c(x) = x 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 の道: 0.5 + 0 + 0.5 = 1

1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v 0.4 s 0.2 c(x) = 0 t 0.4 c(x) = 1 w c(x) = x 0.6 1.6 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 0.6 1.6 の道: 0.5 + 0 + 0.5 = 1 0.6 0.6 1.2

1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v 0.3 s 0.4 c(x) = 0 t 0.3 c(x) = 1 w c(x) = x 0.7 1.7 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 0.7 1.7 の道: 0.5 + 0 + 0.5 = 1 0.7 0.7 1.4

1.2.2 ブライスのパラドックス selfish な場合 渋滞を緩和するため、 道路を追加することを考える c(x) = x v s 1 c(x) = 0 t c(x) = 1 w c(x) = x 1 2 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 1 2 の道: 0.5 + 0 + 0.5 = 1 1 1 2

1.2.2 ブライスのパラドックス selfish な場合 社会的に最適な場合 c(x) = x v c(x) = 1 c(x) = x v 0.5 s 1 c(x) = 0 t s c(x) = 0 t 0.5 c(x) = 1 w c(x) = x c(x) = 1 w c(x) = x selfish routing では、ネットワークに改良を 加えたつもりが、逆に性能が悪くなることがある 1 2 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 上の道: 0.5 + 1 = 1.5 下の道: 1 + 0.5 = 1.5 1 2 の道: 0.5 + 0 + 0.5 = 1 1 1 2

1.3 応用 1.3.1 交通ネットワーク 1.3.2 コンピュータネットワーク 1.3.3 物理、工学 1.3.1 交通ネットワーク 昔から研究されている。数百の論文がある 1.3.2 コンピュータネットワーク 当然、幅広く研究されている 1.3.3 物理、工学

1.3.3 物理への応用 理想バネ バネの長さは重りの重さに比例する

1.3.3 物理への応用

1.3.3 物理への応用

2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ

2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の発生源 2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の発生源 source s1 s2

2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の吸収 2.1 モデル 交通網のモデル: 有向グラフ G = (V, E) V は頂点集合、 E は有向辺集合、多重辺をもつ 交通の吸収 sink 交通の発生源 source t1 s1 t2 s2 single-commodity multicommodity source-sink のペア {si, ti } → 品種 i (commodity)

パスとパスの集合 v パス P1 P2 s1 t1 P3 w P5 s2 P4 t2 P1 : P2 : P3 : s1 → v → t1, s1 → v → w → t1, s1 → w → t1 P4 : P5 : s2 → w → t2, s2 → v → w → t2, : commodity i のパスの集合 = { P1, P2, P3 } = { P4, P5 } 1 2

フロー : フロー : パスP の流量 車の台数など(エージェント) P2 v P1 0.3 0.7 s1 t1 P3 w = 0.3 エージェントの数は十分大きいとする 0.3 0.7 s1 十分大きくない場合の 考察は4.4節 t1 P3 w = 0.3 1 P1 : P2 : P3 : s1 → v → t1, s1 → v → w → t1, s1 → w → t1 = 0.7 2 = 0 3 = { P1, P2, P3 } 1

枝ごとに見たフロー : 枝を流れるフロー e1 v 0.3 s1 0.7 e2 t1 e3 w = 0.3 + 0.7 = 1 = 0.7

フローの総量 ri : commodity i に流れるフローの総量(traffic rate) + + = 0.3 + 0.7 + 0 v 0.3 s1 0.7 e2 t1 が成り立つ時、 f を実現可能流と呼ぶ (feasible) e3 w P1 : P2 : P3 : s1 → v → t1, s1 → v → w → t1, s1 → w → t1 + + 1 2 3 = 0.3 + 0.7 + 0 = 1 = r1 = { P1, P2, P3 } なので f は実現可能流 1

コストとコスト関数 (車などの)エージェントが枝を流れるときにはコストがかかる ce1(x) = 1 e1 e2 ce2(x) = x 枝に流れる流量によってコストが決まる → コスト関数 c(x) : 枝 e のコスト関数 ce1(x) = 1 e1 e2 ce2(x) = x

コストとコスト関数 ce1(x) = 1 e1 e2 ce2(x) = x ce2(0.4) = 0.4 0.4 × 0.4 = 0.16 0.6 0.4 e2 ce2(x) = x 下の枝の(単位フロー当りの)コスト ce2(0.4) = 0.4 エージェントのそれぞれに0.4のコストがかかる 下の枝の全体コストは 0.4 × 0.4 = 0.16 上の枝の全体コストは Ce1(0.6) × 0.6 = 1 × 0.6 = 0.6

複数のフローとコスト ce3(x) = 3x ce1(x) = 1 ce2(x) = 1 :パス P の(単位フロー当りの)コスト P1 0.6 ce3(x) = 3x ce1(x) = 1 ce2(x) = 1 0.4 P1の総コストは c P1(f) = ce1(fe1) + ce3(fe3) 4 ×0.6 = 2.4 = ce1(0.6) + ce3(1) = 1 + 3×1 = 4

コスト関数の計算例 c P2 (f) = ce1(fe1) + ce3 (fe3) + ce5(fe5) ce1(x) = x v 0.3 P2 s ce3(x) = 0 t 0.7 P3 ce4(x) = 1 w ce5(x) = x :パス P の(単位フロー当りの)コスト c P2 (f) = ce1(fe1) + ce3 (fe3) + ce5(fe5) 1 0.7 0.7 = 1 + 0 + 0.7 = 1.7 同様に cP1(f) = 2, cP3(f) = 1.7

パスPの総コスト C(f) = cP1(f) fP1+ cP2 (f) fP2 + cP3(f) fP3 ce1(x) = x v : コスト関数 P1 0.3 P2 : 枝 e のコスト関数 s ce3(x) = 0 t 0.7 P3 :パス P のコスト ce4(x) = 1 w ce5(x) = x :全パスのコストの総和 0.3 0.7 C(f) = cP1(f) fP1+ cP2 (f) fP2 + cP3(f) fP3 2 1.7 1.7 = 2 × 0.3 + 1.7 × 0.7 + 1.7 × 0 = 1.79

発表時の注意 (紙の)資料は必ず作ること スライドは(式よりも)図を使う。 具体例、計算例を必ず出す(教科書にはないので自分で作る) (本スライド35ページ中、32ページに図があります) 具体例、計算例を必ず出す(教科書にはないので自分で作る) 記号が多いので、見せ方を工夫する たとえば、いきなり と書かれて 何だったか思い出せますか?

2.2 ナッシュフロー 定義2.2.1 がナッシュ均衡(ナッシュフロー)である def すべての commodity i について、 なるパス について、 すべての について が成り立つ - if = + if otherwise

2.2 ナッシュフロー ピゴーの例題 c(x) = 1 f = 0 A B f = 1 c(x) = x c下 = 1 c(x) = 1 ナッシュフローの 条件に合う c(x) = x

2.2 ナッシュフロー ブライスのパラドックス (枝を加えた直後) c(x) = x v c(x) = 1 0.5 s c(x) = 0 t c(x) = 0 t 0.5 c上 = 1.5 c(x) = 1 w c(x) = x c(x) = x v c(x) = 1 c中 = 1.1 0.5 – 0.1 s 0 + 0.1 c(x) = 0 t c上 ≦ c 中なので ナッシュフローの 条件に合わない 0.5 c(x) = 1 w c(x) = x

2.2 ナッシュフロー ブライスのパラドックス (安定した後) c(x) = x v c(x) = 1 s 1 c(x) = 0 t s 1 c(x) = 0 t c中 = 2 c(x) = 1 w c(x) = x c(x) = x v c(x) = 1 c上 = 2 0 + 0.1 s 1 - 0.1 c(x) = 0 t c中 ≦ c 上なので ナッシュフローの 条件に合う c(x) = 1 w c(x) = x

2.2 ナッシュフロー 定理2.2.2 すべての commodity i について、 すべての なるパス について、

2.2 ナッシュフロー 系2.2.3 各 commodity i について、 なるパス すべての , について、 コスト ci(f) をもつ