نظریه الگوریتمی بازیها- ویکی پدیا
نظریه بازیهای الگوریتمی از آخرین زمینههای پژوهشی است که در تعامل با اقتصاد، علوم کامپیوتر و ریاضیات است. در اوایل دهه ۱۹۹۰ و با ظهور اینترنت, نظریه بازیهای الگوریتمی به واسطه گستردگی زمینههای جدید کاربردش بسیار مورد توجه قرار گرفتهاست. این حوزه مطالعات ریاضی بازیها کاملا متمرکز بر روشهای محاسباتی رایانهای و الگوریتمی است. این مطالعات بین رشتهای بسیار جذاب بوده و غالبا ترکیبی از متدولوژیها و تکنیک هایی از حوزههای بهینه سازی و الگوریتمها و نظریه بازیها است. نظریه بازی الگوریتمی کمکم شایانی به درک بسیاری از بازیهای اساسی در سالهای اخیر نمودهاست و به زمینهای بسیار فعال جهت کارهای پژوهشی تبدیل شدهاست. یکی از کسانی که در این زمینه کار میکند یک ایرانی است: سید وهاب میررکنی مهندسی کامپیوتر خود را از شریف گرفته و دکترا و فوقدکترایش را از امآیتی، وی همچنین برای مایکروسافت و آیبیام کارکردهاست.
بیشتر کسانی که بر روی “نظریهٔ الگوریتمی بازیها” کار میکنند کامپیوتری هستند و زمینه خوبی برای کار و پژوهش به ویژه در کارشناسیارشد و دکترا است. به تازگی کتابی با همین نام “Algorithmic Game Theory ” توسط انتشارات دانشگاه کمبریج چاپ شده که نسخهای از آن در اینترنت قابل دریافت است و برای کسانی که میخواهند در این باره بیشتر بدانند، بسیار عالی است. همینطور اسامی چهار نویسنده (ویراستار) کتاب، زمینههای پژوهشی و درسهایی که ارایه میدهند در زیر آمدهاست:
| http://www.cc.gatech.edu/%7Evazirani/ | Vijay V. Vazirani | |
| http://theory.stanford.edu/%7Etim/ | Tim Roughgarden | |
| http://www.cs.cornell.edu/people/eva/eva.html | Éva Tardos | |
| http://www.cs.huji.ac.il/%7Enoam/ | Noam Nisan |
مباحث این کتاب بصورت اجمالی شامل موارد زیر میشود:
بخش اول:محاسبه در بازی
این بخش شامل توضیحاتی در مورد راه حلهای پایهای، یافتن تعادل نش، یافتن تعادل برای بازی دو نفره در فرم گسترده، طراحی الگوریتمهای ترکیبی برای تعادل بازار، محاسبه تعادل بازار برای برنامههای محدب، بازیهای گرافیکی و رمزنگاری در نظریه بازی است.
بخش دوم: طراحی مکانیزم الگوریتمی
این بخش شامل توضیحاتی در مورد راه حلهای پایهای، یافتن تعادل نش، یافتن تعادل برای بازی دو نفره در فرم گسترده، طراحی الگوریتمهای ترکیبی برای تعادل بازار، محاسبه تعادل بازار برای برنامههای محدب، بازیهای گرافیکی و رمزنگاری در نظریه بازی است.
بخش سوم: نا کار آمدی در تعادل
این بخش شامل توضیحاتی اجمالی در مورد مسیریابی، توازن و مکانیزمهای تخصیص است.
بخش چهارم: موضوعات اضافه شده
این بخش شامل توضیحاتی در مورد طراحی شبکهها، محل تسهیلات، تعادل تعاونی، طراحی شبکههای بازیهای دیگر، بازیهای تصادفی، به اشتراک گذاشتن پهنای باند بازیها میباشد.
استادان برجسته
از استادان بزرگ دنیا که این درس را تدریس میکنند میتوان به موارد زیر اشاره کرد:
| Name & family | ||
|---|---|---|
| mailto:eva@cs.cornell.edu | Instructor: Éva Tardos TA: Thành Nguyen | |
| mailto:vetta@math.mcgill.ca | Prof. Adrian Vetta | |
| mailto:christos@cs.berkeley.edu | Christos H. Papadimitriou | |
| ------------- | Daskalakis Constantinos | |
| zoe«the letter a»@stanford.edu | Roughgarden تیم و Hartline جیسون |
همینطور سایتهای زیر اطلاعات مفیدی در این زمینه در دسترستان خواهد داد:
http://agtb.wordpress.com/2010/06/13/ec10-and-current-trends-in-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†
همینطور اخیرا کنفرانسهایی در این زمینه بر گزار شدهاست که میتوانید از طریق وب سایت زیر به آنها دسترسی داشته باشید.
جنبههای مختلف نظریه بازیهای الگوریتمی:
بررسی اجمالی
نظریه الگوریتمی بازی ترکیبی از تفکر الگوریتمی با بازی نظری، و یا، به طور کلی، مفاهیم اقتصادی است. این درس بر روی مشکلات ناشی از اینترنت و سایر شبکههای کامپیوتری غیر متمرکز تمرکز خواهد داشت. بیشترین تأکید بر روی این ویژگی اینترنت است که بوسیله یک نهاد مرکزی طراحی نشدهاست. اما تعامل پیچیده بسیاری از عوامل اقتصادی، از جمله اپراتورهای شبکه به عنوان خدمات، ارائه دهندگان، طراحان، کاربران، در درجات مختلفی از همکاری و رقابت توسط اینترنت امکان پذیر است.این درس بر روی بسیاری از سئوالات در رابط بین الگوریتمهای بازی و تئوری تمرکز میکند.
مباحث این درس بصورت اجمالی شامل موارد زیر میشود:
- مقدمهای بر الگوریتمها و بازیها (Introduction to Algorithms and Games)
- بازیها در شبکه (Games on Networks)
congestion games
selfish routing in networks
Nash and Wardrop equilibria
coordination ratios (price of anarchy)
pricing network edges
network design with selfish agents
- جنبههای الگوریتمی از تعادل (Algorithmic Aspects of Equilibria)
existence and complexity of equilibria (including Nash and cooperative) complexity of market equilibria fast algorithms for specific games
games with incomplete information
evolutionary games
- جنبههای اقتصادی از مسیریابی اینترنت (Economic aspects of Internet routing)
fairness, charging schemes, and rate control.
- طراحی مکانیسم (Mechanism Design)
general principles
algorithmic mechanism design
distributed aspects
specific applications, eg multicast pricing
cost-sharing mechanisms
- مزایده (Auctions)
combinatorial auctions
frugality
auctions for digital goods
computational aspects of auctions
پیوند به بیرون
پاورپوینت مطلب را میتوانید از اینجا دانلود نمائید.
برای دریافت کتاب نظریه الگوریتمی بازی ها نوشته Noam Nisan اینجا کلیک نمائید.
در زندگی بازیهای بسیاری انجام میدهیم ‘ خواه برای سرگرمی و کودکانه ‘ خواه برای سوداگری و سود آوری ‘ یا حتی عاشقانه‘