Flow Representations of Games: Near Potential Games and Dynamics

Abstract : Despite much interest in using game theoretic models for the analysis of resource allocation problems in multi-agent networked systems, most of the existing works focus on static equilibrium analysis without establishing how an equilibrium can be reached dynamically. In the theory of games, natural distributed dynamics reach an equilibrium only for restrictive classes of games; potential games is an example. These considerations lead to a natural and important question: can we have a systematic approach to analyze dynamic properties of natural update schemes for general games?
Motivated by this question, this talk presents a new approach for the analysis of games, which involves viewing preferences of agents over the strategy profiles as flows on a graph. Using tools from the theory of graph flows (which are combinatorial analogues of those for continuous vector fields), we show that any finite strategic form game can be written as the direct sum of a potential game, a harmonic game, and a nonstrategic part. Hence, this decomposition leads to a new class of games, "harmonic games", with well-understood equilibrium and dynamic properties. Moreover, this approach allows projecting an arbitrary game onto the space of potential games using convex optimization techniques and exploit the relation between the two games to analyze the static and dynamic equilibrium properties of the original game. The second part of the talk uses this idea to study a non-cooperative power control game and investigate the system optimality properties along dynamic trajectories of natural user update schemes for this game.
This is joint work with Ozan Candogan, Ishai Menache, and Pablo Parrilo.
Type de document :
Communication dans un congrès
Roberto Cominetti and Sylvain Sorin and Bruno Tuffin. NetGCOOP 2011 : International conference on NETwork Games, COntrol and OPtimization, Oct 2011, Paris, France. IEEE, 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00646556
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 30 novembre 2011 - 11:28:57
Dernière modification le : mercredi 30 novembre 2011 - 11:28:57

Identifiants

  • HAL Id : hal-00646556, version 1

Collections

Citation

Asuman Ozdaglar. Flow Representations of Games: Near Potential Games and Dynamics. Roberto Cominetti and Sylvain Sorin and Bruno Tuffin. NetGCOOP 2011 : International conference on NETwork Games, COntrol and OPtimization, Oct 2011, Paris, France. IEEE, 2011. 〈hal-00646556〉

Partager

Métriques

Consultations de la notice

41