arXiv preprint ·
Who Observes Whom: Network Rationalizability and Its Complexity
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 \emph{observation network} $G$ in which an edge $i\to j$ means that $i$ observes $j$'s strategy. A set of profiles is \emph{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 \emph{point} conjectures (single profiles) and \emph{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 $\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 $\exists\mathbb{R}$, and in $\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)$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Strategic Repayment and Latent Fragility in Financial Networks: Why Banks Withhold Payable Liquidity
Paying Creators for Training Data Can Increase AI Displacement
An axiomatic foundation for optimized certainty equivalents
Random Utility Models in the Consumption-Budget Setting: Vertex and Network-Flow Characterizations
Settling the Time and Structural Complexity of Bertrand Networks
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.