Outline

 In several modern applications, one has to design algorithms in the presence of self-interested agents. Classic examples include keyword search auctions, school choice, voting, and network routing.  This course is a survey of basic results in game theory, with a focus on existence and computational aspects. The latter is particularly relevant in the age of big data, when there could easily be a large number of agents that are affected by the algorithm. We will view the field of algorithmic game theory through the lens of Theoretical Computer Science, with an emphasis on principled algorithms. Though the course is largely theoretical in nature, almost all problems considered have significant practical motivation which will also be highlighted. 

Topics covered include:

• Equilibrium concepts: Survey of various equilibrium concepts and their computational complexity. Study of the quality of equilibria via the price of anarchy, as well as dynamics that converge to such equilibria.

•  Auction design: Basic auction design concepts from economics literature. Design of simple auctions when the optimal auction has large computational complexity. Auction design in complex settings such as auctioning combinatorial bundles of items.

• Allocations and fairness: Survey of various fairness notions from economics and CS literature. Fairness solutions via randomization, market design, linear programming, and stability. 

• Social choice: Basic voting theory and Arrow's impossibility theorem. Analyzing the quality of voting rules. Fairness in social choice via justified representation and market clearing concepts.