§ 3.  Простая а-игра

Пусть задана прямоугольная матрица

элементы которой a_ij являются вещественными числами. Пусть два лица, которых мы будем ниже называть первый игрок, второй игрок, играют в следующую игру. Первый игрок имеет n стратегий d₁, ¼,d_n и может выбрать любую по своему усмотрению; второй игрок имеет m стратегий q₁, ¼,q_m и тоже выбирает одну из них. При этом ни один из игроков не знает, какую стратегию выберет его противник. Если первый игрок выбрал стратегию d_i, а второй игрок – стратегию q_j, то потери первого игрока в этой ситуации равны числу a_ij. Таким образом, матрица A = (a_ij) является матрицей потерь первого игрока. Поскольку интересы  игроков прямо противоположны, число a_ij можно называть также выигрышем второго игрока в результате ходов (d_i, q_j), а матрицу A – матрицей выигрышей второго игрока. Первый игрок действует так, чтобы уменьшить свои потери, второй игрок хочет увеличить свой выигрыш.

Введем следующие обозначения:

D = {d₁, ¼, d_n} – набор стратегий первого игрока,

Q = {q₁, ¼, q_m} – набор стратегий второго игрока.

Итак,  простой A-игрой называется тройка объектов

                                       {D, Q, A}

Обозначим

Видно, что a_i­ есть максимальные потери, которые понесет первый игрок, если он будет следовать стратегии d_i; a_¯j – минимальные потери, которые он понесет, если второй игрок выберет стратегию q_j.

Рекомендуемые материалы

Определение 1. Число

назовем верхней ценой игры.

Определение 2. Число

назовем нижней ценой игры.

Определение 3. Если a^* = a_*, то число

a = a^* = a_*

ценой игры.

Лемма 1. Имеет место следующее неравенство:

a^* ³ a_*.

Доказательство. Для любых i, j справедливы неравенства

a_i­ ³ a_ij ³ a_¯j,

поэтому

a_i­ ³ a_¯j.

Стало быть

и лемма 1 доказана.

Определение 4. Будем говорить, что точка (i₀, j₀) является седловой (для матрицы A), если для всех i, j выполняются неравенства

Бесплатная лекция: "4.5 Уравнение баланса энтропии" также доступна.

Цена игры существует тогда и только тогда, когда существует седловая точка.

Задачи к § 3

3.1. Первый игрок имеет $1000 для приобретения путевки на курорт. Предположим, что курс доллара к рублю – 1:28. Пусть по некоторым причинам покупка путевки переносится на месяц. В этой ситуации первый игрок должен ответить на вопрос: как поступить с деньгами? Опишите игру как простую А-игру, составьте матрицу потерь для первого игрока, найдите цену игры, если она есть.

3.2.  Предприятие выпускает два вида продукции: мороженое (цена – 5 руб., себестоимость – 3 руб.) и пирожки (цена – 4 руб., себестоимость – 2,5 руб.). В холодную погоду продается 1000 штук мороженого и 6000 штук пирожков; в теплую погоду – 4000 штук мороженого и 1200 штук пирожков. Если продукцию не успели продать в день изготовления, то на следующий день ее продают по цене, в четыре раза меньшей, чем в день изготовления. Сформулируйте задачу как простую А-игру, составьте матрицу потерь для предприятия, найдите цену игры, если она существует.

3.3.  Два противника сражаются на двух позициях. У первого противника – 4 полка, у второго – 3 полка. Каждый из противников может послать на позиции любое количество своих полков. Позиция считается выигрышной для  участника, если он послал на нее большее количество полков, чем его оппонент, и выигрыш составляет 1+число полков противника, «плененных» на этой позиции. В случае, когда количество полков на позиции совпадает, считаем, что на этой позиции ничья, и каждый игрок получает 0 очков. Общий выигрыш каждого участника равен сумме выигрышей на каждой позиции. Опишите игру как простую А-игру, составьте матрицу потерь для первого игрока, найдите цену игры, если она есть.