ダウンロード数: 232

このアイテムのファイル:
ファイル 記述 サイズフォーマット 
j.orl.2015.04.002.pdf73.92 kBAdobe 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
出現コレクション:学術雑誌掲載論文等

アイテムの詳細レコードを表示する

Export to RefWorks


出力フォーマット 


このリポジトリに保管されているアイテムはすべて著作権により保護されています。