5
$\begingroup$

The Von Neumann's Minimax theorem gives the conditions that make the max-min inequality an equality.

I understand the max-min inequality, basically min(max(f))>=max(min(f)).

The Von Neumann's theorem states that, for the inequality to become an equality f(.,y) should always be convex for given y and f(x,.) should always be concave for given x, which also makes sense.

This video says that for a zero-sum perfect information game, the Von Neumann's theorem always holds, so that minimax always equal to maximin, which I did not quite follow.

Questions

  • Why do zero-sum perfect information games satisfy the conditions of Von Neumann's theorem?

  • If we relax the rules to be non-zero-sum or non-perfect information, how would the conditions change?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Here is one of many web pages devoted to the application of Minimax in Tic-Tac-Toe solving: Minimax Algorithm in Game Theory | Set 3 (Tic-Tac-Toe AI – Finding optimal move)

Google search will yield many such results. (I will return to this answer when I have more time, and post more links with more context.)

Here's a high-level explanation on how minimax may be used in the non-chance, perfect information, sequential, partisan, zero-sum set of games [M]:

  • A non minimax evaluation function would look to place integers on the gameboard in positions that grant maximum value (power & influence)
  • A minimax evaluation function would look to place integers on the gameboard in positions that maximize value while minimizing the max value of the opponents next placement

This is partly due to the utilization of "resource stealing strategies" in [M] games.


Note: I need to do some more thinking on the sub questions regarding application beyond zero-sum, perfect-information games, but I don't see any issue with it. Minimax/maximin has wide and fundamental utility in an array of contexts, not strictly related to games except in the sense that every problem can be understood as a type of game or puzzle.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .