We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise β describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter β. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in β and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with β. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in β. Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in β and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.

Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., & Persiano, G. (2016). Convergence to Equilibrium of Logit Dynamics for Strategic Games. ALGORITHMICA, 76(1), 110-142 [10.1007/s00453-015-0025-7].

Convergence to Equilibrium of Logit Dynamics for Strategic Games

PASQUALE, FRANCESCO;
2016

Abstract

We present the first general bounds on the mixing time of the Markov chain associated to the logit dynamics for wide classes of strategic games. The logit dynamics with inverse noise β describes the behavior of a complex system whose individual components act selfishly according to some partial (“noisy”) knowledge of the system, where the capacity of the agent to know the system and compute her best move is measured by parameter β. In particular, we prove nearly tight bounds for potential games and games with dominant strategies. Our results show that for potential games the mixing time is bounded by an exponential in β and in the maximum potential difference. Instead, for games with dominant strategies the mixing time cannot grow arbitrarily with β. Finally, we refine our analysis for a subclass of potential games called graphical coordination games, often used for modeling the diffusion of new technologies. We prove that the mixing time of the logit dynamics for these games can be upper bounded by a function that is exponential in the cutwidth of the underlying graph and in β. Moreover, we consider two specific and popular network topologies, the clique and the ring. For the clique, we prove an almost matching lower bound on the mixing time of the logit dynamics that is exponential in β and in the maximum potential difference, while for the ring we prove that the time of convergence of the logit dynamics to its stationary distribution is significantly shorter.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
Markov Chain; Game theory; Potential games; Convergence time
Auletta, V., Ferraioli, D., Pasquale, F., Penna, P., & Persiano, G. (2016). Convergence to Equilibrium of Logit Dynamics for Strategic Games. ALGORITHMICA, 76(1), 110-142 [10.1007/s00453-015-0025-7].
Auletta, V; Ferraioli, D; Pasquale, F; Penna, P; Persiano, G
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
auletta2016algorithmica.pdf

accesso solo dalla rete interna

Licenza: Copyright dell'editore
Dimensione 589.67 kB
Formato Adobe PDF
589.67 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/184072
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact