講演名 2010-06-21
ある2ソースネットワークにおけるブライスのパラドックス(システムと信号処理及び一般)
浜口 慎平, 金澤 尚史, 潮 俊光,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) コンピュータネットワークにおいて,プレイヤーが自分の遅延を最小にしようと伝送経路を選択することを利己的ルーチングという.最近,進化ゲームを用いて利己的ルーチングが解析されている.シングルソース-シングルシンクネットワークでは,ネットワークの伝送遅延を小さくしようと新たに枝を追加した結果,伝送遅延が大きくなってしまう場合があり,ブライスのパラドックスとして知られている.本報告では,マルチソース-シングルシンクネットワークにおける利己的ルーチングを複数集団レプリケータダイナミクスを用いて定式化し,ある2ソースネットワークにおいて,安定な平衡点となるフローを求める.そして,その2ソースネットワークにおいて枝を追加することにより,ブライスのパラドックスと同様のパラドックスが生じることを示す.
抄録(英) Selfish routing is a selfish route selection of players in computer networks. Players are assumed to select paths so as to minimize their data transfer latencies. Recently, selfish routing is analyzed as an evolutionary game. Additional edges are expected to reduce the average latency of data transfers, but such edges may increase the average latency in some single-source single-sink networks. Such a situation is well known as Braess's paradox. In this paper, we formulate multipopulation replicator dynamics of selfish routing in multisource single-sink networks. Then, in a two-source network, we find flows which correspond to stable equilibrium points of the replicator dynamics. We extend Braess's paradox to multisource single-sink networks and show that such a paradox occurs in a network which is added an edge to the two-source network.
キーワード(和) ブライスのパラドックス / 利己的ルーチン具 / 複数集団レプリケータダイナミクス / パレート最適
キーワード(英) Braess's paradox / selfish routing / multipopulation replicator dynamics / Pareto optimal
資料番号 CAS2010-9,VLD2010-19,SIP2010-30,CST2010-9
発行日

研究会情報
研究会 VLD
開催期間 2010/6/14(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 VLSI Design Technologies (VLD)
本文の言語 JPN
タイトル(和) ある2ソースネットワークにおけるブライスのパラドックス(システムと信号処理及び一般)
サブタイトル(和)
タイトル(英) Braess's Paradox in a Two-source Network
サブタイトル(和)
キーワード(1)(和/英) ブライスのパラドックス / Braess's paradox
キーワード(2)(和/英) 利己的ルーチン具 / selfish routing
キーワード(3)(和/英) 複数集団レプリケータダイナミクス / multipopulation replicator dynamics
キーワード(4)(和/英) パレート最適 / Pareto optimal
第 1 著者 氏名(和/英) 浜口 慎平 / Shimpei HAMAGUCHI
第 1 著者 所属(和/英) 大阪大学大学院基礎工学研究科
Graduate school of Engineering Science, Osaka University
第 2 著者 氏名(和/英) 金澤 尚史 / Takafumi KANAZAWA
第 2 著者 所属(和/英) 大阪大学大学院基礎工学研究科
Graduate school of Engineering Science, Osaka University
第 3 著者 氏名(和/英) 潮 俊光 / Toshimitsu USHIO
第 3 著者 所属(和/英) 大阪大学大学院基礎工学研究科
Graduate school of Engineering Science, Osaka University
発表年月日 2010-06-21
資料番号 CAS2010-9,VLD2010-19,SIP2010-30,CST2010-9
巻番号(vol) vol.110
号番号(no) 87
ページ範囲 pp.-
ページ数 6
発行日