Alumni

PANOZZO FABIO |

Thesis title: | Algorithms for the verification, computation and learning of equilibria in extensive-form games |

Supervisor: | GATTI NICOLA |

Thesis abstract: | The study of strategic-interaction situations has recently received increasing attention in artificial intelligence with the aim of designing autonomous software agents able to act optimally. these situations are customarily modeled as games in which the mechanism describes the rules and strategies describe the behavior of the agents. Particular attention is focused on the study of formal methods to theoretically guarantee the optimality of the agents' behavior. Game theory and microeconomics provide mathematical tools to model strategic-interaction situations and characterize the appropriate solution concepts. However, they do not provide computational tools to and solutions. this problem, commonly called equilibrium computation, is instead central in computer science, whose aim includes assessing the complexity of finding an exact or approximate solution, designing exact or approximate algorithms, and evaluating the application of the algorithms in practical settings. In this thesis, we focus on non-cooperative general-sum extensive-form games. Extensive-form games are more suitable to represent real-world situations providing a richer representation than strategic-form games, where the sequential structure of decision-making is described explicitly and each agent is allowed to be free to change her mind as events unfold. While in zero-sum extensive-form games the main problem is to solve games of large dimension (e.g., poker), in general-sum extensive-form games there are other important issues. the most important is the choice of the most suitable solution concept: it depends on the scenario modelled by the game, e.g. the agents' common knowledge, and it depends on its computability, i.e. the amount of time and memory necessary to solve the game. We can identify two main scenarios, characterized through the knowledge available to agents: the case where the agents have common information and the case where they have incomplete information. Interestingly, with common information, the appropriate solution concepts for extensive-form games refine the concept of Nash equilibrium, while, when agents learn, the appropriate solution concepts relax the concept of Nash equilibrium. More precisely, in the first scenario, it is well known that the Nash equilibrium is not suitable, allowing strategies to be non-sequentially rational. the game theoretic literature provides a number of refinements of Nash equilibrium for extensive-form games that are the appropriate solution concepts. For these solution concepts the verification and computation problems can be hard. In this thesis we show that for some solution concepts the verification problem is easy and we design algorithms to and some refinements of Nash equilibrium. When the information is not common every agent needs to have a set of beliefs over the opponents' behaviour. this beliefs are updating during the learning process, i.e. while the agents repeat the game. In this thesis we discuss the suitable solution concepts for this scenario and we develop efficient evolutionary game theory techniques and algorithms that works with the sequence form representation of extensive-form games allowing an exponential reduction of time and space w.r.t. the algorithms presented in literature. Finally, we experimental evaluate each presented algorithm. |