Repeated games of incomplete information with large sets of states

The famous theorem of R. Aumann and M. Maschler states that the sequence of values of an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$N$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>N</mi> </math> </EquationSource> </InlineEquation>-stage zero-sum game <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$\varGamma _N(\rho )$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <msub> <mi mathvariant="italic">Γ</mi> <mi>N</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">ρ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation> with incomplete information on one side and prior distribution <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\rho $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">ρ</mi> </math> </EquationSource> </InlineEquation> converges as <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$N\rightarrow \infty $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>N</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </math> </EquationSource> </InlineEquation>, and that the error term <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$${\mathrm {err}}[\varGamma _N(\rho )]={\mathrm {val}}[\varGamma _N(\rho )]- \lim _{M\rightarrow \infty }{\mathrm {val}}[\varGamma _{M}(\rho )]$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="normal">err</mi> <mrow> <mo stretchy="false">[</mo> <msub> <mi mathvariant="italic">Γ</mi> <mi>N</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">ρ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">]</mo> </mrow> <mo>=</mo> <mi mathvariant="normal">val</mi> <mrow> <mo stretchy="false">[</mo> <msub> <mi mathvariant="italic">Γ</mi> <mi>N</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">ρ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">]</mo> </mrow> <mo>-</mo> <msub> <mo movablelimits="true">lim</mo> <mrow> <mi>M</mi> <mo stretchy="false">→</mo> <mi>∞</mi> </mrow> </msub> <mi mathvariant="normal">val</mi> <mrow> <mo stretchy="false">[</mo> <msub> <mi mathvariant="italic">Γ</mi> <mi>M</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi mathvariant="italic">ρ</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">]</mo> </mrow> </mrow> </math> </EquationSource> </InlineEquation> is bounded by <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$C N^{-\frac{1}{2}}$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>C</mi> <msup> <mi>N</mi> <mrow> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> </msup> </mrow> </math> </EquationSource> </InlineEquation> if the set of states <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$$K$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>K</mi> </math> </EquationSource> </InlineEquation> is finite. The paper deals with the case of infinite <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$$K$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi>K</mi> </math> </EquationSource> </InlineEquation>. It turns out that, if the prior distribution <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$$\rho $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">ρ</mi> </math> </EquationSource> </InlineEquation> is countably-supported and has heavy tails, then the error term can be of the order of <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$$N^{\alpha }$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>N</mi> <mi mathvariant="italic">α</mi> </msup> </math> </EquationSource> </InlineEquation> with <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$$\alpha \in \left( -\frac{1}{2},0\right) $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi mathvariant="italic">α</mi> <mo>∈</mo> <mfenced close=")" open="(" separators=""> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <mo>,</mo> <mn>0</mn> </mfenced> </mrow> </math> </EquationSource> </InlineEquation>, i.e., the convergence can be anomalously slow. The maximal possible <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$$\alpha $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">α</mi> </math> </EquationSource> </InlineEquation> for a given <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$$\rho $$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mi mathvariant="italic">ρ</mi> </math> </EquationSource> </InlineEquation> is determined in terms of entropy-like family of functionals. Our approach is based on the well-known connection between the behavior of the maximal variation of measure-valued martingales and asymptotic properties of repeated games with incomplete information. Copyright Springer-Verlag Berlin Heidelberg 2014