Misplaced Pages

Parthasarathy's theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Says when particular class of games on the unit square has a mixed value
This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.
Find sources: "Parthasarathy's theorem" – news · newspapers · books · scholar · JSTOR (February 2016)

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).

The theorem is attributed to Thiruvenkatachari Parthasarathy.

Theorem

Let X {\displaystyle X} and Y {\displaystyle Y} stand for the unit interval [ 0 , 1 ] {\displaystyle } ; M X {\displaystyle {\mathcal {M}}_{X}} denote the set of probability distributions on X {\displaystyle X} (with M Y {\displaystyle {\mathcal {M}}_{Y}} defined similarly); and A X {\displaystyle A_{X}} denote the set of absolutely continuous distributions on X {\displaystyle X} (with A Y {\displaystyle A_{Y}} defined similarly).

Suppose that k ( x , y ) {\displaystyle k(x,y)} is bounded on the unit square X × Y = { ( x , y ) : 0 ≤ x , y ≤ 1 } {\displaystyle X\times Y=\{(x,y):0\leq x,y\leq 1\}} and that k ( x , y ) {\displaystyle k(x,y)} is continuous except possibly on a finite number of curves of the form y = ϕ k ( x ) {\displaystyle y=\phi _{k}(x)} (with k = 1 , 2 , … , n {\displaystyle k=1,2,\ldots ,n} ) where the ϕ k ( x ) {\displaystyle \phi _{k}(x)} are continuous functions. For μ ∈ M X , λ ∈ M Y {\displaystyle \mu \in M_{X},\lambda \in M_{Y}} , define

k ( μ , λ ) = ∫ y = 0 1 ∫ x = 0 1 k ( x , y ) d μ ( x ) d λ ( y ) = ∫ x = 0 1 ∫ y = 0 1 k ( x , y ) d λ ( y ) d μ ( x ) . {\displaystyle 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 μ ∈ M X inf λ ∈ A Y k ( μ , λ ) = inf λ ∈ A Y max μ ∈ M X k ( μ , λ ) . {\displaystyle \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 ( ⋅ , ⋅ ) {\displaystyle k(\cdot ,\cdot )} has a value. Note that one player (WLOG Y {\displaystyle Y} ) is forbidden from using a pure strategy.

Parthasarathy goes on to exhibit a game in which

max μ ∈ M X inf λ ∈ M Y k ( μ , λ ) ≠ inf λ ∈ M Y max μ ∈ M X k ( μ , λ ) {\displaystyle \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).

References

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


Stub icon

This game theory article is a stub. You can help Misplaced Pages by expanding it.

Categories: