Computing Equilibria in Games and Populations

3^rd December 2012, 16:00 G12
Prof. Paul Spirakis
Department of Computer Engineering & Informatics
University of Patras
and CTI Patras
Greece

Abstract

We consider here two paradigms of interactions among individual entities, namely (1) games (selfish entities) and (2) interactions in populations (specified by some given set of rules).
The solution concepts that most researchers follow are Nash Equilibria (for games) and Stable Computations (for populations). The talk focuses on the efficiency of computing such solutions.
The criterion for Nash Equilibria is Polynomial Time.
We argue that a corresponding criterion for distributed Stable Computations is Polynomial Space.
We discuss exact and approximate efficient methods for computing Nash Equilibria. We also discuss a variety of models for (distributed) stable computations, and present a space hierarchy.
Some open problems are also highlighted.
The talk is based on recent research of the speaker and his team.