نظریه بازی‌ها کاربردهای وسیعی در بسیاری از حوزه‌ها دارد که مهم‌ترین آن‌ها حوزه‌های اقتصادی، کسب‌وکار، و علوم اجتماعی است. به طور کلی در نظریه بازی‌ها با سیستم‌هایی شامل عامل‌های هوشمند و خودخواه سروکار داریم که هر کدام از آن‌ها بنا به مصالح خویش وضعیت سیستم را تغییر می‌دهند. نظریه بازی‌ها ابزار تحلیل این‌گونه از سیستم‌ها را در اختیار ما قرار می‌دهد و کمک می‌کند تا بتوانیم آن‌ها را به شیوه‌ای درست و منطقی کنترل کنیم. با توجه به رشد بازارهای دیجیتال و گسترده‌‌تر‌شدن و بزرگ‌شدن سیستم‌های کاربردی چندعامله با عامل‌های هوشمند، نیاز به توسعه روش‌ها و الگو‌های محاسباتی و الگوریتمی بیشتر و بیشتر شده است. در بسیاری از موارد بدون این روش‌ها امکان تحلیل و طراحی استراتژی‌های کارا وجود ندارد. هدف از این درس آشنایی با این روش‌ها و الگوریتم‌هاست که با توجه به ماهیت آن، در اصل کاربرد برخی تئوری‌های اصیل علوم کامپیوتر در این حوزه است.

• آشنایی با مقدمات نظریه بازی‌ها - یادآوری (۸ جلسه)
• محاسبه نقاط تعادل و مسائل مربوطه (۶ جلسه)
  • بازی‌های صفرجمع دونفره (Zero-sum Games)‌ و قضیه MinMax
  • بازی‌های صفرجمع چندنفره
  • قضیه نش (Nash Theorem)‌،‌ لم اسپرنر (Sperner’s Lemma) و قضیه بروور (Brouwer’s Theorem)
  • الگوریتم لمکه هاوسون (Lemke Howson Algorithm)
  • مسائل جستجوی تام (Total Search Problems) و کلاس‌های پیچیدگی PPAD، PPP، PPA، و PLS
  • کلاس پیچیدگی مسائل یافتن نقاط تعادل نش
• منطق، اتوماتا و بازی‌های بی‌نهایت (۷ جلسه)
  • گراف بازی‌ (Game Graph) و شرایط برد
  • شرایط برد در حالت غیرقطعی (شرایط بوخی، مولر، رابین و …) و تبدیلات آن‌ها
  • بازی‌های بی‌نهایت و تشخص (Determinacy)‌ و تشخص بی‌حافظه (Memoryless Determinacy)‌
  • ‌شرایط برد منطقی (Logical Winning Conditions)‌
  • اتوماتای درختی
  • بازی‌های زوجیت (Parity Games)‌ و بازی‌های نیمه بازپرداخت (Mean Payoff) و حل آن‌‌ها
  • بازی‌های قابلیت رسیدن (Reachability Games)‌
  • بازی‌های تکرار‌شونده (Repeated Games)
  • فرآیند تصمیم‌گیری مارکف و بازی‌های تصادفی
  • شبیه‌سازی، دوتشابهی (Bisimulation)‌ و بازی‌های ارنفوشت-فریز (Ehrenfeucht-Fraïssé)
• طراحی مکانیزم الگوریتمی (۷ جلسه)
  • آشنایی با مقدمات طراحی مکانیزم و لم مایرسون (Myerson’s Lemma)
  • مثال‌های مختلف از جمله مزایده‌های کوله پشتی (Knapsack Auctions)
  • مزایده‌های بیشینه‌کننده سود (Revenue Maximizing Auctions) و قیمت رزروشده (Reserved Price)
  • مزایده‌های نزدیک بهینه ساده (Near Optimal Auctions)، نامساوی پیامبر (‌‌Prophet Inequality)‌ و قضیه بولو کلمپرر ( Bulow Klemperer Theorem)‌
  • طراحی مکانیزم چند پارامتره و مکانیزم‌های VCG
  • مزایده‌های ترکیبیاتی (Combinatorial Auctions)‌ و مزایده‌ طیف‌های بی‌سیم (Wireless Spectrum)‌
  • طراحی مکانیزم‌ برای حالت‌های غیرخطی - حالت‌های بودجه محدود و مزایده‌های پرچی (Clinching Auctions) و مکانیزم‌های بدون پول‌
  • بازارهای تطابق و تطابق‌های پایدار، بازارهای تبادل کلیه (Kidney Exchange Markets)
• دینامیک بازی‌ها و مسائل یادگیری (۶ جلسه)‌
  • هزینه آشوب (Price of Anarchy) و هزینه ثبات (Price of Stability)
  • بازی‌های پتانسیلی (Potential Games)
  • بازی‌های نرم (Smooth Games)‌ و هزینه آشوب مستحکم
  • تعادل‌های نش قوی (Strong Nash Equilibria)
  • دینامیک‌های بهترین پاسخ (Best Response Dynamics) و نقاط تعادل تقریبی
  • یادگیری، دینامیک‌های بازی ساختگی (Fictitious Play)‌ و دینامیک‌های بدون حسرت (No-Regret Dynamics)‌ و یادگیری تقویتی

• آزمون (۶۰ درصد نمره)
• تمرین (۲۰ درصد نمره)
• سمینار (۲۰ درصد نمره)