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 in which an edge means that observes '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 -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 , and in 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 .
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 on the players and let player observe the strategies of her out-neighbors . Under common knowledge of rationality, payoffs and , a set of profiles is self-sustaining if every can be justified, for each player , by conjectures drawn from that coincide with on ’s closed neighborhood . The largest self-sustaining set is the prediction. We consider two forms of justification. Under point conjectures, justifies by a single profile ; this yields . Under belief conjectures, may hold a probability distribution over such profiles; this yields . 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 . On the empty network, is Bernheim’s point-rationalizability [5] and is correlated rationalizability [6], which for two players is Bernheim–Pearce rationalizability. For every game and every network,
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:
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.
Hierarchies admit compact certificates. When the network is a transitive tournament (equivalently, both and its complement are acyclic), membership reduces recursively to smaller games. Under point conjectures this yields witness trees of strategy vectors, linear in the size of the normal form, and under belief conjectures certificates of polynomial size. Verification is therefore in , and in P for two players (Theorem 5.1).
Cycles break finiteness. On the directed three-cycle we construct 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.
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 for every network (§ 7).
Table 1 summarizes the results.
| Network | Search | Structure and verification |
| Empty | P | : point-rationalizability, finite union of faces, finite stabilization (Thm. 3.2). : correlated rationalizability (Thm. 3.4). |
| One-sided edge, | PPAD-complete | ; verification by one LP (Thm. 4.1). |
| Any network, | PPAD-hard | Hardness persists when for all (Thm. 4.2). |
| Transitive tournament | PPAD-hard | Recursive characterization; certificates of size () or polynomial (); verification in , P for (Thm. 5.1). |
| Directed 3-cycle | PPAD-hard | Non-terminating elimination (Thm. 6.1); only infinite witness sets for but finite ones for in the same game (Thm. 6.2). |
| Complete () | As Nash | Nash equilibrium; verification in P. |
| Ex-post monitoring | P | Non-empty for all games iff ; full set in (Thms. 7.1, 7.2). |
Table 1. Summary of results for an -player game with pure action profiles . Unless stated otherwise, results hold for both point () and belief () 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 -rationalizability [4] restricts first-order beliefs by exogenous information. In our setting the restriction is endogenous: what knows about is the strategy 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 . 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 -player equilibria are FIXP-complete [13], and many decision problems about equilibria are NP-hard [17] or -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 with players , finite action sets , pure profiles and payoffs , extended multilinearly to mixed profiles . We write , for the restriction of to , and
For a finitely supported distribution over we write and define and accordingly. Since is linear in , a mixed strategy is a best response exactly when every action in its support is:
An observation network is a directed graph without self-loops; means that observes the strategy of . Let and . For and , the profiles in that player cannot distinguish from form the fiber
Definition 2.1 (Network rationalizability). Fix and . A set is self-sustaining under point conjectures if for every and there is with . It is self-sustaining under belief conjectures if for every and there is a finitely supported distribution on with . The network-rationalizable sets and 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 . By Carathéodory’s theorem applied to the vector of expected payoffs in , a justifying belief can always be taken to have at most atoms.
Interpretation. A conjecture is a state of the world that player cannot rule out: it agrees with everything she observes and with her own choice, and, because it lies in , 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, 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 means that observes the mixed strategy (§ 7 treats observation of realized actions). Natural readings are Nash’s mass-action interpretation [23], in which is the distribution of actions in population ; 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 . 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 in encodes that 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 on ’s coordinate. Dropping from her own neighborhood produces implausible predictions.
Example 2.2 (Self-knowledge matters). Let , , , and , , , . If witnesses had to agree only on , the set would be self-sustaining: in , player 2 could justify by the witness , in which she herself plays and player 1, observing , plays . Under Definition 2.1, player 2 knows that she plays and that player 1 sees it; hence player 1 plays , against which 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 if and only if and for some, possibly different, . 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 to conjecture any with and for the other coordinates. This ignores what unobserved players themselves observe. With 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 and be the sets of that admit, for every , a point or belief conjecture in as in Definition 2.1. A set is self-sustaining exactly when , respectively . Define elimination stages , , and analogously .
Theorem 2.5 (Fixed-point structure). For every game , network and both variants:
(i) and are the greatest fixed points of and ;
(ii) the stages and are non-increasing, non-empty, compact and semi-algebraic;
(iii) and .
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 , is the intersection over of the projections onto of the sets of tuples with , , and for all . If 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 . Since , induction gives . Monotonicity yields that the stages are non-increasing, and non-emptiness follows from (Theorem 2.6). For (iii), the inclusion holds by induction. Conversely, if , then for each the sets of justifying tuples with are non-empty, compact and nested in , so by Cantor’s intersection theorem some tuple works for all ; its atoms lie in . Hence is self-sustaining. The same argument applies to .
Theorem 2.6 (Monotonicity and existence). If , then and . Moreover , so for every .
Proof. Removing edges enlarges fibers, so any justification under remains valid under . On the fiber of in any is , so the condition is for all . 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 if and only if ,
Remark 2.7 (Support cells). By (2), the condition for player at depends on only through . On each of the finitely many cells on which the support profile is constant, the operators are therefore described by a fixed system of polynomial inequalities linking the observed coordinates of 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 , 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 are the weakly connected components of , every stage and the limit are Cartesian products ;
(ii) if , player ’s condition at any in the set under consideration is ;
(iii) if and (for instance, if is transitive), then every justification of at is also a justification of at every profile in the support of a justification of at .
Proof. (i) For , ; when is a product, ’s condition constrains only , so both operators map products to products. Induction from and Theorem 2.5(iii) give the claim. (ii) The fiber is Profiles in ’s fiber agree with on , hence have the same fiber for .
Theorem 3.2 (Point conjectures on the empty network). (i) , where is the largest family with such that each is a best response to some . That is, is the set of point-rationalizable profiles [5].
(ii) Each stage has the form for downward-closed families of non-empty supports, and the stages stabilize after at most rounds.
(iii) Membership is decidable; for the limit families can be computed by linear programming in time polynomial in the size of the game times .
Proof. (i) By Proposition 3.1(i) the limit is a product, and for a product a witness for is any with and . (ii) By (2), survives a round if and only if the region meets the product of the opponents’ current sets, a condition that depends only on 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 survives if and only if, for some choice of surviving supports of the opponents, the system , is feasible. For this is a linear program; for it is a sentence of the existential theory of the reals.
Under point conjectures, a mixed conjecture about may put weight only on actions that are simultaneously optimal for . 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: , and are the unique best responses to , and , and , , are the unique best responses to , , . Hence all pure profiles are rationalizable, and contains all of them by Theorem 3.4. Under point conjectures, write and ; then player 2’s payoffs from , , are , and . Both and are optimal only at , where is strictly better. So every surviving strategy of player 2 has or . Against , , and symmetrically against ; hence is eliminated in the second round, and .
Let be the actions surviving iterated elimination of strictly dominated strategies, equivalently the correlated rationalizable actions [6], and let be the set of profiles such that, for each , for some distribution on . Its pure profiles are exactly
| 3, 3 | 0, 2 | 0, 0 | |
| 2, 1.5 | , 2 | 2, 1.5 | |
| 0, 0 | 0, 2 | 3, 3 |
caption: is rationalizable but not point-rationalizable.
, and for 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). and . Consequently (1) holds for every network.
Proof. The first identity is Theorem 2.6. For the second, the stages are products by Proposition 3.1; let be the set of actions in the supports of strategies in . We show by induction on that
(a) for every , and
(b) for some .
Statement (a) holds trivially for . Assume (a) at . In the product stage, the fiber of for player is if and empty otherwise. The distributions on induced by beliefs over this fiber are mixtures of product measures with factors in ; by (a) they include every point mass on , and they are supported on that set, so they form all of . Together with (2), this gives (b) at . For (a) at , let , say with . By (b), for the belief that justifies , and by (a) at , since . Applying (b) to gives .
By (a) and (b), consists of the actions in that are best responses to some correlated belief over , 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 . The chain (1) follows from Theorem 2.6.
Finding a Predicted Profile
Since , any algorithm for Nash equilibrium finds a predicted profile; the search problem is therefore in PPAD for two players and in FIXP for exact -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 and . For both variants,
Membership can be decided by one linear program, and from any predicted profile a Nash equilibrium can be computed in polynomial time.
Proof. Let . Player 1 observes everyone, so . Player 2’s belief is supported on profiles ; applying player 1’s condition to each of them gives . Since is linear in player 1’s strategy, is a best response to the mean , and because best-response sets are convex. Hence is a Nash equilibrium. Conversely, if and , then is self-sustaining under point conjectures, with player 2 witnessed by . Together with this proves the identity. Finally, if and only if the linear system
is feasible, and any solution completes to an equilibrium.
Theorem 4.2 (Hardness on every non-empty network). For every and every network with , computing an element of or of is PPAD-hard, even when for every player . For the problem is PPAD-complete.
Proof. Let and let be a bimatrix game. Let and play , 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 and , so the argument of Theorem 4.1 applies to the pair : if , the -coordinate of any predicted profile is a Nash equilibrium strategy of , and the complementary strategy of is obtained by linear programming; if , the restriction to is itself an equilibrium of . Hardness follows from [8, 10], and membership for 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 . Under , player 2 must play , but player 1, who is indifferent against this strategy, may play anything. For instance, is predicted although it is not an equilibrium, since player 2 would rather play against ; across predicted profiles, player 2’s payoff ranges from to . 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 , to which player 1 strictly prefers [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.
| 2.5, 2 | 0, 3 | |
| 2, 1 | 1, 0 |
Table 3. One-sided monitoring versus commitment.
Verification on Hierarchical Networks
We now ask whether a given rational profile belongs to the predicted set. On this is a best-response check; in general it requires certifying a self-sustaining set containing . Suppose the players can be ordered so that each observes all players after her:
Equivalently, is a transitive tournament; equivalently, both 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 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 for all .
For , let be the -player game obtained by fixing player ’s strategy to , on the induced network on .
Theorem 5.1 (Recursive verification). Under (4), if and only if
(a) , and
(b) for some belief with at most atoms in .
The same holds for , with a single profile. Unfolding the recursion yields, for , a certificate of strategy vectors, linear in the size of the normal form, and, for , a certificate of polynomial size in . Membership is therefore in for both variants, and in P for .
Proof. Since for every , all conjectures about a profile whose -th coordinate is are supported on profiles with the same -th coordinate.
The set is self-sustaining in , because conjectures of players stay in it and best responses in coincide with those in . It contains and the -coordinate parts of the atoms of player ’s belief.
Let and , containing the atoms of , be self-sustaining in , and set . Players are justified by their conjectures in , extended by . Because , the belief , extended by , justifies player at every element of . Hence is self-sustaining and contains .
Certificate size. A certificate for consists of the atoms of player ’s belief and their weights, together with certificates for and for each atom in the -player game ; a one-player game requires only a best-response check. For point conjectures the number of strategy vectors satisfies , , so , and gives real entries. For belief conjectures, , which by induction gives . In both cases the constraints are polynomially many polynomial inequalities of size , which is an existential sentence over the reals of polynomial size [7, 26]. For the network is the single edge , 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 with edges , , . Indices are taken modulo 3, so player observes and does not observe .
In the games below , a strategy is , , and depends additively on and . Player ’s gain from action 1 is then linear in and in the expected conjectured value of . By (2), an interior requires this gain to be zero, which links what observes to what she must conjecture; around the cycle these links compound.
Theorem 6.1 (Non-terminating elimination). Let have payoffs . On , for both variants and every ,
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 ’s gain from action 1 is , where is the expected conjectured value of . If , action 1 is in the support of , so by (2) it must be optimal: , with equality if .
We prove the identity for both variants simultaneously by induction on ; the case is trivial. Assume it holds at .
Upper bound. Let and fix . Since , player ’s belief has mean at least in coordinate , so some atom satisfies , and . Thus , and . As is arbitrary, . Since , the same bound holds for point conjectures.
Lower bound. Let and fix . The profile with coordinates in positions lies in , agrees with on , and makes player indifferent. Hence .
The boundary of the strategy space survives: is a Nash equilibrium, and is predicted for every , with witness set . 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 have payoffs . Then, on :
(i) ;
(ii) under point conjectures, every self-sustaining set containing an interior profile is infinite;
(iii) under belief conjectures, every lies in the self-sustaining set of 27 profiles.
Proof. An interior now requires .
(i) For , the interior profiles , and match what players 1, 2 and 3 observe and make them indifferent. Hence is self-sustaining under point conjectures.
(ii) Let be self-sustaining under point conjectures and . Set ; let be a witness for player at and . With , the witness satisfies and, by indifference of the interior player , . Inductively all these coordinates are interior and . Profiles and with and differ in coordinate , so is infinite.
(iii) Let . For and player , the fiber contains profiles whose -coordinate is 0, or 1. If is interior, a belief on the values 0 and 1 with mean makes indifferent. If , the point conjecture with value 0 gives ; if , the point conjecture with value 1 gives .
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 , elimination may never stop under either variant. In , 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:
On 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, is never a best response to a pure action of the column player, yet is a Nash equilibrium.
| 0, 1 | 1, 0 | |
| 0.6, 0 | 0.6, 0 | |
| 1, 0 | 0, 1 |
Table 4. is a best response only to non-degenerate mixtures.
Theorem 7.1 (Existence dichotomy). If , then for every finite game. If , then for every there is an -player game with .
Proof. If , the stages are products , where contains the actions of that are best responses to some profile in . Each is non-empty: a best response to any is, a fortiori, a best response to a profile in for every , and hence lies in . The decreasing sequence is finite, so its limit is a non-empty product.
If , let and play Matching Pennies and give all other players a single action. If , predicted profiles would be pure equilibria, which do not exist. Otherwise, as in Theorem 4.1, player ’s witness satisfies , and , so would be a pure equilibrium.
Theorem 7.2 (Polynomial-time computation). For every game and network, can be computed in time .
Proof. By the self-witnessing property, has a witness for in if and only if some with satisfies , that is, has player best-responding within itself. Precompute in time the indicators . Starting from , each round computes, for every , the set of keys of profiles with , and keeps the profiles with for all . Indexing keys by an array of size at most , a round takes time. This is greatest-fixed-point iteration on the finite lattice ; every round except the last removes a profile, so there are at most 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]R. J. Aumann and A. Brandenburger, “Epistemic conditions for Nash equilibrium,” Econometrica, 63(5):1161–1180, 1995.
- [2]P. Battigalli, Comportamento razionale ed equilibrio nei giochi e nelle situazioni sociali, undergraduate dissertation, Bocconi University, Milan, 1987.
- [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]P. Battigalli and M. Siniscalchi, “Rationalization and incomplete information,” Advances in Theoretical Economics, 3(1), Article 3, 2003.DOI
- [5]B. D. Bernheim, “Rationalizable strategic behavior,” Econometrica, 52(4):1007–1028, 1984.
- [6]A. Brandenburger and E. Dekel, “Rationalizability and correlated equilibria,” Econometrica, 55(6):1391–1402, 1987.
- [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]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]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]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]I. Esponda, “Rationalizable conjectural equilibrium: A framework for robust predictions,” Theoretical Economics, 8(2):467–501, 2013.DOI
- [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]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]M. Foerster, A. Mauleon, and V. J. Vannetelbosch, “Shadow links,” Journal of Economic Theory, 197:105325, 2021.
- [15]D. Fudenberg and D. K. Levine, “Self-confirming equilibrium,” Econometrica, 61(3):523–545, 1993.
- [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]I. Gilboa and E. Zemel, “Nash and correlated equilibria: Some complexity considerations,” Games and Economic Behavior, 1(1):80–93, 1989.DOI
- [18]M. Gilli, “On non-Nash equilibria,” Games and Economic Behavior, 27(2):184–203, 1999.DOI
- [19]E. Kalai and E. Lehrer, “Subjective games and equilibria,” Games and Economic Behavior, 8(1):123–163, 1995.
- [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]M. McBride, “Imperfect monitoring in communication networks,” Journal of Economic Theory, 126(1):97–119, 2006.
- [22]J. F. Nash, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, 36(1):48–49, 1950.
- [23]J. F. Nash, “Non-cooperative games,” Annals of Mathematics, 54(2):286–295, 1951.
- [24]D. G. Pearce, “Rationalizable strategic behavior and the problem of perfection,” Econometrica, 52(4):1029–1050, 1984.DOI
- [25]A. Rubinstein and A. Wolinsky, “Rationalizable conjectural equilibrium: Between Nash and rationalizability,” Games and Economic Behavior, 6(2):299–311, 1994.
- [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]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]A. Tarski, A Decision Method for Elementary Algebra and Geometry, 2nd ed. Berkeley: University of California Press, 1951.