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

نظریهٔ الگوریتمی بازی‌ها  یک گرایش‌ میان‌رشته‌ای بین طراحی الگوریتم (از زیرشاخه‌های علوم رایانه) و نظریۀ بازی‌ها (از زیرشاخه‌های اقتصاد) است که به طراحی و تحلیل الگوریتم‌ها در محیط‌های استراتژیک می‌پردازد.

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

 زمینه‌های پژوهش 
برخی از زمینه‌های مهم پژوهشی در نظریۀ الگوریتمی بازی‌ها عبارتند از:
 طراحی الگوریتمی سازوکارها که به مسائل الگوریتمی مطرح در طراحی سازوکارها می‌پردازد. این بحث با مقالۀ نیسان و رونن در کنفرانس استاک در سال ۱۹۹۹. شروع شد.
 تحلیل کارایی نقاط تعادل که به تحلیل میزان کارایی (یا عدم کارایی) نقاط تعادل در بازی‌های مختلف (مانند راه‌یابی در شبکه) می‌پردازد. این بحث با مقالۀ پاپادیمیتریو و کوتسوپیاس در کنفرانس استکس در سال ۱۹۹۹E. Koutsoupias, C. H. Papadimitriou Worst-case equilibria , STACS 99 شروع شد. در این مقاله، مفهوم هزینۀ هرج و مرج که نسبت کارایی بدترین نقطۀ تعادلی نسبت به نقطۀ بهینه را می‌سنجد معرفی شد.
 محاسبۀ نقاط تعادل بازی‌ها و بازارها. هدف این شاخه طراحی الگوریتم کارا (با زمان اجرای چندجمله‌ای) برای مسئلۀ پیدا کردن نقطۀ تعادل برای بازی‌ها یا بازارهای مختلف، یا اثبات پیچیدگی محاسباتی آنهاست. از نخستین مقاله‌ها در این زمینه می‌توان به مقالۀ دوانور، صابری، پاپادیمیتریو، و وزیرانی در کنفرانس فاکس سال ۲۰۰۲N. R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani. “Market Equilibrium
via a Primal-Dual-Type Algorithm”, Proc. FOCS, 2002. اشاره کرد.

 پیوند به بیرون 

 Truthful Mechanisms With Implicit Payment Computation
 Market Design for a P2P Backup System
 Matching In Networks with Bilateral Contracts
 Algorithmic Game Theory، A ThesisPresented to The Academic Faculty by Aranyak Mehta
 An Algorithmic Game Theory Primer Tim Roughgarden†

 منابع 

رده:نظریه بازی‌ها
رده:نظریه محاسبات
رده:الگوریتم‌ها