CS-693

Introduction to Game Theory

Postgraduate

The course is an introduction to game theory, from the most basic concepts to some more advanced ones which can be used to formulate and solve real-world problems which are typical of, e.g., wireless communications, computer science and economics. In particular, we will study the concepts of strategical thinking, rational decision making, payoffs, utility functions, preferences, pure/mixed strategies, dominant strategies, best-response strategies, normal-form games, solution concepts ((approximate) Nash equilibria, Correlated equilibria), examples of games (symmetric bimatrix games, zero-sum games), formulation of zero-sum games via Linear programming and Minimax theorem. We will also discuss algorithms for computing solution concepts (pure Nash equilibrium computation, Lemke-Howson algorithm,  algorithms for approximate Nash equilibria, Correlated equilibria via Linear programming), extensive games and backward induction,  repeated games, inefficiency of solution concepts (Price of Anarchy, Price of Stability), selfish routing (atomic/non atomic games, Wardrop equilibrium, Braess paradox), mechanism design (First price auctions, Second price auctions), matching theory (Gale-Shapley algorithm). Finally, we will discuss applications of game theory to economical and wireless networking problems.
 

6