[R] Off topic -- when is max min = min max?

Rolf Turner rolf at math.unb.ca
Wed Jan 19 17:51:17 CET 2005


This question has little or nothing to do with R; as usual I'm simply
hoping to take advantage of the great depth of knowledge and
expertise in the R community.

Anyone who is interested in replying should send email directly to me
(rolf at math.unb.ca) and not to this list.

To get to my question:  In a two person zero-sum game, the
value of the game to the row player is

	v_r = max min x'Ay
               x   y

where A is the m x n reward matrix and x and y are vectors of
probabilities summing to 1 (constituting the row player's and
and column player's ``mixed'' strategies, respectively).  Note
that x' means ``x transpose''.

The value of the game to the column player is (the negative of)

	v_c = min max x'Ay
               y   x

These two values, i.e. v_r and v_c, are equal --- as one might hope.
(One man's ceiling is another man's floor, as Paul Simon puts it.)

***Proving*** that they are equal is done (in game theory books) by
setting the problem up as a linear programming problem and invoking
the Duality Theorem.  (The column player's LP turns out to be the
dual of the row player's LP.)

Initially I thought that there must/should be an easier way to
prove that the two values are equal.  But I can't see one.  So
I would like to ask:

	o ***Is*** there a ``simple'' direct proof that v_r = v_c?

	o How crucial is it that we are maximizing and minimizing
	  over the simplices of probability vectors (summing to 1)
	  in m-dimensional and n-dimensional space respectively?

	  Could we optimize over some more general compact (convex?)
	  set in R^{m+n} and preserve the equality?

	o Are there known ``general'' sufficient conditions (on the
	  function phi(.,.) and the domain of optimization) so that

		max min phi(x,y) = min max phi(x,y)       ???
                 x   y              y   x

	o Has anyone any idea where I might look to find answers
	  to such questions?

Thanks for any insights.

				cheers,

					Rolf Turner
					rolf at math.unb.ca




More information about the R-help mailing list