Document

論文紹介
Query Incentive Networks
2006/6/2
加藤公一
1
紹介する論文
Jon M. Kleinberg and Prabhakar Raghavan. 2005.
Query Incentive
Networks. In FOCS '05: 46th Annual IEEE
Symposium on Foundations of
Computer Science. Pittsburgh, PA, 132--141.
2
Insentive Networkとは？
• ネットワーク上のノードが隣のノードにご褒美
（Incentive）をちらつかせながら、情報を得ようとす
るモデル
• 例としては・・・
– P2Pファイル共有
Winny, Share, etc.
– ソーシャルネットワークサービス
Mixi, Orkut, etc.
3
例
$5あげるから
Berryz工房の動
画をくれ！
動画？
持ってるよ
$1 Get!
$4
$5
$1
$3
$1
$4あげるから動画さ
がしてくれない？
答に到達できないと一銭も得られない（成功報酬）
あまり搾取すると答までたどり着けなくなる確率が高くなる
あまり遠慮すると、自分の子孫にたくさん持っていかれる
ノード間のゲームと考える
4
問題
答を得るためには、どのくらいのutility（効
用？）を用意すればよいか？
Utility：ルートノードが答を得るために用意するコスト
5
ここで考えるネットワークのモデル
• Tree Model
– 各ノードにが、ツリー構造を知っているとする
• Branching Model
– ツリー構造ではあるが、各ノードはその構造を知
らない（地図がない状態）
– ノードにはActiveなものとinactiveなものがある
• 例：Mixiでログインしていないユーザ
– ノードあたりの子の数の期待値bが与えられる
6
努力の価値
• ノードが受け取る報酬は整数値しかとらないとする
• 答が見つかった後に、その答を送るためには、ノー
ド通過ごとにコスト1かかる。（最初からそのコストを
見込んで報酬を取り決める）
さもないとZeno（ゼノン）のパラドックス
「用意すべきutilityは無限に小さくできる」
Utility r でうまくいって各ノードの戦略が f v ならば、utility r / a のとき
は戦略 f v / a にすればよい
7
例
報酬：$2
接続コスト：$1
Utility
$10
$7
報酬：$2
接続コスト：$1
報酬：$2
接続コスト：$1
$4
$1
8
記号
T:木全体、 T’：アクティブなもの全体
ノードが答を持っていない確率： p
Rarity（珍しさ？）： n  1 /(1  p)
（平均でn個に一つは答を持っている）
T’内での平均分岐数： b
与えられたIncentiveに対して、ノード vT が隣に渡す量（報酬
f   f v vT
関数、reward func.）： f v
ノードvが子に報酬xを与えたときの成功確率：  v (f , x)
失敗確率：  v (f , x)  1   v (f , x)
9
問題（より詳しく）
十分に高い確率で答を得るために必要な
utility r は b と p の関数としてどうあら
わされるか？
10
ゲーム理論としての視点
• ノード v がプレーヤ
• f v ： v がとる戦略（関数！）
• ノードを通過すると報酬総額が減る
ノード v に報酬 r が与えられたとする。そのときの
ノード v の取得利益の期待値は
(r  x  1) v (g, x)
ナッシュ均衡：上式を最大にするような g v の集合 g
ナッシュ均衡は必ず存在し、唯一に定まることが証明される
（Appendix）
11
結論
b  2 のとき
ある程度以上の確率で成功するためには、必要なutilityは
(n c )
b  2 のとき
ある程度以上の確率で成功するためには、必要なutilityは
O (log n)
（両方とも定数は b に依存）
分岐が激しいほうが少なくて済む
（直感と異なる）
12
証明
記号の定義（以下全員が最適な戦略をとったと仮定して）
 (r ) ：誰も答を知らないと仮定したときに、報酬 r で到達する深さ
ˆ ：ルートが答を知らず、しかも深さ j まで誰も答を知らない確率
j
u j ：  (r )  j  1 となる最小の r
 (u j )  j となることが証明できる
 (r )
3
2
1
r
u1
u2
u3
任意のjに対して (r )  j となるrが存在する
u j は任意の j  0 について定義される
まずは u j の値について解析する
13
u j （breakpoint structure）の計算
帰納的に u1 ,, u j から u j 1 を計算する
ルートが持っているutilityがrのときに、子ノードに u j
を与えたときのペイオフの期待値： l j (r )
l j (r )  (r  u j  1)(1  ˆj )
帰納法の仮定： r  u j 1 ならば l j 1 (r )  l j (r )    l1 (r )
l j (r )
l j 1 ( r )
j 1
r
ルート
u j 1
r
このとき、ルートに
とっての最適戦略
は子に与える報酬
を u j 1 にすること
このときの最適戦略 u j
r
j  1以上の深さまでは進まない
u j 1 はこのへんに！
uj
深さ
j まで到達可能
14
計算の続き
l j (r )
l j 1 ( r )
r
y j 1
u j 1  y j 1 
l j ( y j 1 )  l j 1 ( y j 1 )
( y j 1  u j  1)(1  ˆj )  ( y j 1  u j 1  1)(1  ˆj 1 )
1  ˆj
1

y j 1  u j 1  ˆj 1
u j  u j 1
15
ˆj
の計算
ˆj 1  (1  q(1  pˆj )) d
ただし b
 qd
q ：アクティブなものの率
子ノードの数は d 個
t ( x)  (1  q(1  px)) d
ˆ j  t


 t ( p)
とすると
で計算できる
j 1
16
b  2 のときの証明（概要）
失敗確率を上から押さえて、必要なutility r を上から押さえる
0   0   1   について pb(1  2bd )  1 ならば
（つまり n が十分大きければ、） t を (log(  1 /  0 )) 回繰り返せ
ば  1   0 から  1   1 へ到達可能
Claim 4.3
定義

 j 1  
I1  j 1   0 / n  ˆj
I2
0


 ˆj  1   0 / n
 0 は pb(1  2bd 0 )  1 を満たす
 0 はある条件（Lemma 4.5で使う）を満たす
Lemma 4.4 I  O(1), I  (log n)
1
2
証明：Claim 4.3より明らか
Lemma 4.5
1  ˆ j 1
ある定数 b1  2 が存在して j  I 2 ならば
 b1
1  ˆ
j
証明略
17
Theorem 4.6 b に依存する定数 c  1が存在して ˆj  1   ならば u j
 nc
アイデア：すでに得られた u j とˆj の関係式をうまく使う
u j 1  u j
u j  u j 1

y j 1  u j
u j  u j 1

y j 1
u j  u j 1
1

1  ˆ
j 1
Breakpoint structure
u j  u j 1 1  ˆj
1

y j 1  u j 1  ˆ
1  ˆ
1
1

1
b1  1
j
j 1
u j  u j  u j 1 
u j  u j 1 u j 1  u j  2
u j 1  u j  2
ui  ui 1  1 


 
iI 2 ui 1  ui  2
 b1  1 
Lemma 4.5
u2  u1

u1
u j  2  u j 3
u1
I2
 log n
 1 

 
 b1  1 
 n log(1/(b1 1))
18
b  2 のときの証明（概要）
（再掲！）
0   0   1   について pb(1  2bd )  1 ならば
（つまり n が十分大きければ、） t を (log(  1 /  0 )) 回繰り返せ
ば  1   0 から  1   1 へ到達可能
Claim 4.3
定義


 j 1    ˆ  1   
J1  j 1   0  ˆj
J2
j
0
 0 は pb(1  2bd 0 )  1 を満たす
 は任意（バウンド用）
Lemma 4.7 J1  (log n)
証明：Claim 4.3より明らか
Lemma 4.8
証明略
Lemma 4.9
1  ˆj 1
ある定数 b2  2 が存在して j  J1 ならば
 b2
1  ˆ
j
J 2  O(1)
証明略（  は任意なのでClaim 4.3は使えない）
19
Theorem 4.10
b,  に依存する定数 c' 1 が存在して ˆj  1   ならば u j  c' log n
J1 , J 2 のそれぞれについて上から押さえる
J1 について：
u j  u j 1 
定義： j1  max J1 , j2  max J 2
2(b2  1)
b2  2 を数学的帰納法で証明
j  2 のときはOK
y j 1  u j  1
u j  u j 1

1
1  ˆ
j 1
1  ˆ

1
1
b2  1
j
u j  u j 1
u j 1  u j  y j 1  u j  1 
Lemma 4.7より u j 
b2  1
j1
 (u  u
i 3
i
i 1
2
2(b2  1)
b2  2
)  O(log n)
20
Theorem 4.10の続き
J 2 について：
x  t (x) は範囲 [1   ,1   0 ] で最小値  を持つ
1
u j 1  u j  1 
1  ˆ
j 1
1  ˆ
 1
1
1
 1
ˆj2  ˆj2 1
j
1
 1   1
ˆj2  t (ˆj2 )
21
結論（再掲）
b  2 のとき
ある程度以上の確率で成功するためには、必要なutilityは
(n c )
b  2 のとき
ある程度以上の確率で成功するためには、必要なutilityは
O (log n)
（両方とも定数は b に依存）
分岐が激しいほうが少なくて済む
（直感と異なる）
22
研究の展開
• b  2 のときはどうなるか？
– Binary treeのときは O (log n)
– それ以外のときは？
• b  1 のときはどうなるか？
• TreeではなくてDAGのときは？
23

Download Report