| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2020-12-04 11:10 一般化費用分配モデル下での容量制約付きネットワーク設計ゲーム ○廣瀬暁之（名大）・土中哲秀（中大）・小野廣隆（名大）  COMP2020-21 |
|
| 抄録 | （和） | 費用分配型接続ゲーム(Cost-Sharing Connection Game, CSG)は, ネットワーク上のルーティングゲームの一種であり, このモデルでは, 費用と容量が与えられた辺を持つ有向グラフが与えられる時, 各エージェントはソースからシンクへのパスをできるだけ少ない費用で構築したいと考えている. 各辺の費用は費用分配関数に基づいてエージェントが共有する. 最も素直な費用分配関数は, かかる費用をエージェントの数で割ったものである. この関数は, 人々がものを共有する際にオーバーヘッドが発生しない理想的な設定をモデル化しているが, 現実には多かれ少なかれ何らかのオーバーヘッドが生じることが多い. 本論文では, 費用分配関数を一般化することで, より現実的な費用分配型接続ゲームの場面をモデル化する. 本研究では一般化された費用分配関数の下で, 合計費用と最大費用に関する無秩序の価 格 (Price of Anarchy, PoA) と安定性の価格 (Price of Stability, PoS) を考察した. 一般化した設定にも関わらず, 合計費用 における PoS を除いて, オーバーヘッドのない費用分配関数と同じ上下界とタイトな例が得られることを示す. また, 合計費用における PoS は, 一般化により log n から n に増加する. |
| （英） | The cost-sharing connection game is a variant of routing games on a network. In this model, given a directed graph with edge-costs and edge-capacities, each agent wants to construct a path from a source to a sink with low cost. The cost of each edge is shared by the users based on a cost-sharing function. One of simple cost-sharing functions is defined as the cost divided by the number of users. It models an ideal setting, where no overhead arises when people share things, though it might be quite rare in real life; it is more realistic to consider the setting that the cost that an agent should pay is the original cost per the number of the agents plus the overhead. In this paper, we model the more realistic scenario of cost-sharing connection games by generalizing cost-sharing functions. We investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of sum-cost and max-cost criteria under the generalized cost-sharing function. In spite of the generalization, we obtain the same bounds of PoA and PoS as the cost-sharing with no overhead except PoS of sum-cost, where the PoS of sum-cost increases from log n to n by the generalization. All the bounds that we give are tight. | |
| キーワード | （和） | 容量制約付きネットワーク設計ゲーム / ナッシュ均衡 / 無秩序の代償 / 安定性の代償 / 費用分配型接続ゲーム / / / |
| （英） | Capacitated Network Design Games / Nash Equilibrium / Price of Anarchy / Price of Stability / Cost-sharing connection games / / / | |
| 文献情報 | 信学技報, vol. 120, no. 276, COMP2020-21, pp. 24-27, 2020年12月. | |
| 資料番号 | COMP2020-21 | |
| 発行日 | 2020-11-27 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2020-21 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2020-12-04 - 2020-12-04 |
| 開催地（和） | オンライン開催 |
| 開催地（英） | Online |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2020-12-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 一般化費用分配モデル下での容量制約付きネットワーク設計ゲーム |
| サブタイトル（和） | |
| タイトル（英） | Capacitated Network Design Games on a Generalized Fair Allocation Model |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 容量制約付きネットワーク設計ゲーム / Capacitated Network Design Games |
| キーワード(2)（和/英） | ナッシュ均衡 / Nash Equilibrium |
| キーワード(3)（和/英） | 無秩序の代償 / Price of Anarchy |
| キーワード(4)（和/英） | 安定性の代償 / Price of Stability |
| キーワード(5)（和/英） | 費用分配型接続ゲーム / Cost-sharing connection games |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 廣瀬 暁之 / Toshiyuki Hirose / |
| 第1著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 土中 哲秀 / Tesshu Hanaka / |
| 第2著者 所属（和/英） | 中央大 (略称： 中大) Chuo University (略称： Chuo Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 小野 廣隆 / Hirotaka Ono / |
| 第3著者 所属（和/英） | 名古屋大学 (略称： 名大) Nagoya University (略称： Nagoya Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2020-12-04 11:10:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2020-21 |
| 巻番号（vol） | vol.120 |
| 号番号（no） | no.276 |
| ページ範囲 | pp.24-27 |
| ページ数 | 4 |
| 発行日 | 2020-11-27 (COMP) |
[研究会発表申込システムのトップページに戻る]