Участник:Konstantin 013

Основные авторы описания: К.В.Телегин

1 Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Данный алгоритм находит равновесие Нэша в игре двух лиц с конечным числом стратегий

1.2 Математическое описание алгоритма

Определим игру двух лиц. Пусть первый игрок имеет в своём распоряжении стратегии $x$ из множества стратегий $X$, а второй игрок стратегии $y$ из множества стратегий $Y$. Будем рассматривать игру в нормальной форме. Это означает, что каждый из игроков выбирает стратегию, не зная выбора партнёра. Пару стратегий $(x, y)$ будем называть ситуацией. у первого игрока имеется функция выигрыша $F(x, y)$, а у второго $G(x, y)$. определённые на на множестве всех ситуаций $X × Y$. каждый игрок стремится, по возможности, максимизировать свою функцию выигрыша. Таким образом, игра двух лиц в нормальной форме может быть задаётся набором $\Gamma \langle X, Y, F(x, y), G(x, y) \rangle$ Определение. Ситуация $(x^0, y^0)$ называется равновесием по Нэшу игры $\Gamma$ если: $\max_{x \in X} F(x, y^0) = F(x^0, y^0) \quad , \quad \max_{y \in Y} F(x^0, y) = G(x^0, y^0)$

Иными словами, каждому из игроков невыгодно отколняться от ситуации равновесия.

В данной статье мы рассмотрим нахождение ситуаций равновесий Нэша в случае, когда $X, Y$ - конечные множества. тогда можно считать, что $X = [1, ..., n], Y = [1, ..., m]$, а $F, G$ - являются матрицами $R^{n × m}$

1.3 Вычислительное ядро алгоритма

В описываемом алгоритме выделяется и описывается вычислительное ядро, т.е. та часть алгоритма, на которую приходится основное время работы алгоритма. Если в алгоритме несколько вычислительных ядер, то отдельно описывается каждое ядро. Описание может быть сделано в достаточно произвольной форме: словесной или с использованием языка математических формул. Вычислительное ядро может полностью совпадать с описываемым алгоритмом.