CS 684: Introduction to Algorithms and Logics in Game Theory

CS 684: Introduction to Algorithms and Logics in Game Theory

Prerequisites

CS201, CS340 and Consent of the Instructor

Course Contents:

Games, payoffs and strategies; Two player zero sumgames, minmax theorem and computing mixed strategies via LP; Thegeneral case: Nash equilibrium: existence, algorithms to find equilibrium and complexity Issues; Examples and some other kinds of equilibriums. Social choice theory, Arrow's theorem; Elements of Mechanism design, VCG mechanism. Some extensions such as games modelswith partial information, randomized mechanisms. Extensive games: turn based games, deterministic and stochastic games, winning conditions, determinacy, solving these games. Logics to reason about games and strategies: Alternating time temporal logic and its extensions.

Books and References:

1. Algorithmic Game Theory, edited by N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Cambridge Univ. Press, 2007.
   
2. Some papers/lecture notes may also be referred to.