BriefGPT.xyz
Sep, 2023
光滑纳什均衡:算法与复杂性
Smooth Nash Equilibria: Algorithms and Complexity
HTML
PDF
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty
TL;DR
本文介绍了一种松弛的Nash平衡概念,即σ平滑的Nash平衡,通过使用随机化算法和多项式时间确定性算法,在常数参数范围内,可以更有效地找到近似的σ平滑的Nash平衡。
Abstract
A fundamental shortcoming of the concept of
nash equilibrium
is its
computational intractability
: approximating Nash equilibria in normal-form games is PPAD-hard. In this paper, inspired by the ideas of smoothed
→