Dynamic games with incomplete information

Suppose $(\gamma_n,\sigma_n,\mu_n)\in\mathcal S$ converges to $(\gamma,\sigma,\mu)$. All sequential-rationality inequalities are continuous polynomial inequalities, so they persist in the limit. For each $n$, consistency gives a completely mixed $b_n$ within $1/n$ of $\sigma_n$, whose Bayes beliefs at $\gamma_n$ are within $1/n$ of $\mu_n$.

Factor each reach monomial as $r_h(\gamma,b)=c_h(\gamma)a_h(b)$, where $c_h$ is the product of chance probabilities on the prefix and $a_h$ the product of behavioral probabilities. The finitely many functions $c_h$ are continuous and strictly positive. Thus \[ \rho_n=\max_h\left|\frac{c_h(\gamma)}{c_h(\gamma_n)}-1\right|\longrightarrow0. \] For $\rho_n<1$, multiplying each positive reach probability by a factor in $[1-\rho_n,1+\rho_n]$ changes its normalized probability at an information set by at most $2\rho_n/(1-\rho_n)$. Indeed, the ratio of the old and new normalizers lies in the same interval, and subtracting the two normalized fractions gives this bound directly. The bound is independent of $b_n$, even when its reach probabilities tend to zero.

Consequently the Bayes beliefs generated by $b_n$ at the fixed parameter $\gamma$ converge to $\mu$. Also $b_n\to\sigma$. These are consistency witnesses at $\gamma$, proving that the limit belongs to $\mathcal S$. The graph is closed inside a compact set and hence compact. ∎

Intersecting the compact graph with the closed observation constraint makes $\mathcal A(p)$ compact. The joint set of $(\gamma,e,e^d)$ satisfying the two equilibrium graphs and the observation constraint is likewise closed and bounded. Coordinate projections and the continuous polynomial map $W_d$ preserve compactness. Polynomial quantification and projection preserve semialgebraicity by real quantifier elimination. Compactness gives attainment of extrema whenever the joint set is nonempty.

All defining constraints are first-order formulas with the stated effective coefficients, so exact quantifier elimination decides their feasibility. For the upper endpoint, the decision "there exists a feasible tuple with $W_d\geq q$" locates that endpoint relative to any rational midpoint $q$; for the lower endpoint use $W_d\leq q$. Each decision halves an enclosing interval. The claimed number of decisions follows by solving $(U-L)2^{-k}\leq\varepsilon$. An empty set is reported as such, not assigned fictitious endpoints. A noninterval counterfactual set is not replaced by its endpoint interval when its full description is requested. ∎

On the complementary event, every tuple with exact observation law $p$ satisfies the relaxed data constraint. It retains its exact equilibrium witness, so all parameters in $\Gamma_I(p)$ belong to $\widehat\Gamma_N$. Every compatible policy equilibrium attached to such a parameter is then retained too, proving the second containment. Nothing in this deterministic implication depends on the policy, proving simultaneous coverage. Replacing feasible sets by supersets preserves these containments. Residual size without a proved inclusion or error theorem does not imply the required set relation. ∎

The policy changes only the date-1 cost from 2 to $1/2$. The first action remains uniquely zero. At date 1 the coefficient is $-1/2$ for type zero and $1/2$ for type one, so the unique optimal action is $a_1=\theta$. Its expectation equals $p$. Every $p\in[\kappa,1-\kappa]$ is baseline-compatible and attains its corresponding expectation, giving exactly that interval. The only nontrivial chance probabilities are $p$ and $1-p$, both at least $\kappa$; all utilities and observation probabilities are polynomial. Additional players with one available action can be added without changing any conclusion. ∎

We give the power-bound argument rather than use an unspecified error- bound theorem. The graph of distance to $F_p$ is semialgebraic: the assertion that its value at $z$ is $s\geq0$ says that some $w\in F_p$ has $\|z-w\|_\infty=s$ and that every $w'\in F_p$ has $\|z-w'\|_\infty\geq s$. Equalities and inequalities involving a finite sup norm are finite Boolean combinations of polynomial inequalities. Quantifier elimination applies, including to the universal assertion. The graph of (5) is likewise semialgebraic: there exists a feasible $z$ whose distance is the proposed value, and every feasible $z'$ has distance at most that value. Attainment, already proved, justifies this graph formula exactly.

Take a quantifier-free sign formula for the graph $\{(t,\omega_p(t)):t>0\}$. Discard identically zero polynomials from its finite sign list by replacing their tests with their truth values. This graph has empty interior in $\mathbb R^2$, because it assigns only one value to each $t$. At each of its points at least one polynomial in the list must vanish: otherwise all their signs, and therefore the formula's truth value, would be constant on a small open neighborhood of that point. The product $P(t,y)$ of the remaining nonzero polynomials is a nonzero polynomial and vanishes at every $(t,\omega_p(t))$ with $t>0$. A sign list with no polynomials cannot define this nonempty graph of empty interior, so such a product exists.

Remove the largest common power of $t$ from $P$ and call the resulting polynomial $Q$. Then $Q(0,y)$ is a nonzero polynomial in $y$, and $Q(t,\omega_p(t))=0$ for $t>0$. The limit already proved implies $Q(0,0)=0$. Thus for some integer $k\geq1$ and nonzero coefficient $c$, \[ Q(0,y)=c y^k+O(y^{k+1})\quad\text{as }y\to0. \] Choose $\eta>0$ so that $|Q(0,y)|\geq |c|y^k/2$ for $0\leq y\leq\eta$. On a small compact rectangle $0\leq t\leq\delta_0$, $0\leq y\leq\eta$, the polynomial derivative $\partial Q/\partial t$ is bounded by some finite $M$. Reduce $\delta_0$ to $\delta>0$ so that $\omega_p(t)\leq\eta$ there. For $0<t\leq\delta$, \[ \frac{|c|}{2}\omega_p(t)^k \leq|Q(0,\omega_p(t))| =|Q(0,\omega_p(t))-Q(t,\omega_p(t))| \leq Mt. \] A positive $C$ with $C^k\geq2M/|c|$ proves (6), including $t=0$. If $M=0$, the same calculation forces the modulus to vanish on this interval, and any positive $C$ suffices. Thus no regularity of the inverse correspondence beyond compact semialgebraicity was assumed.

For effectivity under algebraic coefficients, the preceding graph formulas admit effective quantifier elimination. One can alternatively avoid estimating the particular polynomial coefficients: enumerate all triples of positive integer $k$ and positive rational $C,\delta$ in a single dovetailed enumeration, and test (6) by exact quantifier elimination. That assertion is a first-order polynomial formula: introduce $r=\|O(z)-p\|_\infty$ and a nonnegative $s$ with $s^k\leq C^k r$, and require an existing $w\in F_p$ with $\|z-w\|_\infty\leq s$. Universal quantification over the constrained $z\in K$ completes the test. The bound just proved permits enlarging $C$ and shrinking $\delta$ to positive rationals, so a valid triple appears and the enumeration terminates. This is a certificate-producing exact algorithm, not a numerical residual heuristic. ∎

Apply Theorem Theorem (Hausdorff contraction of the full confidence sets) to each graph. For finitely many graphs, take the largest $k$, largest $C$, and the smallest $\delta$, also making $\delta\leq1$. Since $t^{1/k_j}\leq t^{1/k}$ for $0\leq t\leq1$ when $k\geq k_j$, these common constants work. The confidence data event is the same for every policy, so no additional union bound over policies is needed. If two nonempty compact subsets of $\mathbb R$ have Hausdorff distance at most $e$, their maxima and minima differ by at most $e$: match an extreme point of either set to a point within $e$ in the other, and use the corresponding extremal inequality. This proves the endpoint assertion without filling any holes in a policy range.

Finally the probability of a data failure at $N$ is at most $N^{-2}$. The probability of any failure after index $M$ is at most $\sum_{N\geq M}N^{-2}$, which tends to zero. Thus almost surely only finitely many failures occur. Also $r_N=O(\sqrt{\log N/N})\to0$, so $2r_N\leq\delta$ eventually. The deterministic bound then proves the almost-sure convergence and its stated eventual rate. Independence between samples at different sample sizes is not needed for this last argument; within each sample the retained iid assumption is what justifies coverage. ∎

Suppose $(\gamma_n,\sigma_n,\mu_n)\in\mathcal S$ converges to $(\gamma,\sigma,\mu)$. All sequential-rationality inequalities are continuous polynomial inequalities, so they persist in the limit. For each $n$, consistency gives a completely mixed $b_n$ within $1/n$ of $\sigma_n$, whose Bayes beliefs at $\gamma_n$ are within $1/n$ of $\mu_n$.

Factor each reach monomial as $r_h(\gamma,b)=c_h(\gamma)a_h(b)$, where $c_h$ is the product of chance probabilities on the prefix and $a_h$ the product of behavioral probabilities. The finitely many functions $c_h$ are continuous and strictly positive. Thus \[ \rho_n=\max_h\left|\frac{c_h(\gamma)}{c_h(\gamma_n)}-1\right|\longrightarrow0. \] For $\rho_n<1$, multiplying each positive reach probability by a factor in $[1-\rho_n,1+\rho_n]$ changes its normalized probability at an information set by at most $2\rho_n/(1-\rho_n)$. Indeed, the ratio of the old and new normalizers lies in the same interval, and subtracting the two normalized fractions gives this bound directly. The bound is independent of $b_n$, even when its reach probabilities tend to zero.

Consequently the Bayes beliefs generated by $b_n$ at the fixed parameter $\gamma$ converge to $\mu$. Also $b_n\to\sigma$. These are consistency witnesses at $\gamma$, proving that the limit belongs to $\mathcal S$. The graph is closed inside a compact set and hence compact. ∎

Intersecting the compact graph with the closed observation constraint makes $\mathcal A(p)$ compact. The joint set of $(\gamma,e,e^d)$ satisfying the two equilibrium graphs and the observation constraint is likewise closed and bounded. Coordinate projections and the continuous polynomial map $W_d$ preserve compactness. Polynomial quantification and projection preserve semialgebraicity by real quantifier elimination. Compactness gives attainment of extrema whenever the joint set is nonempty.

All defining constraints are first-order formulas with the stated effective coefficients, so exact quantifier elimination decides their feasibility. For the upper endpoint, the decision "there exists a feasible tuple with $W_d\geq q$" locates that endpoint relative to any rational midpoint $q$; for the lower endpoint use $W_d\leq q$. Each decision halves an enclosing interval. The claimed number of decisions follows by solving $(U-L)2^{-k}\leq\varepsilon$. An empty set is reported as such, not assigned fictitious endpoints. A noninterval counterfactual set is not replaced by its endpoint interval when its full description is requested. ∎

On the complementary event, every tuple with exact observation law $p$ satisfies the relaxed data constraint. It retains its exact equilibrium witness, so all parameters in $\Gamma_I(p)$ belong to $\widehat\Gamma_N$. Every compatible policy equilibrium attached to such a parameter is then retained too, proving the second containment. Nothing in this deterministic implication depends on the policy, proving simultaneous coverage. Replacing feasible sets by supersets preserves these containments. Residual size without a proved inclusion or error theorem does not imply the required set relation. ∎

The policy changes only the date-1 cost from 2 to $1/2$. The first action remains uniquely zero. At date 1 the coefficient is $-1/2$ for type zero and $1/2$ for type one, so the unique optimal action is $a_1=\theta$. Its expectation equals $p$. Every $p\in[\kappa,1-\kappa]$ is baseline-compatible and attains its corresponding expectation, giving exactly that interval. The only nontrivial chance probabilities are $p$ and $1-p$, both at least $\kappa$; all utilities and observation probabilities are polynomial. Additional players with one available action can be added without changing any conclusion. ∎