完整後設資料紀錄
DC 欄位語言
dc.contributor.authorChen, Po-Anen_US
dc.contributor.authorLu, Chi-Jenen_US
dc.date.accessioned2017-04-21T06:56:08Z-
dc.date.available2017-04-21T06:56:08Z-
dc.date.issued2016-12en_US
dc.identifier.issn0004-3702en_US
dc.identifier.urihttp://dx.doi.org/10.1016/j.artint.2016.09.002en_US
dc.identifier.urihttp://hdl.handle.net/11536/132792-
dc.description.abstractDifferent types of dynamics have been studied in repeated game play, and one of them which has received much attention recently consists of those based on "no-regret" algorithms from the area of machine learning. It is known that dynamics based on generic no-regret algorithms may not converge to Nash equilibria in general, but to a larger set of outcomes, namely coarse correlated equilibria. Moreover, convergence results based on generic no-regret algorithms typically use a weaker notion of convergence: the convergence of the average plays instead of the actual plays. Some work has been done showing that when using a specific no-regret algorithm, the well-known multiplicative updates algorithm, convergence of actual plays to equilibria can be shown and better quality of outcomes in terms of the price of anarchy can be reached for atomic congestion games and load balancing games. Are there more cases of natural no-regret dynamics that perform well in suitable classes of games in terms of convergence and quality of outcomes that the dynamics converge to? We answer this question positively in the bulletin-board model by showing that when employing the mirror-descent algorithm, a well-known generic no-regret algorithm, the actual plays converge quickly to equilibria in nonatomic congestion games. This gives rise to a family of algorithms, including the multiplicative updates algorithm and the gradient descent algorithm as well as many others. Furthermore, we show that our dynamics achieves good bounds on the outcome quality in terms of the price-of-anarchy type of measures with two different social costs: the average individual cost and the maximum individual cost. Finally, the bandit model considers a probably more realistic and prevalent setting with only partial information, in which at each time step each player only knows the cost of her own currently played strategy, but not any costs of unplayed strategies. For the class of atomic congestion games, we propose a family of bandit algorithms based on the mirror descent algorithms previously presented, and show that when each player individually adopts such a bandit algorithm, their joint (mixed) strategy profile quickly converges with implications. (C) 2016 Elsevier B.V. All rights reserved.en_US
dc.language.isoen_USen_US
dc.subjectMirror-descent algorithmen_US
dc.subjectNo-regret dynamicsen_US
dc.subjectConvergenceen_US
dc.subjectBandit modelen_US
dc.titleGeneralized mirror descents in congestion gamesen_US
dc.identifier.doi10.1016/j.artint.2016.09.002en_US
dc.identifier.journalARTIFICIAL INTELLIGENCEen_US
dc.citation.volume241en_US
dc.citation.spage217en_US
dc.citation.epage243en_US
dc.contributor.department資訊管理與財務金融系 註:原資管所+財金所zh_TW
dc.contributor.departmentDepartment of Information Management and Financeen_US
dc.identifier.wosnumberWOS:000387518000009en_US
顯示於類別:期刊論文