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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

معرفی[ویرایش]

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

زمینه‌های پژوهش[ویرایش]

برخی از زمینه‌های مهم پژوهشی در نظریۀ الگوریتمی بازی‌ها عبارتند از:

  • طراحی الگوریتمی سازوکارها که به مسائل الگوریتمی مطرح در طراحی سازوکارها می‌پردازد. این بحث با مقالۀ نیسان و رونن در کنفرانس استاک در سال ۱۹۹۹[۱] شروع شد.
  • تحلیل کارایی نقاط تعادل که به تحلیل میزان کارایی (یا عدم کارایی) نقاط تعادل در بازی‌های مختلف (مانند راه‌یابی در شبکه) می‌پردازد. این بحث با مقالۀ پاپادیمیتریو و کوتسوپیاس در کنفرانس استکس در سال ۱۹۹۹[۲] شروع شد. در این مقاله، مفهوم هزینۀ هرج و مرج که نسبت کارایی بدترین نقطۀ تعادلی نسبت به نقطۀ بهینه را می‌سنجد معرفی شد.
  • محاسبۀ نقاط تعادل بازی‌ها و بازارها. هدف این شاخه طراحی الگوریتم کارا (با زمان اجرای چندجمله‌ای) برای مسئلۀ پیدا کردن نقطۀ تعادل برای بازی‌ها یا بازارهای مختلف، و یا اثبات پیچیدگی محاسباتی آنهاست. از نخستین مقاله‌ها در این زمینه می‌توان به مقالۀ دوانور، صابری، پاپادیمیتریو، و وزیرانی در کنفرانس فاکس سال ۲۰۰۲[۳] اشاره کرد.

پیوند به بیرون[ویرایش]

منابع[ویرایش]

  1. Nisan, Noam; Ronen, Amir (1999), "Algorithmic mechanism design", Proceedings of the 31st ACM Symposium on Theory of Computing (STOC '99), pp. 129–140, doi:10.1145/301250.301287 .
  2. E. Koutsoupias, C. H. Papadimitriou Worst-case equilibria, STACS 99
  3. N. R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani. “Market Equilibrium via a Primal-Dual-Type Algorithm”, Proc. FOCS, 2002.