مینیماکس

مینیماکس یا کمین بیش[ ۱] یک قانون تصمیم سازی است که در نظریهٔ تصمیم، نظریهٔ بازی ها، آمار و فلسفه برای کمینه کردن ( مینیمم کردن ) احتمال شکست و ضرر در بدترین حالت ( بیشترین احتمال ضرر ) از آن استفاده می شود. به طور مشابه بیشینه کردن سود کمینه ( ماکسمین ) را نیز بیشینهٔ کمینه می نامیم. اساساً برای بازی های دو نفرهٔ مجموعهٔ صفر در نظریهٔ بازی ها فرمول بندی شده است که هم حرکت های جایگزین ( چند انتخابی ) بازیکن ها و هم حرکات هم زمان انتخاب کردن بازیکن ها را پوشش می دهد. این مفهوم را می توانیم به بازی های پیچیده تر و تصمیم سازی های غیر قطعی بسط دهیم.
در نظریهٔ بازی های هم زمان، استراتژی کمینه یک استراتژی مرکب است که قسمتی از حل بازی با مجموعهٔ صفر می باشد. در بازی های مجموعهٔ صفر حل کمینه ( مینیماکس ) مشابه تعادل نش ( نام دانشمند ) است.
برای هر دو نفر، بازی مجموعهٔ صفر با استراتژی های متناهی بسیاری وجود دارد٬یک مقدار θ و استراتژی آمیخته برای هر بازیکن وجود دارد که:
الف ) برای استراتژی در پیش گرفته شده توسط بازیکن دوم بهترین پرداخت ممکن برای بازیکن ۱، θ است.
ب ) برای استراتژی در پیش گرفته شده توسط بازیکن اول بهترین پرداخت ممکن برای بازیکن ۲، θ - است. معادلا استراتژی بازیکن ۱ برای او یک سودمندی ( پرداخت ) θ بدون در نظر گرفتن استراتژی بازیکن دوم تضمین می کند. به طور مشابه بازیکن ۲ می تواند سودمندی θ - را برای خودش تضمین کند.
نام مینیماکس از جایی می آید که هر بازیکن سعی دارد تا بیشینه پرداخت محتمل برای طرف مقابل را کمینه کند. چون بازی مجموعهٔ صفر است او همچنین ماکزیمم ضرر خود را کمینه می کند ( برای مثال مقدار کمینهٔ پرداختش را بیشینه می کند ) .
این قضیه اولین بار توسط جان فون نویمان در سال ۱۹۲۸ انتشار یافت، که از او نقل قول شده است: ” تا جایی که می بینم هیچ قضیه ای از بازی ها بدون این قضیه نخواهد بود. من فکر می کردم هیچ قضیهٔ با ارزشی انتشار نیافته تا زمانی که قضیه مینماکس ( کمینهٔ بیشینه ) اثبات شد! ” . برای تعمیم می توانید قضیهٔ مینماکس سیون - نام دانشمند - قضیهٔ پارتاساراتی را ببینید. هم چنین می توانید مثالی از یک بازی بدون متغیر ببینید.
مثال پیش روبازی مجموعهٔ صفر است که A و B حرکات همزمان انجام می دهند و راه حل مینیماکس را نشان می دهد. فرض کنید هر بازیکن ۳ انتخاب دارد و ماتریس پرداخت برای A در سمت راست نمایش داده شد است. ماتریس پرداخت B را هم مانند ماتریس پرداخت A با علامت معکوس در نظر بگیرید. ( برای مثال اگر انتخاب بازیکن ها A۱ و B۱ باشد، B باید ۳ تا به A بپردازد ) سپس انتخاب کمینهٔ بیشینه برای A ٬A۲ است زیرا در بین بدترین ها بهترین انتخاب این است که باید ۱ بپردازد. در حالی که انتخاب کمینهٔ بیشینه برای B٬B۲ است زیرا در بهترین حالت که کمترین ضرر را می کند این است که چیزی نپردازد. با این وجود این راه حل پایدار نیست زیرا اگرBبداند که A٬A۲ را انتخاب می کند، سپس B ٬B۲ را انتخاب می کند تا ۱ سود کند. هم چنین اگر A باور داشته باشد که B٬B۲ را انتخاب می کند او هم A۱ را انتخاب می کند تا ۳ واحد سود ببرد. اما پس از آن B٬B۲ را انتخاب می کند و به همین ترتیب هر دو بازیکن سختی تصمیم گیری را می فهمند. به همین دلیل به استراتژی پایدارتری نیاز است. بعضی انتخاب ها توسط دیگر انتخاب ها مغلوب می شوند و می توانند حذف شوند: A, A۳ را انتخاب نخواهد کرد. زیرا انتخاب هر کدام از A۱ و A۲ نتیجهٔ بهتری خواهد داشت بدون اینکه انتخاب B اهمیت داشته باشد. همچنین B3, B را انتخاب نخواهد کرد زیرا ترکیباتی از B۲ و B۱ صرف نظر از اینکه A چه انتخابی دارد، نتیجهٔ بهتری خواهد داشت. A با انتخاب A۱ با احتمال ۶/۱ و، A۲ با احتمال ۶/۵ از پرداخت مورد انتظار بیش از ۳/۱ جلوگیری خواهد کرد. پرداخت مورد انتظار برای A، ۳* ( ۱/۶ ) - ۱* ( ۵/۶ ) = - ۱/۳ خواهد بود برای زمانی که B ٬B۱ را انتخاب می کند و - ۲* ( ۱/۶ ) +۰* ( ۵/۶ ) = - ۱/۳ خواهد بود برای زمانی که B, B۲ را انتخاب می کند. مشاب ها زمانی که B استراتژی B۱ را با احتمال ۳/۱ و استراتژی B۲ با احتمال ۳/۲ بدون در نظر گرفتن انتخاب A انتخاب می کند، می تواند مطمئن باشد که حداقل دارای سود مورد انتظار ۳/۱ خواهد بود. این استراتژی مرکب پایداری دارد و اثبات شدنی نیست.