Generalized mirror descents with non-convex potential functions in atomic congestion games

Po-An Chen*

*Corresponding author for this work

研究成果: Conference article同行評審

摘要

When playing specific classes of no-regret algorithms (especially, multiplicative updates) in atomic congestion games, some previous convergence analyses were done with a standard Rosenthal potential function in terms of mixed strategy profiles (probability distributions on atomic flows), which may not be convex. In several other works, the convergence analysis was done with a convex potential function in terms of nonatomic flows as an approximation of the Rosenthal one in terms of distributions. It can be seen that though with different techniques, the properties from convexity help there, especially for convergence time. However, it would be always a valid question to ask if convergence can still be guaranteed directly with the Rosenthal potential function, playing mirror descents individually in atomic congestion games. We answer this affirmatively by showing the convergence, individually playing discrete mirror descents with the help of the smoothness property similarly adopted in many previous works for congestion games and Fisher (and some more general) markets and individually playing continuous mirror descents with the separability of regularization functions.

原文English
頁(從 - 到)558-562
頁數5
期刊CEUR Workshop Proceedings
1623
出版狀態Published - 1 一月 2016
事件9th International Conference on Discrete Optimization and Operations Research, DOOR 2016 - Vladivostok, Russian Federation
持續時間: 19 九月 201623 九月 2016

指紋 深入研究「Generalized mirror descents with non-convex potential functions in atomic congestion games」主題。共同形成了獨特的指紋。

引用此