A Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision Making

Explore algorithms, game theory, and risk-averse decision making in this comprehensive lecture from the Real-Time Decision Making Boot Camp. Delve into real-world applications of decision-making processes, starting with an introduction to algorithms and their basics. Learn about graph theory, shortest path problems, and the Dijkstra algorithm. Examine algorithm design techniques, running time analysis, and NP-Complete problems. Discover approximation algorithms and their application to the Traveling Salesman Problem. Investigate game theory concepts, including equilibria, social optimum, and the Price of Anarchy. Gain insights into risk assessment through Expected Utility Theory, mean-variance framework, and coherent risk measures. Understand the implications of risk attitudes and the algorithmic challenges they present. Conclude with valuable algorithmic insights for tackling complex decision-making scenarios.

Intro
Real-time decision making examples
Algorithms: the basics
Shortest paths example
Modeling the real-world
Graph terminology
Graph examples
Back to shortest paths
Dijkstra shortest path algorithm
(Basic) Algorithm Design Techniques
Algorithm running time
NP-Complete problems
Approximation algorithms
Traveling Salesman Problem
Game theory
Example: Inefficiency of equilibria
Equilibrium
Social Optimum
Price of Anarchy
Optimal route?
What is risk?
Risk I: Expected Utility Theory
Risk II: Mean-variance framework
Risk III: Coherent risk measures
Implications of risk attitudes
Algorithmic challenges
Algorithmic insights