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 .
Figures & tables
| Network | Search | Structure and verification |
|---|---|---|
| Empty | : point-rationalizability, finite union of faces, finite stabilization (Thm. 3.2 ). : correlated rationalizability (Thm. 3.4 ). | |
| One-sided edge, | -complete | ; verification by one LP (Thm. 4.1 ). |
| Any network, | -hard | Hardness persists when for all (Thm. 4.2 ). |
| Transitive tournament | -hard | Recursive characterization; certificates of size ( ) or polynomial ( ); verification in , for (Thm. 5.1 ). |
| Directed -cycle | -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 . |
Game Theory
Game theory studies how interacting decision-makers choose strategies, form agreements, and shape outcomes under competition and cooperation.
See all 247 papers