Если кто-то хочет аппроксимировать потенциальную функцию, то да, даже существует схема аппроксимации с полиномиальным временем (FPTAS). Видеть
Джеймс Б. Орлин, Авраам П. Пуннен, Андреас Шульц: Приближенный локальный поиск в комбинаторной оптимизации. SIAM J. Comput. 33 (5): 1201-1214 (2004).
Однако для некоторых настроек это не интересно. Например, для игр с перегрузками, где существуют чистые равновесия и их вычисления PLS-полны, профили стратегий, которые хорошо аппроксимируют потенциальную функцию, могут быть очень плохими приблизительными равновесиями. Для некоторых настроек приблизительные равновесия с постоянным множителем могут быть вычислены за полиномиальное время, даже если вычисление точного равновесия является PLS-сложным, для других настроек PLS-сложным является вычисление приблизительного равновесия для любого вычисляемого нетривиального приближения за полиномиальное время фактор, как объясняется следующим объявлением бумаги.
Иоаннис Караджаннис, Анджело Фанелли, Ник Гравин, Александр Скопалик: Вычисление приближенных чистых равновесий Нэша в играх с перегрузками. Биржи SIGecom 11 (1): 26-29 (2012).
Обратите внимание, что PLS может быть намного проще, чем FNP.
