Элементы теории игр (стр. 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

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

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