On a Network Generalization of the Min-max Theorem
Constantinos Daskalakis
Microsoft Research New England
Abstract:
According to Aumann, two-person strictly competitive games --- a generalization of zero-sum games --- are "one of the few areas in game theory, and indeed in the social sciences, where a fairly sharp, unique prediction is made". We present a generalization of this class to multiplayer games played on a network, where the nodes are players and the edges are strictly competitive games between their endpoints; that is, we have a network of competitors. Our generalization of the minmax theorem to the network setting comes with interesting consequences: we show that if the players of the network use no-regret learning algorithms, their behavior converges to a Nash equilibrium of the game.