Game theory and applications (GTA)

• Official document (with schedule)

Description

This course provides the basic tools to model the interactions among decision-makers with non-aligned objectives. The set of those decision-makers, together with their preferences, and their knowledge of the interaction forms a non-cooperative game, for which we will study the fundamental notion of (Nash) equilibrium.
We will in particular focus on routing games (with applications in transportation networks) and auction mechanisms (with applications in online keyword auctions)

Keyword

Optimization, Non-cooperative games, Nash equilibrium

Pre-requisites

Basic knowledge in probabilities (ex: conditional probabilities) and function analysis (differentiation). Student must be used to rigorous reasoning.

Content

• Definition of a game, from simple examples (two-player games : jamming game, social networks, collusion between providers)
  • Notions of player, strategy, utility
  • Simple games: prisoner’s dilemma, battle of the sexes, chicken game
  • Diversity of application contexts: should I pay my bus ticket or not? Why announcing an oil shortage creates an oil shortage?
  • Notion of Nash equilibrium (in pure or mixed strategies)
  • Notion of best-response
  • Existence results
• Routing games
  • Wardrop equilibrium and links with optimization problems
  • Price of anarchy: how much do we lose due to user selfishness?
  • How to reduce the price of anarchy using tolls?
• Keyword auctions (how does Google make money?)
  • Auction principle, first-price and second-price auctions
  • Efficiency and truthfulness properties, Vickrey-Clarke-Groves mechanisms
  • Mechanisms currently used: Generalized Second Price auctions

Developed skills

At the end of the course, the students will be able to:

• Model the preferences of participants using a utility function
• Represent the interactions among decision-makers in a finite game with a matrix
• Anticipate the outcome of an interaction via the Nash equilibrium concept
• Analyze the impact of a decision (rule) on the outcome from an interaction, and optimize that decision

Teaching team

Patrick Maillé (coordinator), Bruno Tuffin