A Brief Introduction to Algorithms, Game Theory and Risk-Averse Decision Making
summary
Quick précis of concrete claims and tools: classic graph problems get 2^N brute force or polynomial fixes like 2-approximation via MST for metric TSP; complexity focus is P vs NP and NP‑completeness. Traffic models show Braess paradox (adding a zero‑time link can increase travel time) and prove price of anarchy = 4/3 for linear delays; tolls equalize user equilibrium and social optimum. Introducing risk (mean±stddev, CVaR) breaks optimal substructure, yields nonconvex objectives and a current N^{log N} worst‑case algorithm, so many complexity and mechanism‑design questions remain open.
AI-written summary · about
chapters (26)
- 0:00Intro
- 3:55Real-time decision making examples
- 6:13Algorithms: the basics
- 6:40Shortest paths example
- 8:33Modeling the real-world
- 9:06Graph terminology
- 10:02Graph examples
- 11:51Back to shortest paths
- 14:55Dijkstra shortest path algorithm
- 15:23(Basic) Algorithm Design Techniques
- 15:52Algorithm running time
- 25:05NP-Complete problems
- 27:42Approximation algorithms
- 28:29Traveling Salesman Problem
- 31:57Game theory
- 38:44Example: Inefficiency of equilibria
- 40:07Equilibrium
- 42:14Social Optimum
- 43:43Price of Anarchy
- 47:11Optimal route?
- 49:08What is risk?
- 49:55Risk I: Expected Utility Theory
- 53:29Risk II: Mean-variance framework
- 55:03Risk III: Coherent risk measures
- 56:02Implications of risk attitudes
- 57:51Algorithmic insights
related talks
49mIntroduction and Research Fellows Lightning Talks
34mAlgorithms to live
14mInformation, Learning, And Incentive Design For Societal Networks
40mApproximation Algorithms for Optimization under Uncertainty
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
48mA Simple Condition for Constant Regret in Online Decision-Making
44mSomething for Almost Nothing: Advances in Sub-Linear Time Algorithms
01h 21mAdversarial Bandits: Theory and Algorithms