游戏动态中的一个不可能定理
Jason Milionis1, Christos Papadimitriou1, Georgios Piliouras2
1Department of Computer Science, Columbia University, New York, NY 10027.
概括
游戏理论的纳什平衡 (NE) 不总是可以达到的. 这项研究证明,确定性的玩家行为不能保证在重复的游戏中从所有起点到NE的融合,这表明预测长期行为的局限性.
科学领域:
- 游戏理论 游戏理论
- 动态系统理论 动态系统理论
- 计算复杂性 计算复杂性
背景情况:
- 纳什平衡 (NE) 是游戏理论的一个核心概念,它代表了一个稳定的结果,其中没有玩家从单方面改变他们的策略中获益.
- 尽管NE的普遍存在,但仍不清楚确定性的玩家策略是否可以保证在重复游戏中从任何初始状态转向NE.
研究的目的:
- 调查确定性游戏动力学是否从所有起点始终可以汇聚到纳什平衡.
- 通过使用动态系统理论,探索纳什平衡及其在重复游戏中的近似的可预测性.
主要方法:
- 应用动态系统理论,特别是康利指数理论,来分析游戏动态的收性质.
- 发展不可能的结果,使其趋同到精确和近似的纳什平衡.
主要成果:
- 证明了一般不可能的结果:存在某些游戏,其中所有决定性动力学都未能从所有初始条件汇聚到纳什平衡.
- 证明了近似纳什平衡的更强的不可能结果,表明对于一组重要的游戏,对近似的趋同在实质性的边界上没有保证.
- 鉴定了退化游戏作为不可能发现的关键,根据计算复杂性假设,推测将结果扩展到非退化游戏.
结论:
- 纳什平衡及其近似的概念虽然广泛适用,但基本上是重复游戏中长期玩家行为的不完整预测器.
- 确定性动力学并不总是保证纳什平衡的趋同,突出了理论游戏动力学和预测建模的局限性.
相关概念视频
01:31Alternative Sets of Equilibrium Equations
402
When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
One example of such a situation can be observed in a...
402
01:13Stability of Equilibrium Configuration: Problem Solving
613
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
Problem-solving in the context of the stability of equilibrium configuration...
613
01:26Constraints and Statical Determinacy
617
In structural engineering, the equilibrium of a system is not only determined by its equations of equilibrium but also with the help of constraints. Constraints refer to restrictions on the motion of a system. The proper combinations of constraints can minimize the total number of constraints needed to maintain a system in mechanical equilibrium. When this happens, the system is said to be statically determinate. For such systems, the unknown reaction supports can be estimated using equilibrium...
617
01:12Theorems of Pappus and Guldinus: Problem Solving
749
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
749
02:20Dynamic Equilibrium
51.8K
A reversible chemical reaction represents a chemical process that proceeds in both forward (left to right) and reverse (right to left) directions. When the rates of the forward and reverse reactions are equal, the concentrations of the reactant and product species remain constant over time and the system is at equilibrium. A special double arrow is used to emphasize the reversible nature of the reaction. The relative concentrations of reactants and products in equilibrium systems vary greatly;...
51.8K
01:18First Law: Particles in Two-dimensional Equilibrium
5.1K
Recall that a particle in equilibrium is one for which the external forces are balanced. Static equilibrium involves objects at rest, and dynamic equilibrium involves objects in motion without acceleration; but it is important to remember that these conditions are relative. For instance, an object may be at rest when viewed from one frame of reference, but that same object would appear to be in motion when viewed by someone moving at a constant velocity.
Newton's first law tells us about...
Newton's first law tells us about...
5.1K