Parthasarathy's theorem

From Wikipedia, the free encyclopedia

In mathematics and in particular the study of games on the unit square, Parthasarathy's theorem is a generalization of Von Neumann's minimax theorem. It states that a particular class of games has a mixed value, provided that at least one of the players has a strategy that is restricted to absolutely continuous distributions with respect to the Lebesgue measure (in other words, one of the players is forbidden to use a pure strategy).

terminology: X and Y stand for the unit interval [0,1]; \mathcal M_X is the set of probability distributions on X (\mathcal M_Y defined similarly); AX is the set of class of absolutely continuous distributions on X (AY defined similarly).

[edit] Theorem

Suppose that k(x,y) is bounded on the unit square 0\leq x,y\leq 1; further suppose that k(x,y) is continuous except possibly on a finite number of curves of the form y = φk(x) (with k=1,2,\ldots,n) where the φk(x) are continuous functions.

Further suppose

k(\mu,\lambda)=\int_{y=0}^1\int_{x=0}^1 k(x,y)\,d\mu(x)\,d\lambda(y)= \int_{x=0}^1\int_{y=0}^1 k(x,y)\,d\lambda(y)\,d\mu(x).

Then

\max_{\mu\in{\mathcal M}_X}\,\inf_{\lambda\in A_Y}k(\mu,\lambda)= \inf_{\lambda\in A_Y}\,\max_{\mu\in{\mathcal M}_X} k(\mu,\lambda)


This is equivalent to the statement that the game induced by k(\cdot,\cdot) has a value. Note that one player (WLOG X) is forbidden from using a pure strategy.


Parthasarathy goes on to exhibit a game in which

\max_{\mu\in{\mathcal M}_X}\,\inf_{\lambda\in{\mathcal M}_Y}k(\mu,\lambda)\neq \inf_{\lambda\in{\mathcal M}_Y}\,\max_{\mu\in{\mathcal M}_X} k(\mu,\lambda)

which thus has no value. There is no contradiction because in this case neither player is restricted to absolutely continuous distributions (and the demonstration that the game has no value requires both players to use pure strategies).

[edit] Reference

T. Parthasarathy 1970. On Games over the unit square, SIAM, volume 19, number 2.