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

Теория игр.

В практических задачах иногда необходимо найти оптимальное решение в условиях неопределенности. Такого рода задачами занимается раздел математики «Теория игр и статистических решений». Методы, предложенные в нем, часто не дают оптимального решения, а попросту помогают разобраться в ситуации, оценить каждое решение с различных точек зрения. Руководствуясь этими методами, можно принять до конца продуманное решение. Риск при выборе решения в условиях неопределенности всегда неизбежен. Задача: сделать его по возможности минимальным.

Остановимся на математической теории конфликтных ситуаций. Здесь изучаются проблемы выбора коллективных решений, т.е. когда решение принимается рядом лиц (игроков), интересы которых не совпадают. Цель теории игр – выработка рекомендаций по разумному поведению участников конфликта.

Чтобы сделать возможным математический анализ конфликта, строится его математическая модель, называемая игрой. От реального конфликта игра отличается тем, что ведётся по определённым правилам. Эти правила указывают «права и обязанности» участников, а также исход игры – выигрыш (проигрыш) каждого в зависимости от сложившейся обстановки. Игра – это имитационная модель, развитие которой во времени можно представить как ряд последовательных ходов участников. Ход – это выбор игроком предусмотренного игрой действия. Ходы бывают личные, когда игрок сознательно выбирает вариант действия (шахматы) и случайные, осуществляемые механизмом случайного выбора (бросание кубика, вынимание карт из колоды). Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе в зависимости от сложившейся ситуации. Оптимальной стратегией игрока называется такая, которая обеспечивает ему наилучшее положение в игре, т.е. максимальный выигрыш.

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

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

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

	В1	В2	...	Вn
A1	a11	a12	...	a1n
A2	a21	a22	...	A2n
…
Am	am1	am2	...	amn

ПРИМЕР 5.1.

	В1	В2	В3	В4	В5	min
A1	3	4	5	2	3	2
A2	1	8	4	3	4	1
А3	10	3	1	7	6	1
A4	4	5	3	4	8	3
max	10	8	5	7	8

Какой стратегией лучше всего воспользоваться игроку А? Стремление получить максимальный выигрыш в 10 единиц, может привести к жалкому выигрышу в 1 единицу, т.к. разумный противник в ответ на нашу стратегию А₃ выберет стратегию В₃. Исходя из принципа осторожности («всегда рассчитывай на худшее»), надо выбрать ту стратегию, при которой наш минимальный выигрыш максимален. Это «принцип минимакса»: поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш. Из всех наших минимальных выигрышей максимальным будет 3. Выбрав соответствующую ему стратегию A₄, мы получим гарантированный выигрыш в 3 единицы. Этот выигрыш является нижней ценой игры (максимин). Теперь порассуждаем за противника. Из всех своих стратегий он предпочтёт ту, в которой отдаст минимум из возможных максимальных выигрышей игрока А. Этот выигрыш является верхней ценой игры (минимакс). В нашем примере такой стратегией является В₃. При изменении стратегии одним игроком противник также может сменить стратегию, и цена игры будет колебаться.

Нижняя цена игры V_н– максимальный из всех возможных минимальных выигрышей. Верхняя цена игры V_в – минимальный из всех возможных максимальных выигрышей. В примере V_н =max(min a_ij)=3; V_в=min(max a_ij)=5.

В случае, когда V_н =V_в, минимаксные стратегии игроков будут устойчивыми. Стратегии, при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, их совокупность – решением игры, а выигрыш – седловой точкой. Игры с полной информацией всегда имеют седловую точку и решаются в чистых стратегиях. Но если решение игры известно, то играть не имеет смысла.

Дата добавления: 2014-01-20