Московский Энергетический Институт

(Технический Университет)

Отчёт по лабораторной работе

по теории игр

«Программа поиска оптимальных стратегий для парной антагонистической игры, заданной в матричной форме»

Выполнили студенты

группы А5-01

Ашрапов Далер

Ашрапова Ольга

2005

О сновные понятия теории игр

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

Если цели сторон прямо противоположны, то говорят об антагонистическом конфликте.

Игрой называется упрощённая формализованная модель конфликтной ситуации.

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

Партия состоит из ходов, т.е. выборов игроков из некоторого множества возможных альтернатив.

Ходы могут быть личные и случайные. Личный ход, в отличие от случайного, предполагает сознательный выбор игроком некоторого варианта.

Игры, в которых имеется хотя бы один личный ход, называются стратегическими.

Игры, в которых все ходы случайны, называются азартными.

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

Задача теории игр – нахождение оптимальных стратегий игроков, т.е. стратегий, обеспечивающих им максимальный выигрыш или минимальный проигрыш.

Классификация теоретико-игровых моделей

Игру n лиц принято обозначать как , где — множество стратегий i-го игрока, — платёж игры.

В соответствии с данным обозначением можно предложить следующую классификацию теоретико-игровых моделей:

Дискретные (множества стратегий дискретны)

Конечные

Бесконечные

Непрерывные (множества стратегий непрерывны)

Бесконечные

n лиц ( )

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц (парные)

Антагонистические (игры с нулевой суммой)

(интересы сторон противоположны, т.е. проигрыш одного игрока равен выигрышу другого)

Неантагонистические

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

С неполной информацией

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой

Одноходовые (лотереи)

Многоходовые

Матричное представление парной антагонистической игры

В данном пособии будем рассматривать антагонистические игры двух лиц, заданные в матричной форме. Это означает, что нам известно множество стратегий первого игрока (игрок A) {A_i}, i = 1,…, m и множество стратегий второго игрока (игрок B) {B_j}, j = 1,..., n, а также задана матрица A = ||a_ij|| выигрышей первого игрока. Поскольку речь идёт об антагонистической игре, то предполагается, что выигрыш первого игрока равен проигрышу второго. Считаем, что элемент матрицы a_ij – выигрыш первого игрока при выборе им стратегии A_i и ответе ему второго игрока стратегией B_j. Такую игру будем обозначать как , где m — количество стратегий игрока А, n — количество стратегий игрока В. В общем виде она может быть представлена следующей таблицей:

Пример 1

В качестве простейшего примера рассмотрим игру, партия которой состоит из двух ходов.

1-й ход: Игрок А выбирает одно из чисел (1 или 2), не сообщая о своём выборе сопернику.

2-й ход: Игрок В выбирает одно из чисел (3 или 4).

Итог: Выборы игроков А и В складываются. Если сумма чётная, то В выплачивает её значение игроку А, если же нечётная — наоборот, А выплачивает сумму игроку В.

Данная игра может быть представлена в виде следующим образом:

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

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

При решении игры в матричной форме следует проверить игру на наличие седловой точки. Для этого вводятся две величины:

– нижняя оценка цены игры и

– верхняя оценка цены игры.

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

Можно доказать, что α ≤ V ≤ β, где V – цена игры, т.е., вероятный выигрыш первого игрока.

Если выполняется соотношение α = β = V, то говорят, что игра имеет седловую точку , и решается в чистых стратегиях. Иными словами, имеется пара стратегий , дающих игроку А устойчивый выигрыш, равный цене игры V.

Пример 2

Вернёмся к игре, рассмотренной нами в примере 1 и проверим её на наличие седловой точки.

Для данной игры = -5, = 4, , следовательно, она не имеет седловой точки.

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

Пример 3

Внесём в правила игры из примера 1 некоторые изменения. Предоставим игроку В информацию о выборе игрока А. Тогда у В появятся две дополнительные стратегии:

— стратегия, выгодная для А. Если выбор А — 1, то В выбирает 3, если выбор А — 2, то В выбирает 4;

— стратегия, не выгодная для А. Если выбор А — 1, то В выбирает 4, если выбор А — 2, то В выбирает 3.

Эта игра — с полной информацией.

В данном случае = -5, = -5, , следовательно, игра имеет седловую точку . Данной седловой точке соответствуют две пары оптимальных стратегий: и . Цена игры V= -5. Очевидно, что для А такая игра невыгодна.

Примеры 2 и 3 являются неплохой иллюстрацией к следующей теореме, доказанной в теории игр:

Теорема 1

Всякая парная антагонистическая игра с полной информацией решается в чистых стратегиях.

Т.о. теорема 1 говорит о том, что любая игра двух лиц с полной информацией имеет седловую точку и существует пара чистых стратегий , дающих игроку А устойчивый выигрыш, равный цене игры V.

В случае же отсутствия седловой точки, в качестве решения используются т.н. смешанные стратегии: , где p_i и q_j – вероятности выбора стратегий A_i и B_j первым и вторым игроками соответственно. Решением игры в данном случае является пара смешанных стратегий , максимизирующих математическое ожидание цены игры.

Обобщением теоремы 1 на случай игры с неполной информацией служит следующая теорема:

Теорема 2

Любая парная антагонистическая игра имеет хотя бы одно оптимальное решение, т.е., пару в общем случае смешанных стратегий , дающих игроку А устойчивый выигрыш, равный цене игры V, причём α ≤ V ≤ β.