Понятие об игровых моделях

Лекция 4

Тема: «ЭЛЕМЕНТЫ ТЕОРИИ ИГР»

 

Понятие об игровых моделях

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

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

Ознакомимся с основными понятиями теории игр. Математи­ческая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте, — игрокам и, а исход конфликта — выигрышем. Для каждой формализованной игры вводятся правил а, т.е. система условий, определяющая:

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

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

3) выигрыш, к которому приводит каждая совокупность дей­ствий. Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, вы­игрыш — единицей, а ничью — 1/2.

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

Игра называется игрой с нулевой суммой, или антагонистиче­ско й, если выигрыш одного из игроков равен проигрышу другого, т.е. для полного задания игры достаточно указать величину одно­го из них. Если обозначить а — выигрыш одного из игроков, b — выигрыш другого, то для игры с нулевой суммой b = - а, поэтому достаточно рассматривать, например а.

Выбор и осуществление одного из предусмотренных правила­ми действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной иг­ре). Случайный ход — это случайно выбранное действие (напри­мер, выбор карты из перетасованной колоды). В дальнейшем мы будем рассматривать только личные ходы игроков.

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

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

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

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

 

Платежная матрица.

Нижняя и верхняя цена игры

Рассмотрим парную конечную игру. Пусть игрок А располагает т личными стратегиями, которые обозначим . Пусть у игрока В имеется п личных стратегий, обозначим их . Говорят, что игра имеет размерность т х п. В результате выбора игроками любой пары стратегий и однозначно определяется исход игры, т.е. выигрыш игрока А (положительный или отрицательный) и проигрыш игрока В. Предположим, что значения известны для любой пары страте­гий . Матрица Р=(), i = 1,2,..., т; j = 1, 2,..., п, эле­ментами которой являются выигрыши, соответствующие страте­гиям и , называется платежной матрицей или матрицей игры. Общий вид такой матрицы представлен в таблице:

 

			…
			…
			…
…	…	…	…	…
			…

 

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

Пример. Составить платежную мат­рицу для следующей игры. Игра "поиск".

Игрок А может прятаться в одном из двух убежищ (I и II); игрок В ищет игрока А, и если найдет, то получает штраф 1 ден. ед. от А, в противном слу­чае платит игроку А 1 ден. ед. Необходимо построить платежную матрицу игры.

Решение. Для составления платежной матрицы следует про­анализировать поведение каждого из игроков. Игрок А может спрятаться в убежище I — обозначим эту стратегию через или в убежище II — стратегия .

Игрок В может искать первого игрока в убежище I — стратегия , либо в убежище II — стратегия . Если игрок А находится в убе­жище I и там его обнаруживает игрок В, т.е. осуществляется пара стратегий то игрок А платит штраф, т.е. . Аналогич­но получаем . Очевидно, что стратегии и дают игроку А выигрыш 1, поэтому . Таким образом, для игры " поиск " размера 2х2 получаем платежную матрицу

.

 

Рассмотрим игру т п с матрицей , i =1, 2,..., т; j =1, 2,..., п и определим наилучшую среди стратегий . Выбирая стратегию игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий , для которой выигрыш для иг­рока А минимален (игрок В стремится "навредить" игроку А).

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

, j =1,… n. (1)

Среди всех чисел выберем наибольшее: . Назовем нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно,

. (2)

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

(3)

Среди всех чисел выберем наименьшее , и назовем верхней ценой игры или минимаксным выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следова­тельно,

(4)

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

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

Пример. Определить нижнюю и верхнюю цены игры и соответствующие стратегии в игре «Поиск». Рассмотрим платежную матрицу:

При выборе стратегии (первая строка матрицы) минимальный выигрыш равен и соответству­ет стратегии игрока В. При выборе стратегии (вторая строка матрицы) минимальный выигрыш равен , он достигается при стратегии .

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

Выбирая стратегию (столбец 1), игрок В понимает, что иг­рок А ответит стратегией , чтобы максимизировать свой выиг­рыш (проигрыш В ). Следовательно, максимальный проигрыш игрока В при выбореим стратегии равен max (-l; 1) = 1.

Аналогично максимальный проигрыш игрока В (выигрыш А ) при выборе им стратегии (столбец 2) равен .

Таким образом, при любой стратегии игрока А гарантирован­ный минимальный проигрыш игрока В равен - верхней цене игры.

Любая стратегия игрока В является минимаксной. Дополнив таблицу строкой и столбцом ,получим новую таблицу:

	-1		-1
		-1	-1
		1

 

 

На пе­ресечении дополнительных строки и столбца будем записывать верхнюю и нижнюю цены игр.

Если верхняя и нижняя цены игры совпадают, то общее значе­ние верхней и нижней цены игры называется чистой ценой игры, или ценой игры. Минимакс­ные стратегии, соответствующие цене игры, являются оптимальны­ми стратегиями, а их совокупность — оптимальным решением, или решением игры. В этом случае игрок А получает максимальный га­рантированный (не зависящий от поведения игрока В ) выигрыш v, а игрок В добивается минимального гарантированного (вне зависи­мости от поведения игрока А ) проигрыша v. Говорят, что решение игры обладает устойчивостью, т.е. если один из игроков придержи­вается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.

Пара чистых стратегий и дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент явля­ется одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая ис­кривляется вверх в одном направлении и вниз — в другом).

Пример.

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

.

Решение.

Составим таблицу, в которой кроме матрицы Р, введем столбец и строку .

 

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

 

Столбец заполнен исходя из стратегии игрока А, т.е минимальные числа в строках 1, 2, 3.Аналогично - максимальные числа в столбцах 1, 2, 3 соответственно. Нижняя цена игры )=0,7 (наибольшее число в столбце ) и верхняя цена игры (наименьшее число в строке ). Эти значения равны, т.е. , и достигается на одной и той же паре стратегий . Следовательно, игра имеет седловую точку и цена игры

 

Поделиться:

Воспользуйтесь поиском по сайту: