Аннотация:
В работе дано уточнение верхней оценки сложности алгоритма потенциальных преобразований для решения циклических игр на графах.
Оценка близка к нижней оценке сложности алгоритма потенциальных преобразований.
Получено сведение задачи об оптимальном уклонении к решению циклических игр с временной функцией на ребрах на ориентированных графах.
Ключевые слова:циклические игры с полной информацией, позиционные игры, стационарные равновесия по Нэшу, гарантированная временная сложность, алгоритм потенциальных преобразований.
Полный текст:
PDF файл (329 kB)