Game couplings: Learning dynamics and applications

Modern engineering systems (such as the Internet) consist of multiple coupled subsystems. Such subsystems are designed with local (possibly conflicting) goals, with little or no knowledge of the implementation details of other subsystems. Despite the ubiquitous nature of such systems very little is formally known about their properties and global dynamics. We investigate such distributed systems by introducing a novel game-theoretic construct, that we call game-coupling. Game coupling intuitively allows us to stitch together the payoff structures of two or more games into a new game. In order to study efficiency issues, we extend the price of anarchy framework to this setting, where we now care about local and global performance. Such concerns give rise to a new notion of equilibrium, as well as a new learning paradigm. We prove matching welfare guarantees for both, both for individual subsystems as well as for the global system, using a generalization of the (λ,μ)-smoothness framework [17]. In the second part of the paper, we establish conditions leading to advantageous couplings that preserve or enhance desirable properties of the original games, such as convergence of best response dynamics and low price of anarchy.