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 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$
6
  • $\begingroup$ Why won't you accept the edit? See this post on meta. And please stop rolling it back. $\endgroup$ – Mithical Aug 11 '16 at 14:38
  • $\begingroup$ @Mithrandir see my answer on that post, at least the game-theory tag should be there $\endgroup$ – dontloo Aug 11 '16 at 14:39
  • $\begingroup$ I'll agree with the difference between game-theory and gaming. But can you please edit the other tags out? $\endgroup$ – Mithical Aug 11 '16 at 14:40
  • $\begingroup$ @Mithrandir sure $\endgroup$ – dontloo Aug 11 '16 at 14:43
  • 1
    $\begingroup$ This is an interesting questions - you've clearly done your research - but unfortunately, it seems better for Cross Validated or Data Science. For more information, visit Artificial Intelligence Meta. $\endgroup$ – Ben N Aug 16 '16 at 16:01
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.