The development of game theory in the early 1940’s by John von Neumann was a reaction against the then dominant view that problems in economic theory can be formulated using standard methods from optimization theory. Indeed, most real – world economic problems typically involve conflicting interactions among decision-making agents that cannot be adequately captured by a single (global) objective function, thereby requiring a different, more sophisticated treatment. Accordingly, the main point made by game theorists is to shift the emphasis from optimality criteria to equilibrium conditions.

Game Theory in Pattern Recognition and Machine Learning: graph transduction

As it provides an abstract theoretically-founded framework to elegantly model complex scenarios, game theory has found a variety of applications not only in economics and, more generally, social sciences but also in different fields of engineering and information technologies. In particular, in the past there have been various attempts aimed at formulating problems in computer vision, pattern recognition and machine learning from a game-theoretic perspective and, with the recent development of algorithmic game theory, the interest in these communities around game-theoretic models and algorithms is growing at a fast pace.

The goal of these three lectures is to offer an introduction to the basic concepts of game theory and to provide an overview of the work we’re currently doing in my group on the use of game-theoretic models in pattern recognition, computer vision, and machine learning.

I shall assume no pre-existing knowledge of game theory by the audience, thereby making the lectures self-contained and understandable by a non-expert.

The three lectures will be structured as follows:

• Lecture 1: Introduction to the basic concepts of game theory
• Lecture 2: Evolutionary games and data clustering
• Lecture 3: Contextual pattern recognition and graph transduction

The lectures are based on two (broader) tutorials I gave at ICPR 2010 and CVPR 2011 (with A. Torsello).