Участник:Konstantin 013: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 28 промежуточных версий этого же участника)
Строка 3: Строка 3:
 
== Свойства и структура алгоритмов ==
 
== Свойства и структура алгоритмов ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
Данный алгоритм находит равновесие Нэша в игре двух лиц с конечным числом стратегий
+
Данный алгоритм находит равновесия Нэша в игре двух лиц с конечным числом стратегий
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
Строка 10: Строка 10:
 
<math> \Gamma \langle X, Y, F(x, y), G(x, y) \rangle </math>. Ситуация <math> (x^0, y^0) </math> называется ''равновесием по Нэшу'' игры <math> \Gamma </math> если:
 
<math> \Gamma \langle X, Y, F(x, y), G(x, y) \rangle </math>. Ситуация <math> (x^0, y^0) </math> называется ''равновесием по Нэшу'' игры <math> \Gamma </math> если:
 
<math>
 
<math>
     \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)
+
     \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>
  
Строка 19: Строка 19:
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
Сначала будет естественно для каждого столбца матрицы <math> F </math> найти максимум в нём и для каждой строки матрицы <math> G  </math> найти максимум в ней. Т.е. мы ищем для каждого из <math> m </math> векторов <math> R^n </math> мы ищем максимум и для каждого из <math> n </math> векторов <math> R^m </math> мы ищем максимум.
+
Сначала будет естественно для каждого столбца матрицы <math> F </math> найти максимум в нём (таким образом мы находим наилучший ответ 1-го игрока, при фиксированной стратегии 2-го) и для каждой строки матрицы <math> G  </math> найти максимум в ней (ищем наилучшие ответы 2-го игрока). Т.е. мы ищем для каждого из <math> m </math> векторов <math> R^n </math> мы ищем максимум и для каждого из <math> n </math> векторов <math> R^m </math> мы ищем максимум.
 
После этого для каждой ситуации <math> (x^0, y^0) </math> несложно понять, является ли она равновесием Нэша: нужно просто проверить, что <math> F(x^0, y^0) </math> - максимальный элемент в  <math> y^0 </math>-м столбце матрицы  <math> F </math> и  <math> G(x^0, y^0) </math> - максимальный элемент в  <math> x^0 </math>-ой строке матрицы  <math> G </math>.
 
После этого для каждой ситуации <math> (x^0, y^0) </math> несложно понять, является ли она равновесием Нэша: нужно просто проверить, что <math> F(x^0, y^0) </math> - максимальный элемент в  <math> y^0 </math>-м столбце матрицы  <math> F </math> и  <math> G(x^0, y^0) </math> - максимальный элемент в  <math> x^0 </math>-ой строке матрицы  <math> G </math>.
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
  
Алгоритм в качестве подзадачи многократно использует поис максимума в массиве (n раз для массиве длины m и ь раз для массиве длины n). Затем, для все возможных позиций проверяется, является она равноесием по нэшу, как это описывалось в разделе выше.
+
Алгоритм в качестве подзадачи многократно использует поис максимума в массиве (<math> n </math> раз в массиве длины <math> m </math> и <math> m </math> раз в массиве длины <math> n </math>). Затем, для все возможных позиций проверяется, является она равноесием по нэшу, как это описывалось в разделе выше.
  
 
=== Схема реализации последовательного алгоритма ===
 
=== Схема реализации последовательного алгоритма ===
Строка 43: Строка 43:
 
const std::vector<std::vector<double> > &g)
 
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;
 
std::list<std::pair<int, int> > res;
  
Строка 48: Строка 50:
 
int m = g[0].size();
 
int m = g[0].size();
  
 +
//find best response for first player for each fixed second player's strategy
 
std::vector<double> maxf(m);
 
std::vector<double> maxf(m);
 
for (int i = 0; i < m; ++i) {
 
for (int i = 0; i < m; ++i) {
Строка 56: Строка 59:
 
}
 
}
  
 +
 +
//and best response for second player
 
std::vector<double> maxg(n);
 
std::vector<double> maxg(n);
 
for (int i = 0; i < n; ++i) {
 
for (int i = 0; i < n; ++i) {
Строка 65: Строка 70:
  
  
 +
// consinering best responses for both player check each position if it's nash equilibrium
 
for (int i = 0; i < n; ++i) {
 
for (int i = 0; i < n; ++i) {
 
for (int j = 0; j < m; ++j) {
 
for (int j = 0; j < m; ++j) {
Строка 75: Строка 81:
 
return res;
 
return res;
 
}
 
}
 +
  
  
Строка 81: Строка 88:
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
Сложность поиска максима во всех строках(стоблцах) в этих матрицах составит  <math> O(nm) </math>.
 
Сложность поиска максима во всех строках(стоблцах) в этих матрицах составит  <math> O(nm) </math>.
после этго проверка каждого элемента на равновесие имеет сложность O(1), а всех соответственно O(mn).
+
после этого проверка каждого элемента на равновесие имеет сложность <math> O(1) </math>, а всех соответственно <math> O(nm) </math>.
  
 
=== Информационный граф ===
 
=== Информационный граф ===
Строка 92: Строка 99:
 
Для нахождения максимума в каждой из <math> n </math> строк матрицы <math> F </math> понадобится <math> m - 1 </math> операция сравнения для вещественных чисел.
 
Для нахождения максимума в каждой из <math> n </math> строк матрицы <math> F </math> понадобится <math> m - 1 </math> операция сравнения для вещественных чисел.
 
Аналогично, для нахождения максимума в каждом из <math> m </math> столбцов матрицы <math> G </math> понадобится <math> n - 1 </math> операция сравнения для вещественных чисел.
 
Аналогично, для нахождения максимума в каждом из <math> m </math> столбцов матрицы <math> G </math> понадобится <math> n - 1 </math> операция сравнения для вещественных чисел.
 +
при неограниченном числе ресурсов, все строки  столбцы обрабатываются отдельно, поэтому сложность будет <math> max(m, n) </math>.
 
Далее, для определения каждой ситуации на равновесие нужно просто сравнить значение в <math> F </math> с максимумом в столбце и в <math> G </math> с максимумом в строке, т.е. для каждой ситуации это <math> O(1) </math>, а так как, для каждой ситуации это независимые действия, при неограниченном числе ресурсов все вычисления имеют сложность <math> O(1) </math>.
 
Далее, для определения каждой ситуации на равновесие нужно просто сравнить значение в <math> F </math> с максимумом в столбце и в <math> G </math> с максимумом в строке, т.е. для каждой ситуации это <math> O(1) </math>, а так как, для каждой ситуации это независимые действия, при неограниченном числе ресурсов все вычисления имеют сложность <math> O(1) </math>.
  
Строка 101: Строка 109:
 
'''Выходные данные:'''
 
'''Выходные данные:'''
 
список пар <math> (i, j) </math>, где <math> i \in [1 .. n], j \in [1 .. m] </math>
 
список пар <math> (i, j) </math>, где <math> i \in [1 .. n], j \in [1 .. m] </math>
 +
 +
=== Свойства алгоритма ===
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
 +
 +
=== Особенности реализации последовательного алгоритма ===
 +
 +
=== Локальность данных и вычислений ===
 +
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
  
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
Задача данного раздела - показать пределы [[глоссарий#Масштабируемость|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость|''сильной'']] и [[глоссарий#Слабая масштабируемость|''слабой'']] масштабируемости алгоритма и его реализаций.
+
на графике показана зависимость времени работы программы от размеров матриц (в тестах они задавались квадратными) и от числа процессоров.
 +
диапазоны:
 +
 
 +
'''число процессоров''': [1, 32]
 +
 
 +
'''сторона матриц''': числа от 100 до 24100 с шагом 1000
  
Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).
+
[[File:Plot.jpg|thumb|center|800px|Рис.1. график зависимости времени работы программы от числа процессоров и стороны матрицы]]
  
Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи . При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.
+
На графике видно, что в данных тестах процессы нагружаются оптимально, т.к. их увеличение приводит к сильному уменьшению времени. При данных параметрах можно считать, что время  обратно пропорцинально числу процессов.
  
На рис.5. показана масштабируемость классического алгоритма умножения плотных матриц в зависимости от числа процессоров и размера задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти.
+
=== Динамические характеристики и эффективность реализации алгоритма ===
  
[[File:Plot 3 (1).png|thumb|center|1200px|Рис.1. brr F]]
+
=== Выводы для классов архитектур ===
  
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===

Текущая версия на 17:19, 2 декабря 2017

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

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

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

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

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

Определим игру двух лиц. Пусть первый игрок имеет в своём распоряжении стратегии [math] x [/math] из множества стратегий [math] X [/math], а второй игрок стратегии [math] y [/math] из множества стратегий [math] Y [/math]. Будем рассматривать игру в нормальной форме. Это означает, что каждый из игроков выбирает стратегию, не зная выбора партнёра. Пару стратегий [math] (x, y) [/math] будем называть ситуацией. У первого игрока имеется функция выигрыша [math] F(x, y) [/math], а у второго [math] G(x, y) [/math], определённые на на множестве всех ситуаций [math] X × Y [/math]. каждый игрок стремится, по возможности, максимизировать свою функцию выигрыша. Таким образом, игра двух лиц в нормальной форме задаётся набором [math] \Gamma \langle X, Y, F(x, y), G(x, y) \rangle [/math]. Ситуация [math] (x^0, y^0) [/math] называется равновесием по Нэшу игры [math] \Gamma [/math] если: [math] \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]

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

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

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

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

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

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

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

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

#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;
}

1.6 Последовательная сложность алгоритма

Сложность поиска максима во всех строках(стоблцах) в этих матрицах составит [math] O(nm) [/math]. после этого проверка каждого элемента на равновесие имеет сложность [math] O(1) [/math], а всех соответственно [math] O(nm) [/math].

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

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


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

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

Для нахождения максимума в каждой из [math] n [/math] строк матрицы [math] F [/math] понадобится [math] m - 1 [/math] операция сравнения для вещественных чисел. Аналогично, для нахождения максимума в каждом из [math] m [/math] столбцов матрицы [math] G [/math] понадобится [math] n - 1 [/math] операция сравнения для вещественных чисел. при неограниченном числе ресурсов, все строки столбцы обрабатываются отдельно, поэтому сложность будет [math] max(m, n) [/math]. Далее, для определения каждой ситуации на равновесие нужно просто сравнить значение в [math] F [/math] с максимумом в столбце и в [math] G [/math] с максимумом в строке, т.е. для каждой ситуации это [math] O(1) [/math], а так как, для каждой ситуации это независимые действия, при неограниченном числе ресурсов все вычисления имеют сложность [math] O(1) [/math].

1.9 Входные и выходные данные алгоритма

Входные данные: две матрицы [math] R^{n × m} [/math]

Выходные данные: список пар [math] (i, j) [/math], где [math] i \in [1 .. n], j \in [1 .. m] [/math]

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

на графике показана зависимость времени работы программы от размеров матриц (в тестах они задавались квадратными) и от числа процессоров. диапазоны:

число процессоров: [1, 32]

сторона матриц: числа от 100 до 24100 с шагом 1000

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

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

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

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

}

3 Литература

  1. Васин А.А., Морозов В.В. "Введение в теорию игр с приложениями в экономике"(учебное пособие). - М.: 2003. - 278 с. Pages 91-92