# Algorithmic Game Theory

- Institution: IIT Kharagpur
- Department: Computer Science and Engineering
- Teacher: Prof. Palash Dey
- Level: Graduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106105237)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106105237)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

Game theory is the formal study of interaction between "self-interested" (or "goal-oriented") "systems" (or "agents" or "decision makers" or "players"), and strategic scenarios that arise in such settings. It began life in Economics in the 1940's with the work of von Neumann and Morgenstern, but has since been applied to an extraordinary range of subjects, including political science, evolutionary biology and even to inspection regimes for arms control.

Game theory has for years also played an important, if less recognized, role in several branches of computer science. Applications within computer science include the use of games in automated verification and model checking to model computing systems in an unknown and possibly adverse environment. In AI games are applied to the analysis of multi-agent systems. Recently, with the advent of the internet and e-commerce, many game theoretic questions in the interplay between economics and computing have received extensive attention. These include electronic auctions, and more generally mechanism design questions (inverse game theory) related to finding incentive structures for cooperation between independent entities on the internet.Wherever game theory plays a quantitative role, algorithmic and computational questions related to "solving" games are also of central importance. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments.

Intended audience: Under-graduate And Post-graduates

Prerequisites: Knowledge of algorithms

## Lectures

1. [Lecture 1 : Introduction](https://invisiblenetwork.ai/learn/nptel/106105237/faeae2f9b031) (YouTube)
2. [Lecture 2 : Assumptions of Game Theory](https://invisiblenetwork.ai/learn/nptel/106105237/6f78bd4caa8e) (YouTube)
3. [Lecture 3 : Examples of Games](https://invisiblenetwork.ai/learn/nptel/106105237/8af7c61eb020) (YouTube)
4. [Lecture 4 : Equilibrium Concepts](https://invisiblenetwork.ai/learn/nptel/106105237/84c456dfcfb9) (YouTube)
5. [Lecture 5 : Nash Equilibrium](https://invisiblenetwork.ai/learn/nptel/106105237/4de7cbcac5bf) (YouTube)
6. [Lecture 6 : Indifference Principle](https://invisiblenetwork.ai/learn/nptel/106105237/9f6d1a4b9e02) (YouTube)
7. [Lecture 7 : Security of Players](https://invisiblenetwork.ai/learn/nptel/106105237/2eae49af65ab) (YouTube)
8. [Lecture 8 : Minmax Theorem](https://invisiblenetwork.ai/learn/nptel/106105237/4ba725b53638) (YouTube)
9. [Lecture 9 : Implications of Minmax Theorem](https://invisiblenetwork.ai/learn/nptel/106105237/8391a0e82065) (YouTube)
10. [Lecture 10 : MSNEs of Matrix Games](https://invisiblenetwork.ai/learn/nptel/106105237/8a2df81cd16f) (YouTube)
11. [Lecture 11 : Iterative Eliminations of Dominated Strategies](https://invisiblenetwork.ai/learn/nptel/106105237/d3a4da591aa1) (YouTube)
12. [Lecture 12 : Iterative Eliminations of Dominated Strategies (contd..)](https://invisiblenetwork.ai/learn/nptel/106105237/ba28c3d6aaae) (YouTube)
13. [Lecture 13 : Braess's paradox](https://invisiblenetwork.ai/learn/nptel/106105237/001a19fb5709) (YouTube)
14. [Lecture 14 : Yao's Lemma and its applications](https://invisiblenetwork.ai/learn/nptel/106105237/b3e9e5b8f381) (YouTube)
15. [Lecture 15 : Support Enumeration Algorithm](https://invisiblenetwork.ai/learn/nptel/106105237/1d9bf3d2aad1) (YouTube)
16. [Lecture 16 : Succinct game](https://invisiblenetwork.ai/learn/nptel/106105237/acce42f30b32) (YouTube)
17. [Lecture 17 : Potential Games](https://invisiblenetwork.ai/learn/nptel/106105237/9d9fedca9d66) (YouTube)
18. [Lecture 18 : Best Response Dynamics](https://invisiblenetwork.ai/learn/nptel/106105237/74adb17d8fc5) (YouTube)
19. [Lecture 19 : Fast Convergence of Best Response Dynamics](https://invisiblenetwork.ai/learn/nptel/106105237/4117397d91af) (YouTube)
20. [Lecture 20 : Computing ε-PSNE for Network Congestion Games](https://invisiblenetwork.ai/learn/nptel/106105237/fb81877912e5) (YouTube)
21. [Lecture 21 : PSNE for Congestion Games](https://invisiblenetwork.ai/learn/nptel/106105237/cb78b68fb780) (YouTube)
22. [Lecture 22 : PSNE for Symmetric Congestion Games](https://invisiblenetwork.ai/learn/nptel/106105237/2be39371ef8b) (YouTube)
23. [Lecture 23 : Functional NP](https://invisiblenetwork.ai/learn/nptel/106105237/a78c823fc7e3) (YouTube)
24. [Lecture 24 : PPAD Class](https://invisiblenetwork.ai/learn/nptel/106105237/9f3411218926) (YouTube)
25. [Lecture 25 : Sperner's Lemma](https://invisiblenetwork.ai/learn/nptel/106105237/2cbc08e7e918) (YouTube)
26. [Lecture 26 : Approximate MSNE Computation](https://invisiblenetwork.ai/learn/nptel/106105237/ec2fdf02c638) (YouTube)
27. [Lecture 27 : Correlated Equilibrium](https://invisiblenetwork.ai/learn/nptel/106105237/32135f881fd3) (YouTube)
28. [Lecture 28 : Coarse Correlated Equilibrium](https://invisiblenetwork.ai/learn/nptel/106105237/2a6de32252e0) (YouTube)
29. [Lecture 29 : External Regret Framework](https://invisiblenetwork.ai/learn/nptel/106105237/818892505376) (YouTube)
30. [Lecture 30 : Multiplicative Weight Algorithm](https://invisiblenetwork.ai/learn/nptel/106105237/67ee91ce17fc) (YouTube)
31. [Lecture 31 : Multiplicative Weight Algorithm (Contd..)](https://invisiblenetwork.ai/learn/nptel/106105237/3be3151c71e5) (YouTube)
32. [Lecture 32 : Swap Regret and Correlated Equilibrium](https://invisiblenetwork.ai/learn/nptel/106105237/e22ae03411ec) (YouTube)
33. [Lecture 33 : Swap Regret to External Regret Reduction](https://invisiblenetwork.ai/learn/nptel/106105237/4f3e72f43683) (YouTube)
34. [Lecture 34 : Braess's paradox and Pigou's Network](https://invisiblenetwork.ai/learn/nptel/106105237/4d2d3fc51484) (YouTube)
35. [Lecture 35 : PoA of Selfish Routing Game](https://invisiblenetwork.ai/learn/nptel/106105237/3a25ef23f4b6) (YouTube)
36. [Lecture 36 : PoA of Selfish Load Balancing Game](https://invisiblenetwork.ai/learn/nptel/106105237/488fccdb6a03) (YouTube)
37. [Lecture 37 : Bayesian Game](https://invisiblenetwork.ai/learn/nptel/106105237/fda9ff4debbc) (YouTube)
38. [Lecture 38 : BNE of First Price Auction](https://invisiblenetwork.ai/learn/nptel/106105237/68cd014feca5) (YouTube)
39. [Lecture 39 : Extensive Form Game](https://invisiblenetwork.ai/learn/nptel/106105237/0abd389127eb) (YouTube)
40. [Lecture 40 : Mechanism Design Intro..](https://invisiblenetwork.ai/learn/nptel/106105237/945080aa6b1f) (YouTube)
41. [Lecture 41 : Implementation of Social Choice Functions](https://invisiblenetwork.ai/learn/nptel/106105237/d68284d13c23) (YouTube)
42. [Lecture 42 : Revelation Principle](https://invisiblenetwork.ai/learn/nptel/106105237/a039bb0531db) (YouTube)
43. [Lecture 43 : Properties of Social Choice Function](https://invisiblenetwork.ai/learn/nptel/106105237/a48b6f4a96e1) (YouTube)
44. [Lecture 44 : Gibbard-Satterthwaite Theorem](https://invisiblenetwork.ai/learn/nptel/106105237/3aca4c12193c) (YouTube)
45. [Lecture 45 : Quasilinear Environment](https://invisiblenetwork.ai/learn/nptel/106105237/93ccd4d7719f) (YouTube)
46. [Lecture 46 : Ex-Post Efficiency](https://invisiblenetwork.ai/learn/nptel/106105237/c4ba95b0e5b0) (YouTube)
47. [Lecture 47 : VCG Mechanism](https://invisiblenetwork.ai/learn/nptel/106105237/35e40812f3ae) (YouTube)
48. [Lecture 48 : Example of VCG Mechanism](https://invisiblenetwork.ai/learn/nptel/106105237/d7de9307d57b) (YouTube)
49. [Lecture 49 : Weighted VCG](https://invisiblenetwork.ai/learn/nptel/106105237/58480da81bb9) (YouTube)
50. [Lecture 50 : Affine Maximizer](https://invisiblenetwork.ai/learn/nptel/106105237/2531e3498c3e) (YouTube)
51. [Lecture 51 : Recap of Topics Discussed so Far](https://invisiblenetwork.ai/learn/nptel/106105237/1c6454cc02eb) (YouTube)
52. [Lecture 52 : Single Parameter Domain](https://invisiblenetwork.ai/learn/nptel/106105237/43b7d1c7ab3b) (YouTube)
53. [Lecture 53 : DSIC in Single Parameter Domain](https://invisiblenetwork.ai/learn/nptel/106105237/225d5e43fb60) (YouTube)
54. [Lecture 54 : Mayerson's Lemma](https://invisiblenetwork.ai/learn/nptel/106105237/44cbc0d1039c) (YouTube)
55. [Lecture 55 : Sponsored Search Auction](https://invisiblenetwork.ai/learn/nptel/106105237/51fa538a495d) (YouTube)
56. [Lecture 56 : Intermediate Domain](https://invisiblenetwork.ai/learn/nptel/106105237/59a8427c404e) (YouTube)
57. [Lecture 57 : Algorithmic Mechanism Design](https://invisiblenetwork.ai/learn/nptel/106105237/ba2956d6ccdf) (YouTube)
58. [Lecture 58 : Stable Matching](https://invisiblenetwork.ai/learn/nptel/106105237/cf53bd411013) (YouTube)
59. [Lecture 59 : Gale-Shapley Algorithm](https://invisiblenetwork.ai/learn/nptel/106105237/50831584f15a) (YouTube)
60. [Lecture 60 : Properties of Stable Matching](https://invisiblenetwork.ai/learn/nptel/106105237/b708c21b59ac) (YouTube)