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

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

${\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} }$ is convex for every fixed ${\displaystyle x\in X}$.

Then we have that

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

Sion's minimax theorem, proved by Maurice Sion at 1958,^[6] is a further generalization, relaxing convexity to quasiconvexity. It states:

Let ${\displaystyle X}$ be a convex subset of a linear topological space and let ${\displaystyle Y}$ be a compactconvex subset of a linear topological space. If ${\displaystyle f}$ is a real-valued function on ${\displaystyle X\times Y}$ with

${\displaystyle f(\cdot ,y)}$upper semicontinuous and quasi-concave on ${\displaystyle X}$, for every fixed ${\displaystyle y\in Y}$, and

${\displaystyle f(x,\cdot )}$ lower semicontinuous and quasi-convex on ${\displaystyle Y}$, for every fixed ${\displaystyle x\in X}$.

Then we have that

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

An elementary proof of this theorem is given by Komiya.^[7]

The following example shows that, without the concave-convex condition, the max-min and the min-max need not be equal.^[8] Let f(x.y) = (x-y)² on the domain X = [0,1] and Y = [0,1]. Note that f is convex-convex but not convex-concave. Then:

• For any fixed x, min_yf(x,y) = 0, attained by y=x. Hence, max_xmin_yf(x,y) = 0.
• For any fixed y, max_xf(x,y) = max(y², (1-y)²), attained by x=0 (when y>0.5) or x=1 (when y<0.5). Hence, min_ymax_xf(x,y) = 0.25, attained by y=0.5.

• Parthasarathy's theorem –a generalization of Von Neumann's minimax theorem
• Dual linear program can be used to prove the minimax theorem for zero-sum games.
• Yao's principle –an application of the minimax theorem to computational complexity