نظریه‌ الگوریتمی بازی‌ها

Algorithmic Game Theory

شماره درس: ۴۰۸۳۵	تعداد واحد: ۳
مقطع: کارشناسی ارشد	نوع درس: نظری
پیش‌نیاز: –	هم‌نیاز: –

اهداف درس

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

ریز مواد

آشنایی با مقدمات نظریه بازی‌ها - یادآوری (۸ جلسه)
محاسبه نقاط تعادل و مسائل مربوطه (۶ جلسه)
- بازی‌های صفرجمع دونفره (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)‌ و یادگیری تقویتی

ارزیابی

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

مراجع

T. Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, 2016.
K.R. Apt and E. Grädel (Eds.). Lectures in game theory for computer scientists. Cambridge University Press, 2011.
Y. Shoham and K. Leyton-Brown. Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
N. Nisan, T. Roughgarden, E. Tardos, and V.V. Vazirani. Algorithmic game theory. Cambridge University Press, 2007.