نمایش مبدأ برای بازی هم‌دستی

[[نظریه بازی|نظریه بازی‌ها]] به دو شاخه تقسیم می‌شود: '''بازی‌های هم‌دستی''' (با همکاری، تعاونی) و [[بازی‌های بدون همکاری]]. تفاوت این دو شاخه در وابستگی متقابل بازیکنان است. بازی‌های بدون همکاری مدلی با جزئیات بسیار است که حرکات مجاز برای بازیکنان، [[استراتژی]] و سود و هزینه آن‌ها را تحلیل می‌کند. در این نوع بازی، بازیکنان امکان اتحاد و رفتار مشترک ندارند یا این امکان را دارند اما به شرطی که این رفتار مشترک و معاهده منعقد شده بین آن‌ها اثر خارجی بر بازیگران ثالث نداشته باشد.<ref>http://www.gametheory.net/dictionary/Non-CooperativeGame.html</ref>
در حالی که در بازی‌های هم‌دستی این سطح از جزئیات وجود ندارد و بازی‌هایی هستند میان گروهی از بازیکنان که در آن به اثرات خارجی رفتار مشترکی که آن‌ها در نظر دارند و رویدادی که منجر به این رفتار مشترک شده توجه می‌شود.

در نظریه بازی‌های هم‌دستی، به کلیت استراتژی‌های انتخاب هر بازیکن دقت می‌شود و بیشتر تمرکز معطوف به تحلیل ائتلاف‌هایی که بازیکنان باهم به وجود می‌آورند استراتژی‌های آنان در این ائتلاف است. به این صورت که سود به‌دست آمده پس از ایجاد هر ائتلاف و تأثیر آن بررسی می‌شود و با توجه به نتایج به‌دست آمده در مورد امکان ایجاد یا عدم ایجاد این ائتلاف‌ها تصمیم گرفته می‌شود. در این بازی‌ها آنچه به‌صورت دقیق مشخص نمی‌شود این موضوع است که در فرایند تشکیل این ائتلاف‌ها چه کنش‌هایی میان بازیکنان مختلف رخ می‌دهد.<ref>{{Cite web |url = https://pdfs.semanticscholar.org/8499/0a1e168debdd5fade5b6af2dfa022e521d9f.pdf |title = Cooperative Game Theory: Charactristic Functions, Allocations, Marginal Contribution }}{{پیوند مرده}}</ref><ref name = r2>{{Cite web|url = http://www.uib.cat/depart/deeweb/pdi/hdeelbm0/arxius_decisions_and_games/Cooperative_game_theory.pdf| title = Cooperative Game Theory| first = R | last = Chandrasekaran}}</ref>
برای مثال، فرض کنید که بازیکنان ما احزاب مختلف راه‌یافته به مجلس نمایندگان هستند و هر یک از این احزاب قدرت مشخصی دارد. این قدرت با توجه به تعداد صندلی اشغال شده توسط آن‌ها در مجلس نمایندگان بررسی می‌شود. در نظریه بازی‌های هم‌دستی ائتلاف‌های مختلف و چگونگی در اختیار گرفتن اکثریت توسط آن‌ها مشخص می‌شود، اما به فرایند تشکیل این ائتلاف‌ها و بحث‌ها و مذاکرات لازم توجه نمی‌شود و در اندازه‌گیری‌های ما این مقادیر دخیل نیستند.<ref>http://www.cdam.lse.ac.uk/Reports/Files/cdam-2001-09.pdf</ref>

== مفاهیم ریاضی ==
<math> N = \{1,2,...,n\}</math> نشان‌دهنده مجموعه بازیکنان است. هر زیرمجموعه ناتهی از <math> N</math> یک [[ائتلاف]] یا [[اتحاد]] نامیده می‌شود. برای مثال اعضای مشغول در یک تیم کاری می‌تواند یک ائتلاف باشد. به کل مجموعه <math> N</math> نیز ائتلاف بزرگ گفته می‌شود. همچنین ائتلاف تهی با علامت ∅ نشان داده می‌شود و مجموعه تمام ائتلاف‌ها با [[مجموعه توانی]] <math>N</math> برابر است که آن را با <math>P(N)</math> نمایش می‌دهیم. هر ائتلاف را می‌توان یکی از اجزای این مجموعه برشمرد.

== تابع مشخصه ==
[[تابع مشخصه]] یک بازی <math>n</math> نفره تابعی است که یک مقدار را به هر زیرمجموعه از بازیکن‌ها نسبت می‌دهد.

<math>v : 2^N \to \mathbb{R} </math>

مقدار  <math>v(s)</math> میزان بیشینه سود زیرمجموعه <math>s</math> از بازیکنان را نشان می‌دهد در صورتی که این بازیکنان یک ائتلاف را تشکیل دهند. این میزان با صفر در نظر گرفتن اثر خارجی احتمالی ائتلاف‌های دیگر روی این ائتلاف بررسی می‌شود. در بعضی‌اوقات این مقدار، [[ماکسمین]] هزینه در نظر گرفته می‌شود به این صورت که همه <math>N-s</math> بازیکن دیگر هم به عنوان یک ائتلاف در نظر گرفته می‌شوند.
(<math> v(s) = max_{x \in X_s} min_{y \in YN-S} \sum{\pi_i} (x,y) </math>).<ref name = r10>http://www.math.cornell.edu/~erin/undergrad/121/121review.pdf</ref>

به <math>v(s)</math>، ارزش ائتلاف <math>s</math> نیز گفته می‌شود.<ref name = r3>{{Cite web| url = http://www.utdallas.edu/~chandra/documents/6311/coopgames.pdf | title = Cooperative Game Theory}}</ref>
همچنین <math>v(0)</math> برابر صفر در نظر گرفته می‌شود.

=== ویژگی‌ها ===
==== زبرجمعی ====
توابع مشخصه در این قسمت غالباً به صورت '''توابع زبرجمع''' در نظر گرفته می‌شوند. یک تابع زبرجمع است اگر شرط زیر روی آن برقرار باشد.
(v(S ∪ T) ≥ v(S) + v(T

البته این تعریف زمانی برقرار است که S ∩ T = ∅ هم برقرار باشد. یعنی عبارت دوم شرط عبارت اول است.

==== تقسیم پذیری پایان ناپذیر ====
میزان سود ناشی از هر بازی را تقسیم پذیر پایان ناپذیر می‌نامیم اگر بتوان این میزان را بین بازیکنان مشخص به هر صورت ممکن تقسیم نمود.

==== نسبت ====
یک نسبت به میزان [[سهمی]] گفته می‌شود که یک بازیگر مشخص از سود کلی بدست آمده از آن خود می‌کند. برای یک بازی با n بازیگر مجموعه نسبت‌ها به این صورت نوشته می‌شود.

<math display="block"> E(v) = \{ x^n \in R^n : \sum_{n=1}^n x_i = v(N) , and x_i \leq v(\{i\}), \forall i = 1, 2, ... ,n \}</math>

==== غلبه ====
نسبت x به نسبت y، روی فضای s غلبه دارد [[اگر و تنها اگر]] دو شرط زیر برقرار باشد<ref name= r10 />

<math> x_i < y_i , \forall i \in S</math>

<math>\sum_{i \in s} x_i \leq v(N)
</math>

== ارتباط با بازی‌های بدون همکاری ==
فرض کنیم <math>G</math> یک بازی بدون همکاری است، حال فرض می‌کنیم که بازیکنان توانایی ایجاد ائتلاف‌های مختلف با توانایی اعمال رفتار مشترک را داشته باشند. چند بازی هم‌دستی با <math>G</math> در ارتباط خواهندبود. این بازی‌ها را تمثال‌های <math>G</math> می‌نامیم. دو نمونه معروف از این تمثال‌ها در زیر آمده‌اند.
* '''بازی‌های مؤثر آلفا''' (α-effective game) بازی‌هایی هستند که در آن به ازای هر ائتلاف مجموع سود بازیکنان با پیوستن به آن‌ها ضمانت شده‌است. ضمانت به این معنا است که این میزان، بیشینه کمینه هاست. یعنی بیشینه میزان سود کمینه در صورت انتخاب سایر استراتژی‌ها.
* '''بازی‌های مؤثر بتا''' (β-effective game) بازی‌هایی هستند که در آن به ازای هر ائتلاف مجموع سود بازیکنان با پیوستن به آن‌ها ضمانت استراتژیک شده‌است. ضمانت استراتژیک به‌این معنا است که این میزان، کمینه بیشینه هاست. یعنی کمینه میزان سود بیشینه در صورت انتخاب سایر استراتژی‌ها.<ref>Aumann, Robert J. "The core of a cooperative game without side payments." Transactions of the American Mathematical Society (1961): 539-552.</ref>

== راه حل یا نتیجه یک بازی باهمکاری ==
شامل:

۱- تجزیه <math>N</math> به ائتلاف هاست که این تجزیه، ساختار ائتلاف نامیده می‌شود.
[[ساختار ائتلاف]] <math>CS = \{S_1,..,S_k\}</math> در مجموعه <math>N</math> یک مجموعه‌ای [[ناتهی]] از زیر مجموعه‌های ناتهی از <math>N</math> که شرایط زیر را داشته باشد:

<math>\bigcup\limits_{i=1}^{k} S_i = N; S_i \cap S_j = \emptyset\  if\ i \neq j</math>

<math>v(CS)</math> برابراست با  <math>\sum_{j=1}^{k} v(S_j)</math>.

۲- یک بردار سود یا هزینه است که ارزش هر ائتلاف را بین بازیکنانش تقسیم می‌کند.<ref name= r3 />
بردار <math>x = (x_1, x_2,.., x_n)</math> بردار سود یا هزینه برای یک ساختار ائتلاف  <math>CS = \{S_1,..,S_k\}</math> روی <math> N = \{1,2,...,n\}</math> است اگر:

<math>x_i \geq 0\  \forall i \in N </math>

<math>\sum_{i \in S_j}^{} x_i \leq v(S_j)</math>

نتیجه یک زوج <math>[CS, x]</math> است که <math>x(S) = \sum_{i \in S}^{} x_i</math> سود یا هزینه ائتلاف <math>S</math> تحت بردار <math>x </math> است. <math>x </math> در <math>[CS, x]</math> کارآمد است اگر : <math>\sum_{i \in S_j}^{} x_i = v(S_j)</math>
این بردار برای ساختار ائتلاف <math>CS_N</math> یک [[نسبت دادن]] است اگر کارآمد و تک به تک عاقلانه باشد.

<math>\sum_{i \in S_j}^{} x_i = v(S_j)</math>

<math>x_i \geq v(\{i\}) \ \forall i \in N</math>

== انواع مختلف بازی ==
'''بازی یکنواخت<ref name= r3 />'''

بازی <math>[N,v]</math> یکنواخت است اگر  <math>[S \subseteq T] \Rightarrow v(S) \leq v(T)</math>

بیشتر بازی‌ها یکنواخت هستند. غیریکنواختی در مواقعی به وجود می‌آید که بعضی از بازیکنان به شدت از هم بدشان بیاید یا هزینه‌های برقراری ارتباط به صورت غیرخطی به نسبت اندازه اتحاد افزایش یابد.

'''بازی افزایشی<ref name= r3 />'''

بازی <math>[N,v]</math> افزایشی است اگر <math>[S \cap T = \emptyset] \Rightarrow v(S \cup T) \geq v(S) + v(T) </math> برقرار باشد.

'''بازی محدب<ref name= r3 />'''

یک بازی محدب است اگر <math>v(S \cup T) + v(s \cap T) \geq v(S) + v(T)  \ \ \forall S,T \subseteq N</math> برقرار باشد.
یک بازی محدب، افزایشی است.

'''بازی جمع ثابت<ref name= r3 />'''
یک بازی جمع ثابت است اگر <math>v(S) + v(N-S) = V(N) \ \ \forall S \subseteq N</math>

'''بازی ساده'''

یک بازی ائتلافی ساده است اگر ارزش‌ها در تابع مشخصه ۰ یا ۱ باشند. (۰ به معنای باخت و ۱ به معنای برد است)
یک بازی ساده را می‌توان با <math>W</math> نشان داد که <math>W</math> مجموعه از ائتلاف‌های بازی است که برنده‌اند و باقی ائتلاف‌ها بازنده هستند.
به بازی‌های ساده ابرگراف یا تابع‌های منطقی نیز گفته می‌شود.
* یک بازی ساده '''یکنواخت''' است اگر هر ائتلافی که شامل یک ائتلاف برنده است خود برنده باشد. <math>S \in W</math> و  <math>S\subseteq T</math> نتیجه دهد <math>T \in W</math>.
* یک بازی ساده '''مناسب''' است اگر مکمل هر ائتلاف برنده، بازنده باشد. <math>S \in W</math> نتیجه دهد <math>N\setminus S \notin W</math>.
* یک بازی ساده، قوی است اگر مکمل هر ائتلاف بازنده، برنده باشد. <math>S \notin W</math>  نتیجه دهد <math>N\setminus S \in W</math>.
** اگر یک بازی ساده، مناسب و قوی باشد، یک ائتلاف برنده است اگر و تنها اگر مکمل آن بازنده باشد.
* در یک بازی ساده، بازیکن وتو بازیکنی است که در همه ائتلاف‌های برنده حضور دارد؛ بنابراین اگر چنین بازیکنی وجود داشته باشد، ائتلاف‌هایی که شامل این بازیکن نیستند ائتلاف‌های بازنده‌اند.
** یک بازی ساده ضعیف است اگر بازیکن وتو داشته باشد.
** دیکتاتور در بازی ساده بازیکن وتو است.
* حامل یک بازی ساده <math>W</math>، مجموعه <math>T \subseteq N </math> است به این صورت که به ازای هر ائتلاف <math>S</math> داریم <math>S \in W</math> اگر و تنها اگر <math>S \cap T \in W </math> برقرار باشد.
** اگر یک بازی ساده حامل داشته باشد، از بازیکنانی که جز آن نباشند صرف نظر می‌شود. بعضی‌اوقات به بازی ساده‌ای که متناهی حامل داشته باشد بازی متناهی گفته می‌شود. (حتی اگر تعداد بازیکنان آن نامتناهی باشد)
* عدد ناکامورا در یک بازی ساده برابر با کمینه تعداد ائتلاف‌های برنده است که باهم هیچ اشتراکی نداشته باشند. طبق قضیه ناکامورا این عدد میزان عقلانیت بازی را اندازه می‌گیرد.

بین تعاریف بالا در بازی ساده روابطی وجود دارد.<ref name=peleg02hbscw>{{Cite book | last1 = Peleg | first1 = B. | chapter = Chapter 8 Game-theoretic analysis of voting in committees | doi = 10.1016/S1574-0110(02)80012-1 | title = Handbook of Social Choice and Welfare Volume 1 | series = Handbook of Social Choice and Welfare | volume = 1 | pages = 195–201 | year = 2002 | isbn = 978-0-444-82914-6 | pmid = | pmc =}}</ref> برای مثال:
* اگر یک بازی ساده، ضعیف باشد، مناسب هم هست.
* یک بازی ساده دیکتاتوری است اگر و تنها اگر قوی و ضعیف باشد.

== راه حل‌های عادلانه<ref name= r2 /> ==
فرض اولیه در بازی‌های باهمکاری این است که ائتلاف بزرگ شکل می‌گیرد. چالش این است که هزینه <math>v(N)</math> را بین بازیکنان عادلانه تقسیم کنیم. یک راه حل یک بردار  <math>x \in \R^n</math> است که نشان دهنده تخصیص به بازیکنان است. راه حل‌ها براساس تعریف‌های متفاوتی از عادلانه بودن تعریف می‌شوند.
تعاریف:
* کارآمد بودن: بردار هزینه دقیقاً مقدار کل را تقسیم می‌کند.
* تک به تک عاقلانه: هیج بازیکنی کمتر از چیزی که به تنهایی می‌توانست بدست‌آورد، به‌دست نیاورد.
* وجود داشتن: این راه حل برای همه بازی‌ها وجود داشته باشد.
* منحصر به فرد بودن: این راه حل برای هر بازی منحصربه‌فرد باشد.
* تقارن: راه حل به بازیکن‌های قرینه مقدار یکسان تخصیص دهد. دو بازیکن <math>i</math> و <math>j</math> قرینه هستند اگر <math>v(S \cup \{i\}) = v(S \cup \{j\}), \forall S \subseteq N / \{i,j\} </math>
* افزایشی: تخصیص دادن به یک بازیکن در مجموع دو بازی برابر باشد با مجموع تخصیص دادن به همان بازیکن در دو بازی به صورت تکی.
* صفر تخصیص دادن به بازیکنان پوچ یا مصنوعی: بازیکن پوچ یا مصنوعی <math>i</math> این شرط را دارد: <math>v(S \cup \{i\}) = v(S), \ \forall S \subseteq N / \{i\} </math>  در واقع بازیکن پوچ یا مصنوعی به بازیکنی گفته می‌شود که در فرایند تولید سود هیچ مشارکتی ندارد.
* یک بردار هزینه کارآمد و تک به تک عاقلانه یک [[نسبت دادن]] نامیده می‌شود.

'''چانه زنی [[نش]]'''

در حالتی که ۲ بازیکن داریم استفاده می‌شود.

'''مجموعه پایدار'''

مجموعه پایدار یک بازی اولین راه حلی بود که برای بازی‌های با بیشتر از ۲ بازیکن پیشنهاد شد.
اگر <math>v</math> یک بازی باشد و <math>x</math> و <math>y</math> دو نسبت دادن به <math>v</math>، در این صورت <math>x</math> بر <math>y</math> غلبه می‌کند اگر اتحاد <math> S \neq \emptyset </math> وجود داشته باشد که <math>x_i > y_i , \forall i \in S</math> و <math>\sum_{i \in S}^{} x_i \leq v(S) </math>.
به عبارتی دیگر بازیکنان در <math>S</math> هزینه‌های <math>x</math> را به  <math>y</math> ترجیح می‌دهند و اگر  <math>y</math> انتخاب شود می‌توانند تهدید به ترک اتحاد بزرگ کنند زیرا وقتی به تنهایی عمل کنند حداقل به اندازه <math>y</math> کسب می‌کنند که از<math>y</math>  بیشتر است.
مجموعه پایدار مجموعه‌ای از نسبت دادن هاست که دو شرط زیر را دارند:
* پایداری درونی: هیچ برداری در آن توسط بردار دیگری در مجموعه مغلوب نمی‌شود.
* پایداری بیرونی: همه بردارهای خارج مجموعه توسط بردارهای داخل آن مغلوب می‌شوند.
[[فون نیومن]] و مرگانسترن مجموعه پایدار را به عنوان مجموعه‌ای از رفتارهای قابل قبول در جامعه توصیف می‌کنند؛ زیرا به ازای هر رفتار نامطلوب یک جایگزین قابل قبول وجود دارد و خود رفتارهای قابل قبول برهم برتری ندارند.
* مجموعه پایدار لزوماً وجود ندارد و اگر وجود داشته باشد، معمولاً یکتا نیست. پیدا کردن آن‌ها هم بسیار دشوار است. دشواری‌های پیدا کردن این راه حل باعث به وجود آمدن راه حل‌های دیگر شده‌است.

'''[[هسته (نظریه‌ی بازی‌ها)|هسته]]'''

یکی از ایده‌های اصلی حل این مسئله [[هسته]] است. هسته بر مبنای پایداری هر ائتلاف ایجاد شده‌است. این ایده بر این مبنا است که شرط الزامی برای ایجاد یک ائتلاف، آن است که هیچ زیرمجموعه ای از بازیکنان انگیزه خروج از آن را نداشته باشند. به عبارتی ائتلاف پایدار باشد.

<math>core(v) = \bigg\{ (x_1,...,x_n)/ \sum_{i=1}^{n} x_i \leq v(N), \ \forall S \sum_{i \in S}^{} x_i \geq v(S) \bigg\} </math>

برای بررسی بیشتر این موضوع یک بردار سود را در نظر بگیرید، <math>(x_1, ..., x_n)</math> به صورتی که <math>x_i</math> سود بازیکن <math>i</math>ام باشداگر مجموع توابع مشخصه‌های تک تک بازیکنان حاضر در یک ائتلاف بیشتر از مجموع میزان سود تخصیص یافته به آن‌ها در بردار سود باشد، این ائتلاف حاضر به پذیرش این بردار نخواهد بود این شیوه ناپایدار است. در واقع برای پایداری دو شرط زیر باید برقرار باشند:

اول <math>\sum_{i=1}^{n} x_i \leq v(N) </math>
دوم اینکه مجموعه <math>S</math> از بازیکنان حداقل به اندازه وقتی که ائتلاف  <math>S</math> را تشکیل می‌دادند دریافت کنند. به عبارتی دیگر : <math>\forall S, \sum_{i \in S}^{} x_i \geq v(S) </math>

اگر اندازه هسته بازی برابر ۰ باشد یا به عبارتی این [[مجموعه تهی]] باشد به‌این معناست که هیچ شیوه تقسیم پایداری برای این بازی وجود ندارد و اگر اندازه این هسته بیشتر از ۰ باشد و مجموعه تهی نباشد به‌این معناست که چند شیوه برای تقسیم پایدار بین ائتلاف‌های موجود وجود دارند.
* هسته یک بازی می‌تواند تهی باشد. بازی‌هایی که هسته ناتهی دارند بازی‌های متعادل نامیده می‌شوند.
* هسته بازی لزوماً شامل یک بردار منحصر به فرد نیست.
* هسته، درون هر مجموعه پایداری وجود دارد.

پس جواب داشتن یا نداشتن یک مسئله بازی هم‌دستی به اندازه هسته بستگی دارد. پس بیشتر بحث‌های مربوط به پاسخ این مسئله پیرامون دو سؤال خواهد بود، آیا اندازه هسته این بازی هم‌دستی برابر ۰ است یا خیر؟ آیا بردار تقسیم سود <math>(x_1, ..., x_n)</math> عضو هسته این بازی هم‌دستی یا خیر؟

'''[[مقدار شپلی]]'''<ref>http://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/ieeeis2012d.pdf</ref>

راه حل‌های کلی علاوه بر چگونگی تقسیم کلی سود به تقسیم سود بین اعضای مختلف یک ائتلاف هم می‌پردازند. فرض کنید ائتلاف <math>N</math> شکل گرفته و از شکل‌گیری آن سود <math>v(N)</math> نصیب این ائتلاف خواهد شد. مقدار شپلی، بردار هزینه یکتایی است که اصولی برای این تقسیم تعیین می‌کند. فرض کنید که به هر بازیکن <math>i</math> میزان <math>q_i</math> سود خواهد رسید. این توزیع باید ویژگی‌های کارآمد بودن، تقارن و افزایشی را داشته باشد و همچنین در این توزیع بازیگر پوچ یا مصنوعی نباید از سود سهمی ببرد.
مقدار شپلی یک بازی افزایشی، تک به تک عاقلانه است ولی در کل این حکم درست نیست.

== جستارهای وابسته ==
* [[اجماع]]
[[بازی هماهنگی]]
[[تعادل نش]]

== منابع ==
{{پانویس|۲}}{{نظریه بازی‌ها}}
[[رده:نظریه بازی‌ها]]
[[رده:روش‌های کمی و ریاضی (اقتصاد)]]
[[رده:بازی‌های تعاونی]]