بازی مجموع-صفر

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

ویژگی مجموع صفر (اگر یکی بدست آورد دیگری از دست می دهد) به معنای آن است که هر نتیجه از موقعیت مجموع-صفر یک بهینه ی پارتو می باشد ( بطور کلی هر بازی که همه ی استراتژی های آن بهینه ی پارتو باشند یک بازی کشمکشی نامیده می شود).
وضعیت هایی که شرکت کنندگان همگی می توانن با هم سود یا ضرر کنند غیر مجموع-صفر هستند.بنابراین دو کشور را در نظر بگیرید که یکی مقدار تولیدات موز آن زیاد می باشد و دیگری تولیدات سیب زیادی دارد.حال اگر این دو کشور با هم مبادلات موز و سیب داشته باشند، در این مبادلات هر دو سود خواهند برد و این یک وضعیت غیر مجموع-صفر می باشد. نوع دیگری از بازی های غیر مجموع-صفر این است که در آن مجموع بدست آوردن ها و از دست دادن های بازیکن ها در برخی اوقات بیشتر یا کمتر از مقداری است که با آن شروع کرده اند.

راهکار[ویرایش]

در یک بازی دونفره مجموع-صفر متناهی راه حل های متفاوت تعادل نش، مینیماکس و ماکسیمین راه حل یکسان به دست می دهند. در همه راه حل ها، بازیکنان بر اساس یک استراتژی ترکیبی بازی می کنند.

مثال[ویرایش]

A zero-sum game
A B C
1 30, -30 -10, 10 20, -20
2 10, -10 20, -20 -20, 20

ماتریس نتایج یک بازی، یک نمایش به درد بخور است. به عنوان مثال، بازی دونفره مجموع صفر نمایش داده شده را در نظر بگیرید. ترتیب بازی به این شکل است: بازیکن اول (قرمز) یکی از دو حرکت 1 یا 2 را به صورت پنهانی انتخاب می کند. بازیکن دوم (آبی) بدون اطلاع از انتخاب بازیکن اول، یکی از سه حرکت A، B یا C را به صورت مخفیانه انتخاب می کند. سپس انتخاب ها فاش می شوند و مجموع امتیازات هرکدام از بازیکن ها بر اساس حرکت هایی که انتخاب کرده بودند امتیازاتشان تغییر می کند.

مثال: قرمز حرکت 2 را انتخاب می کند و آبی حرکت B را انتخاب می کند. وقتی امتیازها اختصاص داده می شوند، قرمز 20 امتیاز و آبی 20 امتیاز کسب می کند.

در این مثال، هر دو بازیکن ماتریس نتایج را می دانند وتلاش می کنند امتیاز خود را بیشینه کنند. بازیکن ها باید چه کنند؟ قرمز می تواند این گونه استدلال کند: «با حرکت 2، تا 20 امتیاز از دست می دهم و فقط می توانم 20 امتیاز بگیرم؛ در حالی که با حرکت 1، فقط 10 امتیاز ممکن است از دست بدهم ولی می توانم تا 30 امتیاز به دست آورم. در نتیجه حرکت 1 بهتر به نظر می رسد.» با استدلالی مشابه، آبی حرکت C را انتخاب خواهد کرد. اگر هر دو بازیکن این حرکت ها را انتخاب کنند، قرمز 20 امتیاز کسب خواهد کرد. اما اگر آبی استدلال قرمز را پیش بینی کند که او حرکت 1 را انتخاب می کند، خودش حرکت B را انتخاب خواهد کرد تا 10 امتیاز کسب کند؟ یا اگر در عوض، قرمز این ترفند را پیش بینی کند حرکت 2 را انتخاب می کند تا 20 امتیاز کسب کند؟

امیل بورل و جان فون نویمان به این بینش اساسی معتقد بودند که احتمالات راهی برای برون رفت از این مسئله بغرنج به دست می دهد. دو بازیکن، به جای اتخاذ یک تصمیم قطعی برای انتخاب حرکت، احتمالی را به حرکت هایشان نسبت می دهند. سپس از یک ابزار تصادفی استفاده می کنند که با توجه به احتمالات نسبت داده شده یک حرکت برای آن ها انتخاب می کند. هر بازیکن، احتمالات را به منظور کمینه کردن بیشینه امید ریاضیِ از دست دادن امتیاز، به طور مستقل از استراتژی حریف محاسبه می کند. این روش، منجر به یک مسئله برنامه ریزی خطی با استراتژی های بهینه برای هر بازیکن می شود. این روش مینیماکس تقریباً می تواند برای هر بازی مجموع-صفر دونفره، استراتژی های بهینه را محاسبه کند.


برای مثال گفته شده در بالا، معلوم می شود که قرمز باید حرکت 1 را با احتمال {4 \over 7} و حرکت 2 را با احتمال {3 \over 7} انتخاب کند و آبی باید احتمالات صفر، {4 \over 7} و {3 \over 7} را به سه حرکت A، B و C نسبت دهد. با این روش، قرمز {20 \over 7} امتیازات را به طور میانگین در هر بازی از آن خود خواهد کرد.

روش حل[ویرایش]

تعادل نش برای یک بازی مجموع-صفر دونفره، با حل یک مسئله برنامه ریزی خطی به دست می آید. فرض کنید M ماتریس نتایج یک بازی مجموع-صفر است که در آن عنصر M_{i,j} نتیجه حاصل از حالتی است که بازیکن کمینه کننده از استراتژی i و بازیکن بیشینه کننده از استراتژی j استفاده کند (به عبارت دیگر بازیکنی که تلاش می کند نتیجه نهایی کمینه شود سطر را انتخاب می کند و بازیکنی که تلاش می کند نتیجه نهایی بیشینه شود ستون را انتخاب می کند.) فرض کنید هر عنصر M مثبت باشد. بازی، حداقل یک تعادل نش دارد. تعادل نش با حل کردن برنامه خطی زیر برای یافتن بردار u به دست می آید:

عبارت \sum_{i} u_i را با در نظر گرفتن محدودیت های u>=0 و M u>=1 کمینه کنید.

محدودیت اول می گوید هر عنصر بردار u باید نامنفی باشد و محدودیت دوم می گوید هر عنصر بردار  M u باید حداقل 1 باشد. برای بردار u حاصل معکوس مجموع عناصر آن ارزش بازی است. حاصل ضرب u در ارزش بازی، یک بردار احتمال به دست می دهد که شامل احتمال این است که بازیکن بیشینه کننده هر کدام از استراتژی های ممکن را برگزیند. اگر در ماتریس بازی، همه عناصر مثبت نباشند، باید یک عدد ثابت به هر کدام از عناصر افزود؛ به طوری که آن قدر بزرگ باشد که همه عناصر مثبت شوند. این کار ارزش بازی را به اندازه آن مقدار ثابت افزایش خواهد داد و تاثیری روی استراتژی های ترکیبی تعادل نخواهد داشت. استراتژی ترکیبی تعادل برای بازیکن کمینه کننده را با حل دوگان برنامه خطی داده شده می توان یافت. یا می توان از روش بالا استفاده کرد و با حل ماتریس نتایجِ اصلاح شده (ترانهاده و منفی کردن ماتریس M و افزودن یک عدد ثابت برای مثبت کردن مقادیر) یک بازی جدید به دست آورد و آن را حل کرد. اگر همه جواب های برنامه خطی پیدا شوند، شامل همه تعادل های نش برای بازی خواهند بود. بالعکس، هر برنامه خطی می تواند با استفاده از تغییر متغیری که فرمِ آن را شبیه معادلات بالا کند، تبدیل به یک بازی مجموع-صفر دونفره کرد. در نتیجه چنین بازی هایی به طور کلی معادل برنامه های خطی هستند.

مجموع-ناصفر[ویرایش]

اقتصاد[ویرایش]

همچنین ببینید:

روانشناسی[ویرایش]

پیچیدگی[ویرایش]

گسترش ها[ویرایش]

برداشت های نادرست[ویرایش]

منابع[ویرایش]

مطالعه بیشتر[ویرایش]

  • Raghavan، T.E.S.. Handbook of Game Theory. Elsevier، 1994. 

پیوندهای بیرونی[ویرایش]