06064138

j

06064138 Christodoulou, George Mirrokni, Vahab S. Sidiropoulos, Anastasios Convergence and approximation in potential games. Theor. Comput. Sci. 438, 13-27 (2012). 2012 Elsevier Science Publishers, Amsterdam EN high dimensional data nonlinear dimensionality reduction manifold embedding technique geometry of data Isomaps maximum variance unfolding locally linear embedding local tangent space alignment Laplacian eigenmaps Hessian locally linear embedding diffusion maps

doi:10.1016/j.tcs.2012.02.033

The paper addresses the field of game theory and, in particular, convergence and approximation within potential games. Convergence speed to approximately optimal states is investigated within selfish routing games and cut games. The authors provide bounds in terms of the number of rounds, model the sequential interaction between players by a best-response walk in the state graph; the goal is to bound the social value of the states at the end of these walks -- by taking into account the cut and the total happiness as the social functions. Ruxandra Stoean (Craiova)