EASSS Course on Game Theory:
strategic and cooperative games

Tutorial at the 12th European Agent Systems Summer School (EASSS 2010)
Saint Etienne, France, August 2010.

• Abstract: For designing or analyzing agent societies, modeling interactions between agents is essential. The agents may be in a conflicting or in a cooperative context. In both cases, we can model the interaction in the form of a game: we can abstract the interaction using a set of actions, some rules and a description of the outcomes of the game. The field of game theory studies such games. The field describes a wide variety of game types and corresponding solution concepts to "solve" them. The goal of this tutorial is to introduce two important kinds of games: the strategic (also called non-cooperative) games that model situations of conflicts, and the coalitional (also called cooperative) games that model situations of cooperation. This introductory course is aimed at students who have no previous acquaintance with game theory. As such, only some elementary mathematical training is assumed. The main goal of the course is to introduce the most fundamental concepts and results. We will start with introducing the basics of strategic games. Then, we will introduce coalitional games and survey some issues addressed by some potential applications, and how they can be addressed by multiagent systems.
• Lecturer: Stéphane Airiau (ILLC, University of Amsterdam).
• Litterature:
  • A Course in Game Theory by Martin J. Osborne and Ariel Rubinstein (available here)
  • An Introduction to MultiAgent Systems by Michael Wooldridge (Chapter 11 and Chapter 13)
  • Multiagent Systems by Yoav Shoham and Kevin Leyton-Brown (Chapters 3-6, Chapter 12)
• Slides:
  • Strategic games (handout, 8up)
  • Cooperative games (part 1)(handout, 8up)
  • Cooperative games (part 2)(handout, 8up)

• Strategic games (2h)
  • Normal form games: best response, pure and mixed strategies, Nash equilibrium, dominated strategies, Pareto efficient outcomes, regret.
  • Extensive form games: equilibria and sub-game perfect equilibria.
  • Other games: repeated games, congestion games, stochastic games, Bayesian games.
• Cooperative games (4h)
  Agents need to decide what coalition to form and how to share the outcome of the cooperation between the members of the coalition. Coalitional game theory proposes many solution concepts to share the outcome (focusing on the stability of the coalitions formed or on fairness).
  • Games with and without transferable utility with examples.
  • Solutions concepts for games with transferable utility:
    • - the core and other stability concepts (kernel, nucleolus).
    • - a fair solution concept: The Shapley value.
  • Simple games: a tool to analyze voting situations. In particular, we will introduce some tools to measure the voting power of the agents.
  • Representation and complexity issues.
  • Hedonic games and games with non-transferable utility.
  • Games with externalities.
  • Issues from the multiagent systems litterature (examples of application, manipulation, communication, dynamic environments, uncertainty, short term/long term coalitions, overlaping coalitions, search of an optimal coalition structure).

---

Last modified: Tue Aug 31 14:57:24 CEST 2010