报告人：李翰禹 (北京大学计算机学院)

题目：Climbing the Ladder of Rationality: Approaching Nash Equilibria in Bounded-Rational Multi-Agent Systems

时间：2023/10/10 15:10-18:00

地点：地学楼108

摘要：

It is well-accepted that Nash equilibria represent the outcome of a rational multi-agent system. However, agents' rationality in reality is bounded due to cognitive limitations, time constraints, and computational capacity during decision-making. Thus, a bounded-rational multi-agent system may only reach an approximate Nash equilibrium. It is natural to conjecture that as the rationality extent of agents tends to infinity, the approximate Nash equilibrium converges to the Nash equilibrium. Surprisingly, this conjecture is not true in general; we demonstrate a natural dynamical-system model of bounded rationality so that the conjecture fails. Notwithstanding, we identify two conditions on bounded rationality tending to infinity under which the multi-agent systems are indeed able to arbitrarily close to any given Nash equilibrium. In our model, bounded rationality is captured by a natural number, so that the rationality becomes comparable. In contrast to the existing literature, our study is based on automata theory, which does not involve (Bayesian) probability at all. This allows us to circumvent the difficulty of the common prior and modeling belief in the study of bounded rationality in multi-agent systems, which is especially important in the context of computational game theory. As a concrete application, we show that the no-trade theorem fails in the presence of bounded rationality, even if the rationality extent of agents tends to infinity.