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.
Discrete evolution rules related to multiplicative weights (and online learning primitives) have also been considered, for example, by @cite_3 , however, such evolution rules are customized by design to achieve good performance in selfish routing. Our analysis demonstrates that multiplicative weights may well serve as a primitive of adaptation in a wide variety of environments (an argument that intuitively corresponds with the success that multiplicative weights-based boosting algorithms in machine learning theory, such as AdaBoost, have met practical applications).
@cite_3
1978335532
We study the question of whether a large population of agents in a traffic network is able to converge to an equilibrium quickly. To that end, we consider a round-based variant of the Wardrop model. Every agent is allowed to reroute its traffic once in a while with the aim of finding a path with minimal latency. As a first result we find that using a replication policy which allows agents to imitate others gives rise to a bicriterial approximate equilibrium very quickly. In particular, the time bound depends logarithmically on the ratio between minimum and maximum latency but is otherwise independent of the network size. In the single-commodity case, this bicriteria approximate equilibrium has an intuitive interpretation as a state in which almost all agents are almost happy. This kind of approximate equilibrium, however, is transient. In order to reach a global approximation, we need to add an exploration component which enables the agents to explore the strategy space independently of the other agents. Although it can be shown that, when used exclusively, exploration policies imply an exponential lower bound, applying exploration carefully allows the population to approximate the global Wardrop equilibrium in polynomial time. Since the distributed and concurrent fashion of our policies bears the risk of oscillating behavior, we must take into account the steepness of the latency functions. We show that the relevant parameter is elasticity, a parameter closely related to the polynomial degree. This improves significantly over earlier results which depend on the absolute slope and therefore have a pseudopolynomial flavor.