Evolutionary dynamical models and multi-agent learning algorithms for games in sequence-form

The study of strategic interactions, called games, among rational agents has been playing an increasingly prominent role in the field of artificial intelligence. Evolutionary game theory combines dynamical systems and game theory in order to describe the behavior of large populations of agents repeatedly colliding. Furthermore, it represents an useful instrument to characterize the dynamics of multi--agent learning procedures whose aim is instead to determine the optimal course of actions for agents that cooperate or compete, within the same environment, to achieve a certain objective. Our analysis is entirely focused on the class of non--cooperative games in extensive--form which supply an explicit description of the sequential structure of decision making that each agent has to face. In order to examine an extensive--form game, we need to refer to alternative representations, typically normal or agent--form. However, the latter suffer from the main drawback of being exponentially large in the size of the game tree, thus making the use of most state--of--the--art algorithms unaffordable. The crucial idea behind our work is to overcome this issue by relying on the sequence--form whose particular framework causes an exponential decrease in the size of the representation of the underlying stage game. In particular, we design sequence--form evolutionary dynamical models that are realization equivalent to their counterparts, either in normal or agent--form, already existing in literature. Nevertheless, we point out how there exists at least one noteworthy normal--form model that does not admit realization equivalent sequence--form dynamics requiring polynomial computation time and space. Finally, we develop a novel version of Generalized Infinitesimal Gradient Ascent (GIGA), a multi--agent learning gradient ascent--based technique for which a realization equivalent procedure working over the sequence--form has been recently derived.

Lo studio delle interazioni strategiche tra agenti razionali, comunemente chiamate giochi, riveste un ruolo sempre più importante nel campo dell'intelligenza artificiale. La teoria dei giochi evolutiva combina sistemi dinamici e teoria dei giochi al fine di descrivere il comportamento di ampie popolazioni di agenti che entrano ripetutamente in contatto tra loro. Essa rappresenta inoltre un utile strumento per caratterizzare le dinamiche di procedure di apprendimento multiagente il cui scopo è invece di determinare il corso ottimale delle azioni di agenti che collaborano o competono, all'interno dello stesso ambiente, per raggiungere un certo obiettivo. La nostra analisi è interamente concentrata sulla classe dei giochi non cooperativi in forma estesa, la quale fornisce una descrizione esplicita della struttura sequenziale decisionale a cui ciascun agente deve far fronte. Al fine di esaminare un gioco in forma estesa, occorre fare riferimento a rappresentazioni alternative, tipicamente la forma normale o agente. Tuttavia, queste ultime soffrono dell'importante inconveniente di essere esponenzialmente grandi rispetto alla dimensione dell'albero di gioco, rendendo quindi l'uso di molti algoritmi allo stato dell'arte insostenibile in pratica. L'idea cruciale sulla quale si fonda il nostro lavoro è di superare questo problema facendo affidamento sulla forma sequenza la cui particolare conformazione causa una compressione esponenziale della rappresentazione del gioco sottostante. In particolare, vengono implementati dei modelli dinamici evolutivi in forma sequenza che sono equivalenti per realizzazione alle loro controparti, in forma normale o in forma agente, già esistenti in letteratura. Ciononostante, facciamo notare come esista almeno un modello notevole in forma normale che non ammette dinamiche equivalenti per realizzazione in forma sequenza aventi complessità computazionale polinomiale. In conclusione, viene sviluppata una versione di Generalized Infinitesimal Gradient Ascent (GIGA), una tecnica di apprendimento multiagente per cui una procedura equivalente per realizzazione che sfrutta la forma sequenza è stata recentemente derivata.