CVPR 2011 Tutorial — Game Theory in Computer Vision and Pattern Recognition
CVPR 2011 Tutorial
Game Theory in Computer Vision and Pattern Recognition
June 20th, 2011
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. 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 this tutorial is to offer an introduction to the basic concepts of game theory
and to provide a critical overview of its main applications in computer vision and pattern recognition. We shall assume no
pre-existing knowledge of game theory by the audience, thereby making the tutorial self-contained and understandable by a
non-expert.
Topics covered
PART 1 slides
- Introduction to game theory
- What is a game?
- Mixed strategies, expected payoffs, Nash equilibria.
- Complexity and algorithmic issues
- Game equilibria in CV&PR
- Polymatrix games, contextual pattern recognition, and graph transduction
- Evolutionary games and data clustering
PART 2 slides
- Applications
- Image/video segmentation and medical image analysis
- Content-based image retrieval
- Matching, in-outlier detection, detection of anomalous behavior
- Repeated games and online learning
- Learning in repeated games
- Learning with experts and regret-based learning
- Boosting