C03

ネットワーク上での社会的効用と
個人的効用の対立問題に対する
アルゴリズム的研究
浅野孝夫、渡邉敏正、今井桂子
中央大学、広島大学、中央大学
[email protected]
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
4
T. Roughgarden:
The price of stability for
network design with fair
cost allocation,
t
1
FOCS 2004, 295--304
s
5
8
v
1
1
t2
(a)
s
s
5
5
4
v
4
8
v
1 1
t1
8
1 1
t2
t1
s
2.5
2.5
4
v
8
1 1
t1
t2
t2
s
1 +
s
k
t
k agents
1 +
k
t
k agents
s
5
s
3 2.5 2.5 5
v
1 1
t2
t1
3
5
v
1 1
t1
t2
s
1 21
t1 t2
0 0
1
1 1
k
3 k-1
tk-1 tk
t3
0
0 0
s
1
1
1
1 21 3 k-1
k
tk-1 tk
t1 t2 t3
0 0 0
0 0
1 
最適解のコストは　1 　であるが、

唯一のNash均衡解は
コストがそれより
極めて大きい。
1 
問題の具体例
解1
10
5
4
12
6
6
2
6
4
7
6
12
10
13
6+4+10+2+13=35
8
解2
6+4+2+6+5+6+7=36
7
解3(最適解)
6+6+5+4+10=31
適用例2 (1.52, 改善案の出力)
1.52近似
26
改善案 (最適解)
合流フロー (confluent flow)
• 「フローが出ていく辺が1本以下」という条件を
すべての点で満たすもの
分割可能フロー
分割不可能フロー
合流フロー
(splittable flow)
(unsplittable flow)
(confluent flow)
10
合流フローの例
• インターネット・ルーティング
• 避難経路
• CDN（コンテンツ配信ネットワーク）
• ブロードキャストなど
11
問題定義（混雑最小化問題）
• 入力
– 有向グラフ
– シンク
– 各点の需要
0.3
0.1
0.3
0.2
0.2
0.4
0.5
12
問題定義（混雑最小化問題）


点の混雑
フローの混雑：
：
を流れるフローの合計
• 目的
すべての需要をシンクに流
す合流フローで，混雑が最
小になるものを求めること
シンクで最大となる
0.3
0.1
0.3
0.2
0.6 0.2
1.4 0.4
0.5
13
問題定義（混雑最小化問題）


点の混雑
フローの混雑：
：
を流れるフローの合計
• 目的
すべての需要をシンクに流
す合流フローで，混雑が最
小になるものを求めること
シンクで最大となる
0.3
0.1
0.3
0.2
1.1 0.2
0.9 0.4
0.5
14
問題定義（混雑最小化問題）
0.3
0.1
0.6 0.2
0.3
0.1
0.3
0.2
1.1 0.2
0.3
1.4 0.4
0.2
0.9 0.4
0.5
フローの混雑：1.4
0.5
フローの混雑：1.1
15
オンデマンド・データ・ブロードキャスティング
• ・サーバに数種類のページが存在し，クライアント
•
からリクエストを受け取る
・サーバは，受け取ったリクエストに対し，ページを送信する
(本研究では，各時刻に1ページしか送信できない)
ページAを送ろう！
時刻 01
ページAが
欲しい！
ページA
が
欲しい！
ページBが
欲しい！
16
オンデマンド・データ・ブロードキャスティング
• ・サーバに数種類のページが存在し，クライアント
•
からリクエストを受け取る
送信するページをブロードキャストすることにより
・サーバは，受け取ったリクエストに対し，ページを送信する
すべてのクライアントがページを受け取ることができる
(本研究では，各時刻に1ページしか送信できない)
ページAを送ろう！
時刻 1
ページA
が
1欲しい！ 1
ページAが
欲しい！
A
A
ページBが
欲しい！
A
A
17
オンデマンド・データ・ブロードキャスティング
目的：すべてのリクエストを満たし，平均の
レスポンスタイムを最小化する．
時刻 1
レスポンスタイム
1
1
A
ページBが
欲しい！
A
A
A
18
平均レスポンスタイム最小化問題
例
● 入力
▲ ページ数
▲ 時刻
n
t の，ページ p に
対するリクエスト数 rt
リクエストの最大到着時刻：
時刻
T n
時刻 0
T
までにすべてのリ
クエストが満たされる
p
A
A
B
r 2
A
0
r 1
B
0
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. Tados: Algorithm
Design, Addison-Wesley, 2005の日本語
訳）共立出版、2008 （予定）
４．近似アルゴリズム、アルゴリズム・サイエン
スシリーズ、共立出版、2008（予定）
５．情報数学：コンピュータアルゴリズムの解析
とその応用、コロナ社、2008（予定）
最大充足化問題(MAX SAT)
入力：重み付き（論理和形式の）クローズの集合
C1  x1 , C2  x2 , C3  x3 , C4  x1  x2 ,
w(C1 )  4, w(C2 )  2, w(C3 )  6, w(C 4 )  8,
C5  x2  x2 , C6  x1  x2  x3
w(C5 )  2, w(C6 )  6
出力：満たされるクローズの重みの和が
最大になるような真偽割当
( x1 , x2 , x3 )  (0,1,0) 最適解
C2 ,C3 ,C4 ,C6 が満たされる（重み２２）
最大充足化問題(MAX SAT)は値
F ( x)   j 1 w(C j )C j ( x)
m
が最大となるような真偽割当
x  ( x1 ,..., x2 n )  {0,1}
2n
を求める問題
（ mはクローズの個数）
MAX SATに対する確率的方法
x  ( p1,..., p2 n ) :ランダム真偽割当
p
C j (x )  1 
k
(
1

i 1
p
p ji ) :
( x で C j  x j1    x jk が満たされる確率 )
p
F (x )  
p
m
p
w
(
C
)
C
(
x
)
j
j
j 1
p
x の期待値
F ( x )  F ( x )を満たす真偽割当は条件
q
p
付き確率法で多項式時間で得られる
Johnsonの0.5-近似アルゴリズム
p
x : 各x i を 0.5の確率で１を割り当て
k個のリテラルからなる
る
クローズは
1  0.5k の確率で１になる (満たされる )
W kはk個のリテラル
期待値
F (x )  
p
からなるクローズの
m
p
j 1 w(C j )C j ( x )
 k 1 (1  0.5 )Wk  0.5W
k
重みの総和
Wはクローズ
の重みの総和
MAX SATの0-1整数計画問題定式化
max  j 1 w(C j ) z j
m
s.t.
y j1   y jk  z j
y i  yn  j  1
(C j  x j1   x jk )
( j  1,..., m)
y i {0,1}
z j  {0,1}
(i  1,...,2n)
( j  1,..., m)
MAX SATの線形計画緩和
max  j 1 w(C j ) z j
m
s.t.
y j1   y jk  z j
y i  yn  j  1
0  yi  1
0 z j 1
(C j  x j1   x jk )
( j  1,..., m)
(i  1,...,2n)
( j  1,..., m)
一般にNP-困難な問題の多くは整数
計画問題をして定式化できる．
• その整数条件を外して線形計画問題や
半正定値計画問題に緩和して解き，
• その最適解の値を元の整数計画問題の
最適解の値の下界あるいは上界として
用いて，解の品質を保証するというものが，
数理計画法に基づく近似アルゴリズム
設計法である
• 数理計画法の双対理論に基づいた手法
が，近似アルゴリズムでも適用可能になる
• 小数解を値を保存しつつ整数化する
C j  x j1    x jk が
最適解( y*, z*)で満たされる確率
C j ( y*)  1  i 1 (1  y *j i )
k
 y  y
 1  1 

k

k
k
k

 z 
1

  1  1    1  1   z *j



k
 k



m
*
最適解 ( y*, z*)での期待値 (W *   j 1 w(C j )z j )
*
ji

*
jk
m
*
j 1 w(C j ) C j ( y ) 
k 1
1

 1  W *  0.632W *
 e
*
j
k
  1  *
1  1    Wk
  k 
f(y)
GW
f(y)=y
1
f2(y)
Johnson
f(y)=0.5
0.5
f1(y)
f3(y)
0
0.5
y
1
f(y)
GW
f(y)=y
1
f2(y)
Johnson
f(y)=0.5
0.5
f1(y)
f3(y)
0
0.5
y
1

Download Report