Ioannis Avramopoulos

Ioannis Avramopoulos, Nikolaos Vasiloglou

The main topic of this paper are algorithms for computing Nash equilibria. We cast our particular methods as instances of a general algorithmic abstraction, namely, a method we call {\em algorithmic boosting}, which is also relevant to other fixed-point computation problems. Algorithmic boosting is the principle of computing fixed points by taking (long-run) averages of iterated maps and it is a generalization of exponentiation. We first define our method in the setting of nonlinear maps. Secondly, we restrict attention to convergent linear maps (for computing dominant eigenvectors, for example, in the PageRank algorithm) and show that our algorithmic boosting method can set in motion {\em exponential speedups in the convergence rate}. Thirdly, we show that algorithmic boosting can convert a (weak) non-convergent iterator to a (strong) convergent one. We also consider a {\em variational approach} to algorithmic boosting providing tools to convert a non-convergent continuous flow to a convergent one. Then, by embedding the construction of averages in the design of the iterated map, we constructively prove the existence of Nash equilibria (and, therefore, Brouwer fixed points). We then discuss implementations of averaging and exponentiation, an important matter even for the scalar case. We finally discuss a relationship between dominant (PageRank) eigenvectors and Nash equilibria.

Ioannis Avramopoulos

We show that, by using multiplicative weights in a game-theoretic thought experiment (and an important convexity result on the composition of multiplicative weights with the relative entropy function), a symmetric bimatrix game (that is, a bimatrix matrix wherein the payoff matrix of each player is the transpose of the payoff matrix of the other) either has an interior symmetric equilibrium or there is a pure strategy that is weakly dominated by some mixed strategy. Weakly dominated pure strategies can be detected and eliminated in polynomial time by solving a linear program. Furthermore, interior symmetric equilibria are a special case of a more general notion, namely, that of an "equalizer," which can also be computed efficiently in polynomial time by solving a linear program. An elegant "symmetrization method" of bimatrix games [Jurg et al., 1992] and the well-known PPAD-completeness results on equilibrium computation in bimatrix games [Daskalakis et al., 2009, Chen et al., 2009] imply then the compelling P = PPAD.

Ioannis Avramopoulos

We show that evolutionarily stable states in general (nonlinear) population games (which can be viewed as continuous vector fields constrained on a polytope) are asymptotically stable under a multiplicative weights dynamic (under appropriate choices of a parameter called the learning rate or step size, which we demonstrate to be crucial to achieve convergence, as otherwise even chaotic behavior is possible to manifest). Our result implies that evolutionary theories based on multiplicative weights are compatible (in principle, more general) with those based on the notion of evolutionary stability. However, our result further establishes multiplicative weights as a nonlinear programming primitive (on par with standard nonlinear programming methods) since various nonlinear optimization problems, such as finding Nash/Wardrop equilibria in nonatomic congestion games, which are well-known to be equipped with a convex potential function, and finding strict local maxima of quadratic programming problems, are special cases of the problem of computing evolutionarily stable states in nonlinear population games.