Участник:Sveta
Основные авторы описания: Закирова С.В. Поиск равновесия в дуополии Штакельберга
Свойства и структура алгоритмов
Общее описание алгоритма
Модель дуополии Штакельберга является развитием модели дуополии Курно. Если в модели Курно считается, что участники рынка не прогнозируют отклика конкурента на собственные действия, то в модели Штакельберга один участник рынка не прогнозирует поведения конкурента, а второй учитывает поведение первого, зная, что конкурент не ответит на его действия. Другими словами, второй участник рынка знает, что первый участник рынка ведет себя в соответствии с моделью Курно. [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[])
{
int n = strtol(argv[1], NULL, 10);
int m = strtol(argv[2], NULL, 10);
vector<vector<double>> H(n, vector<double>(m));
vector<vector<double>> G(n, vector<double>(m));
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();
}
}
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] операций.
Информационный граф
Опишем граф алгоритма в виде рисунка.
Ресурс параллелизма алгоритма
Каждую строку можно обрабатывать отдельным процессором. Таким образом каждый процессор бежит по строке и ищет там максимум (с условием благосклонности к лидеру). После этого процессоры синхронизируются и мы ищем максимум из уже найденых значений, таким образом мы получаем наибольший выигрыш для лидера, после чего находим все равновесия по Штакельбергу.
Параллельная сложность: [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();
}