論文紹介 Query Incentive Networks 2006/6/2 加藤公一

紹介する論文 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.

Insentive Networkとは？ ネットワーク上のノードが隣のノードにご褒美（Incentive）をちらつかせながら、情報を得ようとするモデル 例としては・・・ P2Pファイル共有 Winny, Share, etc. ソーシャルネットワークサービス Mixi, Orkut, etc.

$5あげるからBerryz工房の動画をくれ！ 例 $5あげるからBerryz工房の動画をくれ！ $1 Get! 動画？持ってるよ $4 $3 $5 $1 $1 $4あげるから動画さがしてくれない？ 答に到達できないと一銭も得られない（成功報酬） あまり搾取すると答までたどり着けなくなる確率が高くなる あまり遠慮すると、自分の子孫にたくさん持っていかれる ノード間のゲームと考える

問題 答を得るためには、どのくらいのutility（効用？）を用意すればよいか？ Utility：ルートノードが答を得るために用意するコスト

ここで考えるネットワークのモデル Tree Model 各ノードにが、ツリー構造を知っているとする Branching Model ツリー構造ではあるが、各ノードはその構造を知らない（地図がない状態） ノードにはActiveなものとinactiveなものがある 例：Mixiでログインしていないユーザ ノードあたりの子の数の期待値bが与えられる

ノードが受け取る報酬は整数値しかとらないとする 努力の価値 ノードが受け取る報酬は整数値しかとらないとする 答が見つかった後に、その答を送るためには、ノード通過ごとにコスト1かかる。（最初からそのコストを見込んで報酬を取り決める） さもないとZeno（ゼノン）のパラドックス 「用意すべきutilityは無限に小さくできる」 Utility r でうまくいって各ノードの戦略が　　ならば、utility 　のときは戦略　　　　にすればよい

例 報酬：$2 接続コスト：$1 報酬：$2 接続コスト：$1 報酬：$2 接続コスト：$1 Utility $10 $7 $4 $1

記号 T:木全体、 T’：アクティブなもの全体 ノードが答を持っていない確率： p Rarity（珍しさ？）： T’内での平均分岐数： b 与えられたIncentiveに対して、ノード 　が隣に渡す量（報酬関数、reward func.）： ノードvが子に報酬xを与えたときの成功確率： 失敗確率： （平均でn個に一つは答を持っている）

問題（より詳しく） 十分に高い確率で答を得るために必要なutility r は b と p の関数としてどうあらわされるか？

ゲーム理論としての視点 ノード がプレーヤ ： がとる戦略（関数！） ノードを通過すると報酬総額が減る ノード がプレーヤ 　　： がとる戦略（関数！） ノードを通過すると報酬総額が減る ノード に報酬 が与えられたとする。そのときのノード の取得利益の期待値は ナッシュ均衡：上式を最大にするような の集合 ナッシュ均衡は必ず存在し、唯一に定まることが証明される （Appendix）

結論 のとき ある程度以上の確率で成功するためには、必要なutilityは のとき （両方とも定数は b に依存） 分岐が激しいほうが少なくて済む （直感と異なる）

証明 記号の定義（以下全員が最適な戦略をとったと仮定して） ：誰も答を知らないと仮定したときに、報酬 r で到達する深さ ：ルートが答を知らず、しかも深さ j まで誰も答を知らない確率 ：　　　　　　　　　となる最小の r となることが証明できる 3 2 1 任意のjに対して となるrが存在する は任意の について定義される まずは の値について解析する

（breakpoint structure）の計算 帰納的に　　　　　　から　　　を計算する ルートが持っているutilityがrのときに、子ノードに　　　を与えたときのペイオフの期待値： 帰納法の仮定：　　　　　ならば ルート このとき、ルートにとっての最適戦略は子に与える報酬を　　　にすること このときの最適戦略 以上の深さまでは進まない はこのへんに！ 深さ　　まで到達可能

計算の続き

　の計算 ただし ：アクティブなものの率 子ノードの数は d 個 とすると で計算できる

のときの証明（概要） 失敗確率を上から押さえて、必要なutility r を上から押さえる Claim 4.3 について ならば 　　　のときの証明（概要） 失敗確率を上から押さえて、必要なutility r を上から押さえる Claim 4.3 について　　　　　　　　　　　ならば （つまり n が十分大きければ、） t を　　　　　　　　　　回繰り返せば から 　　へ到達可能 定義 は　　　　　　　　　　　　を満たす はある条件（Lemma 4.5で使う）を満たす Lemma 4.4 証明：Claim 4.3より明らか Lemma 4.5 ある定数　　　　が存在して　　　　　ならば 証明略

Theorem 4.6 b に依存する定数 が存在して ならば アイデア：すでに得られた と の関係式をうまく使う アイデア：すでに得られた　　と　　の関係式をうまく使う Breakpoint structure Lemma 4.5

のときの証明（概要） （再掲！） Claim 4.3 について ならば 　　　のときの証明（概要） （再掲！） Claim 4.3 について　　　　　　　　　　　ならば （つまり n が十分大きければ、） t を　　　　　　　　　　回繰り返せば から 　　へ到達可能 定義 は　　　　　　　　　　　　を満たす は任意（バウンド用） Lemma 4.7 証明：Claim 4.3より明らか Lemma 4.8 ある定数　　　　が存在して　　　　　ならば 証明略 Lemma 4.9 証明略（　　は任意なのでClaim 4.3は使えない）

Theorem 4.10 に依存する定数 が存在して ならば のそれぞれについて上から押さえる 定義： について： を数学的帰納法で証明 　　　に依存する定数 　　 　が存在して　　　　　　　　ならば のそれぞれについて上から押さえる 定義： について： を数学的帰納法で証明 のときはOK Lemma 4.7より

Theorem 4.10の続き について： は範囲　　　　　　　　　で最小値　　　を持つ

結論（再掲） のとき ある程度以上の確率で成功するためには、必要なutilityは のとき （両方とも定数は b に依存） 分岐が激しいほうが少なくて済む （直感と異なる）

研究の展開 　　　　のときはどうなるか？ Binary treeのときは それ以外のときは？ TreeではなくてDAGのときは？