2015/11/07 by Alexander Gasnikov, Gasnikov, Alexander, Evgenia Gasnikova +5
Computer Science · Mathematics · Physics and Astronomy · #Distributed Control Multi-Agent Systems #FOS: Mathematics #Mathematical Biology Tumor Growth #Opinion Dynamics and Social Influence #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.1511.02390
openalex publication_date 2015/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An universal primal-dual approach of description equilibriums in large class of hierarchical congestion population games is proposed. At the very core of the approach is hierarchy of enclosed to each other transport networks. In different time-scales corresponding logit dynamics on this networks is considered. This dynamics reflect restricted rationality of the agents. Searching of equilibrium configuration to the multi-level convex optimization problem is reduced (in other words variational principle for these class of the games/models is formulated). Then the dual problem is formulated. This problem has natural interpretation in turn and it is more computationally attractive then the primal one. So an effective primal-dual method for this problem is proposed. This method is based on the composite fast gradient method. Due to primal-duality the solution of the primal problem from the dual iterative process is recovered. To fulfil one iteration of this method the rather complex problem of calculation characteristic function on graph is solved. A special technique (smooth version of Bellman--Ford approach to the shortest path problem) is proposed (based on some ideas of Yu. Nesterov) that allows to do it in a cheap manner. It also should be mentioned that different tricks of small parameters methods are actively used.