Online Monotone Games
  Algorithmic game theory (AGT) focuses on the design and analysis of
algorithms for interacting agents, with interactions rigorously formalized
within the framework of games. Results from AGT find applications in domains
such as online bidding auctions for web advertisements and network routing
protocols. Monotone games are games where agent strategies naturally converge
to an equilibrium state. Previous results in AGT have been obtained for convex,
socially-convex, or smooth games, but not monotone games. Our primary
theoretical contributions are defining the monotone game setting and its
extension to the online setting, a new notion of regret for this setting, and
accompanying algorithms that achieve sub-linear regret. We demonstrate the
utility of online monotone game theory on a variety of problem domains
including variational inequalities, reinforcement learning, and generative
adversarial networks.
