文献

J-GLOBAL ID：202102227357351937   整理番号：21A0332083

一般化費用分配モデル下での容量制約付きネットワーク設計ゲーム

Capacitated Network Design Games on a Generalized Fair Allocation Model

著者 (3件)： 廣瀬暁之 (名古屋大) ,  土中哲秀 (中央大 理工) ,  小野廣隆 (名古屋大)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 120  号： 276(COMP2020 18-27)  ページ： 24-27 (WEB ONLY)  発行年： 2020年11月27日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 費用分配型接続ゲーム(Cost-Sharing Connection Game,CSG)は,ネットワーク上のルーティングゲームの一種であり,このモデルでは,費用と容量が与えられた辺を持つ有向グラフが与えられる時,各エージェントはソースからシンクへのパスをできるだけ少ない費用で構築したいと考えている.各辺の費用は費用分配関数に基づいてエージェントが共有する.最も素直な費用分配関数は,かかる費用をエージェントの数で割ったものである.この関数は,人々がものを共有する際にオーバーヘッドが発生しない理想的な設定をモデル化しているが,現実には多かれ少なかれ何らかのオーバーヘッドが生じることが多い.本論文では,費用分配関数を一般化することで,より現実的な費用分配型接続ゲームの場面をモデル化する.本研究では一般化された費用分配関数の下で,合計費用と最大費用に関する無秩序の価格(Price of Anarchy,PoA)と安定性の価格(Price of Stability,PoS)を考察した.一般化した設定にも関わらず,合計費用におけるPoSを除いて,オーバーヘッドのない費用分配関数と同じ上下界とタイトな例が得られることを示す.また合計費用におけるPoSは,一般化によりlog nからnに増加する.(著者抄録)

シソーラス用語： 制約条件 ,  *設計 ,  ネットワーク ,  *ゲーム ,  *Nash均衡 ,  状態 ,  安定条件 ,  容量制約 ,  無秩序性
準シソーラス用語： *ネットワーク設計 ,  安定性条件 ,  無秩序

分類 (1件)： 数値計算  (JE02000J)

引用文献 (14件)：

• Michal Feldman and Tom Ron. Capacitated network design games. Theory of Computing Systems, 57 : 576-597, 2015.
• Thomas Erlebach and Matthew Radoja. Further results on capaci-tated network design games. In Proceedings of 8th Symposium on Algorithmic Game Theory (SAGT2015), pages 57-68, 2015 .
• Michal Feldman and Geri Ofir. Do capacity constraints constrain coalitions? ACM Transactions on Economics and Computation,5(1):No.8, 2016.
• Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Éva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for net-work design with fair cost allocation. SIAM Journal on Computing,38(4):1602-1623, 2008.
• Robert J. Aumann. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games IV, Annals of Mathe-matical Study, 40:287-324, 1959.

タイトルに関連する用語 (5件)： 分配 ,  モデル ,  容量制約 ,  ネットワーク設計 ,  ゲーム