Newsgroups: rec.puzzles
From: hoey@pooh.tec.army.mil (Dan Hoey)
Date: 1995/12/08
Subject: Re: ASK MARILYN

Jamie Dreier (pl436...@brownvm.brown.edu) wrote:

: The classic sort of game theoretic analysis doesn't generally go by
: maximizing minimum *expected* payoffs, but we can certainly extend the
: idea here.

That's quite a bizarre thing to say, since the subject known as "Game
Theory" consists almost entirely of analysis of how to maximize the
minimum expected payoff of imperfect-knowledge games.  The analysis of
perfect-knowledge games has had to content itself with other names.

I've seen three books on the subject (_The Compleat Strategist_, some
Dover title like _Analysis of Games of Strategy_, and a recent course
text that looked promising).  I suspect there are dozens of books and
hundreds of research papers.

: But now the question is, what is the relevance of this maximin? Is there
: any reason to suppose it is the 'best' move in any sense? I can't see any
: reason whatsoever....

It's at least _a_ criterion for best move, and it gives you the best
possible guarantee of your chance of winning a car.  I do not know of
any other criterion that is not maximizing the minimum expected payoff
over some distribution--the only disagreement I have seen is over what
distribution has been specified.  Do you have a different criterion to
propose that maximizes some other measure of goodness?

: Maximin strategies are important in very, very limited contexts, I think.

I think not.  I think some other things about that statement, which I
will forbear to mention.

The usual context is when you are in a zero-sum game, so you should
plan for the case when your opponent will minimize your payoff.  It
turns out that many games (such as this) have a _stable_ strategy,
such that you cannot increase the payoff if your opponent plays the
stable strategy, and your opponent cannot decrease your payoff if you
play the stable strategy.

Another context is in artifically-constructed problems, where you are
asked to provide an answer that does not rely on information that was
not provided in the problem statement.  If the answer requires
maximizing your expectation over an unknown probability distribution,
you may not have any better option than to maximize over the
worst-case distribution.  Solving the problem for a fixed distribution
that you assert to have been intended is not usually considered
responsive.

The subject of artificially-constructed problems is by far the more
limited context, being mostly concerned with puzzles constructed for
recreational or instructive purposes.  But limited as that context may
be, you have found it.

Dan
Hoey@AIC.NRL.Navy.Mil