Further results on sequence-form evolutionary dynamics : normal-form dynamics, agent-form dynamics and learning algorithms

Evolutionary game theory provides the principal tools to model the dynamics of multi-agent learning algorithms. While there is a long-standing literature on evolutionary game theory in strategic-form games, in the case of extensive-form games few results are known and the exponential size of the representations currently adopted makes the evolutionary analysis of such games unaffordable. The main goal of this thesis is to overcome this limitation focusing on dynamics for the sequence-form of extensive-form games, providing seven dynamics: one realization equivalent to the agent-form replicator dynamics, one realization equivalent to the normal-form and one to the agent-form logit dynamics, one realization equivalent to the normal-form and one to the agent-form BNN dynamics, one realization equivalent to the normal-form and one to the agent-form Smith dynamics. All our dynamics, with the exception of normal-form BNN and normal-form Smith dynamics, require polynomial compute time and space, providing an exponential compression w.r.t. the dynamics currently known and providing thus tools that can be effectively employed. Furthermore, we use our tools to compare the agent-form and normal-form dynamics and, in case of replicator dynamics and logit dynamics, to provide new “hybrid” dynamics, generated by the convex combination of the respective normal-form and agent-form. Finally we design two new multi-agent learning algorithms: one whose dynamics is the one prescribed by normal-form logit dynamics and a policy gradient one, based on Boltzmann updates.

La teoria dei giochi evolutiva, fornisce gli strumenti principali per la modellazione delle dinamiche degli algoritmi di apprendimento multi-agente. Se per i giochi in forma strategica esiste un'ampia letteratura legata alla teoria dei giochi evolutiva, lo stesso non si può dire per i giochi in forma estesa riguardo ai quali si conoscono pochi risultati. Inoltre la dimensione esponenziale della rappresentazione attualmente adottata rende l'analisi evolutiva di questi giochi impraticabile. Lo scopo principale di questa tesi è di superare questa limitazione concentrandoci su dinamiche evolutive per la forma sequenza di giochi in forma estesa. Presentiamo sette diverse dinamiche: una equivalente a livello di realizzazione alla forma agente del replicator dynamics, una equivalente a livello di realizzazione alla forma normale e una alla forma agente del logit dynamics, una equivalente a livello di realizzazione alla forma normale e una alla forma agente del BNN dynamics, una equivalente a livello di realizzazione alla forma normale e una alla forma agente dello Smith dynamics. Tutte le nostre dinamiche, ad eccezione della forma normale del BNN dynamics e della forma normale dello Smith dynamics, richiedono tempo e spazio computazionale polinomiale permettendo una compressione esponenziale rispetto alle dinamiche conosciute e ci forniscono quindi uno strumento che può essere efficacemente utilizzato. Inoltre queste dinamiche ci permettono di comparare facilmente le dinamiche in forma agente con quelle in forma normale. In più, nel caso del replicator dynamics e del logit dynamics, forniamo due nuove dinamiche “ibride”, generate dalla combinazione convessa delle rispettive forme agente e normale. Infine progettiamo due nuovi algoritmi di apprendimento multi-agente: uno la cui dinamica è quella prescritta dalla forma normale del logit dynamics e una di tipo policy gradient, basata su aggiornamenti di Boltzmann.