بازی هم‌دستی
نظریه بازی‌ها به دو شاخه تقسیم می‌شود: بازی‌های هم‌دستی (با همکاری، تعاونی) و بازی‌های بدون همکاری. تفاوت این دو شاخه در وابستگی متقابل بازیکنان است. بازی‌های بدون همکاری مدلی با جزئیات بسیار است که حرکات مجاز برای بازیکنان، استراتژی و سود و هزینه آن‌ها را تحلیل می‌کند. در این نوع بازی، بازیکنان امکان اتحاد و رفتار مشترک ندارند یا این امکان را دارند اما به شرطی که این رفتار مشترک و معاهده منعقد شده بین آن‌ها اثر خارجی بر بازیگران ثالث نداشته باشد. در حالی که در بازی‌های هم‌دستی این سطح از جزئیات وجود ندارد و بازی‌هایی هستند میان گروهی از بازیکنان که در آن به اثرات خارجی رفتار مشترکی که آن‌ها در نظر دارند و رویدادی که منجر به این رفتار مشترک شده توجه می‌شود.
در نظریه بازی‌های هم‌دستی، به کلیت استراتژی‌های انتخاب هر بازیکن دقت می‌شود و بیشتر تمرکز معطوف به تحلیل ائتلاف‌هایی که بازیکنان باهم به وجود می‌آورند استراتژی‌های آنان در این ائتلاف است. به این صورت که سود به‌دست آمده پس از ایجاد هر ائتلاف و تأثیر آن بررسی می‌شود و با توجه به نتایج به‌دست آمده در مورد امکان ایجاد یا عدم ایجاد این ائتلاف‌ها تصمیم گرفته می‌شود. در این بازی‌ها آنچه به‌صورت دقیق مشخص نمی‌شود این موضوع است که در فرایند تشکیل این ائتلاف‌ها چه کنش‌هایی میان بازیکنان مختلف رخ می‌دهد. برای مثال، فرض کنید که بازیکنان ما احزاب مختلف راه‌یافته به مجلس نمایندگان هستند و هر یک از این احزاب قدرت مشخصی دارد. این قدرت با توجه به تعداد صندلی اشغال شده توسط آن‌ها در مجلس نمایندگان بررسی می‌شود. در نظریه بازی‌های هم‌دستی ائتلاف‌های مختلف و چگونگی در اختیار گرفتن اکثریت توسط آن‌ها مشخص می‌شود، اما به فرایند تشکیل این ائتلاف‌ها و بحث‌ها و مذاکرات لازم توجه نمی‌شود و در اندازه‌گیری‌های ما این مقادیر دخیل نیستند.
formula_1 نشان‌دهنده مجموعه بازیکنان است. هر زیرمجموعه ناتهی از formula_2 یک ائتلاف یا اتحاد نامیده می‌شود. برای مثال اعضای مشغول در یک تیم کاری می‌تواند یک ائتلاف باشد. به کل مجموعه formula_2 نیز ائتلاف بزرگ گفته می‌شود. همچنین ائتلاف تهی با علامت ∅ نشان داده می‌شود و مجموعه تمام ائتلاف‌ها با مجموعه توانی formula_4 برابر است که آن را با formula_5 نمایش می‌دهیم. هر ائتلاف را می‌توان یکی از اجزای این مجموعه برشمرد.
تابع مشخصه یک بازی formula_6 نفره تابعی است که یک مقدار را به هر زیرمجموعه از بازیکن‌ها نسبت می‌دهد.
formula_7
مقدار formula_8 میزان بیشینه سود زیرمجموعه formula_9 از بازیکنان را نشان می‌دهد در صورتی که این بازیکنان یک ائتلاف را تشکیل دهند. این میزان با صفر در نظر گرفتن اثر خارجی احتمالی ائتلاف‌های دیگر روی این ائتلاف بررسی می‌شود. در بعضی‌اوقات این مقدار، ماکسمین هزینه در نظر گرفته می‌شود به این صورت که همه formula_10 بازیکن دیگر هم به عنوان یک ائتلاف در نظر گرفته می‌شوند. (formula_11).
به formula_8، ارزش ائتلاف formula_9 نیز گفته می‌شود. همچنین formula_14 برابر صفر در نظر گرفته می‌شود.
توابع مشخصه در این قسمت غالباً به صورت توابع زبرجمع در نظر گرفته می‌شوند. یک تابع زبرجمع است اگر شرط زیر روی آن برقرار باشد. (v(S ∪ T) ≥ v(S) + v(T
البته این تعریف زمانی برقرار است که S ∩ T = ∅ هم برقرار باشد. یعنی عبارت دوم شرط عبارت اول است.
میزان سود ناشی از هر بازی را تقسیم پذیر پایان ناپذیر می‌نامیم اگر بتوان این میزان را بین بازیکنان مشخص به هر صورت ممکن تقسیم نمود.
یک نسبت به میزان سهمی گفته می‌شود که یک بازیگر مشخص از سود کلی بدست آمده از آن خود می‌کند. برای یک بازی با n بازیگر مجموعه نسبت‌ها به این صورت نوشته می‌شود.
formula_15
نسبت x به نسبت y، روی فضای s غلبه دارد اگر و تنها اگر دو شرط زیر برقرار باشد
formula_16
formula_17
فرض کنیم formula_18 یک بازی بدون همکاری است، حال فرض می‌کنیم که بازیکنان توانایی ایجاد ائتلاف‌های مختلف با توانایی اعمال رفتار مشترک را داشته باشند. چند بازی هم‌دستی با formula_18 در ارتباط خواهندبود. این بازی‌ها را تمثال‌های formula_18 می‌نامیم. دو نمونه معروف از این تمثال‌ها در زیر آمده‌اند.
شامل:
۱- تجزیه formula_4 به ائتلاف هاست که این تجزیه، ساختار ائتلاف نامیده می‌شود. ساختار ائتلاف formula_22 در مجموعه formula_4 یک مجموعه‌ای ناتهی از زیر مجموعه‌های ناتهی از formula_4 که شرایط زیر را داشته باشد:
formula_25
formula_26 برابراست با formula_27.
۲- یک بردار سود یا هزینه است که ارزش هر ائتلاف را بین بازیکنانش تقسیم می‌کند. بردار formula_28 بردار سود یا هزینه برای یک ساختار ائتلاف formula_22 روی formula_1 است اگر:
formula_31
formula_32
نتیجه یک زوج formula_33 است که formula_34 سود یا هزینه ائتلاف formula_35 تحت بردار formula_36 است. formula_36 در formula_33 کارآمد است اگر : formula_39 این بردار برای ساختار ائتلاف formula_40 یک نسبت دادن است اگر کارآمد و تک به تک عاقلانه باشد.
formula_39
formula_42
بازی یکنواخت
بازی formula_43 یکنواخت است اگر formula_44
بیشتر بازی‌ها یکنواخت هستند. غیریکنواختی در مواقعی به وجود می‌آید که بعضی از بازیکنان به شدت از هم بدشان بیاید یا هزینه‌های برقراری ارتباط به صورت غیرخطی به نسبت اندازه اتحاد افزایش یابد.
بازی افزایشی
بازی formula_43 افزایشی است اگر formula_46 برقرار باشد.
بازی محدب
یک بازی محدب است اگر formula_47 برقرار باشد. یک بازی محدب، افزایشی است.
بازی جمع ثابت یک بازی جمع ثابت است اگر formula_48
بازی ساده
یک بازی ائتلافی ساده است اگر ارزش‌ها در تابع مشخصه ۰ یا ۱ باشند. (۰ به معنای باخت و ۱ به معنای برد است) یک بازی ساده را می‌توان با formula_49 نشان داد که formula_49 مجموعه از ائتلاف‌های بازی است که برنده‌اند و باقی ائتلاف‌ها بازنده هستند. به بازی‌های ساده ابرگراف یا تابع‌های منطقی نیز گفته می‌شود.
بین تعاریف بالا در بازی ساده روابطی وجود دارد. برای مثال:
فرض اولیه در بازی‌های باهمکاری این است که ائتلاف بزرگ شکل می‌گیرد. چالش این است که هزینه formula_63 را بین بازیکنان عادلانه تقسیم کنیم. یک راه حل یک بردار formula_64 است که نشان دهنده تخصیص به بازیکنان است. راه حل‌ها براساس تعریف‌های متفاوتی از عادلانه بودن تعریف می‌شوند. تعاریف:
چانه زنی نش
در حالتی که ۲ بازیکن داریم استفاده می‌شود.
مجموعه پایدار
مجموعه پایدار یک بازی اولین راه حلی بود که برای بازی‌های با بیشتر از ۲ بازیکن پیشنهاد شد. اگر formula_70 یک بازی باشد و formula_71 و formula_72 دو نسبت دادن به formula_70، در این صورت formula_71 بر formula_72 غلبه می‌کند اگر اتحاد formula_76 وجود داشته باشد که formula_77 و formula_78. به عبارتی دیگر بازیکنان در formula_35 هزینه‌های formula_71 را به formula_72 ترجیح می‌دهند و اگر formula_72 انتخاب شود می‌توانند تهدید به ترک اتحاد بزرگ کنند زیرا وقتی به تنهایی عمل کنند حداقل به اندازه formula_72 کسب می‌کنند که ازformula_72 بیشتر است. مجموعه پایدار مجموعه‌ای از نسبت دادن هاست که دو شرط زیر را دارند: فون نیومن و مرگانسترن مجموعه پایدار را به عنوان مجموعه‌ای از رفتارهای قابل قبول در جامعه توصیف می‌کنند؛ زیرا به ازای هر رفتار نامطلوب یک جایگزین قابل قبول وجود دارد و خود رفتارهای قابل قبول برهم برتری ندارند.
هسته
یکی از ایده‌های اصلی حل این مسئله هسته است. هسته بر مبنای پایداری هر ائتلاف ایجاد شده‌است. این ایده بر این مبنا است که شرط الزامی برای ایجاد یک ائتلاف، آن است که هیچ زیرمجموعه ای از بازیکنان انگیزه خروج از آن را نداشته باشند. به عبارتی ائتلاف پایدار باشد.
formula_85
برای بررسی بیشتر این موضوع یک بردار سود را در نظر بگیرید، formula_86 به صورتی که formula_87 سود بازیکن formula_65ام باشداگر مجموع توابع مشخصه‌های تک تک بازیکنان حاضر در یک ائتلاف بیشتر از مجموع میزان سود تخصیص یافته به آن‌ها در بردار سود باشد، این ائتلاف حاضر به پذیرش این بردار نخواهد بود این شیوه ناپایدار است. در واقع برای پایداری دو شرط زیر باید برقرار باشند:
اول formula_89 دوم اینکه مجموعه formula_35 از بازیکنان حداقل به اندازه وقتی که ائتلاف formula_35 را تشکیل می‌دادند دریافت کنند. به عبارتی دیگر : formula_92
اگر اندازه هسته بازی برابر ۰ باشد یا به عبارتی این مجموعه تهی باشد به‌این معناست که هیچ شیوه تقسیم پایداری برای این بازی وجود ندارد و اگر اندازه این هسته بیشتر از ۰ باشد و مجموعه تهی نباشد به‌این معناست که چند شیوه برای تقسیم پایدار بین ائتلاف‌های موجود وجود دارند.
پس جواب داشتن یا نداشتن یک مسئله بازی هم‌دستی به اندازه هسته بستگی دارد. پس بیشتر بحث‌های مربوط به پاسخ این مسئله پیرامون دو سؤال خواهد بود، آیا اندازه هسته این بازی هم‌دستی برابر ۰ است یا خیر؟ آیا بردار تقسیم سود formula_86 عضو هسته این بازی هم‌دستی یا خیر؟
مقدار شپلی
راه حل‌های کلی علاوه بر چگونگی تقسیم کلی سود به تقسیم سود بین اعضای مختلف یک ائتلاف هم می‌پردازند. فرض کنید ائتلاف formula_4 شکل گرفته و از شکل‌گیری آن سود formula_63 نصیب این ائتلاف خواهد شد. مقدار شپلی، بردار هزینه یکتایی است که اصولی برای این تقسیم تعیین می‌کند. فرض کنید که به هر بازیکن formula_65 میزان formula_97 سود خواهد رسید. این توزیع باید ویژگی‌های کارآمد بودن، تقارن و افزایشی را داشته باشد و همچنین در این توزیع بازیگر پوچ یا مصنوعی نباید از سود سهمی ببرد. مقدار شپلی یک بازی افزایشی، تک به تک عاقلانه است ولی در کل این حکم درست نیست.
بازی هماهنگی تعادل نش