نظریه الگوریتمی بازی‌ها
نظریهٔ الگوریتمی بازی‌ها (به انگلیسی: Algorithmic Game Theory) یک گرایش میان‌رشته‌ای بین طراحی الگوریتم (از زیرشاخه‌های علوم رایانه) و نظریۀ بازی‌ها (از زیرشاخه‌های اقتصاد) است که به طراحی و تحلیل الگوریتم‌ها در محیط‌های استراتژیک می‌پردازد.
معرفی[ویرایش]
نظریه بازی‌های الگوریتمی از آخرین زمینه‌های پژوهشی است که در تعامل با اقتصاد، علوم کامپیوتر و ریاضیات است. در اوایل دهه ۱۹۹۰ و با ظهور اینترنت، این نظریه به واسطه گستردگی زمینه‌های جدید کاربردش مورد توجه قرار گرفته‌است. این حوزه مطالعات ریاضی بازی‌ها کاملاً متمرکز بر روشهای محاسباتی رایانه‌ای و الگوریتمی است. این مطالعات بین رشته‌ای بسیار جذاب بوده و غالبا ترکیبی از متدولوژی‌ها و تکنیک‌هایی از حوزه‌های بهینه سازی و الگوریتم‌ها و نظریه بازی‌ها است.
زمینه‌های پژوهش[ویرایش]
برخی از زمینه‌های مهم پژوهشی در نظریۀ الگوریتمی بازی‌ها عبارتند از:
- طراحی الگوریتمی سازوکارها که به مسائل الگوریتمی مطرح در طراحی سازوکارها می‌پردازد. این بحث با مقالۀ نیسان و رونن در کنفرانس استاک در سال ۱۹۹۹[۱] شروع شد.
- تحلیل کارایی نقاط تعادل که به تحلیل میزان کارایی (یا عدم کارایی) نقاط تعادل در بازی‌های مختلف (مانند راه‌یابی در شبکه) می‌پردازد. این بحث با مقالۀ پاپادیمیتریو و کوتسوپیاس در کنفرانس استکس در سال ۱۹۹۹[۲] شروع شد. در این مقاله، مفهوم هزینۀ هرج و مرج که نسبت کارایی بدترین نقطۀ تعادلی نسبت به نقطۀ بهینه را می‌سنجد معرفی شد.
- محاسبۀ نقاط تعادل بازی‌ها و بازارها. هدف این شاخه طراحی الگوریتم کارا (با زمان اجرای چندجمله‌ای) برای مسئلۀ پیدا کردن نقطۀ تعادل برای بازی‌ها یا بازارهای مختلف، یا اثبات پیچیدگی محاسباتی آنهاست. از نخستین مقاله‌ها در این زمینه می‌توان به مقالۀ دوانور، صابری، پاپادیمیتریو، و وزیرانی در کنفرانس فاکس سال ۲۰۰۲[۳] اشاره کرد.
پیوند به بیرون[ویرایش]
- 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†
منابع[ویرایش]
- ↑ 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.
- ↑ E. Koutsoupias, C. H. Papadimitriou Worst-case equilibria بایگانی‌شده در ۱۳ مارس ۲۰۱۶ توسط Wayback Machine, STACS 99
- ↑ N. R. Devanur, C. H. Papadimitriou, A. Saberi, V. V. Vazirani. “Market Equilibrium via a Primal-Dual-Type Algorithm”, Proc. FOCS, 2002.