Теорема о минимаксе

В математической области теории игр теорема о минимаксе — это теорема, обеспечивающая условия, гарантирующие, что неравенство максимума и минимума также является равенством. Первой теоремой в этом смысле является фон Неймана минимаксная теорема об играх с нулевой суммой, опубликованная в 1928 году: ^[1] который считался отправной точкой теории игр . Цитируется высказывание Фон Неймана: « Насколько я понимаю, не могло бы быть никакой теории игр… без этой теоремы… Я думал, что нечего публиковать, пока не будет доказана теорема о минимаксе ». ^[2]

С тех пор в литературе появилось несколько обобщений и альтернативных версий исходной теоремы фон Неймана. ^[3]^[4]

Формально теорема фон Неймана о минимаксе гласит:

Позволять $X\subset \mathbb {R} ^{n}$ и $Y\subset \mathbb {R} ^{m}$ — компактные выпуклые множества. Если $f:X\times Y\rightarrow \mathbb {R}$ — непрерывная функция, вогнуто-выпуклая, т.е.

f(\cdot ,y):X\to \mathbb {R}

является вогнутым для фиксированного

y

, и

f(x,\cdot ):Y\to \mathbb {R}

является выпуклым для фиксированного

x

.

Тогда у нас есть это

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

Особый случай: билинейная функция [ править ]

Теорема справедлива, в частности, если $f(x,y)$ является линейной функцией по обоим аргументам (и, следовательно, билинейной ), поскольку линейная функция одновременно вогнута и выпукла. Таким образом, если $f(x,y)=x^{\mathsf {T}}Ay$ для конечной матрицы $A\in \mathbb {R} ^{n\times m}$ , у нас есть:

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

Билинейный частный случай особенно важен для игр с нулевой суммой , когда набор стратегий каждого игрока состоит из лотерей по действиям ( смешанные стратегии ), а выигрыши индуцируются ожидаемым значением . В приведенной выше формулировке $A$ – платежная матрица .

См. также [ править ]

Теорема Сиона о минимаксе
Теорема Партасарати — обобщение теоремы фон Неймана о минимаксе.
Двойную линейную программу можно использовать для доказательства теоремы о минимаксе для игр с нулевой суммой.
Принцип минимакса Яо

Ссылки [ править ]

^ Фон Нейман, Дж. (1928). «К теории настольных игр». Математика Энн. 100 : 295-320. дои : 10.1007/BF01448847 . S2CID 122961988 .
^ Джон Л. Касти (1996). Пять золотых правил: великие теории математики 20-го века – и почему они важны . Нью-Йорк: Wiley-Interscience. п. 19 . ISBN 978-0-471-00261-1 .
^ Ду, Дин-Чжу; Пардалос, Панос М., ред. (1995). Минимакс и приложения . Бостон, Массачусетс: Springer US. ISBN 9781461335573 .
^ Брандт, Феликс; Брилл, Маркус; Суксомпонг, Варут (2016). «Порядковая теорема о минимаксе». Игры и экономическое поведение . 95 : 107–112. arXiv : 1412.4198 . дои : 10.1016/j.geb.2015.12.010 . S2CID 360407 .

Эта математическому анализу, статья, посвященная незавершена . Вы можете помочь Википедии, расширив ее .

Эта по теории игр статья незавершена . Вы можете помочь Википедии, расширив ее .

[1] Фон Нейман, Дж. (1928). «К теории настольных игр». Математика Энн. 100 : 295-320. дои : 10.1007/BF01448847 . S2CID 122961988 .

[Casti-2] Джон Л. Касти (1996). Пять золотых правил: великие теории математики 20-го века – и почему они важны . Нью-Йорк: Wiley-Interscience. п. 19 . ISBN 978-0-471-00261-1 .

[3] Ду, Дин-Чжу; Пардалос, Панос М., ред. (1995). Минимакс и приложения . Бостон, Массачусетс: Springer US. ISBN 9781461335573 .

[4] Брандт, Феликс; Брилл, Маркус; Суксомпонг, Варут (2016). «Порядковая теорема о минимаксе». Игры и экономическое поведение . 95 : 107–112. arXiv : 1412.4198 . дои : 10.1016/j.geb.2015.12.010 . S2CID 360407 .

[1]

[2]

[3]

[4]