Элементы теории игр (стр. 1 )

Элементы теории игр.

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

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

Любой партнер стремиться принимать оптимальное решение и при этом сталкивается не только со своими целями., но и с целями партнера, и зависит от решений, которые будет принимать партнер.

Методы для решения задач с конфликтной ситуацией разработаны в математической теории, которая называется теорией игр.

Основные понятия теории игр:

Игра - математическая модель конфликтной ситуации.

Игроки - стороны, участвующие в конфликте.

Выигрыш - исход конфликта.

Для любой формализованной игры вводятся правила, которые определяют:

1.  варианты действия игроков;

2.  объем информации каждого игрока о поведении партнера;

3.  выигрыш, к которому приводит каждая совокупность действий.

Как правило выигрыш или проигрыш может быть задан количественно.

Например выигрыш - 1;

проигрыш - 0;

ничья - 1/2.

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

Мы будем рассматривать парные игры.

Пусть имеются 2 игрока: А и В. Их интересы противоположны. Игра - это ряд действий игроков А и В.

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

а - выигрыш игрока А;

в - выигрыш игрока В, тогда

а=-в.

В этом случае достаточно рассматривать только а.

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

Личный ход - это сознательный выбор игроком одного из возможных действий (например, ход в шахматах).

Случайный ход - случайно выбранное действие (например, выбор карты из колоды).

Стратегия игрока - это совокупность правил, определяющих выбор игрока при любом личном ходе, в зависимости от ситуации.

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

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

Решение игры - это выбор каждым игроком стратегии, которая удовлетворяет условию оптимальности, те есть один игрок должен получить максимальный выигрыш, когда другой игрок придерживается своей стратегии. в то же время другой игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными.

Условие устойчивости: каждому из игроков должно быть не выгодно отказаться от своей стратегии. Оптимальная стратегия должна удовлетворять условию устойчивости.

Если игра повторяется много раз, то игроков интересует выигрыш или проигрыш в среднем.

Целью теории игр является определение максимальной стратегии каждого игрока.

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

Платежная матрица. Верхняя и нижняя цена игры.

Рассмотрим парную конечную игру:

Игрок А имеет m стратегий A1, A2,…,Am.

Игрок В имеет n стратегий B1, B2,…,Bn.

Размерность игры m´n.

В результате выбора игроками любой пары стратегий Ai и Bj (i=1,2,…m; j=1,2,…n) однозначно определяется исход игры, то есть выигрыш игрока А aij и проигрыш игрока В - aij.

Матрица P=(aij) (i=1,2,…m; j=1,2,…n), элементами которой являются выигрыши, соответствующие стратегиям Ai и Bj, называется платежной матрицей или матрицей игры. Общий вид матрицы:

Таблица 1

	B1	B2	…	Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

Строки этой таблицы соответствуют стратегиям игрока А, столбцы - стратегиям игрока В.

Пример 17. Игра "Поиск"

Игрок А может спрятаться в одном из убежишь I или II. Игрок В ищет игрока А. Если найдет, то получает от А штраф $1, если не найдет, то платит игроку А $1.

Стратегии игрока А:

А1 - игрок А прячется в убежище I;

А2 - игрок А прячется в убежище II.

Стратегии игрока В:

В1 - игрок В ищет в убежище I;

В2 - игрок В ищет в убежище II.

Если игрок А в убежище I и В его обнаружил (стратегия A1B1), то платит штраф $1 (а11=-1). Аналогично для стратегии A2B2 а22=-1.

Если А в убежище I, а В его не обнаружил (стратегия A1B2), то игрок А получает $1 (а12=1). Аналогично для стратегии A2B1 а21=1.

Размерность игры 2´2.

Платежная матрица игра, матрица размером 2´2:

-1	1
1	-1

Рассмотрим игру m´n с матрицей Р=(аij) размером m´n.

Определим наилучшую стратегию игрока А среди стратегий A1, A2,…,Am.

Выбирая стратегию Аi, игрок А рассчитывает, что В выберет стратегию Вj, для которой выигрыш А минимален (игрок В вредит А).

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

- минимальное число в i-ой строке платежной матрицы.

Среди всех возможных выберем максимальное:

- нижняя цена игры (максимин) - максимальный гарантированный выигрыш игрока А.

Стратегия, соответствующая максимину называется максиминной стратегией.

Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А. Выбирая стратегию Вj, игрок В максимально возможный при этом выигрыш игрока А. Обозначим - самый большой элемент в столбце j. Тогда

- верхняя цена игры (минимакс) - минимальный гарантированный выигрыш игрока В.

Стратегия, соответствующая минимаксу называется минимаксной стратегией.

Принцип, диктующий игрокам выбор "осторожных" минимаксных или максиминных стратегий называется принципом минимакса.

Найдем верхнюю и нижнюю цену игры "Поиск".

Следовательно, игрок А может выбирать любую стратегию А1 или А2, они обе масиминны. Нижняя цена игры равна -1.

Любая стратегия игрока В минимаксна и верхняя цена игры равна 1.

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

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

Пара чистых стратегий Ai Bj дает оптимальное решение игры тогда и только тогда, когда aij - максимум в своем столбце и минимум в своей строке. Такая ситуация, если она существует, называется седловой точкой.

Пусть А* В* - пара чистых стратегий при которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша игрока. P(Ai, Bj)=aij. Тогда, из условия оптимальности в седловой точке выполняется неравенство P(Ai, B*)£ P(A*,B*)£ P(A*,Bj), которое справедливо для всех i=1,2,…m; j=1,2,…n.

Пример.

Найти верхнюю и нижнюю цену игры.

0,5	0,6	0,8
0,9	0,7	0,8
0,7	0,6	0,6

Имеет ли игра седловую точку?

Решение:

Найдем минимумы по строкам и максимумы по столбцам. Среди минимумов найдем максимум max(0,5;0,7;0,6)=0,7 Минимксная стратегия А2. Среди максимумов найдем минимум min(0,9;0,7;0,8)=0,7 Максиминная стратегия В2.

	В1	В2	В3
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,6	0,6	0,6
	0,9	0,7	0,8

Таким образом , следовательно игра имеет седловую точку а22, соответствующую стратегии А2В2 (решение игры) и чистая цена игры .

Задания.

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

1.

0,3	0,6	0,8
0,9	0,4	0,2
0,7	0,5	0,4

2.

4	5	3
6	7	4
5	2	3

3.

8	9	9	4
6	5	8	7
3	4	5	6

4.

2	5	3
6	4	5
3	7	8
2	3	4

5.

4	9	5	3
7	8	6	9
7	4	2	6
8	3	4	7

6.

4	5	6	7	9
3	4	6	5	6
7	6	10	8	11
8	5	4	7	3

Решение игр в смешанных стратегиях.

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

Смешанной стратегией SA игрока А называется применение чистых стратегий А1, А2,…,Аi,…Аm с вероятностями p1, p2,…,pi,…pm, причем сумма вероятностей равна 1: . Смешанные стратегии игрока записываются в виде матрицы:

,

или в виде строки . Аналогично свешанные стратегии игрока В обозначаются:

или , где сумма вероятностей появления стратегий игрока В равна 1: .

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

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

,

где - нижняя цена игры; - верхняя.

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

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

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

Пусть задана платежная матрица игры:

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

, а игрок В чистую стратегию (соответствует первому столбцу платежной матрицы Р), равен цене игры :

.

Тот же средний выигрыш получит игрок А, если игрок В выберет стратегию , то есть: . Учитывая, что , получим систему уравнений для определения оптимальной стратегии и цены игра :

Решая эту систему получим оптимальную стратегию и цену игры:

Применяя теорему об активных стратегиях - оптимальной стратегии игрока В, получаем, что при любой чистой стратегии игрока А ( или ) средней проигрыш игрока В равен цене игры :

Решая эту систему получим оптимальную стратегию и цену игры:

Пример 18:

Игра "Поиск" задана платежной матрицей без седловой точки:

Ищем решение в смешанных стратегиях; для игрока А средней выигрыш равен цене игры , для игрока В средний проигрыш равен цене игры. Системы уравнений имеет вид:

Решая эти системы получаем

Это означает, что оптимальная стратегия каждого игрока состоит в том, чтобы чередовать свои чистые стратегии случайным образом, выбирая каждое из убежищ с вероятностью 1/2, при этом средней выигрыш равен 0.

Задания:

Найти смешанные стратегии игроков и цену игры:

1.

-2	2
1	-1

2.

2	3
1	2

3.

4	-2
1	3

Нелинейное программирование.

Классическое определение экстремума.

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

В общем виде задача нелинейного программирования имеет вид:

,

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

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

·  среди ограничений нет неравенств;

·  необязательны условия отрицательности переменных;

·  нет дискретных переменных;

·  m<n (число ограничений меньше числа неизвестных);

·  непрерывны и имеет частные производные II порядка.

Задача нелинейного или математического программирования ставится следующим образом: найти переменные , удовлетворяющие условиям и обращающим в максимум (минимум) функцию .

Пример 19:

Фирма для производства продукции расходует два средства (например труд и капитал). х1 и х2 - затраты факторов производства. Факторы производства будем считать взаимозаменяемыми, т. е. можно применять такие методы производства, при которых величина затрат капитала в соответствии с величиной затрат труда оказывается больше или меньше (трудоемкость производства). Объем производства является функцией затрат производства (производственная функция) Издержки зависят от расходов обоих факторов и от цен этих факторов . Совокупные издержки: . Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции z.

Математическая модель:

Для решения данного класса задач применяются методы классической оптимизации.

Введем понятие экстремума.

Пусть функция дважды дифференцируема в точке и в некоторой ее окрестности. Если для всех точек Х из этой окрестности выполнено: или то имеет локальный экстремум в точке (максимум или минимум соответственно).

Точка , в которой все частные производные равны 0, называется стационарной точкой.

Необходимое условие существования экстремума.

Если в точке функция имеет экстремум, то первые производные в этой точке равны 0:

, то есть все точки экстремума удовлетворяют системе уравнений:

.

Однако необходимое условие не является достаточным. Для получения достаточного условия необходимо определить знак дифференциала второго порядка .

Достаточное условие существования экстремума:

a)  в точке функция имеет максимум, если и минимум, если , для всех , не обращающихся в ноль одновременно ();

b)  если может принимать, в зависимости от то положительные, то отрицательные значения, то в точке экстремума нет;

c)  если может обращаться в ноль, не только при нулевых приращениях , то вопрос о существовании экстремума в точке остается открытым.

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

Найдем значение частных производных второго порядка в стационарной тоске :

.

Обозначим через определитель, составленный из :

.

Тогда достаточное условие функции двух переменных имеет вид:

a)  если , то в точке максимум; если , то в точке функция достигает минимума ();

b)  если , то экстремума нет;

c)  если , то вопрос об экстремуме остается открытым.

Пример 20.

Исследовать на экстремум функцию .

Решение.

Найдем частные производные:

.

Приравниваем их нулю:

Решая полученную систему, находим три стационарные точки .

Найдем вторые частные производные:

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

В точке

.

Вопрос об экстремуме остается открытым (такая точка называется седловой).

В точке , а также в точке

.

Функция в этих точках имеет минимум, так как .

Глобальный экстремум.

Функция имеет в точке глобальный максимум или глобальный минимум если неравенство или соответственно выполнено для всех точек Х из этой области.

Терема Вейерштрассе: Если область замкнута и ограниченна, то дифференцируемая функция достигает в этой области своих наибольшего и наименьшего значений в стационарной точке или в граничной точке области.

Алгоритм нахождения глобального экстремума.

1.  Найти все стационарные точки функции в области и вычислить значение функции в них.

2.  Исследовать функцию на экстремум на границе области .

3.  Сравнить значения функций п.1 и п.2 и выбрать из них максимальное и минимальное.

Условный экстремум.

Пусть необходимо найти экстремум функции , при условии .

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

И пусть имеют непрерывные частные производные по всем переменным.

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

Метод множителей Лагранжа.

Пусть решается задача определения условного экстремума функции.

Строится функция Лагранжа, которая в области допустимых решений достигает максимума (минимума) для тех же значений переменных , что и целевая функция :

,

где - постоянный множитель Лагранжа.

Экономический смысл множителей Лагранжа: если - доход, а - издержки i-го ресурса, то - цена (оценка) i-го ресурса, характеризующая изменение целевой функции в зависимости от изменения размера i-го ресурса (маргинальная оценка).

- функция n+m переменных . Определение стационарных точек этой функции приводит к решению системы уравнений:

.

Таким образом, нахождение условного экстремума функции сводится к нахождению локального экстремума функции Лагранжа.

Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточного условия существования экстремума: исследование знака второго дифференциала в стационарной точке, при условии, что переменные приращения связаны соотношением:

.

Пример 21.

Найти экстремум функции , при условии, что переменные связаны соотношением: .