Recursive Reasoning With Reduced Complexity and Intermittency for Nonequilibrium Learning in Stochastic Games
- 28 February 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks and Learning Systems
- Vol. 34 (11) , 8467-8481
Abstract
In this article, we propose a computationally and communicationally efficient approach for decision-making in nonequilibrium stochastic games. In particular, due to the inherent complexity of computing Nash equilibria, as well as the innate tendency of agents to choose nonequilibrium strategies, we construct two models of bounded rationality based on recursive reasoning. In the first model, named level- $k$ thinking, each agent assumes that everyone else has a cognitive level immediately lower than theirs and—given such an assumption—chooses their policy to be a best response to them. In the second model, named cognitive hierarchy, each agent conjectures that the rest of the agents have a cognitive level that is lower than theirs, but follows a distribution instead of being deterministic. To explicitly compute the boundedly rational policies, a level-recursive algorithm and a level-paralleled algorithm are constructed, where the latter one can have an overall reduced computational complexity. To further reduce the complexity in the communication layer, modifications of the proposed nonequilibrium strategies are presented, which do not require the action of a boundedly rational agent to be updated at each step of the stochastic game. Simulations are performed that demonstrate our results.Keywords
Funding Information
- Army Research Office (W911NF-19-1-0270)
- Office of Naval Research (ONR) Minerva (N00014-18-1-2160)
- NSF (CAREER CPS-1851588, SATC-1801611, S&AS 1849198)
- Onassis Foundation—Scholarship (F ZQ 064-1/2020-2021)
This publication has 26 references indexed in Scilit:
- Faster Learning and Adaptation in Security Games by Exploiting Information AsymmetryIEEE Transactions on Signal Processing, 2016
- Depth of reasoning and higher order beliefsJournal of Economic Behavior & Organization, 2014
- Cyber–Physical Security of a Smart Grid InfrastructureProceedings of the IEEE, 2011
- Level-k Auctions: Can a Nonequilibrium Model of Strategic Thinking Explain the Winner's Curse and Overbidding in Private-Value Auctions?Econometrica, 2007
- A Cognitive Hierarchy Model of GamesThe Quarterly Journal of Economics, 2004
- Behavioural Game Theory: Thinking, Learning and Teaching2004
- Human-robot interactions during the robot-assisted urban search and rescue response at the World Trade CenterIEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2003
- Behavioral game theory: Plausible formal models that predict accuratelyBehavioral and Brain Sciences, 2003
- Learning in gamesEuropean Economic Review, 1998
- Learning in extensive-form games: Experimental data and simple dynamic models in the intermediate termGames and Economic Behavior, 1995