中央研究院 資訊科學研究所

Equilibrium describes a steady state in which the system would stay once it is reached. However, for a general game or market, computing a Nash equilibrium or market equilibrium is believed to be hard. To address this issue, a line of research is to consider natural efficient dynamics which players have incentive to follow, and study how the system evolves according to such dynamics. We show that when employing the mirror-descent algorithm (with bulletin-board posting), 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, for the class of atomic congestion games, we propose a family of bandit algorithms based on the mirror-descent algorithms with only bandit feedback, and show that when each player individually adopts such a bandit algorithm, their joint (mixed) strategy pro
file quickly converges with implications.

For computing market equilibrium, we design algorithms to solve a rational convex program for bijective markets, where everyone is a seller of only one good and also a buyer for a bundle of goods. (Jain reduced equilibrium computation in linear Arrow-Debreu markets to that in bijective markets.) Our algorithm for computing linear Arrow-Debreu market equilibrium is based on solving the rational convex program formulated by Devanur et al., repeatedly alternating between a step of gradient-descent-like updates and a follow-up step of optimization. Convergence can be achieved by a new analysis different from that for Fisher markets.