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

Ai \ Bj	B1	B2	…	Bn	i
A1	a11	a12	…	a1n	1
A2	a21	a22	…	a2n	2
…	…	…	…	…	…
Am	am1	am2	…	amn	m
j	1	2	…	n

В таблице приведены числа α_i = min a_ij - минимально возможный выигрыш игрока А, применяющего стратегию A_i (i = 1,m ) и β_j = max a_ij - максимально возможный проигрыш игрока В, если он пользуется стратегией βj ( j = 1, n ).

Число называют нижней чистой ценой игры (максимином), а соответствующую ему чистую стратегию – максиминной.

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

Число называют верхней чистой ценой игры (минимаксом), а соответствующую чистую стратегию минимаксной.

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

Ясно, что α ≤ β .

Если α = β , то говорят, что игра имеет седловую точку в чистых стратегиях и чистую цену игры v = α = β . Стратегии образующие седловую точку, являются оптимальными. Тройку ( ) называют решением игры.

Пример. Для отопления коттеджа в зимний период используется уголь, цена на который зависит от времени года и характера зимы. Летом тонна угля стоит 7,5 ден. ед., в мягкую зиму — 8,5, в обычную — 9,0, а в холодную — 9,5. Расход угля в отопительный сезон полностью определяется характером зимы: на мягкую зиму достаточно 6 тонн, на обычную требуется 7 тонн, а в холодную расходуется 8 тонн. Понятно, что затраты домовладельца зависят от количества угля, запасенного им летом. При анализе возможных вариантов уровня запаса следует иметь в виду, что при необходимости недостающее количество угля можно приобрести и зимой. Кроме того, надо учесть, что продать непотребовавшийся уголь возможности не будет. Используя игровой подход, составить платежную матрицу.

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

Заготавливая уголь летом, домовладелец может ориентироваться либо на мягкую (его первая чистая стратегия А₁), либо на обычную (вторая чистая стратегия А₂), либо на холодную зиму (третья чистая стратегия А₃), покупая соответственно 6, 7 или 8 тонн угля. Игрок П может реализовать либо мягкую зиму (первая его чистая стратегия — состояние П₁), либо обычную ( второе возможное состояние П₂ природы), либо холодную (третье возможное состояние П₃), что потребует затрат 6, 7 или 8 тонн угля соответственно. Таким образом, платежная матрица игры будет иметь размерность 33 (табл.8.1).

Таблица 8.1

Ai / Пj	П1(6)	П2(7)	П3(8)	i
A1(6)	-45	-54	-64	-64
A2(7)	-52,5	-52,5	-62	-62
A3(8)	-60	-60	-60	-60
j	-45	-52,5	-60

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

Вычислим элемент а₁₁, соответствующий ситуации (А₁;П₁). Это наиболее благоприятный случай. В самом деле, домовладелец в расчете на мягкую зиму купил летом 6 т угля, заплатив 6  7,5 = 45 ден.ед. Наступившая зима оказалась мягкой и потому дополнительных затрат зимой не потребовалось. Таким образом, «выигрыш» игрока А равен — 45, т.е. а₁₁= -45.

Рассмотрим ситуацию (А₁;П₂), т.е. случай, когда домовладелец приобретает летом 6 т угля в расчете на мягкую зиму, а зима оказывается обыкновенной, когда требуется 7 т. Приходится дополнительно приобретать зимой 1 т угля по цене 9 ден. ед., так, что общие расходы на отопление составляют 45 + 9 = 54 ден. ед. и «выигрыш» в этом случае будет равен — 54 ден. ед., т.е. а₁₂ = -54.

В ситуации (А₁;П₃) общие расходы, учитывая холодную зиму, составят 45 + 2  9,5 = 64 ден.ед., а потому а₁₃ =-64. Рассуждая аналогично, находят и остальные элементы платежной матрицы. Равенство а₂₁= а₂₂ = -52,5 и а₃₁= а₃₂ = а₃₃ =-60 объясняются тем, что неизрасходованный на отопление уголь продать (по условию задачи) для возмещения лишних затрат возможности нет. По табл.8.1 находим нижнюю  и верхнюю  чистые цены:

при этом ==-60.

Таким образом, рассмотренная игра имеет седловую точку , ею является пара чистых стратегий А₃ и П₃, соответствующих  и , чистая цена v = -60. Эти чистые стратегии будут оптимальными стратегиями игроков. Учитывая характер исследованной ситуации, в ответ имеет смысл внести только рекомендации сознательному игроку А, поскольку игрок П (природа), к нашим советам прислушаться не может. Итак, домовладельцу следует запасать с лета 8 т угля. При этом затраты его будут минимальными и составят 60 ден. ед.