نظرية الحد الأدنى الأقصى

**نظرية الحد الأدنى الأقصى** هي مبدأ أساسي في نظرية الألعاب والاستمثال المحدب وضعه عالم الرياضيات المجري جون فون نيومان، وينص على أن كُلّ لعبة تحتوي على لاعبين اثنين ولها مجموع صفري فإنّها تنطوي على استراتيجيات مثالية تضمن للاعبين المشتركين أقل خسارة ممكنة أو أكبر ربح ممكن بحيث يكون الحد الأقصى لأدنى ربح مساويًا الحد الأدنى لأقصى خسارة مما يُحقق التوازن.

يُمكن كتابة الصيغة الرياضية لنظرية الحد الأدنى الأقصى على النحو التالي:

\max_{x\in X} \min_{y\in Y} f(x,y) = \min_{y\in Y} \max_{x\in X}f(x,y)

في العموم يكون الطرف الأيسر دائمًا أكبر من الطرف الأيمن (متباينة الحد الأقصى - الحد الأدنى)، ولا يتساوى الطرفان إلا في ظل شروط معينة تُطبّق على المجموعتين 𝑋 و𝑌 وعلى الدالة 𝑓 وفقًا لنظرية الحد الأدنى الأقصى. نُشرت نظرية الحد الأدنى الأقصى لأول مرة عام 1928، ثُم ظهور العديد من التعميمات والصيغ البديلة لنظرية فون نيومان الأصلية في الأدبيات، غير أن النظرية الأصلية اعتُبرت بمثابة نُقطة الانطلاق لنظرية الألعاب، حتى أن جون فون نيومان وصف النظرية بقوله: "لا يمكن على حد علمي أن تكون هناك نظرية للألعاب بدون تلك النظرية... لذلك كنت أعتقد أنه لا يوجد شيء يستحق النشر حتى يتم إثبات نظرية الحد الأدنى الأقصى." 

## الدوال الثنائية الخطية وألعاب المجموع الصفري
استندت نظرية فون نيومان الأصلية إلى نظرية الألعاب، وتنطبق مبادئ نظرية الحد الأدنى الأقصى على الحالة التي يكون فيها:

* العنصران 𝑋 و𝑌 عبارة عن مبسطات قياسية حيث:
X = \{ (x_1, \dots, x_n) \in [0,1]^n : \sum_{i = 1}^n x_i = 1 \}
 Y = \{ (y_1, \dots, y_m) \in [0,1]^m : \sum_{j = 1}^m y_j = 1 \}

* وتكون الدالة f(x,y) دالة ثنائية خطية، وبالتالي يمكن كتابتها بالنسبة لمصفوفة منتهية A \in \mathbb{R}^{n \times m} على النحو التالي: f(x,y) = x^\mathsf{T} A y أو يُمكن كتابتها بصورة مكافئة على النحو التالي:f(x,y) = \sum_{i=1}^n\sum_{j=1}^m A_{ij}x_iy_j

وبناءً على هذه الافتراضات، فقد أثبت جون فون نيومان أن:

\max_{x \in X} \min_{y \in Y} x^\mathsf{T} A y = \min_{y \in Y}\max_{x \in X} x^\mathsf{T} A y. 

حيث يُمثل المتغير 𝑋 في سياق ألعاب المجموع الصفري بين لاعبين مجموعة استراتيجيات اللاعب الأول، بينما يُمثل المتغير 𝑌 مجموعة استراتيجيات اللاعب الثاني، ويكون كلا من 𝑋 و𝑌 عبارة عن احتمالات عشوائية لأفعال اللاعبين (ما يُسمى بالاستراتيجيات المختلطة)، وتُحدد عوائدهما بواسطة مصفوفة العوائد A، على حين ترمز الدالة f(x,y) إلى القيمة المتوقعة للعائد الذي يحصل عليه اللاعب الأول عندما يلعب بالاستراتيجية X ويلعب اللاعب الثاني بالاستراتيجية Y.

## الدوال المقعرة المحدبة
وصلة=https://en.wikipedia.org/wiki/File:Saddle_point.svg|تصغير|منحنى يوضح الدالة  is وهي دالة مقعرة محدبة
يُمكن تعميم نظرية فون نيومان للحد الأدنى الأقصى لتشمل المجالات المدمجة والمحدبة، والدوال المقعرة في وسيطها الأول والمحدبة في وسيطها الثاني (المعروفة بالدوال المقعرة المحدبة). بصورة رسمية، ولعمل ذلك نفترض أن Y \subseteq \mathbb{R}^m مجموعتين مدمجتين محدبتين. إذا كانت f: X \times Y \rightarrow \mathbb{R} دالة متصلة ومقعرة-محدبة أي أن:

* الدالة f(\cdot,y): X \to \mathbb{R} دالة مقعرة لكل قيمة ثابتة للمتغير y عندما y \in Y
* الدالة f(x,\cdot): Y \to \mathbb{R} دالة محدبة لكل قيمة ثابتة للمتغير x عندما
x \in X

عندئذ يُمكن القول بأن:

\max_{x\in X} \min_{y\in Y} f(x,y) = \min_{y\in Y} \max_{x\in X}f(x,y).

## نظرية سيون للحد الأدنى الأقصى
تُعدّ نظرية سيون للحد الأدنى الأقصى تعميمًا لنظرية فون نيومان للحد الأدنى الأقصى، وهي نظرية وضعها عالم الرياضيات الأمريكي الكندي موريس سيون، وفيها لا يُشترط أن يكون العاملان X و Y عبارة عن مُبسطين قياسيين، ولا أن تكون الدالة f دالة ثنائية الخطية. وتنص نظرية سيون للحد الأدنى الأقصى على ما يلي:

إذا كانت 𝑋 تمثل مجموعة جزئية محدبة من فضاء طوبولوجي خطي، وكانت 𝑌 مجموعة جزئية محدبة مضغوطة من فضاء طوبولوجي خطي، وإذا كانت 𝑓 دالة حقيقية القيم على X\times Y حيث:

* الدالة f(\cdot,y) دالة شبه متصلة من الأعلى وشبه مقعرة على 𝑋 لكل y ثابتة القيمة بشرط أن تكون y\in Y
* الدالة f(x,\cdot) دالة شبه متصلة من الأسفل وشبه محدبة على 𝑌 لكل 𝑥 ثابتة القيمة بشرط أن تكون x\in X

عندئذ يكون:

\sup_{x\in X}\min_{y\in Y} f(x,y) = \min_{y\in Y}\sup_{x\in X} f(x,y). 

## مراجع

تصنيف:استمثال رياضي
تصنيف:خوارزميات
تصنيف:علوم الحاسب
تصنيف:مبرهنات رياضية
تصنيف:نظرية الألعاب