Участник: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 Вычислительное ядро алгоритма

Сначала будет естественно для каждого столбца матрицы $F$ найти максимум в нём и для каждой строки матрицы $G$ найти максимум в ней. Т.е. мы ищем для каждого из $m$ векторов $R^n$ мы ищем максимум и для каждого из $n$ векторов $R^m$ мы ищем максимум. После этого для каждой ситуации $(x^0, y^0)$ несложно понять, является ли она равновесием Нэша: нужно просто проверить, что $F(x^0, y^0)$ - максимальный элемент в $y^0$-м столбце матрицы $F$ и $G(x^0, y^0)$ - максимальный элемент в $x^0$-ой строке матрицы $G$.