Участник:Konstantin 013
Основные авторы описания: К.В.Телегин
Свойства и структура алгоритмов
Общее описание алгоритма
Данный алгоритм находит равновесие Нэша в игре двух лиц с конечным числом стратегий
Математическое описание алгоритма
Определим игру двух лиц. Пусть первый игрок имеет в своём распоряжении стратегии [math]\displaystyle{ x }[/math] из множества стратегий [math]\displaystyle{ X }[/math], а второй игрок стратегии [math]\displaystyle{ y }[/math] из множества стратегий [math]\displaystyle{ Y }[/math]. Будем рассматривать игру в нормальной форме. Это означает, что каждый из игроков выбирает стратегию, не зная выбора партнёра. Пару стратегий [math]\displaystyle{ (x, y) }[/math] будем называть ситуацией. У первого игрока имеется функция выигрыша [math]\displaystyle{ F(x, y) }[/math], а у второго [math]\displaystyle{ G(x, y) }[/math], определённые на на множестве всех ситуаций [math]\displaystyle{ X × Y }[/math]. каждый игрок стремится, по возможности, максимизировать свою функцию выигрыша. Таким образом, игра двух лиц в нормальной форме задаётся набором [math]\displaystyle{ \Gamma \langle X, Y, F(x, y), G(x, y) \rangle }[/math]. Ситуация [math]\displaystyle{ (x^0, y^0) }[/math] называется равновесием по Нэшу игры [math]\displaystyle{ \Gamma }[/math] если: [math]\displaystyle{ \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) }[/math]
Иными словами, каждому из игроков невыгодно отколняться от ситуации равновесия.[1]
В данной статье мы рассмотрим нахождение ситуаций равновесий Нэша в одном специальном случае для множеств [math]\displaystyle{ X, Y }[/math]. Назовём игру [math]\displaystyle{ \Gamma }[/math] биматричной, если [math]\displaystyle{ X, Y }[/math] - конечные множества. тогда можно считать, что [math]\displaystyle{ X = [1, ..., n], Y = [1, ..., m] }[/math], а [math]\displaystyle{ F, G }[/math] - являются матрицами [math]\displaystyle{ R^{n × m} }[/math]
Вычислительное ядро алгоритма
Сначала будет естественно для каждого столбца матрицы [math]\displaystyle{ F }[/math] найти максимум в нём и для каждой строки матрицы [math]\displaystyle{ G }[/math] найти максимум в ней. Т.е. мы ищем для каждого из [math]\displaystyle{ m }[/math] векторов [math]\displaystyle{ R^n }[/math] мы ищем максимум и для каждого из [math]\displaystyle{ n }[/math] векторов [math]\displaystyle{ R^m }[/math] мы ищем максимум. После этого для каждой ситуации [math]\displaystyle{ (x^0, y^0) }[/math] несложно понять, является ли она равновесием Нэша: нужно просто проверить, что [math]\displaystyle{ F(x^0, y^0) }[/math] - максимальный элемент в [math]\displaystyle{ y^0 }[/math]-м столбце матрицы [math]\displaystyle{ F }[/math] и [math]\displaystyle{ G(x^0, y^0) }[/math] - максимальный элемент в [math]\displaystyle{ x^0 }[/math]-ой строке матрицы [math]\displaystyle{ G }[/math].
Макроструктура алгоритма
Алгоритм в качестве подзадачи многократно использует поис максимума в массиве (n раз для массиве длины m и ь раз для массиве длины n). Затем, для все возможных позиций проверяется, является она равноесием по нэшу, как это описывалось в разделе выше.
Схема реализации последовательного алгоритма
Данный код реализует последовательную версию алгоритма
#include <vector>
#include <algorithm>
#include <list>
#include <utility>
std::list<std::pair<int, int> >
nash_equilibrium(
const std::vector<std::vector<double> > &f,
const std::vector<std::vector<double> > &g)
{
std::list<std::pair<int, int> > res;
int n = f.size();
int m = g[0].size();
std::vector<double> maxf(m);
for (int i = 0; i < m; ++i) {
maxf[i] = f[0][i];
for (int j = 1; j < n; ++j) {
maxf[i] = std::max(maxf[i], f[j][i]);
}
}
std::vector<double> maxg(n);
for (int i = 0; i < n; ++i) {
maxg[i] = g[i][0];
for (int j = 1; j < m; ++j) {
maxg[i] = std::max(maxg[i], g[i][j]);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (f[i][j] == maxf[j] && g[i][j] == maxg[i]) {
res.emplace_back(i, j);
}
}
}
return res;
}
Последовательная сложность алгоритма
Сложность поиска максима во всех строках(стоблцах) в этих матрицах составит [math]\displaystyle{ O(nm) }[/math]. после этго проверка каждого элемента на равновесие имеет сложность O(1), а всех соответственно O(mn).
Информационный граф
Для начала был создан граф поиска максимума для каждого столбца матрицы F. поиск максимума для каждой строки матрицы G делается аналогично.
Ресурс параллелизма алгоритма
Для нахождения максимума в каждой из [math]\displaystyle{ n }[/math] строк матрицы [math]\displaystyle{ F }[/math] понадобится [math]\displaystyle{ m - 1 }[/math] операция сравнения для вещественных чисел. Аналогично, для нахождения максимума в каждом из [math]\displaystyle{ m }[/math] столбцов матрицы [math]\displaystyle{ G }[/math] понадобится [math]\displaystyle{ n - 1 }[/math] операция сравнения для вещественных чисел. Далее, для определения каждой ситуации на равновесие нужно просто сравнить значение в [math]\displaystyle{ F }[/math] с максимумом в столбце и в [math]\displaystyle{ G }[/math] с максимумом в строке, т.е. для каждой ситуации это [math]\displaystyle{ O(1) }[/math], а так как, для каждой ситуации это независимые действия, при неограниченном числе ресурсов все вычисления имеют сложность [math]\displaystyle{ O(1) }[/math].
Входные и выходные данные алгоритма
Входные данные: две матрицы [math]\displaystyle{ R^{n × m} }[/math]
Выходные данные: список пар [math]\displaystyle{ (i, j) }[/math], где [math]\displaystyle{ i \in [1 .. n], j \in [1 .. m] }[/math]
Программная реализация алгоритма
Масштабируемость алгоритма и его реализации
на графике показана зависимость производительности от размеров матриц (в тестах они задавались квадратными) и от числа процессоров. диапазоны:
число процессоров: [1, 32]
сторона матриц: числа от 100 до 24100 с шагом 1000
.png)
Существующие реализации алгоритма
Данный код реализует параллельную версию алгоритма
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <mpi.h>
using namespace std;
vector<vector<double> >
create_local_matrix(
int n,
int m,
int n_proc,
int rank)
{
int loc_n = rank < n % n_proc ? n / n_proc + 1 : n / n_proc;
vector<vector<double> > F(loc_n, vector<double>(m));
for (auto &i: F) {
for (auto &j: i) {
j = rand() % 1000;
}
}
return F;
}
vector<double>
calc_max_in_rows(const vector<vector<double> > &G)
{
vector<double> G_max(G.size());
for (int i = 0; i < G.size(); ++i) {
G_max[i] = G[i][0];
for (int j = 1; j < G[i].size(); ++j) {
G_max[i] = max(G_max[i], G[i][j]);
}
}
return G_max;
}
vector<double>
calc_max_in_cols(const vector<vector<double> > &F)
{
vector<double> F_max(F[0].size());
for (int i = 0; i < F_max.size(); ++i) {
F_max[i] = F[0][i];
for (int j = 1; j < F.size(); ++j) {
F_max[i] = max(F_max[i], F[j][i]);
}
}
return F_max;
}
int
main(int argc, char *argv[])
{
int n_proc;
int rank;
int n, m;
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &n_proc);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
//reading and sending n and m;
if (rank == 0) {
// this is main process
cin >> n >> m;
if (n < m) {
swap(n, m);
}
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
MPI_Bcast(&m, 1, MPI_INT, 0, MPI_COMM_WORLD);
//Create and fill its part of matrices F and G
srand(time(NULL));
vector<vector<double> > F = create_local_matrix(n, m, n_proc, rank);
vector<vector<double> > G = create_local_matrix(n, m, n_proc, rank);
//every process calculate max in every its rows of matrix G and columns of matrix F
int loc_n = rank < n % n_proc ? n / n_proc + 1 : n / n_proc;
//columns of F
vector<double> loc_F_col_max = calc_max_in_cols(F);
//and rows of G
vector<double> loc_G_row_max = calc_max_in_rows(G);
//now we gather this local maximums in on common vector
vector<double> F_max(m);
MPI_Allreduce(loc_F_col_max.data(), F_max.data(), m, MPI_DOUBLE, MPI_MAX, MPI_COMM_WORLD);
//find nash equilibriums
vector<pair<int, int> > loc_ans;
for (int i = 0; i < loc_n; ++i) {
for (int j = 0; j < m; ++j) {
if (F[i][j] == F_max[j] && G[i][j] == loc_G_row_max[i]) {
loc_ans.push_back(make_pair(i, j));
}
}
}
MPI_Finalize();
}
Литература
- ↑ Васин А.А., Морозов В.В. "Введение в теорию игр с приложениями в экономике"(учебное пособие). - М.: 2003. - 278 с. Pages 91-92