A central task of artificial intelligence is the design of artificial agents
that act towards specified goals in partially observed environments. Since such
environments frequently include interaction over time with other agents with
their own goals, reasoning about such interaction re
我们介绍了一种简单的广义形式虚拟博弈算法,用于寻找二人零和游戏的均衡点,该算法实现等价于 Fictitious Play 的广义形式。与类似的广义形式虚拟博弈算法和反事实遗憾最小化算法相比,我们比较了其性能。这三种算法在减少存储需求和计算复杂度方面具有相同的优势,该新算法直观且容易实现,是寻求快速且简便的游戏求解工具的一个吸引人的选择。
本文提出了一种新的算法方法来解决优化一些目标(如社会福利)的相关均衡问题,并且给出了一种适用于所有紧凑表示的足够条件,同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题,这个框架可以识别出新的类别的博弈,其中包括基于树图的图形多项式博弈。同样使用类似的方法,我们导出了一种足够的条件来处理最优粗糙相关均衡问题,并使用其证明了单例拥塞博弈的可跟踪性。
本文研究在任何 n 个玩家和 m 个动作的博弈中,通过对混合策略均衡进行少量取样,可以得到近似均衡。本文研究了三种不同类型的均衡,并且得出了近似均衡的上下限,这些结果表明,我们可以使用少量的样本来测试玩家是否根据近似均衡进行游戏,即使是在大型博弈中。此外,本文的研究结果大幅改进了先前对于大型博弈中近似均衡支持集大小的估计,对于所有三种均衡,我们证明了支持集大小为 polylogarithmic,而以前的最佳上限是多项式的。