1 Расчетная часть

1.1. Постановказадачи

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

В игре могут сталкиваться интересы двух противников (игра парная или игра двух лиц), интересы n (n > 2) противников (игра множественная или игра n лиц). Существуют игры с бесконечным множеством игроков.

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

Задача первого игрока – максимизировать свой выигрыш.

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

Необходимо создать программу для автоматизированного решения данной задачи с использованием ЭВМ.

1.2. Математическая модель

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

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

Каждая фиксированная стратегия, которую может выбрать игрок, называется его чистой стратегией.

Процесс игры состоит в выборе каждым игроком i одной своей стратегии.В результате сложившейся ситуации s игрок i получает выигрыш.

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

Ситуация s в игре называется приемлемой для игрока i, если этот игрок, изменяя в ситуации s свою стратегию si на какую-либо другую si', не может увеличить своего выигрыша.

Ситуация s, приемлемая для всех игроков, называется ситуацией равновесия.

Процесс нахождения ситуации равновесия в бескоалиционной игре есть процесс решения игры.

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

Предположим, что игрок А имеет m стратегий: А₁, А₂ , …, А_m а игрок В – n стратегий: B₁, B₂ , …, B_m

Пусть игрок А выбрал стратегию А_i, а игрок В – стратегию B_j. Будем считать, что выбор игроками стратегий _Аi и _Bj. однозначно определяет исход игры – выигрыш a_ij игрока А и выигрыш b_ij игрока В, причем эти выигрыши связаны равенством bij = a_ij.

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

Если нам известны значения _aij выигрыша при каждой паре стратегий , i = 1,2,…,m, j = 1,2,…,n, то их удобно записывать или в виде матрицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В (табл. 1),