cs.GTNov 15, 2026

Who Observes Whom: Network Rationalizability and Its Complexity

Authors: Mojtaba Fayaz-Bakhsh, MohammadAmin Fazli

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).

Figures & tables

Explore similar work

CardsList
  1. Safe Equilibrium

    Jan 12, 2022Sam GanzfriedGame TheoryNash Equilibrium