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

در نظریه بازی‌ها، منظور از هسته مجموعه‌ای از تمام تقسیم‌بندی‌هایی است که نمی‌توان آن را توسط یک زیرمجموعه (ائتلاف) از شرکت‌کننده‌ها بهبود داد. یک ائتلاف را می‌گوییم می‌توان روی یک تقسیم‌بندی بهبود داد اگر تمام افراد شرکت‌کننده در آن ائتلاف مقدار بیشتری نسبت به یک تقسیم‌بندی دیگر که دقیقاً مانند تقسیم‌بندی اول است به جز اینکه هر شرکت‌کننده در آن ائتلاف بخش متفاوتی از مقادیر را دریافت کند به‌طوری‌که قسمتی از کل مقادیر باشد که آن ائتلاف با شکل گرفتن می‌تواند بدست آورد.

یک تخصیص، دارای ویژگی هسته است؛ اگر ائتلافی (تخصیصی) وجود نداشته باشد که بتواند بر آن بهبود یابد. هسته مجموعه‌ای از تمام تخصیص‌های امکان‌پذیر با ویژگی هسته است.

یک ائتلاف، زیر مجموعه‌ای از مجموعه‌ای از بازیکنان است که استراتژی‌ها را هماهنگ می‌کنند و در مورد نحوهٔ تقسیم بازپرداخت کل در میان اعضا توافق می‌کنند. به‌طور کلی در یک بازی با N بازیکن 2^N ائتلاف وجود دارد.^[۱]

تاریخچه

مفهوم هسته در نظریهٔ بازی دارای تاریخچهٔ طولانی است. ایدهٔ اولیهٔ هسته سال ۱۸۸۱ توسط فرانسیس یسیدرو اجورث در مباحث روند تجارت میان افراد اقتصادی در محیط‌ های تجاری غیر بازار مطرح شد.[۲] این فرایندهای تجاری بر اساس فرمول قرارداد تجاری مشترک بود. یک تخصیص کالاهای اقتصادی باید در برابر روندهای بازدارنده میان ائتلاف‌های چنین عوامل اقتصادی پایدار باشد. تخصیص‌هایی که این اصل ایمنی تجارت مجدد را برقرار می‌کنند، به عنوان تخصیص‌های تعادلی اجورث (Edgeworth) شناخته می‌شوند. مجموعه‌ای از تخصیص‌های تعادلی اجورث توسط خودش «منحنی قرارداد» یا «هستهٔ یک اقتصاد» نام‌گذاری شده‌اند.[۳] جان فون نویمان و اسکار مورگنشترن نیز هسته را یک ایدهٔ جالب می‌پنداشتند، ولی آن‌ها فقط با بازی‌های مجموع-صفر که در آن‌ها هسته همیشه خالی است، کار می‌کردند. تعریف امروزی هسته توسط گیلیس (Gillies) سال ۱۹۹۶ معرفی شد.[۴] پس از توسعه نظریهٔ بازی، ایده بنیادی مسدود کردن توسط گیلیس، سال۱۹۵۳، در پایان‌نامه دکتری او مطرح شد. این ایده در ۱۹۵۹ با پیوند کارهای مرتبط گیلیس و اجورث، توسط مارتین شوبیک (Martin Shubik) توسعه یافت.[۳]

تعریف

• یک بازی همکاری ${\displaystyle (N,v)}$را در نظر بگیرید که ${\displaystyle N}$ مجموعه تمام بازیکانان و ${\displaystyle v}$ تابع مشخصه آن است.

یک تقسیم‌بندی ${\displaystyle x\in \mathbb {R} ^{N}}$ مغلوب تقسیم‌بندی ${\displaystyle y}$است اگر ائتلاف ${\displaystyle C}$وجود داشته باشد به‌طوری‌که هر بازیکن در ${\displaystyle C}$، ${\displaystyle y}$را ترجیح دهد. به صورت رسمی: ${\displaystyle x_{i}\leq y_{i}}$ برای تمام ${\displaystyle i\in C}$ و وجود داشته باشد ${\displaystyle i\in C}$که ${\displaystyle x_{i}<y_{i}}$

و هچنین ${\displaystyle C}$بتواند ${\displaystyle y}$را وادار کند (با تهدید به ترک ائتلاف همگانی و تشکیل ${\displaystyle C}$) به صورت رسمی : ${\displaystyle \sum _{i\in C}y_{i}\leq v(C)}$.[5]

وقتی که هسته وجود داشته باشد و خالی نباشد مجموعه‌ای از تقسیم‌بندی‌هایی است که مغلوب نشوند.

• تعریف دیگری که هم‌ارز تعریف بالا است:

یک تقسیم‌بندی ${\displaystyle x\in \mathbb {R} ^{N}}$عضو هسته است اگر:

1. بهره‌وری: ${\displaystyle \sum _{i\in N}x_{i}=v(N)}$
2. عقلانیت ائتلاف: ${\displaystyle \sum _{i\in C}x_{i}\geq v(C)}$ به ازای هر زیرمجموعه (ائتلاف) ${\displaystyle C\subseteq N}$.

ویژگی‌ها

• هسته همیشه خوش‌تعریف است اما می‌تواند خالی باشد.
• هسته مجموعه بسته و محدب است.
• گر v ∈ G^N یک بازی جمع_ثابت باشد، آنگاه ∅=(C(V.
• اگر {∅} \ ${\displaystyle B\subset 2^{N}}$ مجموعه‌ای از ائتلاف‌های غیرخالی در مجموعه N بازیکن باشد، مجموعهٔ B در صورتی در تعادل است که ${\displaystyle \lambda _{S}>0}$ برای S ∈ B وجود داشته باشد، به‌طوری‌که برای هر بازیکن [۳] i ∈ N:

${\displaystyle \sum _{S\in B:i\in S}\lambda _{S}=1}$

• قضیهٔ بنداروا-شاپلی(Bondareva-Shapley): هسته یک بازی غیرخالی است اگر و تنها اگر بازی «متعادل» باشد.[۶][۷]
• هر تعادل رقابتی ویژگی هسته را دارد (اما نه برعکس).
• یک توالی از N تخصیص ${\displaystyle x_{1}^{N},x_{2}^{N},x_{3}^{N},...}$، هستهٔ عادلانه از (V, δ) است، اگر برای هر S ⊆ N داشته باشیم:[۸]

${\displaystyle x_{*}^{N}(S,\delta )\geq (1-\delta )\sum _{t=1}^{\infty }\delta ^{t-1}V(N;x_{t-1}^{N})(S)}$

• در یک بازی N نفره که N عددی فرد است، در بازی که یک واحد کالا را میان یک ائتلاف که حداقل ${\displaystyle {\frac {(N+1)}{2}}}$ عضو دارد، تقسیم می‌کنیم؛ یک هستهٔ خالی وجود دارد که به این معنی است که هیچ ائتلاف پایداری وجود ندارد.

مثال

مثال ۱: معدنچی‌ها

گروهی از n معدنچی را در نظر بگیرید که تعدادی قطعه طلا پیدا کردند. اگر هر دو معدنچی بتوانند یک قطعه طلا را حمل کنند پس سود هر ائتلاف S برابر:$${\displaystyle {\displaystyle v(S)={\begin{cases}|S|/2,&{\text{if}}|S|{\text{ is even}};\\(|S|-1)/2,&{\text{if}}|S|{\text{ is odd}}.\end{cases}}}}$$اگر تعداد معدنچی‌ها زوج و بیشتر از ۲ نفر باشند پس هسته شامل مجموعه‌ای می‌شود که هر معدنچی در آن ۱/۲ طلا به دست می‌آورد. اما اگر تعداد معدنچی‌ها فرد باشد هسته خالی می‌شود.

مثال ۲: دستکش‌ها

احمد و حسین هر دو دستکش می‌بافند. تمام دستکش‌ها یک اندازه هستند و هر دو دستکش که تشکیل یک جفت بدهند را می‌توان به ارزش ۵ تومان فروخت. اگر هر کس ۳ دستکش داشته باشد می‌خواهیم بدانیم چگونه درآمد حاصل از فروش را بین این دو نفر تقسیم کنیم؟

با توجه به اینکه آن‌ها روی هم ۳ جفت دستکش دارند پس روی هم ۱۵ تومان سود می‌کنند با توجه به اینکه هرکس به صورت جدا ۵ تومان سود می‌کند و حالت دیگری وجود ندارد پس هسته این بازی شامل (۷٫۵، ۷٫۵) می‌شود همچنین (۵، ۱۰) و یا (۹، ۶) هم شامل هسته می‌شوند.

مثال ۳: کفش‌ها

برای این بازی فرض کنید که اندازه تمام کفش‌ها یکسان هستند و هر لنگهٔ چپ و راست کفش تشکیل یک جفت می‌دهند که ارزش آن ۱۰ تومان است. ۲۰۰۱ نفر بازیکن داریم که ۱۰۰۰ نفر آن‌ها لنگهٔ چپ کفش را دارند و ۱۰۰۱ دیگری لنگهٔ راست کفش را دارند. موضوع جالب این بازی هسته آن است:

هسته شامل یک مجموعه است که در آن بازیکنان که لنگهٔ چپ کفش (کمیاب) را دارند ۱۰ تومان و بازیکنان با لنگهٔ راست صفر تومان می‌گیرند هیچ تقسیم‌بندی دیگری هم نمی‌تواند این تقسیم‌بندی را مغلوب کند زیرا هیچ بازیکنی که لنگ چپ کفش را دارد زیر ۱۰ تومان را قبول نمی‌کند و هر تقسیم‌بندی که مقدار مثبتی به هر بازیکن با لنگهٔ راست بدهد باید کمتر از ۱۰۰۰۰ تومان به سایر بازیکنان بدهد که همان بازیکنان به‌طور جدا می‌توانند ۱۰۰۰۰ تومان بدست آورند. پس فقط یک تقسیم‌بندی در هسته وجود دارد.

مثال۴:بازی سادهٔ ۳ نفره سود قابل انتقال

تابع مشخصهٔ یک بازی سه نفرهٔ سود قابل انتقال که در آن رأی حداقل دو نفر برندهٔ ائتلاف را تعیین می‌کند، به صورت زیر تعریف می‌کنیم:

۱=(v(S برای هر S حاوی حداقل دو عضو، v({i})=۰ برای همهٔ i ∈ N.

واضح است که ∅=(C(N,V می‌شود، زیرا هر توافقی از بازپرداخت‌های امکان‌پذیر که به ائتلاف بزرگ پیشنهاد شود، حداقل توسط یک ائتلاف مسدود می‌شود.[۹]

هسته در بازی‌های رأی‌گیری

بازی‌های رأی‌گیری نشان‌دهنده یک کلاس ویژه‌ای از بازی‌های تعاملی هستند؛ که در آن رأی‌دهندگانی از ائتلاف‌ها وجود دارند، که این قدرت را دارند که نظر خود را بدون در نظر گرفتن سایر رأی‌دهندگان اعمال کنند؛ این در حالی است که سایر رأی‌دهندگان قدرت تأثیرگذاری بر نتیجه را ندارند. مفهومی که می‌تواند نتیجهٔ رأی‌گیری را مشخص کند، هسته می‌باشد.

اگرچه بازی‌های رأی‌گیری نوع خاصی از بازی‌های تعاملی هستند، در عین حال ممکن است در ساختار بسیار پیچیده باشند. علاوه بر این، وجود یک راه‌حل مانند هسته، به هیچ‌وجه در این بازی‌ها تضمین شده نیست. در بسیاری از بازی‌های رأی‌گیری هسته خالی است، «پارادوکس کندورسه یا رأی‌گیری» نمونه‌ای از بازی سه نفرهٔ ساده با این ویژگی است.[۱۰]

هسته در نظریه تعادل عمومی

تعادل والراسین (Walrasian equilibria) یک اقتصاد مبادله‌ای در مدل عمومی تعادل، درون هسته یک بازی همکاری بین شرکت‌کننده‌ها می‌اقتد.

جستارهای وابسته

• اقتصاد رفاه
• نظریه بازی‌های همکاری
• کارایی پارتو

منابع

1. Coalitional Game Theory for Communication Networks: A Tutorial, Authors: Walid Saad , Zhu Han , M´erouane Debbah , Are Hjørungnes ,and Tamer Bas ,cited:arXiv:0905.4057 doi:10.1109/MSP.2009.000000 .Submitted on 25 May 2009

^{[۱][۲][۳][۴][۵][۶][۷][۸][۹][۱۰]}

1. خطای یادکرد: خطای یادکرد:برچسب <ref>‎ غیرمجاز؛ متنی برای یادکردهای با نام MSP 2009 وارد نشده است. (صفحهٔ راهنما را مطالعه کنید.).
2. Kannai, Y. (1992). "The core and balancedness". In Aumann, Robert J. ; Hart, Sergiu. Handbook of Game Theory with Economic Applications. I. Amsterdam: Elsevier. pp. 355–395. ISBN 978-0-444-88098-7.
3. R.P. Gilles, The Cooperative Game Theory of Networks and Hierarchies, Theory and Decision Library C 44, doi: 10.1007/978-3-642-05282-8_2, .C Springer-Verlag Berlin Heidelberg 2010
4. Gillies, D. B. (1959). "Solutions to general non-zero-sum games". In Tucker, A. W. ; Luce, R. D. Contributions to the Theory of Games IV. Annals of Mathematics Studies. 40. Princeton: Princeton University Press. pp. 47–85.
5. As noted by Shapley, L. S. ; Shubik, M. (1969). "On Market Games". Journal of Economic Theory. 1 (1): 9–25. doi:10.1016/0022-0531(69)90008-8. due to the contribution of Mr. E. Kohlberg
6. Bondareva, Olga N. (1963). "Some applications of linear programming methods to the theory of cooperative games (In Russian)". Problemy Kybernetiki. 10: 119–139.
7. Shapley, Lloyd S. (1967). "On balanced sets and cores". Naval Research Logistics Quarterly. 14: 453–460. doi:10.1002/nav.3800140404.
8. On the Core of Dynamic Cooperative Games, Authors: Ehud Lehrer, Marco Scarsini, cited: arXiv:1203.2832 [cs.GT], doi: 10.1007/s13235-013-0078-7, Submitted on 13 Mar 2012.
9. Peters H. (2015) TU-Games: Domination, Stable Sets, and the Core. In: Game Theory. Springer Texts in Business and Economics. Springer, Berlin, Heidelberg doi: https://doi.org/10.1007/978-3-662-46950-7_16
10. Aymeric Lardon. The core of voting games: a partition approach. International Game Theory Review, World Scientific Publishing, 2015, 17 (3), <10.1142/S0219198915500012>. <halshs-00544034v2>