This course is a survey of theoretical models and algorithms for decision-making at scale. Such models have become vital to the modern algorithmic toolkit, with wide-ranging applications to platforms for social choice, interpersonal interactions, sharing economy, and crowdsourcing. We will view these problems through the lens of Theoretical Computer Science. Settings considered include:
- Decision-making under Uncertainty: We will study classic models for making decisions in the face of uncertainty about the future, and how they apply to modern large-scale platforms. We will study stochastic optimization, online algorithms, and regret minimization.
- Fairness and Collective Decisions: We will study desiderata for making decisions in a population via preference aggregation, as well as models for partitioning resources based on preferences. We with focus on utility maximization, truthfulness, and fairness. In contexts where satisfying multiple desiderata is impossible, we will study approximation techniques.
- Decisions and Networks: This is widely studied as non-cooperative game theory. We will analyze the convergence of basic dynamics such as no-regret. Decentralized decision making of humans cannot be studied without an understanding of how people influence each other. We will study classic models for opinion dynamics and spread of influence, and how these are impacted by the social network.
Several of the lectures will touch upon topics from beyond Computer Science, notably from Economics, Operations Research, and Sociology. Though the course is theoretical in nature, almost all problems considered have significant practical motivation which will also be highlighted.