betaFeedback

WorksComputer Science

Who Observes Whom: Network Rationalizability and Its Complexity

Abstract

Nash equilibrium and rationalizability sit at opposite informational extremes: the former presumes that each player knows all opponents' strategies, the latter that players reason from common knowledge of rationality alone. When visibility is partial and asymmetric, we study the solution concepts induced by a directed observation network GG in which an edge i→ji\to j means that ii observes jj's strategy. A set of profiles is self-sustaining if every profile in it can be justified, for every player, by conjectures from the same set that agree with everything the player observes. We consider point conjectures (single profiles) and belief conjectures (distributions over profiles). Both range from Nash equilibrium on the complete network to point- and correlated rationalizability on the empty network, and shrink monotonically as links are added. Network topology governs both behavior and complexity. A predicted profile can be found in polynomial time on the empty network, whereas a single link makes search PPAD\mathsf{PPAD}-hard: under one-sided two-player monitoring, the observed player's strategies are exactly her Nash equilibrium strategies. On hierarchical networks (transitive tournaments), membership reduces recursively to smaller games and admits polynomial-size certificates, placing verification in ∃R\exists\mathbb{R}, and in P\mathsf{P} for two players. On the directed three-cycle, however, iterated elimination may never terminate under either variant, and under point conjectures interior predictions may admit only infinite witness sets, a pathology that belief conjectures avoid in the same game. Finally, when only realized pure actions are observed, the solution set is guaranteed to be non-empty exactly when the network has no edges, and is computable in time O(n∣A∣2)O(n|A|^2).

Introduction

Two benchmark solution concepts frame non-cooperative game theory. Under the epistemic reading of Nash equilibrium [22, 1], every player correctly knows the strategies chosen by the others and best-responds to them. Rationalizability [5, 24] drops all such knowledge and characterizes the implications of common knowledge of rationality and payoffs [27]. Many environments lie between these extremes. In supply chains, organizational hierarchies, markets with local intelligence and multi-agent systems, each agent observes the behavior of particular peers and remains uninformed about everyone else. This paper asks what rational players do in such environments and how the structure of who observes whom shapes both the predictions and the computational cost of deriving them.

We model the observation structure as a directed network GG on the players and let player ii observe the strategies of her out-neighbors Ni(G)N_i(G). Under common knowledge of rationality, payoffs and GG, a set of profiles SS is self-sustaining if every σ∈S\sigma\in S can be justified, for each player ii, by conjectures drawn from SS that coincide with σ\sigma on ii’s closed neighborhood Nˉi(G)=Ni(G)∪{i}\bar{N}_i(G)=N_i(G)\cup\{i\}. The largest self-sustaining set is the prediction. We consider two forms of justification. Under point conjectures, ii justifies σi\sigma_i by a single profile σ′∈S\sigma^{\prime} \in S; this yields R(Γ,G)\mathcal{R}(\Gamma,G). Under belief conjectures, ii may hold a probability distribution over such profiles; this yields Rβ(Γ,G)\mathcal{R}^{\beta}(\Gamma,G). The belief variant is the natural specialization of rationalizable conjectural equilibrium [25, 11] to signals that reveal neighbors’ strategies; the point variant is its refinement in which each player entertains a single hypothesis about the state of play.

Both variants equal Nash equilibrium on the complete network KnK_n. On the empty network, R\mathcal{R} is Bernheim’s point-rationalizability [5] and Rβ\mathcal{R}^{\beta} is correlated rationalizability [6], which for two players is Bernheim–Pearce rationalizability. For every game and every network,

NE(Γ)⊆R(Γ,G)⊆Rβ(Γ,G)⊆Rcor(Γ),(1)\mathrm{NE}(\Gamma) \subseteq\mathcal{R}(\Gamma,G) \subseteq\mathcal{R}^{\beta}(\Gamma,G) \subseteq\mathcal{R}^{\mathrm{cor}}(\Gamma), \tag*{(1)}

and both variants expand as links are removed. The general fixed-point properties of these sets are of the kind familiar from the conjectural-equilibrium literature, and we collect them in § 2. Our contribution is to show how the topology of the network determines the predictions and their complexity:

  1. One link suffices for hardness. On the empty network a predicted profile can be found in polynomial time. With a single one-sided link between two players, the observed player’s strategies under either variant are exactly her Nash equilibrium strategies, while the observer best-responds to them (Theorem 4.1). Consequently, finding a predicted profile is PPAD-hard on every network with at least one edge, even when all players have non-trivial action sets (Theorem 4.2). Monitoring thus constrains the monitored: being observed removes a player’s freedom to be mis-predicted.

  1. Hierarchies admit compact certificates. When the network is a transitive tournament (equivalently, both GG and its complement are acyclic), membership reduces recursively to smaller games. Under point conjectures this yields witness trees of 2n−n−12^n-n-1 strategy vectors, linear in the size of the normal form, and under belief conjectures certificates of polynomial size. Verification is therefore in ∃R\exists\mathbb{R}, and in P for two players (Theorem 5.1).

  1. Cycles break finiteness. On the directed three-cycle we construct 2×2×22 \times2 \times2 games in which every round of elimination removes interior profiles, so the process never terminates, under both variants (Theorem 6.1). In a dual game, every interior profile is predicted but under point conjectures only infinite self-sustaining sets witness it, whereas belief conjectures admit witnesses with 27 profiles (Theorem 6.2). Non-termination thus persists under beliefs, while in this game infinite witnesses arise only from point conjectures.

  1. Ex-post monitoring. When realized pure actions rather than strategies are observed, the solution set is non-empty for every game if and only if the network has no edges, and it can be computed exactly in time O(n∣A∣2)O(n|A|^2) for every network (§ 7).

Table 1 summarizes the results.

NetworkSearchStructure and verification
EmptyPR\mathcal{R}: point-rationalizability, finite union of faces, finite stabilization (Thm. 3.2). Rβ\mathcal{R}^{\beta}: correlated rationalizability (Thm. 3.4).
One-sided edge, n=2n = 2PPAD-complete{(σ1,σ2):σ2∈π2(NE), σ1∈BR1(σ2)}\{(\sigma_1,\sigma_2) : \sigma_2 \in\pi_2(\mathrm{NE}),\ \sigma_1 \in\mathrm{BR}_1(\sigma_2)\}; verification by one LP (Thm. 4.1).
Any network, E≠∅E \ne\varnothingPPAD-hardHardness persists when ∣Ai∣≥2\lvert A_i\rvert\ge2 for all ii (Thm. 4.2).
Transitive tournamentPPAD-hardRecursive characterization; certificates of size 2n−n−12^n-n-1 (R\mathcal{R}) or polynomial (Rβ\mathcal{R}^{\beta}); verification in ∃R\exists\mathbb{R}, P for n=2n = 2 (Thm. 5.1).
Directed 3-cyclePPAD-hardNon-terminating elimination (Thm. 6.1); only infinite witness sets for R\mathcal{R} but finite ones for Rβ\mathcal{R}^{\beta} in the same game (Thm. 6.2).
Complete (KnK_n)As NashNash equilibrium; verification in P.
Ex-post monitoringPNon-empty for all games iff E=∅E = \varnothing; full set in O(n∣A∣2)O(n\lvert A\rvert^2) (Thms. 7.1, 7.2).

Table 1. Summary of results for an nn-player game with pure action profiles A=∏iAiA = \prod_i A_i. Unless stated otherwise, results hold for both point (R\mathcal{R}) and belief (Rβ\mathcal{R}^{\beta}) conjectures.

Related literature. Rationalizability. Bernheim [5] introduced rationalizability together with point-rationalizability, in which conjectures are single strategy profiles, and showed that point-rationalizable strategies are rationalizable; Pearce [24] characterized rationalizability by iterated elimination of never-best responses, and Brandenburger and Dekel [6] studied the correlated version, which coincides with iterated strict dominance. Battigalli and Siniscalchi’s Δ\Delta-rationalizability [4] restricts first-order beliefs by exogenous information. In our setting the restriction is endogenous: what ii knows about jj is the strategy jj actually uses, which must itself be justified.

Conjectural equilibrium. Conjectural equilibrium [2, 3], subjective equilibrium [19], self-confirming equilibrium [15], Berk–Nash equilibrium [12] and non-Nash steady states [18] require beliefs to be consistent with feedback about play. Rubinstein and Wolinsky [25] combined such consistency with rationalizability, and Esponda [11] developed the resulting framework for robust predictions. Our belief variant is the instance of this approach in which signals are projections of the strategy profile onto neighborhoods of a network. Rather than general signal structures, we study how graph-theoretic properties of the network (one-sided links, acyclicity, cycles) determine the predictions, their finiteness, and their complexity. In network formation, McBride [21] applies conjectural equilibrium under local monitoring, and Foerster, Mauleon and Vannetelbosch [14] study rationalizable conjectural pairwise stability when some links are hidden, showing that larger observation radii shrink the set of stable networks, a counterpart of the monotonicity in Theorem 2.6.

Epistemics and networks. Aumann and Brandenburger [1] show that mutual knowledge of conjectures yields Nash equilibrium; network rationalizability localizes such knowledge along the edges of GG. In graphical games [20] and network games [16] the network encodes payoff interactions; here payoffs are arbitrary and the network encodes information.

Complexity. Computing a Nash equilibrium is PPAD-complete for two players [10, 8]; exact nn-player equilibria are FIXP-complete [13], and many decision problems about equilibria are NP-hard [17] or ∃R\exists\mathbb{R}-complete [26]. Two-player rationalizability, by contrast, reduces to iterated strict dominance and is solvable by linear programming. Our results locate the transition between these regimes in the network.

Model

Games, networks and self-sustaining sets

A finite game is Γ=(N,(Ai)i∈N,(ui)i∈N)\Gamma= (N,(A_i)_{i\in N},(u_i)_{i\in N}) with players N={1,…,n}N = \{1,\ldots,n\}, finite action sets AiA_i, pure profiles A=∏iAiA = \prod_i A_i and payoffs ui:A→Ru_i : A \to\mathbb{R}, extended multilinearly to mixed profiles σ∈Σ=∏iΔ(Ai)\sigma\in\Sigma= \prod_i \Delta(A_i). We write Σ−i=∏j≠iΔ(Aj)\Sigma_{-i} = \prod_{j\ne i}\Delta(A_j), σM\sigma_M for the restriction of σ\sigma to M⊆NM \subseteq N, and

BRi(σ−i)=argmax⁡τi∈Δ(Ai) ui(τi,σ−i),BRipure(σ−i)=argmax⁡ai∈Ai ui(ai,σ−i).\mathrm{BR}_i(\sigma_{-i}) = \underset{\tau_i\in\Delta(A_i)}{\operatorname{argmax}}\ u_i(\tau_i,\sigma_{-i}), \qquad\mathrm{BR}^{\mathrm{pure}}_i(\sigma_{-i}) = \underset{a_i\in A_i}{\operatorname{argmax}}\ u_i(a_i,\sigma_{-i}).

For a finitely supported distribution μ\mu over Σ\Sigma we write ui(τi,μ)=∑σ′ ⁣,μ(σ′)ui(τi,σ′)u_i(\tau_i,\mu) = \sum_{\sigma'\!,\mu(\sigma')} u_i(\tau_i,\sigma') and define BRi(μ)\mathrm{BR}_i(\mu) and BRipure(μ)\mathrm{BR}^{\mathrm{pure}}_i(\mu) accordingly. Since ui(τi,μ)u_i(\tau_i,\mu) is linear in τi\tau_i, a mixed strategy is a best response exactly when every action in its support is:

τi∈BRi(μ)⟺supp⁡(τi)⊆BRipure(μ).(2)\tau_i \in\mathrm{BR}_i(\mu) \Longleftrightarrow\operatorname{supp}(\tau_i) \subseteq\mathrm{BR}_i^{\mathrm{pure}}(\mu). \tag*{(2)}

An observation network is a directed graph G=(N,E)G=(N,E) without self-loops; (i,j)∈E(i,j)\in E means that ii observes the strategy of jj. Let Ni(G)={j:(i,j)∈E}N_i(G)=\{j:(i,j)\in E\} and N‾i(G)=Ni(G)∪{i}\overline{N}_i(G)=N_i(G)\cup\{i\}. For S⊆ΣS\subseteq\Sigma and σ∈Σ\sigma\in\Sigma, the profiles in SS that player ii cannot distinguish from σ\sigma form the fiber

Wi(σ,S)={σ′∈S:σN‾i(G)′=σN‾i(G)}.W_i(\sigma,S)=\{\sigma'\in S:\sigma'_{\overline{N}_i(G)}=\sigma_{\overline{N}_i(G)}\}.

Definition 2.1 (Network rationalizability). Fix Γ\Gamma and GG. A set S⊆ΣS\subseteq\Sigma is self-sustaining under point conjectures if for every σ∈S\sigma\in S and i∈Ni\in N there is σ′∈Wi(σ,S)\sigma'\in W_i(\sigma,S) with σi∈BRi(σ−i′)\sigma_i\in\mathrm{BR}_i(\sigma'_{-i}). It is self-sustaining under belief conjectures if for every σ∈S\sigma\in S and i∈Ni\in N there is a finitely supported distribution μ\mu on Wi(σ,S)W_i(\sigma,S) with σi∈BRi(μ)\sigma_i\in\mathrm{BR}_i(\mu). The network-rationalizable sets R(Γ,G)R(\Gamma,G) and Rβ(Γ,G)R^\beta(\Gamma,G) are the unions of all self-sustaining sets of the respective kind.

Point conjectures are beliefs concentrated on a single profile, so every set that is self-sustaining under point conjectures is self-sustaining under belief conjectures, and R(Γ,G)⊆Rβ(Γ,G)R(\Gamma,G)\subseteq R^\beta(\Gamma,G). By Carathéodory’s theorem applied to the vector of expected payoffs in RAi\mathbb{R}^{A_i}, a justifying belief can always be taken to have at most ∣Ai∣+1|A_i|+1 atoms.

Interpretation. A conjecture is a state of the world that player ii cannot rule out: it agrees with everything she observes and with her own choice, and, because it lies in SS, it is itself coherent from every player’s point of view. Iterating this requirement expresses common knowledge of rationality, payoffs and the network. The two variants differ in how players treat uncertainty about what they do not see. Under belief conjectures, ii may hedge across several coherent states; under point conjectures she commits to one hypothesis. A conjectured mixed strategy is then a strategy its owner might actually be using, so it can put weight on several actions only if they are simultaneously optimal for that owner. This restriction is what separates point- from ordinary rationalizability on the empty network (Example 3.3).

An edge (i,j)(i,j) means that ii observes the mixed strategy σj\sigma_j (§ 7 treats observation of realized actions). Natural readings are Nash’s mass-action interpretation [23], in which σj\sigma_j is the distribution of actions in population jj; delegated play through auditable randomized programs; and the view of mixed strategies as transparent intentions, which is exactly the informational assumption behind mixed Nash equilibrium, here imposed only along the edges of GG. As in Nash equilibrium, a player evaluates deviations holding the strategies of others fixed: observation conveys information about what others do, not the power to influence it (Remark 4.3).

Including ii in N‾i(G)\overline{N}_i(G) encodes that ii knows her own strategy and knows that those who monitor her see that strategy rather than a counterfactual one. It implies a self-witnessing property used repeatedly below: every profile in the support of a justifying conjecture agrees with σ\sigma on ii’s coordinate. Dropping ii from her own neighborhood produces implausible predictions.

Example 2.2 (Self-knowledge matters). Let A1={T,B}A_1=\{T,B\}, A2={L,R}A_2=\{L,R\}, E={(1,2)}E=\{(1,2)\}, and u(T,L)=(1,1)u(T,L)=(1,1), u(T,R)=(0,1)u(T,R)=(0,1), u(B,L)=(0,1)u(B,L)=(0,1), u(B,R)=(1,0)u(B,R)=(1,0). If witnesses had to agree only on Ni(G)N_i(G), the set {(T,L),(B,R)}\{(T,L),(B,R)\} would be self-sustaining: in (B,R)(B,R), player 2 could justify RR by the witness (T,L)(T,L), in which she herself plays LL and player 1, observing LL, plays TT. Under Definition 2.1, player 2 knows that she plays RR and that player 1 sees it; hence player 1 plays BB, against which RR is strictly worse.

Example 2.3 (Partial consensus). Let players 1 and 2 observe each other and player 3 be isolated. Player 3 has a constant payoff and selects whether players 1 and 2 play Chicken or Matching Pennies. Then (σ1,σ2,σ3)∈R(Γ,G)(\sigma_1,\sigma_2,\sigma_3)\in R(\Gamma,G) if and only if σ1∈BR1(σ2,σ3′)\sigma_1\in\mathrm{BR}_1(\sigma_2,\sigma'_3) and σ2∈BR2(σ1,σ3′′)\sigma_2\in\mathrm{BR}_2(\sigma_1,\sigma''_3) for some, possibly different, σ3′,σ3′′\sigma'_3,\sigma''_3. Players 1 and 2 are mutually consistent in the Nash sense but may disagree about the unobserved state of the world.

Remark 2.4 (Coordinatewise convexification). One might instead allow ii to conjecture any σ′\sigma' with σNi‾′=σNi‾\sigma'_{\overline{N_i}}=\sigma_{\overline{N_i}} and σj′∈conv⁡(πj(S))\sigma'_j \in\operatorname{conv}(\pi_j(S)) for the other coordinates. This ignores what unobserved players themselves observe. With E={(1,2)}E=\{(1,2)\} in Matching Pennies, it would let player 2 believe that player 1 mixes uniformly, although player 2 knows that player 1 sees her strategy and best-responds to it; every strategy of player 2 would survive. Belief conjectures over fibers avoid this, because each profile in the support of the belief remains coherent.

Fixed points and elimination

Let TG(S)T_G(S) and TGβ(S)T_G^\beta(S) be the sets of σ∈Σ\sigma\in\Sigma that admit, for every ii, a point or belief conjecture in Wi(σ,S)W_i(\sigma,S) as in Definition 2.1. A set is self-sustaining exactly when S⊆TG(S)S \subseteq T_G(S), respectively S⊆TGβ(S)S \subseteq T_G^\beta(S). Define elimination stages R0=ΣR_0=\Sigma, Rt+1=TG(Rt)R_{t+1}=T_G(R_t), and analogously RtβR_t^\beta.

Theorem 2.5 (Fixed-point structure). For every game Γ\Gamma, network GG and both variants:

(i) R(Γ,G)\mathcal{R}(\Gamma,G) and Rβ(Γ,G)\mathcal{R}^\beta(\Gamma,G) are the greatest fixed points of TGT_G and TGβT_G^\beta;

(ii) the stages Rt\mathcal{R}_t and Rtβ\mathcal{R}_t^\beta are non-increasing, non-empty, compact and semi-algebraic;

(iii) R(Γ,G)=⋂tRt\mathcal{R}(\Gamma,G)=\bigcap_t \mathcal{R}_t and Rβ(Γ,G)=⋂tRtβ\mathcal{R}^\beta(\Gamma,G)=\bigcap_t \mathcal{R}_t^\beta.

Proof. Both operators are monotone, and the union of post-fixed points is a post-fixed point; Tarski’s theorem gives (i). For (ii), with ki=∣Ai∣+1k_i=|A_i|+1, TGβ(S)T_G^\beta(S) is the intersection over ii of the projections onto σ\sigma of the sets of tuples (σ,σ1,…,σki,λ)(\sigma,\sigma^1,\ldots,\sigma^{k_i},\lambda) with σm∈S\sigma^m \in S, σNi‾m=σNi‾\sigma^m_{\overline{N_i}}=\sigma_{\overline{N_i}}, λ∈Δki\lambda\in\Delta^{k_i} and ∑mλmui(σi,σ−im)≥∑mλmui(ai,σ−im)\sum_m \lambda_m u_i(\sigma_i,\sigma^m_{-i})\geq\sum_m \lambda_m u_i(a_i,\sigma^m_{-i}) for all aia_i. If SS is compact and semi-algebraic, so is this set; projection preserves compactness and, by the Tarski–Seidenberg theorem [28], semialgebraicity. The point variant is the case ki=1k_i=1. Since TG(S)⊆TGβ(S)T_G(S)\subseteq T_G^\beta(S), induction gives Rt⊆Rtβ\mathcal{R}_t\subseteq\mathcal{R}_t^\beta. Monotonicity yields that the stages are non-increasing, and non-emptiness follows from NE⁡(Γ)⊆Rt⊆Rtβ\operatorname{NE}(\Gamma)\subseteq\mathcal{R}_t\subseteq\mathcal{R}_t^\beta (Theorem 2.6). For (iii), the inclusion ⊆\subseteq holds by induction. Conversely, if σ∈⋂tRtβ\sigma\in\bigcap_t\mathcal{R}_t^\beta, then for each ii the sets of justifying tuples with σm∈Rtβ\sigma^m\in\mathcal{R}_t^\beta are non-empty, compact and nested in tt, so by Cantor’s intersection theorem some tuple works for all tt; its atoms lie in ⋂tRtβ\bigcap_t\mathcal{R}_t^\beta. Hence ⋂tRtβ\bigcap_t\mathcal{R}_t^\beta is self-sustaining. The same argument applies to R\mathcal{R}.

Theorem 2.6 (Monotonicity and existence). If E′⊆EE'\subseteq E, then R(Γ,G)⊆R(Γ,G′)\mathcal{R}(\Gamma,G)\subseteq\mathcal{R}(\Gamma,G') and Rβ(Γ,G)⊆Rβ(Γ,G′)\mathcal{R}^\beta(\Gamma,G)\subseteq\mathcal{R}^\beta(\Gamma,G'). Moreover R(Γ,Kn)=Rβ(Γ,Kn)=NE⁡(Γ)\mathcal{R}(\Gamma,K_n)=\mathcal{R}^\beta(\Gamma,K_n)=\operatorname{NE}(\Gamma), so ∅≠NE⁡(Γ)⊆R(Γ,G)⊆Rβ(Γ,G)\varnothing\ne\operatorname{NE}(\Gamma)\subseteq\mathcal{R}(\Gamma,G)\subseteq\mathcal{R}^\beta(\Gamma,G) for every GG.

Proof. Removing edges enlarges fibers, so any justification under GG remains valid under G′G'. On KnK_n the fiber of σ\sigma in any S∋σS\ni\sigma is {σ}\{\sigma\}, so the condition is σi∈BR⁡i(σ−i)\sigma_i\in\operatorname{BR}_i(\sigma_{-i}) for all ii. Non-emptiness is Nash’s theorem.

We also record that pure profiles which are self-sustaining as pure profiles (§ 7) remain so as degenerate mixed profiles: since ai∈BR⁡ipure(a−i′)a_i\in\operatorname{BR}_i^{\mathrm{pure}}(a'_{-i}) if and only if δai∈BR⁡i(δa−i′)\delta_{a_i}\in\operatorname{BR}_i(\delta_{a'_{-i}}),

Rpure(Γ,G)⊆R(Γ,G)⊆Rβ(Γ,G).(3)\mathcal{R}^{\mathrm{pure}}(\Gamma,G)\subseteq\mathcal{R}(\Gamma,G)\subseteq\mathcal{R}^\beta(\Gamma,G). \tag*{(3)}

Remark 2.7 (Support cells). By (2), the condition for player ii at σ\sigma depends on σi\sigma_i only through supp⁡(σi)\operatorname{supp}(\sigma_i). On each of the finitely many cells on which the support profile (supp⁡(σi))i(\operatorname{supp}(\sigma_i))_i is constant, the operators are therefore described by a fixed system of polynomial inequalities linking the observed coordinates of σ\sigma to the conjectured ones. § 6 shows that, on cyclic networks, iterating these finitely many rules can nonetheless require infinitely many steps.

The Empty Network

When G=∅G = \varnothing, fibers constrain only a player’s own coordinate. We begin with a decomposition that holds on every network.

Proposition 3.1 (Decomposition). For both variants:

(i) if N1,…,NmN_1,\ldots,N_m are the weakly connected components of GG, every stage and the limit are Cartesian products ∏rπNr(⋅)\prod_r \pi_{N_r}(\cdot);

(ii) if Ni(G)=N∖{i}N_i(G)=N\setminus\{i\}, player ii’s condition at any σ\sigma in the set under consideration is σi∈BRi(σ−i)\sigma_i\in\mathrm{BR}_i(\sigma_{-i});

(iii) if k∈Ni(G)k\in N_i(G) and Nk(G)⊆Ni(G)‾N_k(G)\subseteq\overline{N_i(G)} (for instance, if GG is transitive), then every justification of kk at σ\sigma is also a justification of kk at every profile in the support of a justification of ii at σ\sigma.

Proof. (i) For i∈Nri\in N_r, Ni‾⊆Nr\overline{N_i}\subseteq N_r; when SS is a product, ii’s condition constrains only σNr\sigma_{N_r}, so both operators map products to products. Induction from Σ\Sigma and Theorem 2.5(iii) give the claim. (ii) The fiber is {σ}.(iii)\{\sigma\}. (iii) Profiles in ii’s fiber agree with σ\sigma on Nk‾⊆Ni‾\overline{N_k}\subseteq\overline{N_i}, hence have the same fiber for kk.

Theorem 3.2 (Point conjectures on the empty network). (i) R(Γ,∅)=∏iPi\mathcal{R}(\Gamma,\varnothing)=\prod_i P_i, where (Pi)i(P_i)_i is the largest family with Pi⊆Δ(Ai)P_i\subseteq\Delta(A_i) such that each σi∈Pi\sigma_i\in P_i is a best response to some σ−i′∈∏j≠iPj\sigma'_{-i}\in\prod_{j\ne i}P_j. That is, R(Γ,∅)\mathcal{R}(\Gamma,\varnothing) is the set of point-rationalizable profiles [5].

(ii) Each stage has the form ∏i⋃Bi∈Bi(t)Δ(Bi)\prod_i\bigcup_{B_i\in\mathcal{B}^{(t)}_i}\Delta(B_i) for downward-closed families Bi(t)\mathcal{B}^{(t)}_i of non-empty supports, and the stages stabilize after at most ∑i(2∣Ai∣−1)\sum_i(2^{|A_i|}-1) rounds.

(iii) Membership is decidable; for n=2n=2 the limit families can be computed by linear programming in time polynomial in the size of the game times 2O(∣A1∣+∣A2∣)2^{O(|A_1|+|A_2|)}.

Proof. (i) By Proposition 3.1(i) the limit is a product, and for a product ∏jPj\prod_j P_j a witness for ii is any σ′\sigma' with σi′=σi\sigma'_i=\sigma_i and σ−i′∈∏j≠iPj\sigma'_{-i}\in\prod_{j\ne i}P_j. (ii) By (2), σi\sigma_i survives a round if and only if the region {σ−i′:supp⁡(σi)⊆BRipure(σ−i′)}\{\sigma'_{-i}:\operatorname{supp}(\sigma_i)\subseteq\mathrm{BR}^{\mathrm{pure}}_i(\sigma'_{-i})\} meets the product of the opponents’ current sets, a condition that depends only on supp⁡(σi)\operatorname{supp}(\sigma_i) and that is inherited by subsets of supports. The families are non-increasing, and each round that changes something removes a support. (iii) A support BiB_i survives if and only if, for some choice of surviving supports BjB_j of the opponents, the system σj′∈Δ(Bj)\sigma'_j\in\Delta(B_j), Bi⊆BRipure(σ−i′)B_i\subseteq\mathrm{BR}^{\mathrm{pure}}_i(\sigma'_{-i}) is feasible. For n=2n=2 this is a linear program; for n≥3n\ge3 it is a sentence of the existential theory of the reals.

Under point conjectures, a mixed conjecture about jj may put weight only on actions that are simultaneously optimal for jj. The next example shows that this can eliminate pure actions that are rationalizable, so the inclusion of point-rationalizability in rationalizability [5] can be strict even on pure actions.

Example 3.3 (Point- versus ordinary rationalizability). In the game of Table 2, no pure action is strictly dominated: TT, BB and DD are the unique best responses to LL, RR and 12L+12R\frac{1}{2}L+\frac{1}{2}R, and LL, RR, MM are the unique best responses to TT, BB, DD. Hence all pure profiles are rationalizable, and Rβ(Γ,∅)\mathcal{R}^{\beta}(\Gamma,\varnothing) contains all of them by Theorem 3.4. Under point conjectures, write σ1′=(αT,αD,αB)\sigma'_1=(\alpha_T,\alpha_D,\alpha_B) and α~=αT+12αD\tilde{\alpha}=\alpha_T+\frac{1}{2}\alpha_D; then player 2’s payoffs from LL, MM, RR are 3α~3\tilde{\alpha}, 22 and 3(1−α~)3(1-\tilde{\alpha}). Both LL and RR are optimal only at α~=12\tilde{\alpha}=\frac{1}{2}, where MM is strictly better. So every surviving strategy of player 2 has qL=0q_L=0 or qR=0q_R=0. Against qR=0q_R=0, u1(T)−u1(D)=10−9qL≥1u_1(T)-u_1(D)=10-9q_L\ge1, and symmetrically against qL=0q_L=0; hence DD is eliminated in the second round, and R(Γ,∅)⊊Rβ(Γ,∅)\mathcal{R}(\Gamma,\varnothing)\subsetneq\mathcal{R}^{\beta}(\Gamma,\varnothing).

Let Ai∗A_i^* be the actions surviving iterated elimination of strictly dominated strategies, equivalently the correlated rationalizable actions [6], and let Rcor(Γ)\mathcal{R}^{\mathrm{cor}}(\Gamma) be the set of profiles σ\sigma such that, for each ii, supp⁡(σi)⊆BRicor(ν)\operatorname{supp}(\sigma_i)\subseteq\mathrm{BR}^{\mathrm{cor}}_i(\nu) for some distribution ν\nu on ∏j≠iAj∗\prod_{j\ne i}A_j^*. Its pure profiles are exactly

LLMMRR
TT3, 30, 20, 0
DD2, 1.5−10-10, 22, 1.5
BB0, 00, 23, 3

caption: DD is rationalizable but not point-rationalizable.

∏iAi∗\prod_i A_i^*, and for n=2n = 2 it consists of the profiles in which each player uses a mixed strategy that is a best response to some belief over the opponent’s rationalizable actions, that is, a rationalizable mixed strategy in the sense of Bernheim and Pearce.

Theorem 3.4 (Endpoints of belief conjectures). Rβ(Γ,Kn)=NE⁡(Γ)R^\beta(\Gamma, K_n) = \operatorname{NE}(\Gamma) and Rβ(Γ,∅)=Rcor⁡(Γ)R^\beta(\Gamma, \varnothing) = R^{\operatorname{cor}}(\Gamma). Consequently (1) holds for every network.

Proof. The first identity is Theorem 2.6. For the second, the stages are products ∏iPi(t)\prod_i P_i^{(t)} by Proposition 3.1; let Ai(t)A_i^{(t)} be the set of actions in the supports of strategies in Pi(t)P_i^{(t)}. We show by induction on tt that

(a) δai∈Pi(t)\delta_{a_i} \in P_i^{(t)} for every ai∈Ai(t)a_i \in A_i^{(t)}, and

(b) Pi(t+1)={σi∈Pi(t):supp⁡(σi)⊆BR⁡ipure(ν)P_i^{(t+1)} = \{\sigma_i \in P_i^{(t)} : \operatorname{supp}(\sigma_i) \subseteq\operatorname{BR}_i^{\mathrm{pure}}(\nu) for some ν∈Δ(∏j≠iAj(t))}\nu\in\Delta(\prod_{j \ne i} A_j^{(t)})\}.

Statement (a) holds trivially for t=0t = 0. Assume (a) at tt. In the product stage, the fiber of σ\sigma for player ii is {σi}×∏j≠iPj(t)\{\sigma_i\} \times\prod_{j \ne i} P_j^{(t)} if σi∈Pi(t)\sigma_i \in P_i^{(t)} and empty otherwise. The distributions on A−iA_{-i} induced by beliefs over this fiber are mixtures of product measures with factors in Pj(t)P_j^{(t)}; by (a) they include every point mass on ∏j≠iAj(t)\prod_{j \ne i} A_j^{(t)}, and they are supported on that set, so they form all of Δ(∏j≠iAj(t))\Delta(\prod_{j \ne i} A_j^{(t)}). Together with (2), this gives (b) at tt. For (a) at t+1t + 1, let ai∈Ai(t+1)a_i \in A_i^{(t+1)}, say ai∈supp⁡(σi)a_i \in\operatorname{supp}(\sigma_i) with σi∈Pi(t+1)\sigma_i \in P_i^{(t+1)}. By (b), ai∈BR⁡ipure(ν)a_i \in\operatorname{BR}_i^{\mathrm{pure}}(\nu) for the belief ν\nu that justifies σi\sigma_i, and δai∈Pi(t)\delta_{a_i} \in P_i^{(t)} by (a) at tt, since ai∈Ai(t+1)⊆Ai(t)a_i \in A_i^{(t+1)} \subseteq A_i^{(t)}. Applying (b) to δai\delta_{a_i} gives δai∈Pi(t+1)\delta_{a_i} \in P_i^{(t+1)}.

By (a) and (b), Ai(t+1)A_i^{(t+1)} consists of the actions in Ai(t)A_i^{(t)} that are best responses to some correlated belief over ∏j≠iAj(t)\prod_{j \ne i} A_j^{(t)}, which is the standard characterization of iterated elimination of strictly dominated strategies [6]. The sets stabilize after finitely many rounds, and by (b) the limit is Rcor⁡(Γ)R^{\operatorname{cor}}(\Gamma). The chain (1) follows from Theorem 2.6.

Finding a Predicted Profile

Since NE⁡(Γ)⊆R(Γ,G)⊆Rβ(Γ,G)\operatorname{NE}(\Gamma) \subseteq R(\Gamma, G) \subseteq R^\beta(\Gamma, G), any algorithm for Nash equilibrium finds a predicted profile; the search problem is therefore in PPAD for two players and in FIXP for exact nn-player solutions [10, 13]. On the empty network it is much easier: by (3) and Theorems 7.1 and 7.2, a predicted pure profile exists and can be computed in polynomial time. A single observation link changes this.

Theorem 4.1 (One-sided monitoring). Let n=2n = 2 and E={(1,2)}E = \{(1, 2)\}. For both variants,

R(Γ,G)=Rβ(Γ,G)={(σ1,σ2):σ2∈π2(NE⁡(Γ)), σ1∈BR⁡1(σ2)}.R(\Gamma, G) = R^\beta(\Gamma, G) = \{(\sigma_1, \sigma_2) : \sigma_2 \in\pi_2(\operatorname{NE}(\Gamma)),\ \sigma_1 \in\operatorname{BR}_1(\sigma_2)\}.

Membership can be decided by one linear program, and from any predicted profile a Nash equilibrium (σ1′,σ2)(\sigma_1', \sigma_2) can be computed in polynomial time.

Proof. Let σ∈Rβ(Γ,G)\sigma\in R^\beta(\Gamma, G). Player 1 observes everyone, so σ1∈BR⁡1(σ2)\sigma_1 \in\operatorname{BR}_1(\sigma_2). Player 2’s belief μ\mu is supported on profiles (σ^1,σ2)∈Rβ(Γ,G)(\hat{\sigma}_1, \sigma_2) \in R^\beta(\Gamma, G); applying player 1’s condition to each of them gives σ^1∈BR⁡1(σ2)\hat{\sigma}_1 \in\operatorname{BR}_1(\sigma_2). Since u2u_2 is linear in player 1’s strategy, σ2\sigma_2 is a best response to the mean σˉ1=∑μ(σ^)σ^1\bar{\sigma}_1 = \sum\mu(\hat{\sigma})\hat{\sigma}_1, and σˉ1∈BR⁡1(σ2)\bar{\sigma}_1 \in\operatorname{BR}_1(\sigma_2) because best-response sets are convex. Hence (σˉ1,σ2)(\bar{\sigma}_1,\sigma_2) is a Nash equilibrium. Conversely, if (σ1∗,σ2)∈NE⁡(Γ)(\sigma_1^*,\sigma_2) \in\operatorname{NE}(\Gamma) and σ1∈BR⁡1(σ2)\sigma_1 \in\operatorname{BR}_1(\sigma_2), then {(σ1,σ2),(σ1∗,σ2)}\{(\sigma_1,\sigma_2),(\sigma_1^*,\sigma_2)\} is self-sustaining under point conjectures, with player 2 witnessed by (σ1∗,σ2)(\sigma_1^*,\sigma_2). Together with R⊆Rβ\mathcal{R} \subseteq\mathcal{R}^{\beta} this proves the identity. Finally, σ2∈π2(NE⁡(Γ))\sigma_2 \in\pi_2(\operatorname{NE}(\Gamma)) if and only if the linear system

σ1′∈Δ(A1),σ1′(a1)=0∀a1∉BR⁡1pure(σ2),u2(σ1′,a2)≥u2(σ1′,b2)∀a2∈supp⁡(σ2), b2∈A2\sigma_1' \in\Delta(A_1), \quad\sigma_1'(a_1)=0 \quad\forall a_1 \notin\operatorname{BR}^{\mathrm{pure}}_1(\sigma_2), \quad u_2(\sigma_1',a_2) \ge u_2(\sigma_1',b_2) \quad\forall a_2 \in\operatorname{supp}(\sigma_2),\ b_2 \in A_2

is feasible, and any solution completes σ2\sigma_2 to an equilibrium.

Theorem 4.2 (Hardness on every non-empty network). For every n≥2n \ge2 and every network GG with E≠∅E \ne\varnothing, computing an element of R(Γ,G)\mathcal{R}(\Gamma,G) or of Rβ(Γ,G)\mathcal{R}^{\beta}(\Gamma,G) is PPAD-hard, even when ∣Ak∣≥2|A_k| \ge2 for every player kk. For n=2n=2 the problem is PPAD-complete.

Proof. Let (i,j)∈E(i,j) \in E and let Γ0\Gamma_0 be a bimatrix game. Let ii and jj play Γ0\Gamma_0, and give every other player two actions that affect no one’s payoff, including her own. The strategies of these players are unconstrained and irrelevant to ii and jj, so the argument of Theorem 4.1 applies to the pair (i,j)(i,j): if (j,i)∉E(j,i) \notin E, the jj-coordinate of any predicted profile is a Nash equilibrium strategy of Γ0\Gamma_0, and the complementary strategy of ii is obtained by linear programming; if (j,i)∈E(j,i) \in E, the restriction to {i,j}\{i,j\} is itself an equilibrium of Γ0\Gamma_0. Hardness follows from [8, 10], and membership for n=2n=2 from the reduction to Nash equilibrium.

Remark 4.3 (A link pins down the observed player only). Theorem 4.1 constrains the observed player but not the observer. In the game of Table 3, the unique Nash equilibrium is (12T+12B,23L+13R)(\frac{1}{2}T+\frac{1}{2}B,\frac{2}{3}L+\frac{1}{3}R). Under E={(1,2)}E=\{(1,2)\}, player 2 must play 23L+13R\frac{2}{3}L+\frac{1}{3}R, but player 1, who is indifferent against this strategy, may play anything. For instance, (T,23L+13R)(T,\frac{2}{3}L+\frac{1}{3}R) is predicted although it is not an equilibrium, since player 2 would rather play RR against TT; across predicted profiles, player 2’s payoff ranges from 23\frac{2}{3} to 73\frac{7}{3}. The link should not be read as commitment: a leader would choose her strategy in anticipation of the follower’s reply, for example committing to LL, to which player 1 strictly prefers TT [9]. Here, as in Nash equilibrium, player 2 takes player 1’s strategy as given; observation gives information to the observer, not leverage to the observed.

LLRR
TT2.5, 20, 3
BB2, 11, 0

Table 3. One-sided monitoring versus commitment.

Verification on Hierarchical Networks

We now ask whether a given rational profile σ\sigma belongs to the predicted set. On KnK_n this is a best-response check; in general it requires certifying a self-sustaining set containing σ\sigma. Suppose the players can be ordered so that each observes all players after her:

Ni(G)={i+1,…,n}(i=1,…,n).(4)N_i(G)=\{i+1,\ldots,n\} \qquad(i=1,\ldots,n). \tag*{(4)}

Equivalently, GG is a transitive tournament; equivalently, both GG and its complement are acyclic, since a two-cycle in either graph is excluded and an acyclic tournament is transitive. Player 1 observes everyone, and player nn is observed by everyone and observes no one. Players with a single action can be deleted without affecting anything, and the induced network on the remaining players again satisfies (4); we may therefore assume ∣Ai∣≥2|A_i| \ge2 for all ii.

For τ∈Δ(An)\tau\in\Delta(A_n), let Γ∣τ\Gamma_{\mid\tau} be the (n−1)(n-1)-player game obtained by fixing player nn’s strategy to τ\tau, on the induced network G′G' on {1,…,n−1}\{1,\ldots,n-1\}.

Theorem 5.1 (Recursive verification). Under (4), σ=(σ−n,σn)∈Rβ(Γ,G)\sigma=(\sigma_{-n},\sigma_n)\in\mathcal{R}^{\beta}(\Gamma,G) if and only if

(a) σ−n∈Rβ(Γ∣σn,G′)\sigma_{-n}\in\mathcal{R}^{\beta}(\Gamma|_{\sigma_n},G'), and

(b) σn∈BR⁡n(μ)\sigma_n\in\operatorname{BR}_n(\mu) for some belief μ\mu with at most ∣An∣+1|A_n|+1 atoms in Rβ(Γ∣σn,G′)\mathcal{R}^{\beta}(\Gamma|_{\sigma_n},G').

The same holds for R\mathcal{R}, with μ\mu a single profile. Unfolding the recursion yields, for R\mathcal{R}, a certificate of 2n−n−12^n-n-1 strategy vectors, linear in the size M=n∏i∣Ai∣M=n\prod_i|A_i| of the normal form, and, for Rβ\mathcal{R}^{\beta}, a certificate of polynomial size in MM. Membership is therefore in ∃R\exists\mathbb{R} for both variants, and in P for n=2n=2.

Proof. Since n∈Ni‾(G)n\in\overline{N_i}(G) for every ii, all conjectures about a profile whose nn-th coordinate is σn\sigma_n are supported on profiles with the same nn-th coordinate.

(⇒)(\Rightarrow) The set {ω−n:ω∈Rβ(Γ,G), ωn=σn}\{\omega_{-n}:\omega\in\mathcal{R}^{\beta}(\Gamma,G),\ \omega_n=\sigma_n\} is self-sustaining in (Γ∣σn,G′)(\Gamma|_{\sigma_n},G'), because conjectures of players i<ni<n stay in it and best responses in Γ∣σn\Gamma|_{\sigma_n} coincide with those in Γ\Gamma. It contains σ−n\sigma_{-n} and the (n−1)(n-1)-coordinate parts of the atoms of player nn’s belief.

(⇐)(\Leftarrow) Let S0∋σ−nS_0\ni\sigma_{-n} and S1,…,SkS_1,\ldots,S_k, containing the atoms of μ\mu, be self-sustaining in (Γ∣σn,G′)(\Gamma|_{\sigma_n},G'), and set S={(ω−n,σn):ω−n∈⋃mSm}S=\{(\omega_{-n},\sigma_n):\omega_{-n}\in\bigcup_m S_m\}. Players i<ni<n are justified by their conjectures in ⋃mSm\bigcup_m S_m, extended by σn\sigma_n. Because Nn(G)=∅N_n(G)=\varnothing, the belief μ\mu, extended by σn\sigma_n, justifies player nn at every element of SS. Hence SS is self-sustaining and contains σ\sigma.

Certificate size. A certificate for σ\sigma consists of the atoms of player nn’s belief and their weights, together with certificates for σ−n\sigma_{-n} and for each atom in the (n−1)(n-1)-player game Γ∣σn\Gamma|_{\sigma_n}; a one-player game requires only a best-response check. For point conjectures the number of strategy vectors satisfies T(n)=2T(n−1)+(n−1)T(n)=2T(n-1)+(n-1), T(1)=0T(1)=0, so T(n)=2n−n−1T(n)=2^n-n-1, and M≥n2nM\ge n2^n gives O(M)O(M) real entries. For belief conjectures, T(n)≤(∣An∣+2)T(n−1)+(∣An∣+1)(n−1)T(n)\le(|A_n|+2)T(n-1)+(|A_n|+1)(n-1), which by induction gives T(n)≤n∏i(∣Ai∣+2)≤n2n∏i∣Ai∣≤M2T(n)\le n\prod_i(|A_i|+2)\le n2^n\prod_i|A_i|\le M^2. In both cases the constraints are polynomially many polynomial inequalities of size O(M)O(M), which is an existential sentence over the reals of polynomial size [7, 26]. For n=2n=2 the network is the single edge (1,2)(1,2), and Theorem 4.1 applies.

The recursion peels off the player who is observed by all, which is possible precisely because monitoring is acyclic. The next section shows that once monitoring is cyclic, finite unfolding can fail.

Cyclic Monitoring

On the empty network, elimination stops after finitely many rounds (Theorem 3.2), and on hierarchies every predicted profile has a finite certificate (Theorem 5.1). We show that both properties can fail on the smallest network of neither kind: the directed three-cycle C3C_3 with edges (1,2)(1,2), (2,3)(2,3), (3,1)(3,1). Indices are taken modulo 3, so player ii observes i+1i+1 and does not observe i+2i+2.

In the games below Ai={0,1}A_i=\{0,1\}, a strategy is pi=σi(1)p_i=\sigma_i(1), ui(0,⋅)=0u_i(0,\cdot)=0, and ui(1,⋅)u_i(1,\cdot) depends additively on ai+1a_{i+1} and ai+2a_{i+2}. Player ii’s gain from action 1 is then linear in pi+1p_{i+1} and in the expected conjectured value of pi+2p_{i+2}. By (2), an interior pi∈(0,1)p_i\in(0,1) requires this gain to be zero, which links what ii observes to what she must conjecture; around the cycle these links compound.

Theorem 6.1 (Non-terminating elimination). Let Γdbl\Gamma_{\mathrm{dbl}} have payoffs ui(1,ai+1,ai+2)=ai+2−2ai+1u_i(1,a_{i+1},a_{i+2})=a_{i+2}-2a_{i+1}. On C3C_3, for both variants and every t≥0t\ge0,

Rt∩(0,1]3=Rtβ∩(0,1]3=(0,2−t]3.\mathcal{R}_t\cap(0,1]^3=\mathcal{R}^{\beta}_t\cap(0,1]^3=(0,2^{-t}]^3.

Hence the stages decrease strictly at every round, elimination never terminates, and no profile in which every player uses action 1 with positive probability is predicted.

Proof. Player ii’s gain from action 1 is Δi=pˉi+2−2pi+1\Delta_i=\bar{p}_{i+2}-2p_{i+1}, where pˉi+2\bar{p}_{i+2} is the expected conjectured value of pi+2p_{i+2}. If pi>0p_i>0, action 1 is in the support of σi\sigma_i, so by (2) it must be optimal: Δi≥0\Delta_i\ge0, with equality if pi<1p_i<1.

We prove the identity for both variants simultaneously by induction on tt; the case t=0t=0 is trivial. Assume it holds at tt.

Upper bound. Let ω∈Rt+1β∩(0,1]3\omega\in R^\beta_{t+1}\cap(0,1]^3 and fix ii. Since ωi>0\omega_i>0, player ii’s belief has mean at least 2ωi+12\omega_{i+1} in coordinate i+2i+2, so some atom ω′∈Rtβ\omega'\in R^\beta_t satisfies ωi′=ωi>0\omega'_i=\omega_i>0, ωi+1′=ωi+1>0\omega'_{i+1}=\omega_{i+1}>0 and ωi+2′≥2ωi+1>0\omega'_{i+2}\ge2\omega_{i+1}>0. Thus ω′∈Rtβ∩(0,1]3=(0,2−t]3\omega'\in R^\beta_t\cap(0,1]^3=(0,2^{-t}]^3, and ωi+1≤12ωi+2′≤2−(t+1)\omega_{i+1}\le\frac{1}{2}\omega'_{i+2}\le2^{-(t+1)}. As ii is arbitrary, ω∈(0,2−(t+1)]3\omega\in(0,2^{-(t+1)}]^3. Since Rt+1⊆Rt+1βR_{t+1}\subseteq R^\beta_{t+1}, the same bound holds for point conjectures.

Lower bound. Let ω∈(0,2−(t+1)]3\omega\in(0,2^{-(t+1)}]^3 and fix ii. The profile ω′\omega' with coordinates (ωi,ωi+1,2ωi+1)(\omega_i,\omega_{i+1},2\omega_{i+1}) in positions (i,i+1,i+2)(i,i+1,i+2) lies in (0,2−t]3=Rt∩(0,1]3(0,2^{-t}]^3=R_t\cap(0,1]^3, agrees with ω\omega on N‾i={i,i+1}\overline{N}_i=\{i,i+1\}, and makes player ii indifferent. Hence ω∈Rt+1⊆Rt+1β\omega\in R_{t+1}\subseteq R^\beta_{t+1}.

The boundary of the strategy space survives: (0,0,0)(0,0,0) is a Nash equilibrium, and (0,0,p3)(0,0,p_3) is predicted for every p3p_3, with witness set {(0,0,p3),(0,0,0)}\{(0,0,p_3),(0,0,0)\}. What fails is finiteness of the process. Because indifference forces a doubling along each observation link, a conjecture that justifies one player imposes a stronger requirement on the next, and the requirement propagates around the cycle indefinitely. Beliefs do not help, since some atom must carry at least the mean. Reversing the slope produces the dual phenomenon, and here the two variants part ways.

Theorem 6.2 (Finite and infinite witnesses). Let Γhalf\Gamma_{\mathrm{half}} have payoffs ui(1,ai+1,ai+2)=ai+2−12ai+1u_i(1,a_{i+1},a_{i+2})=a_{i+2}-\frac{1}{2}a_{i+1}. Then, on C3C_3:

(i) (0,1)3⊆R(Γhalf,C3)⊆Rβ(Γhalf,C3)(0,1)^3\subseteq R(\Gamma_{\mathrm{half}},C_3)\subseteq R^\beta(\Gamma_{\mathrm{half}},C_3);

(ii) under point conjectures, every self-sustaining set containing an interior profile is infinite;

(iii) under belief conjectures, every (p1,p2,p3)∈(0,1)3(p_1,p_2,p_3)\in(0,1)^3 lies in the self-sustaining set ∏j{0,pj,1}\prod_j\{0,p_j,1\} of 27 profiles.

Proof. An interior pip_i now requires pˉi+2=12pi+1\bar{p}_{i+2}=\frac{1}{2}p_{i+1}.

(i) For (p1,p2,p3)∈(0,1)3(p_1,p_2,p_3)\in(0,1)^3, the interior profiles (p1,p2,12p2)(p_1,p_2,\frac{1}{2}p_2), (12p3,p2,p3)(\frac{1}{2}p_3,p_2,p_3) and (p1,12p1,p3)(p_1,\frac{1}{2}p_1,p_3) match what players 1, 2 and 3 observe and make them indifferent. Hence (0,1)3(0,1)^3 is self-sustaining under point conjectures.

(ii) Let SS be self-sustaining under point conjectures and ω(0)∈S∩(0,1)3\omega^{(0)}\in S\cap(0,1)^3. Set k0=1k_0=1; let ω(r+1)∈S\omega^{(r+1)}\in S be a witness for player krk_r at ω(r)\omega^{(r)} and kr+1=kr+1k_{r+1}=k_r+1. With vr=ωkr+1(r)v_r=\omega^{(r)}_{k_{r+1}}, the witness satisfies ωkr+1(r+1)=vr\omega^{(r+1)}_{k_{r+1}}=v_r and, by indifference of the interior player krk_r, ωkr+1+1(r+1)=12vr\omega^{(r+1)}_{k_{r+1}+1}=\frac{1}{2}v_r. Inductively all these coordinates are interior and vr=2−rv0v_r=2^{-r}v_0. Profiles ω(r)\omega^{(r)} and ω(s)\omega^{(s)} with r<sr<s and r≡s(mod3)r\equiv s\pmod3 differ in coordinate kr+1k_r+1, so SS is infinite.

(iii) Let S=∏j{0,pj,1}S=\prod_j\{0,p_j,1\}. For ω∈S\omega\in S and player ii, the fiber contains profiles whose (i+2)(i+2)-coordinate is 0, pi+2p_{i+2} or 1. If ωi\omega_i is interior, a belief on the values 0 and 1 with mean 12ωi+1∈[0,12]\frac{1}{2}\omega_{i+1}\in[0,\frac{1}{2}] makes ii indifferent. If ωi=0\omega_i=0, the point conjecture with value 0 gives Δi≤0\Delta_i\le0; if ωi=1\omega_i=1, the point conjecture with value 1 gives Δi≥0\Delta_i\ge0.

Together with Theorem 5.1, these games separate acyclic from cyclic monitoring and illustrate the role of the conjecture format. On hierarchies, finite certificates always exist. On C3C_3, elimination may never stop under either variant. In Γhalf\Gamma_{\mathrm{half}}, point conjectures require infinite witness sets, because a single hypothesis must be refined along an infinite chain, whereas beliefs short-circuit the chain by mixing boundary profiles. Whether belief conjectures always admit finite witnesses is open.

Ex-Post Monitoring

When players observe the realized actions of their neighbors rather than their strategies, the analogue of Definition 2.1 lives on pure profiles:

Rpure(Γ,G)=⋃{S⊆A: ∀a∈S ∀i ∃a′∈S with aNi(G)′=aNi(G), ai∈BRipure(a−i′)}.\mathcal{R}^{\mathrm{pure}}(\Gamma,G)=\bigcup\left\{S\subseteq A:\ \forall a\in S\ \forall i\ \exists a'\in S\text{ with }a'_{N_i(G)}=a_{N_i(G)},\ a_i\in\mathrm{BR}^{\mathrm{pure}}_i(a'_{-i})\right\}.

On KnK_n this is the set of pure Nash equilibria. On the empty network it is the set of profiles surviving iterated elimination of actions that are never best responses to a pure profile of surviving opponent actions. This can exclude actions used in mixed equilibria: in the game of Table 4, MM is never a best response to a pure action of the column player, yet (M,12L+12R)(M,\frac{1}{2}L+\frac{1}{2}R) is a Nash equilibrium.

LLRR
TT0, 11, 0
MM0.6, 00.6, 0
BB1, 00, 1

Table 4. MM is a best response only to non-degenerate mixtures.

Theorem 7.1 (Existence dichotomy). If E=∅E=\varnothing, then Rpure(Γ,G)≠∅\mathcal{R}^{\mathrm{pure}}(\Gamma,G)\ne\varnothing for every finite game. If E≠∅E\ne\varnothing, then for every n≥2n\ge2 there is an nn-player game with Rpure(Γ,G)=∅\mathcal{R}^{\mathrm{pure}}(\Gamma,G)=\varnothing.

Proof. If E=∅E=\varnothing, the stages are products ∏iAi(t)\prod_i A_i^{(t)}, where Ai(t+1)A_i^{(t+1)} contains the actions of Ai(t)A_i^{(t)} that are best responses to some profile in ∏j≠iAj(t)\prod_{j\ne i}A_j^{(t)}. Each Ai(t+1)A_i^{(t+1)} is non-empty: a best response to any a−i∈∏j≠iAj(t)a_{-i}\in\prod_{j\ne i}A_j^{(t)} is, a fortiori, a best response to a profile in ∏j≠iAj(s)\prod_{j\ne i}A_j^{(s)} for every s≤ts\le t, and hence lies in Ai(t+1)A_i^{(t+1)}. The decreasing sequence is finite, so its limit is a non-empty product.

If (i,j)∈E(i,j)\in E, let ii and jj play Matching Pennies and give all other players a single action. If (j,i)∈E(j,i)\in E, predicted profiles would be pure equilibria, which do not exist. Otherwise, as in Theorem 4.1, player jj’s witness a′a' satisfies aj′=aja'_j=a_j, aj∈BRjpure(ai′)a_j\in\mathrm{BR}^{\mathrm{pure}}_j(a'_i) and ai′∈BRipure(aj′)a'_i\in\mathrm{BR}^{\mathrm{pure}}_i(a'_j), so (ai′,aj′)(a'_i,a'_j) would be a pure equilibrium.

Theorem 7.2 (Polynomial-time computation). For every game and network, Rpure(Γ,G)\mathcal{R}^{\mathrm{pure}}(\Gamma,G) can be computed in time O(n∣A∣2)O(n|A|^2).

Proof. By the self-witnessing property, a∈Sa\in S has a witness for ii in SS if and only if some a′∈Sa'\in S with aNi′=aNia'_{N_i}=a_{N_i} satisfies ai′∈BRipure(a−i′)a'_i\in\mathrm{BR}^{\mathrm{pure}}_i(a'_{-i}), that is, has player ii best-responding within a′a' itself. Precompute in time O(n∣A∣)O(n|A|) the indicators bi(a)=I[ai∈BRipure(a−i)]b_i(a)=\mathbb{I}[a_i\in\mathrm{BR}^{\mathrm{pure}}_i(a_{-i})]. Starting from S=AS=A, each round computes, for every ii, the set KiK_i of keys aNi′a'_{N_i} of profiles a′∈Sa'\in S with bi(a′)=1b_i(a')=1, and keeps the profiles aa with aNi∈Kia_{N_i}\in K_i for all ii. Indexing keys by an array of size at most ∣A∣|A|, a round takes O(n∣A∣)O(n|A|) time. This is greatest-fixed-point iteration on the finite lattice 2A2^A; every round except the last removes a profile, so there are at most ∣A∣|A| rounds.

Conclusion

Network rationalizability treats the observation structure of a game as a primitive and asks what common knowledge of rationality implies when each player sees only part of what others do. A single observation link transmits the full computational hardness of Nash equilibrium; hierarchical monitoring admits compact certificates; and cyclic monitoring can produce elimination processes that never stop. Comparing point and belief conjectures separates the effects of the network from those of the conjecture format: non-termination on the cycle persists under beliefs, whereas in our example infinite witnesses do not.

Several questions remain open. First, is membership decidable on every network? Remark 2.7 reduces the operators to finitely many polynomial rules, but Theorem 6.1 rules out termination of naive elimination; relatedly, it is open whether the predicted sets are always semi-algebraic. Second, whether belief conjectures always admit finite witness sets, in contrast to Theorem 6.2(ii), is open. Third, for two players on the empty network our algorithm for point-rationalizability is exponential only in the number of actions; whether membership is polynomial is open. Fourth, a type-space characterization in the spirit of [27, 1] would make precise the epistemic reading of self-sustaining sets. Finally, adding links shrinks the set of predictions, but, as Remark 4.3 shows, it does so asymmetrically, constraining the observed player while leaving the observer free among her best responses. How such asymmetric constraints translate into welfare, and in particular when being observed helps or hurts a player, is a natural question for information and network design.

References

  1. [1]R. J. Aumann and A. Brandenburger, “Epistemic conditions for Nash equilibrium,” Econometrica, 63(5):1161–1180, 1995.
  2. [2]P. Battigalli, Comportamento razionale ed equilibrio nei giochi e nelle situazioni sociali, undergraduate dissertation, Bocconi University, Milan, 1987.
  3. [3]P. Battigalli and D. Guaitoli, “Conjectural equilibria and rationalizability in a game with incomplete information,” in Decisions, Games and Markets, P. Battigalli, A. Montesano, and F. Panunzi, Eds. Dordrecht: Kluwer, 1997, pp. 97–124.DOI
  4. [4]P. Battigalli and M. Siniscalchi, “Rationalization and incomplete information,” Advances in Theoretical Economics, 3(1), Article 3, 2003.DOI
  5. [5]B. D. Bernheim, “Rationalizable strategic behavior,” Econometrica, 52(4):1007–1028, 1984.
  6. [6]A. Brandenburger and E. Dekel, “Rationalizability and correlated equilibria,” Econometrica, 55(6):1391–1402, 1987.
  7. [7]J. Canny, “Some algebraic and geometric computations in PSPACE,” in Proc. 20th ACM Symposium on Theory of Computing (STOC), 1988, pp. 460–467.DOI
  8. [8]X. Chen, X. Deng, and S.-H. Teng, “Settling the complexity of computing two-player Nash equilibria,” Journal of the ACM, 56(3):14:1–14:57, 2009.arxiv.org/abs/0704.1678
  9. [9]V. Conitzer and T. Sandholm, “Computing the optimal strategy to commit to,” in Proc. 7th ACM Conference on Electronic Commerce (EC), 2006, pp. 82–90.DOI
  10. [10]C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou, “The complexity of computing a Nash equilibrium,” SIAM Journal on Computing, 39(1):195–259, 2009.
  11. [11]I. Esponda, “Rationalizable conjectural equilibrium: A framework for robust predictions,” Theoretical Economics, 8(2):467–501, 2013.DOI
  12. [12]I. Esponda and D. Pouzo, “Berk–Nash equilibrium: A framework for modeling agents with misspecified models,” Econometrica, 84(3):1093–1130, 2016.arxiv.org/abs/1411.1152
  13. [13]K. Etessami and M. Yannakakis, “On the complexity of Nash equilibria and other fixed points,” SIAM Journal on Computing, 39(6):2531–2597, 2010.DOI
  14. [14]M. Foerster, A. Mauleon, and V. J. Vannetelbosch, “Shadow links,” Journal of Economic Theory, 197:105325, 2021.
  15. [15]D. Fudenberg and D. K. Levine, “Self-confirming equilibrium,” Econometrica, 61(3):523–545, 1993.
  16. [16]A. Galeotti, S. Goyal, M. O. Jackson, F. Vega-Redondo, and L. Yariv, “Network games,” Review of Economic Studies, 77(1):218–244, 2010.
  17. [17]I. Gilboa and E. Zemel, “Nash and correlated equilibria: Some complexity considerations,” Games and Economic Behavior, 1(1):80–93, 1989.DOI
  18. [18]M. Gilli, “On non-Nash equilibria,” Games and Economic Behavior, 27(2):184–203, 1999.DOI
  19. [19]E. Kalai and E. Lehrer, “Subjective games and equilibria,” Games and Economic Behavior, 8(1):123–163, 1995.
  20. [20]M. Kearns, M. L. Littman, and S. Singh, “Graphical models for game theory,” in Proc. 17th Conference on Uncertainty in Artificial Intelligence (UAI), 2001, pp. 253–260.
  21. [21]M. McBride, “Imperfect monitoring in communication networks,” Journal of Economic Theory, 126(1):97–119, 2006.
  22. [22]J. F. Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, 36(1):48–49, 1950.
  23. [23]J. F. Nash, “Non-cooperative games,” Annals of Mathematics, 54(2):286–295, 1951.
  24. [24]D. G. Pearce, “Rationalizable strategic behavior and the problem of perfection,” Econometrica, 52(4):1029–1050, 1984.DOI
  25. [25]A. Rubinstein and A. Wolinsky, “Rationalizable conjectural equilibrium: Between Nash and rationalizability,” Games and Economic Behavior, 6(2):299–311, 1994.
  26. [26]M. Schaefer and D. Štefankovič, “Fixed points, Nash equilibria, and the existential theory of the reals,” Theory of Computing Systems, 60(2):172–193, 2017.
  27. [27]T. C.-C. Tan and S. R. da C. Werlang, “The Bayesian foundations of solution concepts of games,” Journal of Economic Theory, 45(2):370–391, 1988.
  28. [28]A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd ed. Berkeley: University of California Press, 1951.

Paper details

vlnc:W_kmedat79
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents