请输入您要查询的字词:

 

单词 MinimaxInequality
释义

minimax inequality


The minimax inequality was first proved by John von Neumann. It is the starting point to discuss two-players zero-sum static games theoryMathworldPlanetmath.

𝐓𝐡𝐞𝐨𝐫𝐞𝐦𝟏:minimaxinequality,simplestrategies¯

For any m×n matrix Ai,j, we have

(1)max1immin1jnAi,jmin1jnmax1imAi,j

(2)max1immin1jnAi,j=min1jnmax1imAi,j if and only if Ai,j~Ai~,j~Ai~,j  i,j is valid for some (i~,j~)

For a 2 players zero-sum gameMathworldPlanetmath, the entries of Ai,j is interpreted as the payoff when player 1 has chosen the ith strategy while player 2 has chosen the jth strategy. The value Ai~,j~ is known as the value of the game.

𝐏𝐫𝐨𝐨𝐟 Since min1jnAi,jmax1imAi,j  i,j.The LHS is independent of j while the RHS is independent of i, therefore we obtainmax1immin1jnAi,jmin1jnmax1imAi,j

𝐓𝐡𝐞𝐨𝐫𝐞𝐦𝟐:minimaxinequality,mixedstrategies¯

Let Sm={xm|xi0i,i=1mxi=1}m.For any m×n matrix Ai,j, we have

maxxSmminySni=1mj=1nAi,jxiyj=minySnmaxxSmi=mj=1nAi,jxiyj

Here 0xi1 is interpreted as the probability that Player 1 will choose strategy i while 0yj1 is the probability that Player 2 will choose strategy j.

𝐏𝐫𝐨𝐨𝐟 For any xSm and any ySn we have maxxSmminySni=1mj=1nAi,jxiyji=1mj=1nAi,jxiyj

Taking maximum for xSm on both sides, we have maxxSmminxSni=1mj=1nAi,jxiyjmaxsSmi=1mj=1nAi,jxiyj

Taking minimum for ySn on both sides, we have v1=maxxSmminySni=1mj=1nAi,jxiyjv2=minySnmaxxSmi=1mj=1nAi,jxiyj

The prove of other half of the inequality takes two steps:

Step 1Suppose there is a ySn such that j=1nAi,jyj0There is some x~Sm such that i=1m(j=1nAi,jyj)x~i0

maxxSni=1mj=1nAi,jxiyj0v2=minySnmaxxSmi=1mj=1nAi,jxiyj0  (*1)

Step 2Suppose there is a xSm such that i=1mAi,jxiyj>0There is some y~Sn such that j=1n(i=1mAi,jxi)y~j0

minySni=1mj=1nAi,jxiyj0v1=maxxSmminySni=1mj=1nAi,jxiyj0  (*2)

Combining (*1) and (*2) we see that either 0v1 or v20 is the case and v1<0<v2 cannot be valid. Repeat the same procedure to the matrix A~i,j=Ai,j-λ and we see that v1-λ<0<v2-λ is invalid, i.e. v1<λ<v2 is not valid for any λ. Since λ is arbitrary, we conclude that v2v1.

An entire theory on minimax has already been developed and is one of the major research area in optimization theory. The following contains some good sources for further reference:

References

  • 1 V.F.Demyanov and V.N.Malozemov, Introduction to Minimax, Keter Publishing House Jerusalem Ltd, 1974.
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 10:47:06