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

Текущая версия от 21:44, 5 декабря 2017

Основные авторы описания: Закирова С.В. Поиск равновесия в дуополии Штакельберга

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

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

Модель дуополии Штакельберга является развитием модели дуополии Курно. Если в модели Курно считается, что участники рынка не прогнозируют отклика конкурента на собственные действия, то в модели Штакельберга один участник рынка не прогнозирует поведения конкурента, а второй учитывает поведение первого, зная, что конкурент не ответит на его действия. Другими словами, второй участник рынка знает, что первый участник рынка ведет себя в соответствии с моделью Курно. ^[1]

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

Есть множество стратегий первого игрока [math]\displaystyle{ X }[/math] и множество стратегий [math]\displaystyle{ Y }[/math] второго игрока. Первым ходит игрок, называемый лидером, его стратегия [math]\displaystyle{ x \in X }[/math]. Второй игрок, называемый подчиненным, ходит стратегией [math]\displaystyle{ y \in Y }[/math]. У каждого игрока есть своя функция выигрыша. Для лидера это функция [math]\displaystyle{ H(x,y) }[/math]. Для подчиненного [math]\displaystyle{ G(x,y) }[/math]. Оба хотят максимизировать свой выигрыш, при условии лояльности(лояльность, это когда при условии одинакового выигрыша для второго, он максимизирует выигрыш первого) второго игрока по отношении к первому. Набор стратегий [math]\displaystyle{ (x^*,y^*) }[/math] называется равновесием Штакельберга^[2], если [math]\displaystyle{ y^* = R(x^*) }[/math] есть наилучший ответ подчиненного на стратегию лидера, которая находится как решение задачи [math]\displaystyle{ H(x^*, y^*) = max H(x,R(x)) }[/math] (максимум берется по всем стратегиям [math]\displaystyle{ x }[/math] из [math]\displaystyle{ X }[/math])

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

Вычислительным ядром данного алгоритма является поиск максимума в строке. Таким образом мы находим наилучший ответ второго игрока.

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

Как уже сказано в пункте выше, основнуая составляющая часть алгоритма это поиск максимума в строке.

Алгоритм можно представить как многократное повторение(по количеству строк) поиска максимума в строках первой матрицы. После этого поиск максимума по элементам второй матрицы, индексы которых уже были найдены в первой итерации.

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

#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;



int main(int argc, char *argv[])
{
        //считиываем m и n
	int n = strtol(argv[1], NULL, 10);
	int m = strtol(argv[2], NULL, 10);

        //создаем матрицы G и H
	vector<vector<double>> H(n, vector<double>(m));
	vector<vector<double>> G(n, vector<double>(m));

        //инициализируем матрицы G и H
	srand(time(NULL));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			H[i][j] = rand();
			G[i][j] = rand();
		}
	}

        //ищем максимум в G благожелательно к лидеру на каждую его стратегию
	vector<int> ind(n);
	for(int i = 0; i < n; ++i){
		double max_in_line = H[i][0];
		int ind_max = 0;
		for(int j = 0; j < m; ++j){
			if (G[i][j] > max_in_line) {
				max_in_line = G[i][j];
				ind_max = j;
			} else if (G[i][j] == max_in_line) {
				if (H[i][j] > H[i][ind_max]) {
					ind_max = j;
					max_in_line = G[i][j];
				} 
			}
		}
		ind[i] = ind_max;
	}

        //ищем с учетом ответа второго наилучшую тратегию для лидера
	int str_h = 0;
	for(int i = 0; i < n; ++i) {
		if (H[i][ind[i]] > H[str_h][ind[str_h]]) {
			str_h = i;
		} 
	}


}

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

Для первой части - поиска наилучших стратегий для воторого потребуется [math]\displaystyle{ m * n }[/math] операций сравенения.

Для второй части - поиска наилучших стратегий первого потребуется [math]\displaystyle{ n }[/math] операций сравнения.

Таким образом результирующая сложность алгоритма - [math]\displaystyle{ О(n * m) }[/math] операций.

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

Опишем граф алгоритма в виде рисунка.

Круглые элеменеты графа - элементы матрицы G. Под max, имеется в виду функция поиска максимума в строке (причем с уметом благожелательности).

max2 - опять же функция поиска максимума для первого, исходя из ответов второго.

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

Каждую строку можно обрабатывать отдельным процессором. Таким образом каждый процессор бежит по строке и ищет там максимум (с условием благосклонности к лидеру). После этого процессоры синхронизируются и мы ищем максимум из уже найденых значений, таким образом мы получаем наибольший выигрыш для лидера, после чего находим все равновесия по Штакельбергу.

Параллельная сложность: [math]\displaystyle{ О(m) }[/math], где [math]\displaystyle{ m }[/math] число столбцов а нашей матрице.

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

Входными данными являются пара матриц [math]\displaystyle{ H(x,y) }[/math], [math]\displaystyle{ G(x,y) }[/math] одинакового размера [math]\displaystyle{ n * m }[/math] (стратегии обоих игроков). Выходные данные это множество пар чисел [math]\displaystyle{ (x^*,y^*) }[/math], где каждая из пар является равновесием по Штакельбергу в нашей дуаполии.

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

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

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

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

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

Проведём исследование масштабируемости параллельной реализации алгоритма. Набор и границы значений изменяемых параметров запуска реализации алгоритма:

число процессоров [1,2 4, 8 : 32] со значениями квадрата целого числа;

размер матрицы(для тестов бралась квадратная матрица) [1000:10000] с шагом 1000.

На следующем рисунке приведен график производительности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

сведения о программно-аппаратной среде

компьютер: суперкомпьютор Ломоносов

компилятор с использованными опциями оптимизации: mpicxx версии openmpi/1.8.4-gcc

библиотеки: #include <mpi.h>, #include <iostream>, #include <cstdlib>, #include <ctime>, #include <vector>

выводы о масштабируемости

Мы получили ожидаемые результаты(в целом), что производительность увеличивается с увеличеснием количества процессоров и уменьшается с увеличеннием количества строк. Это можно объяснить тем, что выбранный алгоритм очень хорошо распараллеливается, а «общение» процессоров почти не требуется (это важно так как эта процедура достаточно ресурсозатратна).

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

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

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

Написанная мной, текущая реализация алгоритма:

#include <mpi.h>
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

using namespace std;



int main(int argc, char * argv[])
{

	int comm_sz, my_rank;
	MPI_Init(&argc, &argv);
	MPI_Comm comm = MPI_COMM_WORLD;
	MPI_Comm_size(comm, &comm_sz);
	MPI_Comm_rank(comm, &my_rank);

	//считываем размеры матрицы
	int n,m;
	if (my_rank == 0) {
		n = strtol(argv[1], NULL, 10);
		m = strtol(argv[2], NULL, 10);
	}

	MPI_Bcast(&m, 1, MPI_INT, 0, comm);
	MPI_Bcast(&n, 1, MPI_INT, 0, comm);

	//делим матрицу
	int local_n = n / comm_sz;
	int rem = n % comm_sz;
	if(my_rank < rem) {
		local_n++;
	}

	vector<vector<double> > G(local_n, vector<double> (m, -5)) , H(local_n, vector<double> (m, -5));

	//генирируем мартицу
	srand(time(NULL));
	for(int i = 0; i < local_n; ++i) {
		for(int j = 0; j < m; ++j) {
			H[i][j] = rand();
			G[i][j] = rand();
		}
	}

	double s_time = 0;
	if (rank == 0) {
		s_time = MPI_Wtime();
	}

	//ищем максимум в G благожелательно к лидеру на каждую его стратегию
	vector<int> local_ind(local_n);
	vector<double> local_max(local_n);
	for(int i = 0; i < local_n; ++i){
		double max_in_line = G[i][0];
		int ind_max = 0;
		for(int j = 0; j < m; ++j){
			if (G[i][j] > max_in_line) {
				max_in_line = G[i][j];
				ind_max = j;
			} else if (G[i][j] == max_in_line) {
				if (H[i][j] > H[i][ind_max]) {
					ind_max = j;
					max_in_line = G[i][j];
				} 
			}
		}
		local_ind[i] = ind_max;
		local_max[i] = H[i][ind_max];
	}

	//ищем с учетом ответа второго наилучшую тратегию для лидера
	double max_in_proc = local_max[0];
	for (int i = 0; i < local_n; ++i) {
		if(max_in_proc < local_max[i]) {
			max_in_proc = local_max[i];
		}
	}

	double res_max;
	
	MPI_Allreduce(&max_in_proc, &res_max, 1, MPI_DOUBLE, MPI_MAX, comm);

	//ищем все равновесия по Штакельбергу
	for (int i = 0; i < local_n; ++i) {
		if(res_max == local_max[i]) {
			//i, max_ind[i] равновесие по Штакельбергу
		}
	}

	//выводим время
	double f_time = 0;
	if (rank == 0) {
		f_time = MPI_Wtime();
		cout << n << ' ' << f_time - s_time << endl;
	}





	MPI_Finalize();

}

Литература

↑ Шагин, В. Л. Теория игр с экономическими приложениями. Учебное пособие. — М., ГУ-ВШЭ, 2003.
↑ Васин А.А., Морозов В.В. "Введение в теорию игр с приложениями в экономике"(учебное пособие). - М.: 2003. - 278 с. Pages 131-132

[1] Шагин, В. Л. Теория игр с экономическими приложениями. Учебное пособие. — М., ГУ-ВШЭ, 2003.

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

[1]

[2]