Game theory with algorithms

The course introduces the students to the fundamental concepts of Game Theory and demonstrates the use of these concepts in computer science field. Game theory is the discipline aimed at modeling scenarios in which rational agents have to make specific decisions that have mutual and possibly conflicting consequences. In the recent time, game theory has played a vital role in the understanding of computer and communication networks and providing insights into questions such as allocation of network resources, analysis and effects of competitive and/or cooperative agents, wireless network protocols, network dynamics, wireless security, performance optimization, and network traffic and topology. In this course we will systematically investigate main concepts and methods of modern game theory and its algorithmic applications.

Course Content

Part 1. Introduction to game theory

  • Games and solutions. Game theory and mechanism design. Examples from real life and computer applications.
  • Strategic form games. Matrix and continuous games. Dominant and dominated strategies. Iterative elimination of strictly dominated strategies.
  • Nash Equilibrium; existence and uniqueness. Pareto efficiency. Pure and mixed strategies equilibrium.
  • Other concepts and refinement. Correlated and coarsed correlated equilibrium. Trembling hand equilibrium.
  • Algorithms for calculating Nash equilibrium for non-degenerate games. Support enumeration and vertex enumeration.
  • Lemke-Howson algorithm and its complexity.

Part 2. Games in extensive form and dynamic games

  • Extensive games with perfect information. Backward induction and subgame perfect equilibrium.
  • Applications in bargaining games. Ultimatum games, Rubinstein bargaining model.
  • Infinitely/finitely repeated games. Trigger strategies. Folk theorems. Imperfect monitoring and perfect public equilibrium.
  • Games with incomplete information: Mixed and behavioral strategies. Bayesian Nash equilibrium in pure strategies.
  • Games with incomplete information: Perfect Bayesian equilibrium. Pooling, separating and hybrid cases.
  • Evolution games and replication dynamic. Evolutionarily stable strategies.
  • Axelrod tournaments

Part 3. Different applications

  • Matching algorithms. TTC and Gale-Shapley algorithms.
  • Voting and indexes of power. Shapley and Banzhaf index and its calculation. Voting schemes.
  • Cooperative games. Shapley value and applications.
  • Mechanism design: Optimal auctions; revenue-equivalence theorem. Social choice viewpoint. Revelation principle. Incentive compatibility. VCG mechanisms.
  • Auctions. Practical applications.

Course tools

Python (NashPy, Axelrod)

Prerequisites

Python. Basic calculus and probability

Lecturer

Dr. Oleksii Ignatenko is a doctor of physical and mathematical sciences (2019).
He is a leading research fellow in Institute of Software Systems NAS of Ukraine.
He is an associate professor at the Institute of Applied System Analysis of Igor Sikorsky Kyiv Polytechnic Institute (from 2006), Kyiv-Mohyla Academy (from 2019) and Kyiv Academic University (from 2019).

Fields of interests: game theory and applications in computer science, agent-based modeling, reinforcement learning.