پرش به محتوا

مفهوم راه‌حل

از ویکی‌پدیا، دانشنامهٔ آزاد

در نظریه بازی‌ها، مفهوم راه حل (به انگلیسی: Solution concept)، یک قانون صوری برای پیش‌بینی نحوه‌ای است که یک بازی انجام می‌شود. این پیش‌بینی‌ها راه حل نامیده می‌شوند و توصیف می‌کنند کدام استراتژی‌ها توسط کدام بازیکن‌ها اتخاذ می‌شوند و از این‌رو نتیجهً بازی را پیش‌بینی می‌کنند. از مورد استفاده‌ترین مفاهیم راه حل می‌توان به مفاهیم تعادل اشاره کرد. در مفاهیم تعادل به دنبال یک مجموعه از استراتژی‌ها می‌گردیم، یک استراتژی برای هر بازیکن، به گونه‌ای که استراتژی هر فرد بهترین (مطلوب‌ترین) استراتژی اوست زمانی‌که همهٔ بازیکنان بهترین پاسخ تصریح شدهٔ خود را بازی می‌کنند.

از نمونه مفاهیم تعادل می‌توان به تعادل استراتژی غالب، بهینه پارتو بودن، حذف مکرر استراتژی‌های مغلوب و از همه معروف‌تر، تعادل نش، اشاره کرد. مفاهیم راه‌حل متعدد برای بازی‌های متعدد به بیش از یک راه حل ختم می‌شوند.

تعریف صوری

[ویرایش]

اگر کلاس همهٔ بازی‌ها باشد و برای هر بازی فرض کنید مجموعهٔ استراتژی‌های باشد. یک مفهوم راه‌حل یک عنصر از حاصل ضرب مستقیم است؛ به توصیفی دیگر یک تابع است طوری‌که برای همهٔ ، باشد.

استراتژی غالب و مغلوب

[ویرایش]

برخی مواقع بهترین انتخاب یک بازیکن، هر کاری که بقیهٔ بازیکنان بکنند یکی است. این استراتژی یک استراتژی غالب برای آن بازیکن نامیده می‌شود. در نتیجه یک استراتژی، غالب است در صورتی که همیشه بهتر از هر استراتژی دیگری باشد، برای هر استراتژی پروفایلی از بقیهٔ بازیکنان، یک استراتژی اکیداً غالب است در صورتی که بدون در نظر گرفتن این که بقیهٔ بازیکنان چه کاری انجام می‌دهند، سود اکیداً بیشتری نسبت به بقیهٔ استراتژی‌ها داشته باشد. اگر یک بازیکن یک استراتژی غالب داشته باشد همیشه در تعادل آن را بازی خواهد کرد. یک استراتژی ضعیف غالب است در صورتی که، صرف نظر از آنچه که هر بازیکنی دیگر انجام می‌دهد، استراتژی برای بازیکن حداقل به اندازهٔ هر استراتژی دیگری سود داشته باشد و در مواردی بیشتر باشد.

اگر استراتژی‌های بهتر در بازی داشته باشیم در مقابل استراتژی‌های بدتر هم داریم. به این استراتژی‌های بدتر استراتژی‌های مغلوب گفته می‌شود. داشتن استراتژی مغلوب به این معناست که یک انتخاب برای بازیکن وجود دارد که از آن استراتژی بهتر است. اگر یک بازی غیر همکارانه باشد، با توجه به مفاهیم عقلانیت‌پذیری، بازیکنان عاقلانه عمل کنند، استراتژی‌هایی که اکیداً مغلوب هستند از مجموعهٔ استراتژی‌هایی که ممکن است قابل اجرا باشند حذف می‌شوند.

بعنوان مثال، در نمونهٔ زیر از بازی معمای زندانی‌ها، استراتژی همکاری برای هر دو بازیکن توسط استراتژی خیانت اکیداً مغلوب شده‌است. چرا که هردو بازیکن همیشه برایشان سود بیشتری دارد که خیانت کنند، بدون توجه به این که بازیکن دیگر چه کاری می‌کند.

زندانی ۲ همکاری زندانی ۲ خیانت
زندانی ۱ همکاری ۰٫۵-, ۰٫۵- ۱۰-, ۰
زندانی ۱ خیانت ۰, ۱۰- ۲-, ۲-

تعادل نش

[ویرایش]

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

دوباره به همان مثال معمای زندانی‌ها برمی‌گردیم. در این مثال زمانی که هردو بازیکن خیانت کنند در تعادل نش هستیم.

زندانی ۲ همکاری زندانی ۲ خیانت
زندانی ۱ همکاری ۰٫۵-, ۰٫۵- ۱۰-, ۰
زندانی ۱ خیانت ۰, ۱۰- ۲-, ۲-

مینی‌ماکس/ماکسی‌مین

[ویرایش]

مینی‌ماکس

[ویرایش]

در بازی‌های رقابت و درگیری، ما اغلب علاقه‌مند به دانستن استراتژی‌هایی هستیم که می‌توان آن‌ها را بازی کرد و بازی کردن آن‌ها میزان قرار گرفتن در معرض برخی از رویدادهای منفی را کاهش می‌دهد. برای مثال در یک سناریوی جنگ، فرض کنید می‌شود از چند راه مختلف آذوقه به سربازان رساند و در هر راه به احتمالی بمباران می‌شویم، در این سناریو مطلوب است انتخابی کنیم که میزان آسیبی که به سربازان می‌رسد را کمینه کند.

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

ماکسی‌مین

[ویرایش]

در مقابل یک استراتژی ماکسی‌مین زمانی است که بازیکن سعی می‌کند بیشترین سود ممکن را بدست آورد. این به این معناست که انتخابی مد نظر است که شانس بدست آوردن بالاترین سود ممکن را داشته باشد - حتی اگر این استراتژی ممکن باشد احتمال ضرر بالایی هم داشته باشد - این استراتژی ماکسی‌مین بهترین بهترین‌ها هم نامیده می‌شود.

بهینه پارتو

[ویرایش]

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

زندانی ۲ همکاری زندانی ۲ خیانت
زندانی ۱ همکاری ۰٫۵-, ۰٫۵- ۱۰-, ۰
زندانی ۱ خیانت ۰, ۱۰- ۲-, ۲-

برای بیان بهینگی پارتو به روشی دیگر می‌توان به بازی شکار گوزن اشاره کرد. فرض کنید دو بازیکن داریم که هرکدام از عمل دیگری بی‌خبر هستند. هرکدام می‌توانند یا به شکار گوزن بروند یا به شکار خرگوش و اگر به شکار گوزن بروند در صورتی سود می‌کنند که هردو با هم به شکار بروند و اگر به شکار خرگوش بروند کمتر سود می‌کنند چون ارزش یک خرگوش کمتر از ارزش یک گوزن است. فرم استراتژیک بازی در زیر نشان داده شده.

فرد ۲ خرگوش فرد ۲ گوزن
فرد ۱ خرگوش ۲٬۲ ۰, ۲
فرد ۱ گوزن ۲, ۰ ۵, ۵

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

استنتاج معکوس

[ویرایش]

در برخی بازی‌ها چندین تعادل نش داریم که برخی از آن‌ها اصلاً واقع‌گرایانه نیستند. در بازی‌های پویا تعادل‌های نش غیر واقع‌گرایانه را با روش استنتاج معکوس می‌توان حذف کرد. استنتاج معکوس بر اساس این تفکر است که تمام اعمال آیندهٔ بازیکنان عاقلانه خواهد بود. در نتیجه این روش استنتاج تهدیدهای غیر واقع‌گرایانه را از بازی می‌کند چرا که این نوع تهدیدها از دید یک بازیکن عاقل اعمال نمی‌شوند. استنتاج معکوس یکی از روش‌های محاسبهٔ تعادل نش زیربازی کامل در بازی‌های ترتیبی است.[۱]

برای مثال یک بازی پویا فرض کنید که در آن، یک تازه‌وارد به صنعت فیلم می‌خواهد از طریق فیلم‌سازی کسب درآمد کند. یک شرکت دیگر هم وجود دارد که روی صنعت فیلم‌سازی به صورت انحصاری تسلط داشته و در صورتی که به شرکت تازه‌وارد اجازهٔ عرضه بدهد از سودش کم می‌شود. اول از همه شرکت تازه‌وارد می‌تواند تصمیم بگیرد که به صنعت وارد شود یا نشود. اگر وارد نشود سود اش صفر و سود شرکت دیگر همانی خواهد بود که از اول بود و صنعت در انحصار او باقی می‌ماند. اگر شرکت تازه‌وارد به صنعت وارد شود شرکت دوم دو کار می‌تواند بکند: یا با پایین آوردن قیمت‌های خود به مقابله پرداخته، سود خود را کم کرده و در عوض شرکت تازه‌وارد را از دور خارج کند؛ یا این که با شرکت تازه‌وارد مقابله نکند، کمی سود خود را کم کند، و هردو به کسب درآمد بپردازند (باز هم از سود انحصار کمتر است).

در صورتی که شرکت تازه‌وارد به صنعت وارد شود، بهترین پاسخ شرکت دیگر این است که مقابله نکند. اگر شرکت تازه‌وارد بداند شرکت دیگر مقابله نمی‌کند هم بهترین پاسخش این است که به صنعت وارد شود؛ لذا حالتی که شرکت تازه‌وارد به صنعت وارد شده و شرکت دیگر مقابله نکند یک تعادل نش است. در مقابل اگر شرکت تازه‌وارد بداند که شرکت دیگر قرار است مقابله کند، بهترین پاسخ آن‌ها این است که به صنعت وارد نشوند و ضرر نکنند. اما اگر شرکت تازه‌وارد به صنعت وارد نشود، مهم نیست شرکت دیگر مقابله کند یا نکند و اگر وارد نشود اصلاً هیچوقت قیمت‌های خود را پایین نمی‌آورد و از طرفی برایش بهترین پاسخ هم هست. پس استراتژی پروفایلی که شرکت تازه‌وارد وارد صنعت نشود و شرکت دیگر مقابله کند هم یک تعادل نش است. زمانی که به گرهٔ انتخاب مقابله کردن یا نکردن می‌رسیم، غیر عقلانی است که مقابله کنیم و در نتیجه حالتی که شرکت دوم مقابله کند غیر عقلانی بوده و از تعادل‌ها می‌تواند حذف شود.

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

[ویرایش]

منابع

[ویرایش]
  1. Drew Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
  • Cho, I-K.; Kreps, D. M. (1987). "Signaling Games and Stable Equilibria". Quarterly Journal of Economics. 102 (2): 179–221. doi:10.2307/1885060.
  • Govindan, Srihari & Robert Wilson, 2008. "Refinements of Nash Equilibrium," The New Palgrave Dictionary of Economics, 2nd Edition.[۱]
  • Hines, W. G. S. (1987) Evolutionary stable strategies: a review of basic theory. Theoretical Population Biology 31:195–272.
  • Kohlberg, Elon & Jean-François Mertens, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-37, September.
  • Leyton-Brown, Kevin; Shoham, Yoav (2008). Essentials of Game Theory: A Concise, Multidisciplinary Introduction. San Rafael, CA: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.
  • Mertens, Jean-François, 1989. "Stable Equilibria - A reformulation. Part 1 Basic Definitions and Properties," Mathematics of Operations Research, Vol. 14, No. 4, Nov. [۲]
  • Noldeke, G. & Samuelson, L. (1993) An evolutionary analysis of backward and forward induction. Games & Economic Behaviour 5:425–454.
  • Maynard Smith, J. (1982) Evolution and the Theory of Games. شابک ‎۰−۵۲۱−۲۸۸۸۴−۳
  • Barr, N. (2012). "3.2.2 The relevance of efficiency to different theories of society". Economics of the Welfare State (5th ed.). Oxford University Press. p. 46. ISBN 978-0-19-929781-8. {{cite book}}: Cite has empty unknown parameter: |1= (help)
  • Osborne, Martin J.; Rubinstein, Ariel (1994). A course in game theory. MIT Press. ISBN 978-0-262-65040-3.