X

Algorithmic Game Theory

By Prof. Palash Dey   |   IIT Kharagpur
Learners enrolled: 2183
ABOUT THE COURSE:
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

INDUSTRY SUPPORT: All Software Companies Especially Google, Microsoft, Etc.
Summary
Course Status : Ongoing
Course Type : Elective
Duration : 12 weeks
Start Date : 25 Jul 2022
End Date : 14 Oct 2022
Exam Date : 29 Oct 2022 IST
Enrollment Ends : 08 Aug 2022
Category :
  • Computer Science and Engineering
Credit Points : 3
Level : Postgraduate

Page Visits



Course layout


Week 1: Introduction to game theory: Non-cooperative game theory, Zero sum and general sum games,
Week 2: Minmax strategies, Nash equilibrium
Week 3: Yao’s Lemma, Special Classes Games
Week 4: Potential Games, Local Search
Week 5: Complexity Classes: FNP, TFNP, PPAD
Week 6: Correlated Equilibrium, Coarse Correlated Equilibrium, Multiplicative Weight
Week 7: 
No Regret Dynamics, No Swap Regret
Week 8: Selfish Routing, Selfish Load Balancing
Week 9: Bayesian Games, Extensive Form Games, Mechanism Design
Week 10: Gibbard Satterwaite Theorem, Quasi-Linear Environment
Week 11: VCG Mechanism, Knapsack Mechanism
Week 12: Stable Matching, House Allocation

Books and references

  1. Nisan/Roughgarden/Tardos/Vazirani (eds), Algorithmic Game Theory, Cambridge University, 2007.
  2. Game Theory by Michael Maschler, Eilon Solan, and Shmuel Zamir.
  3. Game Theory and Mechanism Design by Y. Narahari

Instructor bio

Prof. Palash Dey

IIT Kharagpur
Prof. Palash Dey is an Assistant Professor in the Department of Computer Science and Engineering at Indian Institute of Technology, Kharagpur since 2018. Before joining IIT Kharagpur, he was a post-doctoral INSPIRE faculty in TIFR, Mumbai for one year. He finished his Ph.D. and M.E. from the Department of Computer Science and Automation at Indian Institute of Science, Bangalore in 2017 and 2013 respectively. Prior to that, he finished his B.E. from the Department of Computer Science and Engineering at Jadavpur University in 2010. His primary field of research is algorithmic game theory. He is broadly interested in theoretical computer science.

Course certificate

The course is free to enroll and learn from. But if you want a certificate, you have to register and write the proctored exam conducted by us in person at any of the designated exam centres.
The exam is optional for a fee of Rs 1000/- (Rupees one thousand only).
Date and Time of Exams: 29 October 2022 Morning session 9am to 12 noon; Afternoon Session 2pm to 5pm.
Registration url: Announcements will be made when the registration form is open for registrations.
The online registration form has to be filled and the certification exam fee needs to be paid. More details will be made available when the exam registration form is published. If there are any changes, it will be mentioned then.
Please check the form for more details on the cities where the exams will be held, the conditions you agree to when you fill the form etc.

CRITERIA TO GET A CERTIFICATE

Average assignment score = 25% of average of best 8 assignments out of the total 12 assignments given in the course.
Exam score = 75% of the proctored certification exam score out of 100

Final score = Average assignment score + Exam score

YOU WILL BE ELIGIBLE FOR A CERTIFICATE ONLY IF AVERAGE ASSIGNMENT SCORE >=10/25 AND EXAM SCORE >= 30/75. If one of the 2 criteria is not met, you will not get the certificate even if the Final score >= 40/100.

Certificate will have your name, photograph and the score in the final exam with the breakup.It will have the logos of NPTEL and IIT Kharagpur .It will be e-verifiable at nptel.ac.in/noc.

Only the e-certificate will be made available. Hard copies will not be dispatched.

Once again, thanks for your interest in our online courses and certification. Happy learning.

- NPTEL team


MHRD logo Swayam logo

DOWNLOAD APP

Goto google play store

FOLLOW US