Участник:Sveta

Общая схема описания алгоритмов имеет следующий вид:

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

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

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

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

Есть множество стратегий первого игрока [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] называется равновесием Штакельберга, если [math]\displaystyle{ y^* = R(x^*) }[/math] есть наилучший ответ подчиненного на стратегию лидера, которая находится как решение задачи [math]\displaystyle{ H(x^*, y^*) = max H(x,R(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], где каждая из пар является равновесием по Штакельбергу в нашей дуаполии.