How can we make good decisions when our information about the future is incomplete or uncertain? We routinely confront this dilemma in, say, trying to sell a house, buying a stock, choosing an employer, seeking medical treatment, or starting a business. In almost all cases, we are making a prediction about the future and trying to optimize our expected gain. In many cases, we are not acting alone but rather in competition with other players, which requires us to also anticipate their actions. Similarly, many societal decisions pose problems of fair division or social choices (voting). This course teaches mathematical and algorithmic techniques for modeling and solving these types of problems. The main topics covered are the following:
1. Optimal Stopping Rules: when to stop looking
2. Probability and Paradoxes: how to calculate odds
3. Multi-armed Bandits: how to explore
4. Caching: what to forget
5. Scheduling: what to do first
6. Bayes's Rule: how to predict
7. Game Theory: how to strategize
8. Cake Cutting: how to be fair
9. Voting: how to reconcile individual differences
10. Machine Learning: how to generalize from example