ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究 浅野 孝夫、渡邉敏正、今井桂子 中央大学、広島大学、中央大学 asano@ise.chuo-u.ac.jp 2007-05-14

Algorithmic Game Theory アルゴリズム的ゲーム理論 個人的効用と社会的効用の対立問題 に対するアルゴリズム的アプローチ Nash均衡の計算 様々なNash均衡がある 最良(最悪）のNash均衡 。

Best-Response Dynamics and Nash Equilibria E. Anshelevich, A. Dasgupta, J. Kleinberg, E.Tardos, T.Wexler and T. Roughgarden: The price of stability for network design with fair cost allocation, FOCS 2004, 295--304

問題の具体例 解1 解2 解3(最適解) 6+4+10+2+13=35 6+4+2+6+5+6+7=36 10 5 8 4 12 6 6 2 　　解2 　6+4+2+6+5+6+7=36 解3(最適解) 6+6+5+4+10=31 7

適用例2 (1.52, 改善案の出力) 1.52近似 改善案 (最適解) 26

合流フロー (confluent flow) 「フローが出ていく辺が1本以下」という条件を すべての点で満たすもの 分割可能フロー (splittable flow) 分割不可能フロー (unsplittable flow) 合流フロー (confluent flow) 10

合流フローの例 インターネット・ルーティング 避難経路 CDN（コンテンツ配信ネットワーク） ブロードキャスト　など 11

問題定義（混雑最小化問題） 入力 有向グラフ シンク 各点 の需要 0.3 0.1 0.2 0.3 0.2 0.4 0.5 12

問題定義（混雑最小化問題） 目的 すべての需要をシンクに流 す合流フローで，混雑が最 小になるものを求めること 点 の混雑 ： を流れるフローの合計 フローの混雑： 目的 すべての需要をシンクに流 す合流フローで，混雑が最 小になるものを求めること シンクで最大となる 0.3 0.1 0.6 0.2 0.3 0.2 1.4 0.4 0.5 13

問題定義（混雑最小化問題） 目的 すべての需要をシンクに流 す合流フローで，混雑が最 小になるものを求めること 点 の混雑 ： を流れるフローの合計 フローの混雑： 目的 すべての需要をシンクに流 す合流フローで，混雑が最 小になるものを求めること シンクで最大となる 0.3 0.1 1.1 0.2 0.3 0.2 0.9 0.4 0.5 14

問題定義（混雑最小化問題） 0.3 0.1 0.3 0.1 0.6 0.2 1.1 0.2 0.3 0.2 0.3 0.2 1.4 0.4 0.9 0.4 0.5 0.5 フローの混雑：1.4 フローの混雑：1.1 15

オンデマンド・データ・ブロードキャスティング ・サーバに数種類のページが存在し，クライアント からリクエストを受け取る ・サーバは，受け取ったリクエストに対し，ページを送信する (本研究では，各時刻に1ページしか送信できない) ページAを送ろう！ 時刻 1 ページAが 欲しい！ ページAが 欲しい！ ページBが欲しい！ 16

オンデマンド・データ・ブロードキャスティング ・サーバに数種類のページが存在し，クライアント からリクエストを受け取る ・サーバは，受け取ったリクエストに対し，ページを送信する (本研究では，各時刻に1ページしか送信できない) 送信するページをブロードキャストすることにより すべてのクライアントがページを受け取ることができる ページAを送ろう！ 時刻 1 ページAが 欲しい！ ページAが 欲しい！ ページBが欲しい！ 1 1 A A A 17 A

オンデマンド・データ・ブロードキャスティング 目的：すべてのリクエストを満たし，平均の レスポンスタイムを最小化する． 時刻 1 レスポンスタイム ページBが欲しい！ 1 1 A A A 18 A

時刻 までにすべてのリクエストが満たされる 平均レスポンスタイム最小化問題 例 時刻 ● 入力 ▲ ページ数 ▲ 時刻 の，ページ　 に 対するリクエスト数 A A B リクエストの最大到着時刻：　　 時刻　　 までにすべてのリクエストが満たされる 19

研究成果 1. An Improved Analysis of Goemans and Williamson's LP-relaxation for MAX SAT, Theoretical Computer Science, 339—353, 2006 2. 組合せ最適化：理論とアルゴリズム, （B. Korte and J. Vygen: Combinatorial Optimization: Theory and Algorithm, Springer, 3rd edition, 2006の日本語訳）シュプリンガー・フェアラーク東京, 1—664, 2005

３．アルゴリズムデザイン, (J. Kleinberg and E ３．アルゴリズムデザイン, (J. Kleinberg and E. Tados: Algorithm Design, Addison-Wesley, 2005の日本語訳）共立出版、2008 （予定） ４．近似アルゴリズム、アルゴリズム・サイエンスシリーズ、共立出版、2008（予定） ５．情報数学：コンピュータアルゴリズムの解析とその応用、コロナ社、2008（予定）

入力：重み付き（論理和形式の）クローズの集合 最大充足化問題(MAX SAT) 入力：重み付き（論理和形式の）クローズの集合 出力：　満たされるクローズの重みの和が　 最大になるような真偽割当　 最適解 が満たされる（重み２２）

最大充足化問題(MAX SAT)は値 が最大となるような真偽割当 を求める問題

MAX　SATに対する確率的方法

Johnsonの0.5-近似アルゴリズム

MAX SATの0-1整数計画問題定式化

MAX SATの線形計画緩和

一般にNP-困難な問題の多くは整数計画問題をして定式化できる． その整数条件を外して線形計画問題や 　半正定値計画問題に緩和して解き， その最適解の値を元の整数計画問題の最適解の値の下界あるいは上界として 　用いて，解の品質を保証するというものが，数理計画法に基づく近似アルゴリズム 　設計法である 数理計画法の双対理論に基づいた手法が，近似アルゴリズムでも適用可能になる 小数解を値を保存しつつ整数化する

f(y) GW 1 f(y)=y f2(y) Johnson f(y)=0.5 0.5 f1(y) f3(y) y 0.5 1

f(y) GW 1 f(y)=y f2(y) Johnson f(y)=0.5 0.5 f1(y) f3(y) y 0.5 1