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
Marcello Pelillo      Andrea Torsello
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

  1. Introduction to game theory
    • What is a game?
    • Mixed strategies, expected payoffs, Nash equilibria.
    • Complexity and algorithmic issues
  2. Game equilibria in CV&PR
    • Polymatrix games, contextual pattern recognition, and graph transduction
    • Evolutionary games and data clustering
  3. PART 2 slides

  4. Applications
    • Image/video segmentation and medical image analysis
    • Content-based image retrieval
    • Matching, in-outlier detection, detection of anomalous behavior
  5. Repeated games and online learning
    • Learning in repeated games
    • Learning with experts and regret-based learning
    • Boosting