En aquest projecte estudiem el comportament dinàmic del Sum Celebrity i Max Celebrity Games definits per Alvarez et al. 2016 i Àlvarez & Messegué 2016, respectivament. Aquests treballs analitzen les propietats estructurals dels equilibris de Nash junt amb la relació entre el cost social i el cost social òptim (Preu de l'anarquia i Preu de l'estabilitat) d'acord amb els paràmetres que defineixen aquests jocs: alfa o cost de l'enllaç, beta o distància crítica i els pesos de cadascun dels jugadors. En aquest projecte analitzem les diferents dinàmiques dels models del Sum i Max Celebrity Games i la seva convergència a configuracions d'equilibri en funció de la distància crítica. Una dinàmica consisteix en una seqüència de moviments on la política de selecció del jugador i el tipus d'estratègia egoista que el jugador corresponent aplica, pot afectar la convergència. El punt de partida és que en ambdós models calcular la Best Response per a un jugador és computable en temps polinòmic per ß = 1, però NP-hard per ß > 1. A causa d'aquesta diferència en el comportament, els dos casos han estat analitzats per separat. Per ß = 1 hem obtingut que per a tots dos models el problema de calcular un equilibri de Nash és temps polinòmic. A més, en el cas del Max hem demostrat l'existència de cicles en una dinàmica en la qual s'aplica el Best Response, en contraposició amb el Sum on no són possibles. Atès que el problema de calcular la Best Response per a tots dos models quan ß > 1 és NP-hard, hem proposat un model greedy en què les possibles estratègies d'un jugador estan restringides. Tot i que està demostrat l'existència de cicles, no hem trobat experimentalment una instància cíclica per als jocs Sum i Max Greedy Celebrity Games.

In this project we study the dynamic behavior of Sum Celebrity and Max Celebrity Games defined in Àlvarez et al. 2016 and Àlvarez & Messegué 2016, respectively. These works analyze the structural properties of the Nash equilibrium graphs and the relationship between the social cost and the optimal social cost (Price of the Anarchy and Price of Stability) according to the parameters that define these games: alpha or cost of each link, beta or critical distance and weights of each of the players. In this project we analyze different dynamics of the Sum and Max Celebrity Games models and their convergence to equilibrium configurations as a function of the critical distance. A dynamics consists of a sequence of movements where both the policy to select the player and the kind of selfish strategy that the corresponding player applies, can affect convergence. The starting point is that in both models the Best Response strategy of a player is computable in polynomial time for ß = 1, but NP-hard for ß > 1. Due to this difference in behavior, both cases have been analyzed separately. For ß = 1 we have obtained that for both models the problem of computing a Nash equilibrium is polynomial time. Furthermore, in the case of Max we have proven the existence of cycles in a Best Response dynamics, in contrast to the Sum where they are not possible. Since the problem of computing a Best Response for both models when ß > 1 is NP-hard, we have proposed a greedy model in which the possible strategies of a player are restricted. Although the existence of cycles is proven, we have not found experimentally a cyclic instance for the Sum and Max Greedy Celebrity Games.