VIII Международная студенческая научная конференция Студенческий научный форум - 2016

Содержание

Введение 3

1. Теоретическая справка по методу Брауна-Робинсон 4

2. Пример использования разработанной программы, решение задачи недружественного поглощения двух компаний и анализ выходных данных 11

Заключение 18

Список литературы 19

Приложение 20

Введение

В наше время существует достаточно большое количество задач, решение которых в аналитическом виде или невозможно в принципе в элементарных функциях, либо связано с большим объёмом работы, что чревато большим временем расчётов и может быть критичным в современном динамичном мире. В такой ситуации остро встаёт вопрос поиска методов решения, используя которые мы можем находить компромисс между временем получения ответа и точностью вычислений. К таким методам в теории игр относится и метод Брауна-Робинсон – итерационный алгоритм поиска частных оптимальных стратегий игроков А и В.

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

В практической части мы реализуем метод Брауна-Робинсона в среде Matlab и решим две задачи – одну задачу разберём достаточно подробно, занеся процесс решения в специальную таблицу и проверив, являются ли полученные нами смешанные стратегии игроков оптимальными с заданной точностью. Вторую задачу мы наполним смысловым содержанием и постараемся взять платёжную матрицу достаточно большой размерности, чтобы провести анализ зависимости времени вычислений и количества итераций от заданной точности, сделаем вывод о сходимости и применимости данного метода при решении реальных задач.

1. Теоретическая справка по методу Брауна-Робинсон

Зачастую на практике при решении задач на антагонистические игры мы сталкиваемся с платёжными матрицами достаточно большого размера, которые невозможно решить ни графическим методом, ни методом Шепли-Сноу по причине большой трудоёмкости. В таком случае имеет смысл использовать метод Брауна-Робинсона, который также называют методом фиктивного разыгрывания или итеративным процессом поиска частного решения в смешанных стратегиях. Данный метод является приблизительным и способен дать решение игры для обоих игроков с определенной степенью точности – той, которую мы заранее зададим. Таким образом, мы можем сами искать баланс между скоростью вычислений и необходимой точностью. Разберём этот метод более подробно.

Предположим, что одна и та же антагонистическая ситуация повторяется многократно и каждый из игроков обладает информацией о предыдущем поведении соперника. Тогда каждый из игроков будет выбирать свою следующую стратегию, опираясь на информацию о смешанной стратегии оппонента, которая вытекает из предыдущих реализаций ситуаций. Таким образом мы получили итеративный процесс выбора стратегий для каждого игрока. Чтобы лучше понять, почему решение, полученное данным методом, будет оптимальным, рассмотрим сначала алгоритм реализаци данного метода. Для данного итерационного метода принципиальное отличие от остальных шагов имеет первый шаг, поэтому мы рассмотрим первые 2 шага и общий k+1 шаг. Для определённости, будем считать, что игрок А первым выбирает стратегию, однако игрок B не знает в рамках одной ситуации, какую стратегию выбрал игрок А.

Шаг 1:

На первом шаге ни один из игроков не знает стратегии другого и выбирает стратегию на основе своих предпочтений, например, для игрока А это может быть максимизация своего среднего выигрыша, а для игрока B – минимизация среднего проигрыша. Таким образом, игрок А выбрал свою чистую стратегию , а игрок B выбрал стратегию .

Шаг 2:

На втором шаге игрок А уже знает, какую стратегию игрок B выбрал на первом шаге и исходит из предположения, что он будет использовать ту же стратегию, что была на предыдущем шаге. Именно поэтому все шаги после первого не отличаются друг от друга – каждый из игроков считает, что его оппонент будет придерживаться той же стратегии, что и на предыдущем шаге, и что на текущем шаге необходимо выбрать такую чистую стратегию, которая бы максимизировала выигрыш (для игрока А) или минимизировала проигрыш (для игрока В) при стратегии оппонента из предыдущего шага. В наших терминах это можно записать следующим образом:

Где – номер чистой стратегии, которую игрок А выбрал на втором шаге. Очевидно, что на втором шаге стратегия каждого из игроков на предыдущем шаге – чистая. Запишем чистую стратегию игрока В на первом шаге в виде смешанной :

Тогда:

– показатель неэффективности стратегии .

Аналогично для игрока B: его стратегия на втором шаге должна минимизировать его потери при стратегии игрока А:

Запишем чистую стратегию игрока А на первом шаге в виде смешанной :

Тогда:

– показатель эффективности стратегии .

K+1 шаг:

Обобщим процедуру выбора стратегии на k+1 шаге и разобъем её на 2 этапа:

1. Выбор такой чистой стратегии каждым из игроков, которая бы максимизировала (для игрока А) или минимизировала (для игрока B) значение функции выигрыша при смешанной стратегии оппонента на k-ом шаге (Q(k) для игрока А и P(k) для игрока В).

Для игрока А это выглядит следующим образом:

Следовательно, на k+1 шаге игрок А выберет чистую стратегию.

Заметим, что – показатель неэффективности стратегии Q(k).

Для игрока В:

Следовательно, на k+1 шаге игрок А выберет чистую стратегию.

Заметим, что – показатель эффективности стратегии P(k).

1. Необходимо определить смешанную стратегию оппонента, изменившуюся в связи с реализацией ситуации на k-ом шаге. Пусть – количество появлений i-ой стратегии на k-ом шаге процесса, а – частота появления i-ой стратегии на k-ом шаге процесса (считаем, что частота эквивалентна вероятности появления i-ого события). Тогда для k+1 значения имеем:

При :

При :

Аналогично пересчитаем частоты для игрока В:

По мнению автора данного творческого задания, в силу того что метод Брауна-Робинсона почти не используется при «ручном» счёте из-за не очень быстрой сходимости (в связи с чем достичь необходимой точности при «ручном» счёте будет достаточно затруднительно) и сравнительной легкости в реализации на ЭВМ, альтернативой указанным выше формулам может быть прямой подсчёт количества раз, которое была выбрана та или иная стратегия, с последующим делением каждого такого значения на k – количества реализованных ситуаций.

1. Для k+1 итерации необходимо рассчитать показатель эффективности (для игрока А – ) или показатель неэффективности (для игрока В – ) полученной на k+1 шаге процесса. Очевидно, что при

А общая формула для k+1 шага:

Как будет показано ниже, условием остановки данного алгоритма для достижения точности ε необходимо, чтобы выполнялось неравенство:

(*)

Если данное условие не выполняется, необходимо вернуться к 1. и сделать ещё одну итерацию.

Таким образом, мы видим, что данный алгоритм достаточно прост как в понимании, так и в реализации на ЭВМ.

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

(1)

Таким образом, если при некотором будет справедливо, тогда, согласно написанному выше двойному неравенству, V будет ценой игры, а стратегии P(k) и Q(k) будут оптимальными. Таким образом, мы найдем частное решение заданной игры.

С помощью описанного алгоритма мы можем получить две бесконечные последовательности чистых стратегий и , выбранных игроками на основе предположительных смешанных стратегиях и , удовлетворяющих неравенству (1).

Последовательности чистых стратегий, смешанные стратегии которых удовлетворяют условию

(2)

называются разрешающими.

Если последовательность чистых стратегий – разрешающая, то отсюда не следует, что соответствующие им смешанные стратегии сходятся. Однако, если они сходятся:

,

то стратегии удовлетворяют равенству (2), следовательно, являются оптимальными стратегиями игроков. Таким образом, описанный процесс будет иметь место только при выполнении (2). Утверждение о том, что полученные с помощью описанного алгоритма последовательности чистых стратегий и являются разрешающими, было доказано американским математиком Джулией Робинсон, благодаря чему и была доказана сходимость алгоритма, который мы знаем как алгоритм Брауна-Робинсон.

Последнее, что будет доказано в теоретической части данной работы, – утверждение, что при выполнении (*), мы получим решение с ценой игры, отличающейся от истинной не больше чем на :

Так как и , можно записать, что

– неравенство будет верным (3)

Так как и , можно записать, что

– неравенство будет верным (4)

Тогда в силу того что и :

(5)

(6)

Введём величину , которая стремится к 0 при , в силу того что невозрастаетс ростом k, а неубывает с ростом k.

Если мы поставим условие на (**), то из (5) будет следовать справедливость (3), а из (6) – справедливость (4) при . Теперь умножим (3) на (-1) и сложим с (4):

Итак, мы получили, что некотором k-ом шаге выполняется неравенство (**), из которого следует, что величина будет отличаться от цены игры V не больше чем на .

1. Пример использования разработанной программы, решение задачи недружественного поглощения двух компаний и анализ выходных данных

В данном разделе домашнего творческого задания мы рассмотрим решение двух задач с помощью алгоритма Брауна-Робинсон, реализованного в среде Matlab. Код данного алгоритма, реализованного в виде функции, приведен в Приложении. Её входными параметрами являются платежная матрица С и заданная точность ε .

Задача 1.

С =

ε = 0.0001

Приведем решение данной задачи в виде следующей таблицы:

№ шага k	Чистая стратегия игрока А на k-ом шаге	Чистая стратегия игрока B на k-ом шаге	Смешанная стратегия P(k), которая, по предположению игрока B, будет выбрана игроком B на k+1 шаге	Смешанная стратегия Q(k), которая, по предположению игрока А, будет выбрана игроком B на k+1 шаге	α(P(k))	β(Q(k))	α(k)	β(k)	β(k)- α(k)	ε
1	1	2	(1;0;0)	(0;1;0;0)	2,00	3,00	2,00	3,00	1,00	> 2ε
2	1	1	(1;0;0)	(0,5;0,5;0;0)	2,00	2,50	2,00	2,50	0,50	> 2ε
3	1	1	(1;0;0)	(0,6667;0,3333;0;0)	2,00	3,00	2,00	2,50	0,50	> 2ε
4	3	1	(0,75;0;0,25)	(0,75;0,25;0;0)	2,25	3,25	2,25	2,50	0,25	> 2ε
5	3	3	(0,6;0;0,4)	(0,6;0,2;0,2;0)	2,20	3,20	2,25	2,50	0,25	> 2ε
6	3	2	(0,5;0;0,5)	(0,5;0,3333;0,1667;0)	2,00	2,83	2,25	2,50	0,25	> 2ε
7	3	2	(0,4286;0;0,5714)	(0,4286;0,4286;0,1429;0)	1,86	2,71	2,25	2,50	0,25	> 2ε
8	2	2	(0,375;0,125;0,5)	(0,375;0,5;0,125;0)	1,88	2,63	2,25	2,50	0,25	> 2ε
9	2	2	(0,3333;0,2222;0,4444)	(0,3333;0,5556;0,1111;0)	1,89	2,56	2,25	2,50	0,25	> 2ε
10	1	2	(0,4;0,2;0,4)	(0,3;0,6;0,1;0)	2,00	2,60	2,25	2,50	0,25	> 2ε
11	1	2	(0,4545;0,1818;0,3636)	(0,2727;0,6364;0,0909;0)	2,09	2,64	2,25	2,50	0,25	> 2ε
12	1	2	(0,5;0,1667;0,3333)	(0,25;0,6667;0,0833;0)	2,17	2,67	2,25	2,50	0,25	> 2ε
13	1	2	(0,5385;0,1538;0,3077)	(0,2308;0,6923;0,0769;0)	2,23	2,69	2,25	2,50	0,25	> 2ε
14	1	2	(0,5714;0,1429;0,2857)	(0,2143;0,7143;0,0714;0)	2,29	2,71	2,29	2,50	0,21	> 2ε
15	1	2	(0,6;0,1333;0,2667)	(0,2;0,7333;0,0667;0)	2,33	2,73	2,33	2,50	0,17	> 2ε
16	1	2	(0,625;0,125;0,25)	(0,1875;0,75;0,0625;0)	2,38	2,75	2,38	2,50	0,13	> 2ε
17	1	2	(0,6471;0,1176;0,2353)	(0,1765;0,7647;0,0588;0)	2,41	2,76	2,41	2,50	0,09	> 2ε
18	1	2	(0,6667;0,1111;0,2222)	(0,1667;0,7778;0,0556;0)	2,44	2,78	2,44	2,50	0,06	> 2ε
19	1	2	(0,6842;0,1053;0,2105)	(0,1579;0,7895;0,0526;0)	2,42	2,79	2,44	2,50	0,06	> 2ε
20	1	3	(0,7;0,1;0,2)	(0,15;0,75;0,1;0)	2,40	2,75	2,44	2,50	0,06	> 2ε
21	1	3	(0,7143;0,0952;0,1905)	(0,1429;0,7143;0,1429;0)	2,38	2,71	2,44	2,50	0,06	> 2ε
22	1	3	(0,7273;0,0909;0,1818)	(0,1364;0,6818;0,1818;0)	2,36	2,68	2,44	2,50	0,06	> 2ε
23	1	3	(0,7391;0,087;0,1739)	(0,1304;0,6522;0,2174;0)	2,35	2,65	2,44	2,50	0,06	> 2ε
24	1	3	(0,75;0,0833;0,1667)	(0,125;0,625;0,25;0)	2,33	2,63	2,44	2,50	0,06	> 2ε
25	1	3	(0,76;0,08;0,16)	(0,12;0,6;0,28;0)	2,32	2,68	2,44	2,50	0,06	> 2ε
26	2	3	(0,7308;0,1154;0,1538)	(0,1154;0,5769;0,3077;0)	2,38	2,73	2,44	2,50	0,06	> 2ε
27	2	3	(0,7037;0,1481;0,1481)	(0,1111;0,5556;0,3333;0)	2,44	2,78	2,44	2,50	0,06	> 2ε
28	2	1	(0,6786;0,1786;0,1429)	(0,1429;0,5357;0,3214;0)	2,46	2,79	2,46	2,50	0,04	> 2ε
29	2	1	(0,6552;0,2069;0,1379)	(0,1724;0,5172;0,3103;0)	2,48	2,79	2,48	2,50	0,02	> 2ε
30	2	1	(0,6333;0,2334;0,1333)	(0,2;0,5;0,3;0)	2,50	2,80	2,50	2,50	0,00	> 2ε

Итак, из таблицы мы можем сделать вывод, что цена игры равна 2,5. Стоит отметить, что , а значит мы нашли точное решение игры в смешанных стратегиях для обоих игроков. Оптимальные стратегии игроков А и В соответственно равны:

Проверим, является ли найденные стратегии оптимальными:

Таким образом, полученное нами решение – оптимальное. Отметим, что для решения этой задачи с помощью ЭВМ потребовалось около секунды, тогда как ручной обсчёт 30 таких итераций занял бы гораздо большее время.

Ответ:

Задача 2.

Предположим, что мы выступаем в роли компании А, которой грозит недружественное поглощение со стороны компании В и которая имеет на рынке 10 собственных различных финансовых инструментов (обыкновенных акций, привилегированных, облигаций т.д.). Тогда цель игрока А – максимизировать стоимость своей фирмы путем выкупа собственных финансовых инструментов на рынке для поддержания их стоимости, тогда как игрок В стремиться снизить рыночную стоимость ценных бумаг компании А одним из 4-ти способов:

1. Публичный негативный финансовый анализ компании А;

2. Публичное осуждение неэффективности менеджмента компании А;

3. Публичное судебное дело против компании А;

4. Сговор с сотрудником компании А с целью её дискредитировать.

Каждый из этих способов влияет на стоимость ценных бумаг, однако с каждым из них связан риск разоблачения действий компании В, на что рынок ответит ростом стоимости (по сравнению с готовящимся падением) ценных бумаг компании А и падением стоимости В. Будем считать, что эксперты определили агрегированные коэффициенты, показывающие влияние всех вышеперечисленных факторов на стоимость ценных бумаг компании А и записали их в виде матрицы 10х4:

Примем ε = 0.00005

Решение данной задачи:

Для нахождения решения с заданной точностью необходимо было сделать 1109590 итераций. В следующей таблице представлено время поиска решения и количество итераций для нескольких ε от 0.00005 до 0.1:

ε	Время выполнения, сек.	Количество итераций
0,1	1,319	859
0,05	1,337	1301
0,01	1,561	4045
0,005	1,710	8302
0,001	3,585	52700
0,0005	6,274	119964
0,0004	6,478	119967
0,0003	8,758	175052
0,0002	19,346	440130
0,0001	26,535	627703
0,00005	45,183	1109590

Как мы видим, зависимость очень напоминает график функции вида (на самом деле, согласно [1], ), – что позволяет высказать нам предположение о крайне плохой сходимости данного метода для малых ε, однако справедливости ради стоит отметить, что время, за которое была достигнута необходимая точность, для нашего примера (достаточно большого) можно считать приемлемым.

Исходя из этого графика мы также делаем вывод, что количество итераций зависит от ε близким к указанному выше соотношению образом. Именно второй график позволяет нам окончательно заключить, что мы имеем дело со степенной функцией описанного вида, так как рост времени в зависимости от ε можно было списать на неэффективно реализованный алгоритм или на необходимость хранить почти все предыдущие данные итераций.

Заключение

В данном домашнем творческом задании был рассмотрен алгоритм Брауна-Робинсон – приближённый алгоритм для итеративного нахождения частных оптимальных смешанных стратегий игроков при заданной платёжной матрице и необходимой точности. Мы рассмотрели вопрос сходимости данного метода и доказали условие остановки алгоритма для достижения необходимой точности.

В практической части работы мы решили две задачи с помощью программы, реализованной в среде Matlab, – одну достаточно тривиальную и наглядную, но которую невозможно решить графическим методом, а вторую с финансовой постановкой задачи и достаточно большой размерности – 10х4.

Мы получили достаточно хорошие результаты с точки зрения соотношения точности и времени работы, что, с учётом простоты данного метода и достаточной лёгкости его реализации на ЭВМ, позволяет нам сделать вывод о крайней эффективности использования данного метода при решении задач в том числе и достаточно больших размерностей.

Список литературы

1. Лабскер Л.Г., Бабешко Л.О. Игровые методы в управлении экономикой и бизнесом. Учебное пособие.-М.:ДЕЛО.2001.- 464 с.

2. Лабскер Л.Г., Ященко Н.А. Теория игр в экономике. Практикум с решениями задач.Под редакцией Л.Г.Лабскера.-М.:КНОРУС.2014. - 264 с.

Приложение

Код, реализующий алгоритм Брауна-Робинсон в среде Matlab:

function [ QQQ PPP V k Table] = BraunRobinson(C,epsilon )

k=2;

n = 20000000;

aSize = size(C,1);

bSize = size(C,2);

AlfaGeneral = zeros(1,n);

BetaGeneral = zeros(1,n);

StrAN = zeros(1,n);

StrBN = zeros(1,n);

StrA = zeros(1,aSize);

StrB = zeros(1,bSize);

i = zeros(1,n);

j = zeros(1,n);

tech2 = sum(C,2);

tech3 = sum(C,1);

[tech2, i(1)] = max(tech2);

[tech3, j(1)] = max(tech3);

StrAN(1,1) = i(1);

StrBN(1,1) = j(1);

AlfaGeneral(1) = min(C(i(1),:));

BetaGeneral(1) = max(C(:,j(1)));

AlfaMax = AlfaGeneral(1);

AlfaInd = 1;

BetaMin = BetaGeneral(1);

BetaInd = 1;

StrA(i(1)) = StrA(i(1)) + 1;

StrB(j(1)) = StrB(j(1)) + 1;

Parr = zeros(n,aSize);

Qarr = zeros(n,bSize);

P = zeros(1,aSize);

Q = zeros(1,bSize);

P = StrA./sum(StrA);

Q = StrB./sum(StrB);

Parr(1,:) = P(1,:);

Qarr(1,:) = Q(1,:);

for k=2:n

[y, i(k)] = max(C*(Q'));

[y, j(k)] = min(P*C);

StrA(1,i(k)) = StrA(1,i(k)) + 1;

StrB(1,j(k)) = StrB(1,j(k)) + 1;

StrAN(1,k) = i(k);

StrBN(1,k) = j(k);

P = StrA./sum(StrA);

Q = StrB./sum(StrB);

AlfaGeneral(k) = min(P*C);

BetaGeneral(k) = max(C*(Q'));

if (AlfaGeneral(k)>AlfaMax)

AlfaMax = AlfaGeneral(k);

AlfaInd = k;

end

if (BetaGeneral(k)

Код для цитирования: Скопировать