Learning Dynamics for Convergences in Multiagent Systems
陳柏安 教授兼所長國立陽明交通大學資訊管理研究所 15:30–17:00 鴻經館M107Abstract：
From a perspective of designing or engineering for opinion formation games in social networks, the opinion maximization (or minimization) problem has been studied mainly for designing seeding algorithms that aim at selecting a subset of nodes to control their opinions. We first define a two-player zero-sum Stackelberg game of competitive opinion optimization by letting the player under study as the leader minimize the sum of expressed opinions by doing so-called “internal opinion design”, knowing that the other adversarial player as the follower is to maximize the same objective by also conducting her own internal opinion design. We furthermore consider multiagent learning, specifically using the Optimistic Gradient Descent Ascent, and analyze its convergence to equilibria with a fast convergence rate in the simultaneous-game version of competitive opinion optimization.
In another line of previous work, designing learning dynamics has been considered for linear Arrow-Debreu market equilibria. Since Jain reduced equilibrium computation in linear Arrow-Debreu markets to the equilibrium computation in “bijective” markets, we have designed a partially-distributed alternating algorithm for reaching linear bijective market equilibrium, based on solving the rational convex program formulated by Devanur et al., with a convergence rate which can be improved. Thus, we adapt the Optimistic Gradient Descecnt Ascent for a modified program of Devanur et al. with Lagrange multipliers and show converges to market equilibria with bounds of O(1/T^0.5) on the last-iterate convergence rate, where T is the number of iterations, while yet another very recent related work enjoying its proposed distributed dynamics did not consider convergence rates.