Матричные игры

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

Предметом изучения теории игр являются ситуации, когда отсутствует полнота информации, а аппарат теории игр предназначен для выбора оптимальных решений в условиях неопределенности. Методы теории игр разработаны применительно к специфическим конфликтным ситуациям, которые обладают свойством многократной повторяемости. Целью теории игр является выработка рекомендаций по рациональному образу действия участников многократно повторяющегося конфликта. Под конфликтными ситуациями понимается положение, когда сталкиваются интересы двух и более сторон, причем выигрыш зависит от того, как поведут себя другие стороны. Математический анализ конфликта возможен при построении математической модели конфликта. Такая модель называется игрой. От реального конфликта игра отличается тем, что ведется по определенным правилам, которые участникам конфликта известны и строго выполняются. Игра называется парной, если в ней участвуют две стороны. Если в парной игре выигрыш одного из игроков равен проигрышу другого, то такая парная игра называется игрой с нулевой суммой. Конечной игрой называется игра с конечным числом стратегий. Стратегией называется совокупность правил, определяющих выбор варианта действия при каждом ходе в зависимости от сложившейся ситуации. Ходы бывают личные и случайные. При случайном ходе – выбор стратегии случайный. Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает ему максимальный средний выигрыш или минимальный средний проигрыш.

Пусть игрок А имеет m чистых стратегий А₁, А₂, … А_i,…А_m, а игрок В имеет n чистых стратегий B₁, B₂, … B_j,…B_n. Такая игра называется игрой m ´ n. Если игрок А пользуется стратегией А_i, а игрок В пользуется стратегией В_j, то обозначим через а_ij выигрыш игрока А, если а_ij > 0, или проигрыш игрока А, если а_ij < 0. Очевидно, что – это одновременно проигрыш игрока В, если а_ij > 0, и выигрыш игрока В, если а_ij < 0.

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

	В1	В2	…	Вj	…	Вn
А1	а11	а12	…	а 1j	…	а 1n
…	…	…	…	…	…	…	(7.1)
Аi	аi1	а i2…	…	а ij	…	а in
…	…	…	…	…	…	…
Аm	аm1	а m2	…	а mj	…	а mn

Каждая строка этой матрицы соответствует некоторой стратегии игрока А, а каждый столбец – некоторой стратегии игрока В.

Пример игры. Два игрока выкидывают на пальцах числа, причем четное число пальцев – это выигрыш игрока А, нечетное – проигрыш игрока А. Для простоты введем ограничение – игроки выкидывают от 1 до 3 пальцев.

Составим платежную таблицу:

	В1	В2	В3
А1		-3		-3
А2	-3		-5	-5
А3		-5		-5

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

a_i = а_ij.

В нашем примере a₁ = -3; a₂ = -5; a₃ = -5. Далее, среди полученных значений l_i-х определим максимальное

a = a_i = а_ij.

В нашем примере a = -3, т.е. игрок А проигрывает 3 очка. Это число a называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А₁ максиминная, т.е. из всех наихудших ситуаций выбирают наилучшую. Эта величина (a) – гарантированный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В. Меньше нижней цены игры игрок А никогда не «выиграет», если будет придерживаться правил игры.

Игрок В старается максимально уменьшить свой проигрыш. Для этого определяется верхняя цена игры

b = b_j = а_ij.

Соответствующая стратегия называется минимаксной. В нашем примере будет две минимаксных стратегии В₁ и В₂. При этом игрок В проигрывает 4 очка.

Теорема 1. В любой матричной игре справедливо неравенство a £ b, т.е. нижняя цена игры никогда не превосходит верхнюю.

Игра с седловой точкой

Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число u = a = b называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.

Пример. Пусть игра задана следующей платежной матрицей:

	В1	В2	В3	В4	ai
- лучшая стратегия для игрока А – (А3) А1
А2
А3
А4
bj
цена игры u = a = b = 4
min max - лучшая стратегия для игрока В – (В2)

Дата добавления: 2014-12-27