نظرية مينيمكس

في المجال الرياضي لنظرية الألعاب والتحسين المحدب ، تُعرف نظرية المينيماكس بأنها نظرية تنص على أن

${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y)}$

في ظل شروط معينة على المجموعات${\displaystyle X}$و${\displaystyle Y}$وعلى الوظيفة${\displaystyle f}$[ ^{1 ]} صحيحٌ دائمًا أن الطرف الأيسر لا يتجاوز الطرف الأيمن ( متباينة الحد الأقصى-الأدنى ) ^، لكن المساواة لا تتحقق إلا في ظل شروط معينة تحددها نظريات الحد الأدنى الأقصى. أول نظرية في هذا السياق هي نظرية فون نيومان للحد الأدنى الأقصى حول ألعاب المجموع الصفري بين لاعبين، والتي نُشرت عام 1928، ^{[ 2 ]} وتُعتبر نقطة انطلاق نظرية الألعاب . يُنقل عن فون نيومان قوله: " على حد علمي، لا يمكن أن توجد نظرية للألعاب... بدون تلك النظرية... كنت أعتقد أنه لا يوجد شيء يستحق النشر حتى يتم إثبات نظرية الحد الأدنى الأقصى ". ^{[ 3 ]} ومنذ ذلك الحين، ظهرت العديد من التعميمات والصيغ البديلة لنظرية فون نيومان الأصلية في الأدبيات. ^{[ 4 ] [ 5 ]}

استُلهمت نظرية فون نيومان الأصلية ^{[ 2 ] من نظرية الألعاب، وهي تنطبق على الحالة التي}

• ${\displaystyle X}$و${\displaystyle Y}$هي أشكال بسيطة قياسية :${\textstyle X=\{(x_{1},\dots ,x_{n})\in [0,1]^{n}:\sum _{i=1}^{n}x_{i}=1\}}$و${\textstyle Y=\{(y_{1},\dots ,y_{m})\in [0,1]^{m}:\sum _{j=1}^{m}y_{j}=1\}}$، و
• ${\displaystyle f(x,y)}$هي دالة خطية في كلا وسيطيها (أي،${\displaystyle f}$( ثنائية الخطية ) وبالتالي يمكن كتابتها${\displaystyle f(x,y)=x^{\mathsf {T}}Ay}$لمصفوفة محدودة${\displaystyle A\in \mathbb {R} ^{n\times m}}$أو ما يعادل ذلك${\textstyle f(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{m}A_{ij}x_{i}y_{j}}$.

في ظل هذه الافتراضات، أثبت فون نيومان أن

${\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}$

في سياق ألعاب المجموع الصفري بين لاعبين ، المجموعات${\displaystyle X}$و${\displaystyle Y}$تُقابل هذه الاستراتيجيات مجموعات استراتيجيات اللاعب الأول والثاني على التوالي، والتي تتكون من احتمالات عشوائية لأفعالهم (ما يُسمى بالاستراتيجيات المختلطة )، وتُحدد عوائدهم بواسطة مصفوفة العوائد.${\displaystyle A}$الوظيفة${\displaystyle f(x,y)}$يشفر القيمة المتوقعة للعائد الذي سيحصل عليه اللاعب الأول عندما يلعب اللاعب الأول هذه الاستراتيجية${\displaystyle x}$ويلعب اللاعب الثاني الاستراتيجية${\displaystyle y}$.

يمكن تعميم نظرية فون نيومان للمينيماكس لتشمل المجالات المدمجة والمحدبة، والدوال المقعرة في وسيطها الأول والمحدبة في وسيطها الثاني (المعروفة بالدوال المقعرة المحدبة). بصورة رسمية، ليكن${\displaystyle X\subseteq \mathbb {R} ^{n}}$و${\displaystyle Y\subseteq \mathbb {R} ^{m}}$لتكن مجموعات محدبة متراصة . إذا${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$هي دالة متصلة مقعرة-محدبة، أي

${\displaystyle f(\cdot ,y):X\to \mathbb {R} }$يكون مقعرًا لكل قيمة ثابتة${\displaystyle y\in Y}$، و

${\displaystyle f(x,\cdot ):Y\to \mathbb {R} }$تكون محدبة لكل قيمة ثابتة${\displaystyle x\in X}$.

ثم لدينا ذلك

${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}$

تُعدّ نظرية سيون للمينيماكس، التي أثبتها موريس سيون عام 1958، ^{[ 6 ]} تعميمًا إضافيًا، حيث تُخفف من مفهوم التحدب إلى شبه التحدب. وتنص على ما يلي:

يترك${\displaystyle X}$ليكن مجموعة جزئية محدبة من فضاء طوبولوجي خطي، وليكن${\displaystyle Y}$ليكن مجموعة جزئية محدبة مضغوطة من فضاء طوبولوجي خطي . إذا${\displaystyle f}$هي دالة ذات قيم حقيقية على${\displaystyle X\times Y}$مع

${\displaystyle f(\cdot ,y)}$شبه متصل علوي وشبه مقعر على${\displaystyle X}$لكل ثابت${\displaystyle y\in Y}$، و

${\displaystyle f(x,\cdot )}$شبه متصلة من الأسفل وشبه محدبة على${\displaystyle Y}$لكل ثابت${\displaystyle x\in X}$.

ثم لدينا ذلك

${\displaystyle \sup _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\sup _{x\in X}f(x,y).}$

قدم كوميا برهانًا أوليًا لهذه النظرية. ^{[ 7 ]}

يوضح المثال التالي أنه بدون شرط التقعر-التحدب، لا يلزم أن تتساوى قيمتا الحد الأقصى-الأدنى وقيمتا الحد الأدنى-الأقصى. ^{[ 8 ]} لنفترض أن f ( x , y ) = ( x - y ) ^² على المجال X = [0,1] و Y = [0,1]. لاحظ أن f محدبة-محدبة ولكنها ليست محدبة-مقعرة. إذن:

• لأي قيمة ثابتة لـ x ، فإن min _y f( x , y ) = 0، والتي تتحقق عندما y = x . وبالتالي، فإن max _x min _y f(x,y) = 0 .
• لأي قيمة ثابتة لـ y، فإنّ max _x f( x , y ) = max( y² ^, (1- y ) ^² )، والتي تتحقق عندما x = 0 (عندما y > 0.5) أو x = 1 (عندما y < 0.5). وبالتالي، فإنّ min _y max _x f(x, y) = 0.25 ، والتي تتحقق عندما y = 0.5.

• نظرية بارثاساراثي – تعميم لنظرية فون نيومان الصغرى القصوى 
• يمكن استخدام برنامج الخط المزدوج لإثبات نظرية المينيماكس لألعاب المجموع الصفري.
• مبدأ ياو – تطبيق لنظرية المينيماكس على التعقيد الحسابي