Full metadata record
DC FieldValueLanguage
dc.contributor.authorChen, Po-Anen_US
dc.contributor.authorLu, Chi-Jenen_US
dc.date.accessioned2019-08-02T02:24:16Z-
dc.date.available2019-08-02T02:24:16Z-
dc.date.issued2014-01-01en_US
dc.identifier.isbn978-1-4503-2738-1en_US
dc.identifier.urihttp://hdl.handle.net/11536/152435-
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 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? We answer this question positively by showing that when each player individually employs 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 quality of outcomes measured by two different social costs: the average individual cost and the maximum individual cost.en_US
dc.language.isoen_USen_US
dc.subjectMirror-descent algorithmen_US
dc.subjectNo-regret dynamicsen_US
dc.subjectConvergenceen_US
dc.titleGeneralized Mirror Descents in Congestion Games with Splittable Flowsen_US
dc.typeProceedings Paperen_US
dc.identifier.journalAAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMSen_US
dc.citation.spage1233en_US
dc.citation.epage1240en_US
dc.contributor.department交大名義發表zh_TW
dc.contributor.departmentNational Chiao Tung Universityen_US
dc.identifier.wosnumberWOS:000465207100158en_US
dc.citation.woscount0en_US
Appears in Collections:Conferences Paper