미니맥스의 원리

요약 ‘게임이론(theory of game)’에서 가장 알맞은 전략을 찾아내기 위한 원리.

두 사람게임(zero-sum two-person game)에서 참가자 P₁이 취할 수단이 1,2,3,…,m, P₂가 취할 수단이 1,2,3,…,n이라 하고, P₁이 i, P₂가 j인 수단을 취했을 때, P₂가 P₁에게 지불할 금액을 a_ij라 하면 a_ij로 이루어지는 행렬은 지불행렬이라 한다.

지금 P₁이 i를 택했을 때, P₁은 적어도

이것을 최대가 되게 하는 수단을 P₁은 언제나 택할 수 있어서, 그때 받을 금액은

이와 같이 하여 P₂는 많아서

밖에 지불하지 않게 할 수 있다.

그래서 일반적으로

가 되는데, 이것이 일치할 때 두 사람에 대한 최적 수단이 결정된다. 그 필요 충분조건은 지불행렬에 있어서, 행에서 최소인 동시에 열에서 최대인 원소가 존재한다는 것이다. 그와 같은 점을 안점(鞍點:saddle point)이라 한다. 안점이 존재하지 않을 때에는 오직 하나의 수단으로서 두 사람에 대한 최적인 것은 없다. 그 때는 여러 수단을 혼합하여 쓰는 혼합전략을 생각한다.



가 성립한다. 이것이 미니맥스의 원리이다.

이것은 상대방의 대응법을 알 수 없을 때에 가장 견실한 수단이다.