Economic Theory and Algorithms

Combinatorial Games: Definitions, solution methods for impartial combinatorial games (NIM-heaps arithmetic, MEX-rule). Extensive-Form Games: Game-tree representation, complete/incomplete information games, games with perfect recall. Strategic Games: Zero-sum games, mixed strategies, best response strategies, dominant strategies, Nash equilibria, correlated equilibria, approximate equilibria. Algorithms and complexity for computing one/all Nash equilibria (enumeration methods, upper-envelope method, Lemke-Howson, etc.) for bimatrix games. Definition and efficient computation of MAXMIN strategies. Negotiations: Modelling as repeated games, with payoff discounting. Axiomatic characterization and efficient computation of Nash bargaining solutions. Mechanisms: Design of truthful mechanisms. Gibbard-Shatterthwaite Theorem. Auction theory. Vickrey auctions. VCG mechanisms. Generalized second-price auctions. Congestion games: Modelling as potential games. Evaluation methods for Price of Anarchy/Stability. Network design games. Voting theory: Voting rules (majority, veto, Borda, dictatorship). Arrow’s Theorem.