Logit dynamics for strategic games mixing time and metastability

Description:tesi di dottoratoShow FileMIME type:application/pdfFile Size:1.0 Mb
tesi D. Ferraioli.pdf

Description:abstract in inglese a cura dell’autoreShow FileMIME type:application/pdfFile Size:188.7 Kb
abstract in inglese D. Ferraioli.pdf

Description:abstract in italiano a cura dell’autoreShow FileMIME type:application/pdfFile Size:189.5 Kb
abstract in italiano D. Ferraioli.pdf
Soggetto
Game theory; Markov chain; Complex SystemsAbstract
A complex system is generally de_ned as a system emerging from the interaction of
several and di_erent components, each one with their properties and their goals, usually
subject to external inuences. Nowadays, complex systems are ubiquitous and they are
found in many research areas: examples can be found in Economy (e.g., markets), Physics
(e.g., ideal gases, spin systems), Biology (e.g., evolution of life) and Computer Science (e.g.,
Internet and social networks). Modeling complex systems, understanding how they evolve
and predicting the future status of a complex system are major research endeavors.
Historically, physicists, economists, sociologists and biologists have separately studied
complex systems, developing their own tools that, however, often are not suitable for being
adopted in di_erent areas. Recently, the close relation between phenomena in di_erent
research areas has been highlighted. Hence, the aim is to have a powerful tool that is able
to give us insight both about Nature and about Society, an universal language spoken both
in natural and in social sciences, a modern code of nature. In a recent book [16], Tom
Siegfried pointed out game theory as such a powerful tool, able to embrace complex systems
in Economics [3, 4, 5], Biology [13], Physics [8], Computer Science [10, 11], Sociology [12]
and many other disciplines.
Game theory deals with sel_sh agents or players, each with a set of possible actions or
strategies. An agent chooses a strategy evaluating her utility or payo_ that does not depend
only on agent's own strategy, but also on the strategies played by the other players. The way
players update their strategies in response to changes generated by other players de_nes the
dynamics of the game and describes how the game evolves. If the game eventually reaches a
_xed point, i.e., a state stable under the dynamics considered, then it is said that the game
is in an equilibrium, through which we can make predictions about the future status of a
game.
The classical game theory approach assumes that players have complete knowledge about
the game and they are always able to select the strategy that maximizes their utility: in
this rational setting, the evolution of a system is modeled by best response dynamics and
predictions can be done by looking at wellknown Nash equilibrium. Another approach is
followed by learning dynamics: here, players are supposed to \learn" how to play in the
next rounds by analyzing the history of previous plays.
By examining the features and the drawbacks of these dynamics, we can detect the basic
requirements to model the evolution of complex systems and to predict their future status.
Usually, in these systems, environmental factors can inuence the way each agent selects
her own strategy: for example, the temperature and the pressure play a fundamental role
in the dynamics of particle systems, whereas the limited computational power is the main
inuence in computer and social settings. Moreover, as already pointed by Harsanyi and
Selten [9], the complete knowledge assumption can fail due to limited information about
external factors that could inuence the game (e.g., if it will rain tomorrow), or about the
attitude of other players (if they are risk taking), or about the amount of knowledge available
to other players.
Equilibria are usually used to make predictions about the future status of a game: for
this reason, we like that an equilibrium always exists and that the game converges to it.
Moreover, in case that multiple equilibria exist, we like to know which equilibrium will be
selected, otherwise we could make wrong predictions. Finally, if the dynamics takes too long
time to reach its _xed point, then this equilibrium cannot be taken to describe the state of
the players, unless we are willing to wait superpolynomially long transient time.
Thus we would like to have dynamics that models bounded rationality and induces
an equilibrium that always exists, it is unique and is quickly reached. Logit dynamics,
introduced by Blume [6], models a noisyrational behavior in a clean and tractable way.
In the logit dynamics for a game, at each time step, a player is randomly selected for
strategy update and the update is performed with respect to an inverse noise parameter
_ (that represents the degree of rationality or knowledge) and of the state of the system,
that is the strategies currently played by the players. Intuitively, a low value of _ represents
the situation where players choose their strategies \nearly at random" because they are
subject to strong noise or they have very limited knowledge of the game; instead, an high
value of _ represents the situation where players \almost surely" play the best response,
that is, they pick the strategies yielding high payo_ with higher probability. This model
is similar to the one used by physicists to describe particle systems, where the behavior of
each particle is inuenced by temperature: here, low temperature means high rationality
and high temperature means low rationality. It is well known [6] that this dynamics de_nes
an ergodic _nite Markov chain over the set of strategy pro_les of the game, and thus it is
known that a stationary distribution always exists, it is unique and the chain converges to
such distribution, independently of the starting pro_le.
Since the logit dynamics models bounded rationality in a clean and tractable way, several
works have been devoted to this subject. Early works about this dynamics have focused
about longterm behavior of the dynamics: Blume [6] showed that, for 2 _ 2 coordination
games and potential games, the longterm behavior of the system is concentrated in a speci_c
Nash equilibrium; Al_osFerrer and Netzer [1] gave a general characterization of long term
behavior of logit dynamics for wider classes of games. A lot of works have been devoted
to evaluating the time that the dynamics takes to reach speci_c Nash equilibria of a game,
called hitting time: Ellison [7] considered logit dynamics for graphical coordination games
on cliques and rings; Peyton Young [15] extended this work for more general families of
graphs; Montanari and Saberi [14] gave the exact graph theoretic property of the underlying
interaction network that characterizes the hitting time in graphical coordination games;
Asadpour and Saberi [2] studied the hitting time for a class of congestion games.
Our approach is di_erent: indeed, our _rst contribution is to propose the stationary
distribution of the logit dynamics Markov chain as a new equilibrium concept in game
theory. Our new solution concept, sometimes called logit equilibrium, always exists, it is
unique and the game converges to it from any starting point. Instead, previous works only
take in account the classical equilibrium concept of Nash equilibrium, that it is known to
not satisfying all the requested properties. Moreover, the approach of previous works forces
to consider only speci_c values of the rationality parameter, whereas we are interested to
analyze the behavior of the system for each value of _.
In order to validate the logit equilibrium concept we follow two di_erent lines of research:
from one hand we evaluate the performance of a system when it reaches this equilibrium; on
the other hand we look for bounds to the time that the dynamics takes to reach this equi
librium, namely the mixing time. This approach is trained on some simple but interesting
games, such as 2_2 coordination games, congestion games and two team games (i.e., games
where every player has the same utility).
Then, we give bounds to the convergence time of the logit dynamics for very interesting
classes of games, such as potential games, games with dominant strategies and graphical
coordination games. Speci_cally, we prove a twofold behavior of the mixing time: there
are games for which it exponentially depends on _, whereas for other games there exists a
function independent of _ such that the mixing time is always bounded by this function.
Unfortunately, we show also that there are games where the mixing time can be exponential
in the number of players.
When the mixing is slow, in order to describe the future status of the system through the
logit equilibrium, we need to wait a long transient phase. But in this case, it is natural to
ask if we can make predictions about the future status of the game even if the equilibrium
has not been reached yet. In order to answer this question we introduce the concept of
metastable distribution, a probability distribution such that the dynamics quickly reaches it
and spends a lot of time therein: we show that there are graphical coordination games where
there are some distributions such that for almost every starting pro_le the logit dynamics
rapidly converges to one of these distributions and remains close to it for an huge number
of steps. In this way, even if the logit equilibrium is no longer a meaningful description of
the future status of a game, the metastable distributions resort the predictive power of the
logit dynamics.
References
[1] Carlos Al_osFerrer and Nick Netzer. The logitresponse dynamics. Games and Economic
Behavior, 68(2):413 { 427, 2010.
[2] Arash Asadpour and Amin Saberi. On the ine_ciency ratio of stable equilibria in
congestion games. In Proc. of the 5th International Workshop on Internet and Network
Economics (WINE'09), volume 5929 of Lecture Notes in Computer Science, pages 545{
552. Springer, 2009.
[3] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic
Applications, volume 1. Elsevier, 1992.
[4] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic
Applications, volume 2. Elsevier, 1994.
[5] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic
Applications, volume 3. Elsevier, 2002.
[6] Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and
Economic Behavior, 5:387{424, 1993.
[7] Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047{
1071, 1993.
[8] Serge Galam and Bernard Walliser. Ising model versus normal form game. Physica A:
Statistical Mechanics and its Applications, 389(3):481 { 489, 2010.
[9] John C. Harsanyi and Reinhard Selten. A General Theory of Equilibrium Selection in
Games. MIT Press, 1988.
[10] Elias Koutsoupias and Christos H. Papadimitriou. Worstcase equilibria. Computer
Science Review, 3(2):65{69, 2009. Preliminary version in STACS 1999.
[11] Hagay Levin, Michael Schapira, and Aviv Zohar. Interdomain routing and games. In
STOC, pages 57{66, 2008.
[12] Jan Lorenz, Heiko Rauhut, Frank Schweitzer, and Dirk Helbing. How social inuence
can undermine the wisdom of crowd e_ect. Proceedings of the National Academy of
Sciences, 108(22):9020{9025, 2011.
[13] John Maynard Smith. Evolution and the theory of games. Cambridge University Press,
1982.
[14] Andrea Montanari and Amin Saberi. Convergence to equilibrium in local interaction
games. In Proc. of the 50th Annual Symposium on Foundations of Computer Science
(FOCS'09). IEEE, 2009.
[15] Hobart Peyton Young. The di_usion of innovations in social networks, chapter in \The
Economy as a Complex Evolving System", vol. III, Lawrence E. Blume and Steven N.
Durlauf, eds. Oxford University Press, 2003.
[16] Tom Siegfried. A Beautiful Math: John Nash, Game Theory, and the Modern Quest
for a Code of Nature. Joseph Henry Press, 1st ed edition, 2006. [edited by author]
Descrizione
2010  2011
Collections
Data
20120418Autore
Ferraioli, Diodato
Metadata
Mostra tutti i dati dell'itemAutori  Ferraioli, Diodato  
Data Realizzazione  20121018T11:55:46Z  
Date Disponibilità  20121018T11:55:46Z  
Data di Pubblicazione  20120418  
Identificatore (URI)  http://hdl.handle.net/10556/297  
Descrizione  2010  2011  en_US 
Abstract  A complex system is generally de_ned as a system emerging from the interaction of several and di_erent components, each one with their properties and their goals, usually subject to external inuences. Nowadays, complex systems are ubiquitous and they are found in many research areas: examples can be found in Economy (e.g., markets), Physics (e.g., ideal gases, spin systems), Biology (e.g., evolution of life) and Computer Science (e.g., Internet and social networks). Modeling complex systems, understanding how they evolve and predicting the future status of a complex system are major research endeavors. Historically, physicists, economists, sociologists and biologists have separately studied complex systems, developing their own tools that, however, often are not suitable for being adopted in di_erent areas. Recently, the close relation between phenomena in di_erent research areas has been highlighted. Hence, the aim is to have a powerful tool that is able to give us insight both about Nature and about Society, an universal language spoken both in natural and in social sciences, a modern code of nature. In a recent book [16], Tom Siegfried pointed out game theory as such a powerful tool, able to embrace complex systems in Economics [3, 4, 5], Biology [13], Physics [8], Computer Science [10, 11], Sociology [12] and many other disciplines. Game theory deals with sel_sh agents or players, each with a set of possible actions or strategies. An agent chooses a strategy evaluating her utility or payo_ that does not depend only on agent's own strategy, but also on the strategies played by the other players. The way players update their strategies in response to changes generated by other players de_nes the dynamics of the game and describes how the game evolves. If the game eventually reaches a _xed point, i.e., a state stable under the dynamics considered, then it is said that the game is in an equilibrium, through which we can make predictions about the future status of a game. The classical game theory approach assumes that players have complete knowledge about the game and they are always able to select the strategy that maximizes their utility: in this rational setting, the evolution of a system is modeled by best response dynamics and predictions can be done by looking at wellknown Nash equilibrium. Another approach is followed by learning dynamics: here, players are supposed to \learn" how to play in the next rounds by analyzing the history of previous plays. By examining the features and the drawbacks of these dynamics, we can detect the basic requirements to model the evolution of complex systems and to predict their future status. Usually, in these systems, environmental factors can inuence the way each agent selects her own strategy: for example, the temperature and the pressure play a fundamental role in the dynamics of particle systems, whereas the limited computational power is the main inuence in computer and social settings. Moreover, as already pointed by Harsanyi and Selten [9], the complete knowledge assumption can fail due to limited information about external factors that could inuence the game (e.g., if it will rain tomorrow), or about the attitude of other players (if they are risk taking), or about the amount of knowledge available to other players. Equilibria are usually used to make predictions about the future status of a game: for this reason, we like that an equilibrium always exists and that the game converges to it. Moreover, in case that multiple equilibria exist, we like to know which equilibrium will be selected, otherwise we could make wrong predictions. Finally, if the dynamics takes too long time to reach its _xed point, then this equilibrium cannot be taken to describe the state of the players, unless we are willing to wait superpolynomially long transient time. Thus we would like to have dynamics that models bounded rationality and induces an equilibrium that always exists, it is unique and is quickly reached. Logit dynamics, introduced by Blume [6], models a noisyrational behavior in a clean and tractable way. In the logit dynamics for a game, at each time step, a player is randomly selected for strategy update and the update is performed with respect to an inverse noise parameter _ (that represents the degree of rationality or knowledge) and of the state of the system, that is the strategies currently played by the players. Intuitively, a low value of _ represents the situation where players choose their strategies \nearly at random" because they are subject to strong noise or they have very limited knowledge of the game; instead, an high value of _ represents the situation where players \almost surely" play the best response, that is, they pick the strategies yielding high payo_ with higher probability. This model is similar to the one used by physicists to describe particle systems, where the behavior of each particle is inuenced by temperature: here, low temperature means high rationality and high temperature means low rationality. It is well known [6] that this dynamics de_nes an ergodic _nite Markov chain over the set of strategy pro_les of the game, and thus it is known that a stationary distribution always exists, it is unique and the chain converges to such distribution, independently of the starting pro_le. Since the logit dynamics models bounded rationality in a clean and tractable way, several works have been devoted to this subject. Early works about this dynamics have focused about longterm behavior of the dynamics: Blume [6] showed that, for 2 _ 2 coordination games and potential games, the longterm behavior of the system is concentrated in a speci_c Nash equilibrium; Al_osFerrer and Netzer [1] gave a general characterization of long term behavior of logit dynamics for wider classes of games. A lot of works have been devoted to evaluating the time that the dynamics takes to reach speci_c Nash equilibria of a game, called hitting time: Ellison [7] considered logit dynamics for graphical coordination games on cliques and rings; Peyton Young [15] extended this work for more general families of graphs; Montanari and Saberi [14] gave the exact graph theoretic property of the underlying interaction network that characterizes the hitting time in graphical coordination games; Asadpour and Saberi [2] studied the hitting time for a class of congestion games. Our approach is di_erent: indeed, our _rst contribution is to propose the stationary distribution of the logit dynamics Markov chain as a new equilibrium concept in game theory. Our new solution concept, sometimes called logit equilibrium, always exists, it is unique and the game converges to it from any starting point. Instead, previous works only take in account the classical equilibrium concept of Nash equilibrium, that it is known to not satisfying all the requested properties. Moreover, the approach of previous works forces to consider only speci_c values of the rationality parameter, whereas we are interested to analyze the behavior of the system for each value of _. In order to validate the logit equilibrium concept we follow two di_erent lines of research: from one hand we evaluate the performance of a system when it reaches this equilibrium; on the other hand we look for bounds to the time that the dynamics takes to reach this equi librium, namely the mixing time. This approach is trained on some simple but interesting games, such as 2_2 coordination games, congestion games and two team games (i.e., games where every player has the same utility). Then, we give bounds to the convergence time of the logit dynamics for very interesting classes of games, such as potential games, games with dominant strategies and graphical coordination games. Speci_cally, we prove a twofold behavior of the mixing time: there are games for which it exponentially depends on _, whereas for other games there exists a function independent of _ such that the mixing time is always bounded by this function. Unfortunately, we show also that there are games where the mixing time can be exponential in the number of players. When the mixing is slow, in order to describe the future status of the system through the logit equilibrium, we need to wait a long transient phase. But in this case, it is natural to ask if we can make predictions about the future status of the game even if the equilibrium has not been reached yet. In order to answer this question we introduce the concept of metastable distribution, a probability distribution such that the dynamics quickly reaches it and spends a lot of time therein: we show that there are graphical coordination games where there are some distributions such that for almost every starting pro_le the logit dynamics rapidly converges to one of these distributions and remains close to it for an huge number of steps. In this way, even if the logit equilibrium is no longer a meaningful description of the future status of a game, the metastable distributions resort the predictive power of the logit dynamics. References [1] Carlos Al_osFerrer and Nick Netzer. The logitresponse dynamics. Games and Economic Behavior, 68(2):413 { 427, 2010. [2] Arash Asadpour and Amin Saberi. On the ine_ciency ratio of stable equilibria in congestion games. In Proc. of the 5th International Workshop on Internet and Network Economics (WINE'09), volume 5929 of Lecture Notes in Computer Science, pages 545{ 552. Springer, 2009. [3] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic Applications, volume 1. Elsevier, 1992. [4] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic Applications, volume 2. Elsevier, 1994. [5] Robert J. Aumann and S. Hart, editors. Handbook of Game Theory with Economic Applications, volume 3. Elsevier, 2002. [6] Lawrence E. Blume. The statistical mechanics of strategic interaction. Games and Economic Behavior, 5:387{424, 1993. [7] Glenn Ellison. Learning, local interaction, and coordination. Econometrica, 61(5):1047{ 1071, 1993. [8] Serge Galam and Bernard Walliser. Ising model versus normal form game. Physica A: Statistical Mechanics and its Applications, 389(3):481 { 489, 2010. [9] John C. Harsanyi and Reinhard Selten. A General Theory of Equilibrium Selection in Games. MIT Press, 1988. [10] Elias Koutsoupias and Christos H. Papadimitriou. Worstcase equilibria. Computer Science Review, 3(2):65{69, 2009. Preliminary version in STACS 1999. [11] Hagay Levin, Michael Schapira, and Aviv Zohar. Interdomain routing and games. In STOC, pages 57{66, 2008. [12] Jan Lorenz, Heiko Rauhut, Frank Schweitzer, and Dirk Helbing. How social inuence can undermine the wisdom of crowd e_ect. Proceedings of the National Academy of Sciences, 108(22):9020{9025, 2011. [13] John Maynard Smith. Evolution and the theory of games. Cambridge University Press, 1982. [14] Andrea Montanari and Amin Saberi. Convergence to equilibrium in local interaction games. In Proc. of the 50th Annual Symposium on Foundations of Computer Science (FOCS'09). IEEE, 2009. [15] Hobart Peyton Young. The di_usion of innovations in social networks, chapter in \The Economy as a Complex Evolving System", vol. III, Lawrence E. Blume and Steven N. Durlauf, eds. Oxford University Press, 2003. [16] Tom Siegfried. A Beautiful Math: John Nash, Game Theory, and the Modern Quest for a Code of Nature. Joseph Henry Press, 1st ed edition, 2006. [edited by author]  en_US 
Lingua  en  en_US 
Editore  Universita degli studi di Salerno  en_US 
Soggetto  Game theory  en_US 
Soggetto  Markov chain  en_US 
Soggetto  Complex Systems  en_US 
Titolo  Logit dynamics for strategic games mixing time and metastability  en_US 
Tipo  Doctoral Thesis  en_US 
MIUR  INF/01 INFORMATICA  en_US 
Coordinatore  Persiano, Giuseppe  en_US 
Ciclo  X n.s.  en_US 
Tutor  Auletta, Vincenzo  en_US 
Dipartimento  Informatica  en_US 