[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