هسته (نظریه بازی‌ها)

در نظریه بازی‌ها، منظور از هسته مجموعه‌ای از تمام تقسیم‌بندی‌هایی است که نمی‌توان آن را توسط یک زیر مجموعه (ائتلاف) از شرکت‌کننده‌ها بهبود داد. یک ائتلاف را می‌گوییم می‌توان روی یک تقسیم‌بندی بهبود داد اگر تمام افراد شرکت‌کننده در آن ائتلاف مقدار بیشتری نسبت به یک تقسیم‌بندی دیگر که دقیقا مانند تقسیم‌بندی اول است به جز اینکه هر شرکت‌کننده در آن ائتلاف بخش متفاوتی از مقادیر را دریافت کند به‌طوری‌که قسمتی از کل مقادیر باشد که آن ائتلاف با شکل گرفتن می‌تواند بدست آورد.
یک تخصیص، دارای ویژگی هسته است؛ اگر ائتلافی (تخصیصی) وجود نداشته باشد که بتواند بر آن بهبود یابد. هسته مجموعه‌ای از تمام تخصیص‌های امکان‌پذیر با ویژگی هسته است.
یک ائتلاف، زیر مجموعه‌ای از مجموعه‌ای از بازیکنان است که استراتژی‌ها را هماهنگ می‌کنند و در مورد نحوه تقسیم بازپرداخت کل در میان اعضا توافق می‌کنند. به‌طور کلی در یک بازی با N بازیکن 2 N ائتلاف وجود دارد.
تاریخچه
مفهوم هسته در نظریه بازی دارای تاریخچه طولانی است. ایده اولیه هسته سال ۱۸۸۱ توسط فرانسیس یسیدرو اجورث در مباحث روند تجارت میان افراد اقتصادی در محیط‌های تجاری غیر بازار مطرح شد.۲ این فرایندهای تجاری بر اساس فرمول قرارداد تجاری مشترک بود. یک تخصیص کالاهای اقتصادی باید در برابر روندهای بازدارنده میان ائتلاف‌های چنین عوامل اقتصادی پایدار باشد. تخصیص‌هایی که این اصل ایمنی تجارت مجدد را برقرار می‌کنند، به عنوان تخصیص‌های تعادلی ادجورتین (Edgeworthian) شناخته می‌شوند. مجموعه‌ای از تخصیص‌های تعادلی ادجورتین توسط خودش «منحنی قرارداد» یا «هسته یک اقتصاد» نام‌گذاری شده‌اند.۳ جان فون نویمان و اسکار مورگنشترن نیز هسته را یک ایده جالب می‌پنداشتند، ولی آن‌ها فقط با بازی‌های مجموع-صفر که در آن‌ها هسته همیشه خالی است، کار می‌کردند. تعریف امروزی هسته توسط گیلیس (Gillies) سال ۱۹۹۶ معرفی شد.۴ پس از توسعه نظریه بازی، ایده بنیادی مسدود کردن توسط گیلیس، سال۱۹۵۳، در پایان‌نامه دکتری او مطرح شد. این ایده در ۱۹۵۹ با پیوند کارهای مرتبط گیلیس و ادجورت، توسط شوبیک (Shubik) توسعه یافت.۳
تعریف
یک بازی همکاری را در نظر بگیرید که مجموعه تمام بازیکانان و تابع مشخصه آن است.
یک تقسیم‌بندی مغلوب تقسیم‌بندی است اگر ائتلاف وجود داشته باشد به‌طوری‌که هر بازیکن در ، را ترجیح دهد. به صورت رسمی: برای تمام و وجود داشته باشد که
و هچنین بتواند را وادار کند (با تهدید به ترک ائتلاف همگانی و تشکیل ) به صورت رسمی : .5
وقتی که هسته وجود داشته باشد و خالی نباشد مجموعه‌ای از تقسیم‌بندی‌هایی است که مغلوب نشوند.
تعریف دیگری که هم‌ارز تعریف بالا است:
یک تقسیم‌بندی عضو هسته است اگر:
بهره‌وری:
عقلانیت ائتلاف: به ازای هر زیرمجموعه (ائتلاف) .
ویژگی‌ها
هسته همیشه خوش‌تعریف است اما می‌تواند خالی باشد.
هسته مجموعه بسته و محدب است.
گر v ∈ G N یک بازی جمع_ثابت باشد، آنگاه ∅=(C(V.
اگر {∅ \ مجموعه‌ای از ائتلاف‌های غیرخالی در مجموعه N بازیکن باشد، مجموعه B در صورتی در تعادل است که برای S ∈ B وجود داشته باشد، به‌طوری‌که برای هر بازیکن ۳ i ∈ N:
قضیه بنداروا-شاپلی(Bondareva-Shapley): هسته یک بازی غیرخالی است اگر و تنها اگر بازی «متعادل» باشد.۶۷
هر تعادل رقابتی ویژگی هسته را دارد (اما نه برعکس).
یک توالی از N تخصیص ، هسته عادلانه از (V, ) است، اگر برای هر S ⊆ N داشته باشیم:۸
در یک بازی N نفره که N عددی فرد است، در بازی که یک واحد کالا را میان یک ائتلاف که حداقل عضو دارد، تقسیم می‌کنیم؛ یک هسته خالی وجود دارد که به این معنی است که هیچ ائتلاف پایداری وجود ندارد.
مثال
مثال ۱: معدنچی‌ها
گروهی از n معدنچی را در نظر بگیرید که تعدادی قطعه طلا پیدا کردند. اگر هر دو معدنچی بتوانند یک قطعه طلا را حمل کنند پس سود هر ائتلاف S برابر: اگر تعداد معدنچی‌ها زوج و بیشتر از ۲ نفر باشند پس هسته شامل مجموعه‌ای می‌شود که هر معدنچی در آن ۱/۲ طلا به دست می‌آورد. اما اگر تعداد معدنچی‌ها فرد باشد هسته خالی می‌شود.
مثال ۲: دستکش‌ها
احمد و حسین هر دو دستکش می‌بافند. تمام دستکش‌ها یک اندازه هستند و هر دو دستکش که تشکیل یک جفت بدهند را می‌توان به ارزش ۵ تومان فروخت. اگر هر کس ۳ دستکش داشته باشد می‌خواهیم بدانیم چگونه درآمد حاصل از فروش را بین این دو نفر تقسیم کنیم؟
با توجه به اینکه آن‌ها روی هم ۳ جفت دستکش دارند پس روی هم ۱۵ تومان سود می‌کنند با توجه به اینکه هرکس به صورت جدا ۵ تومان سود می‌کند و حالت دیگری وجود ندارد پس هسته این بازی شامل (۷٫۵، ۷٫۵) می‌شود همچنین (۵، ۱۰) و یا (۹، ۶) هم شامل هسته می‌شوند.
مثال ۳: کفش‌ها
برای این بازی فرض کنید که اندازه تمام کفش‌ها یکسان هستند و هر لنگ چپ و راست کفش تشکیل یک جفت می‌دهند که ارزش آن ۱۰ تومان است. ۲۰۰۱ نفر بازیکن داریم که ۱۰۰۰ نفر آن‌ها لنگ چپ کفش را دارند و ۱۰۰۱ دیگر لنگ راست کفش را دارند. موضوع جالب این بازی هسته آن است:
هسته شامل یک مجموعه است که در آن بازیکنان که لنگ چپ کفش (کمیاب) را دارند ۱۰ تومان و بازیکنان با لنگ راست صفر تومان می‌گیرند هیچ تقسیم‌بندی دیگری هم نمی‌تواند این تقسیم‌بندی را مغلوب کند زیرا هیچ بازیکنی که لنگ چپ کفش را دارد زیر ۱۰ تومان را قبول نمی‌کند و هر تقسیم‌بندی که مقدار مثبتی به هر بازیکن با لنگ راست بدهد باید کمتر از ۱۰۰۰۰ تومان به سایر بازیکنان بدهد که همان بازیکنان به‌طور جدا می‌توانند ۱۰۰۰۰ تومان بدست آورند. پس فقط یک تقسیم‌بندی در هسته وجود دارد.
مثال۴:بازی ساده ۳ نفره سود قابل انتقال
تابع مشخصه یک بازی سه نفره سود قابل انتقال که در آن رای حداقل دو نفر برنده ائتلاف را تعیین می‌کند، به صورت زیر تعریف می‌کنیم:
۱=(v(S برای هر S حاوی حداقل دو عضو، v({i)=۰ برای همه i ∈ N.
واضح است که ∅=(C(N,V می‌شود، زیرا هر توافقی از بازپرداخت‌های امکان‌پذیر که به ائتلاف بزرگ پیشنهاد شود، حداقل توسط یک ائتلاف مسدود می‌شود.۹
هسته در بازی‌های رای‌گیری
بازی‌های رای‌گیری نشان دهنده یک کلاس ویژه‌ای از بازی‌های تعاملی هستند؛ که در آن رای‌دهندگانی از ائتلاف‌ها وجود دارند، که این قدرت را دارند که نظر خود را بدون در نظر گرفتن سایر رای‌دهندگان اعمال کنند؛ این در حالی است که سایر رای‌دهندگان قدرت تاثیرگذاری بر نتیجه را ندارند. مفهومی که می‌تواند نتیجه رای‌گیری را مشخص کند، هسته می‌باشد.
اگرچه بازی‌های رای‌گیری نوع خاصی از بازی‌های تعاملی هستند، در عین حال ممکن است در ساختار بسیار پیچیده باشند. علاوه بر این، وجود یک راه حل مانند هسته، به هیچ وجه در این بازی‌ها تضمین شده نیست. در بسیاری از بازی‌های رای‌گیری هسته خالی است، «پارادوکس رای گیری» نمونه‌ای از بازی سه نفره ساده با این ویژگی است.۱۰
هسته در نظریه تعادل عمومی
تعادل والراسین (Walrasian equilibria) یک اقتصاد مبادله‌ای در مدل عمومی تعادل، درون هسته یک بازی همکاری بین شرکت‌کننده‌ها می‌اقتد.
اقتصاد رفاه
نظریه بازی‌های همکاری
کارایی پارتو