このアイテムのアクセス数: 304
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| j.orl.2015.04.002.pdf | 73.92 kB | Adobe PDF | 見る/開く |
| タイトル: | Congestion games viewed from M-convexity |
| 著者: | Fujishige, Satoru Goemans, Michel Harks, Tobias Peis, Britta Zenklusen, Rico |
| 著者名の別形: | 藤重, 悟 |
| キーワード: | Congestion games Discrete convexity Best-response dynamics M-convex function Discrete convexity |
| 発行日: | 17-Apr-2015 |
| 出版者: | Elsevier B.V. |
| 誌名: | Operations Research Letters |
| 巻: | 43 |
| 号: | 3 |
| 開始ページ: | 329 |
| 終了ページ: | 333 |
| 抄録: | Congestion games have extensively been studied till recently. It is shown by Fotakis (2010) that for every congestion game on an extension-parallel network, any best-response sequence reaches a pure Nash equilibrium of the game in n steps, where n is the number of players. We show that the fast convergence of best-response sequences results from M-convexity (of Murota (1996)) of the potential function associated with the game. We also give a characterization of M-convex functions in terms of greedy algorithms. |
| 記述: | Presented at the Aussois Workshop on Combinatorial Optimization, January 5–9, 2015. relation url = preprint version |
| 著作権等: | © 2015 Elsevier. Licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International http://creativecommons.org/licenses/by-nc-nd/4.0/. NOTICE: this is the author's version of a work that was accepted for publication in Operations Research Letters. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Congestion games viewed from M-convexity, VOL 43, ISSUE 3, (2015) doi:10.1016/j.orl.2015.04.002. 許諾条件により本文は2018-04-17に公開. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 This is not the published version. Please cite only the published version. |
| URI: | http://hdl.handle.net/2433/197956 |
| DOI(出版社版): | 10.1016/j.orl.2015.04.002 |
| 関連リンク: | http://www.kurims.kyoto-u.ac.jp/preprint/file/RIMS1816.pdf |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。