Участник: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} G(x^0, y) = G(x^0, y^0) }[/math]

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

В данной статье мы рассмотрим нахождение ситуаций равновесий Нэша в одном специальном случае для множеств [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] найти максимум в нём (таким образом мы находим наилучший ответ 1-го игрока, при фиксированной стратегии 2-го) и для каждой строки матрицы [math]\displaystyle{ G }[/math] найти максимум в ней (ищем наилучшие ответы 2-го игрока). Т.е. мы ищем для каждого из [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].

Макроструктура алгоритма

Алгоритм в качестве подзадачи многократно использует поис максимума в массиве ([math]\displaystyle{ n }[/math] раз в массиве длины [math]\displaystyle{ m }[/math] и [math]\displaystyle{ m }[/math] раз в массиве длины [math]\displaystyle{ n }[/math]). Затем, для все возможных позиций проверяется, является она равноесием по нэшу, как это описывалось в разделе выше.

Схема реализации последовательного алгоритма

Данный код реализует последовательную версию алгоритма

#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)
{
	//f and g are payoff matrices for first and second players respectively

	std::list<std::pair<int, int> > res;

	int n = f.size();
	int m = g[0].size();

	//find best response for first player for each fixed second player's strategy
	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]);
		}
	}


	//and best response for second player
	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]);
		}
	}


	// consinering best responses for both player check each position if it's nash equilibrium
	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]. после этого проверка каждого элемента на равновесие имеет сложность [math]\displaystyle{ O(1) }[/math], а всех соответственно [math]\displaystyle{ O(nm) }[/math].

Информационный граф

Для начала был создан граф поиска максимума для каждого столбца матрицы F. поиск максимума для каждой строки матрицы G делается аналогично.

Рис.1. поиск максимума для каждого столбца матрицы F

Ресурс параллелизма алгоритма

Для нахождения максимума в каждой из [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{ max(m, n) }[/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

Рис.1. график зависимости времени работы программы от числа процессоров и стороны матрицы

На графике видно, что в данных тестах процессы нагружаются оптимально, т.к. их увеличение приводит к сильному уменьшению времени. При данных параметрах можно считать, что время обратно пропорцинально числу процессов.

Существующие реализации алгоритма

Данный код реализует параллельную версию алгоритма

#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();

}