Задание 3. Элементы теории игр

Краткие теоретические сведения

Теория игр – это теория математических моделей, интересы участников которых различны, причём они достигают своей цели различными путями.

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

Виды игр: – комбинаторные (например, шахматы),

– азартные (кости, рулетка),

– стратегические (отсутствие информации о действиях противника).

Рассмотрим стратегические игры. Они бывают парными (2 игрока) и множественными (более двух игроков). Наиболее практическое значение имеют парные игры. Обозначим участников игры через А и В.

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

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

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

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

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

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

Простейший вид стратегической игры – игра двух лиц с нулевой суммой (сумма выигрышей сторон равна нулю).

Рассмотрим матрицу игры А (платёжная матрица)

Строки матрицы соответствуют стратегиям А_i, столбцы – стратегиям В_j

Элемент а_ij матрицы А – выигрыш игрока А, если он выбрал стратегию А_i, а игрок В выбрал стратегию В_j.

Пусть игрок А выбирает некоторую стратегию А_i, тогда в наихудшем случае (если выбор станет известен игроку В) он получит наименьший выигрыш, равный а_ij. Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш.

. (3.1)

Величина α – гарантированный выигрыш игрока А называется нижней ценой игры. Стратегия А_i0, обеспечивающая получение α, называется максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии В_j, его проигрыш не превысит максимума из значений элементов j-го столбца матрицы, т.е. ≤ а_ij.

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

. (3.2)

Величина β называется верхней ценой игры, а соответствующая выигрышу β стратегия В_jо – минимаксной. Фактический выигрыш игрока А при разумных действиях партнёров ограничен нижней и верхней ценой игры. Если же эти выражения равны, т.е.

(3.3)

то выигрыш игрока А – вполне определённое число, игра называется вполне определённой, а выигрыш V (3.3) называется значением игры и равен элементу матрицы а_i0j0. Вполне определённые игры называются играми с седловой точкой. Элемент а_i0j0 в матрице такой игры является одновременно минимальным в строке i₀, максимальным в столбце j₀ и называется седловой точкой.

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

Пример. Определить нижнюю и верхнюю цены для игр, заданных платёжными матрицами А₁ и А₂

, .

Решение. Минимальные значения а_ij в строках матрицы А₁ равны соответственно 2, 3, 1. Максимальное значение из них равно 3. Следовательно, α₁ = 3 – нижняя цена игры, которой соответствует матрица А₁.

Для определения верхней цены матрица найдём максимальные значения элементов в столбцах матрицы. По столбцам имеем (4, 5, 6, 5). Следовательно, β₁ = 4.

Для матрицы А₂

α₂ = max (0, 2, – 1) = 2,

β₂ = min (3, 2, 4, 5) = 2.

Таким образом, α₂ = β₂ = V = 2 – цена игры. Решение данной игры состоит в выборе игроком А стратегии А₂, при этом его выигрыш не меньше 2; для игрока В оптимальной является стратегия В₂, позволяющая ограничит его проигрыш этим же числом. А₂ и В₂ в этом случае называются чистыми стратегиями, а₂₂ – седловая точка матрицы А₂.

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

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

. (3.4)

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

. (3.5)

В дальнейшем соотношения (3.4) и (3.5) используются для решения игры.

Рассмотрим сведение матричной игры к задаче линейного программирования.

Пусть платёжная матрица игры

Матрица не содержит седловой точки, поэтому решение игры представлено в смешанных стратегиях х = (х₁, х₂, …, х_m), у = (у₁, у₂, …, у_n). При оптимальной стратегии игрока А выполняется условие (3.4), а оптимальной стратегии игрока В удовлетворяет условие (3.5). Таким образом, можно рассматривать задачу отыскания оптимальной стратегии игрока А, для которой выполняются следующий ограничения:

(3.6)

Величина V (цена игры) неизвестна, однако можно считать, что V > 0. Последнее условие выполняется всегда, если элементы матрицы неотрицательны, а этого можно достигнуть, прибавляя ко всем элементам матрицы некоторое положительное число.

Преобразуем систему ограничений, разделив все члены неравенств на V. В результате получим

(3.7)

где t_i = x_i / V,

Из условия x₁ + x₂ + …+x_m = 1 следует

. (3.8)

Решение игры должно максимизировать значение V, следовательно, функция

Таким образом, получена задача линейного программирования.

при ограничениях (3.7) и дополнительных условиях t_i ≥ 0. Решая её, находим t_i и величину далее получаем значение x_i = Vt_i.

Для определения стратегии игрока В запишем следующие условия:

(3.9)

Разделив все члены неравенств на V, получим

(3.10)

где u_j = y_j / V, . Переменные u₁, u₂, …, u_n должны быть выбраны так, чтобы выполнялись условия (3.10) и достигался максимум функции

(3.11)

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

Пример. Найти решение игры, заданной матрицей

Решение. Для матрицы А α = 1, β = 3. Матрица не имеет седловой точки.

Составим симметричные двойственные задачи

Задача 1 Задача 2

min Z = t₁ + t₂ max W = u₁ + u₂

Задачу 2 приведём к канонической и решим симплексным методом.

Сi	Баз	аi 0	u1	u2	u3	u4	θ
	u3
	u4						½
	W		–1	–1
	u3	½		5/2		–½	1/5
	u1	½		½		½
	W	½		–1/2		½
	u2	1/5			2/5	–1/5
	u1	2/5			–1/5	3/5
	W	3/5			1/5	2/5	≥ 0 вып
					t1	t2

, ,

u_j = y_j / V, y_j = u_j · V, ,

t_i = x_i / V, x_i = t_i · V,

Варианты заданий к задаче 3