Дипломная работа: Методы приближённого решения матричных игр

а _i – i-я строка матрицы выигрышей;

x^N =(x₁ ^N ,x₂ ^N ,…,x_m ^N ) ÎX – m-мерный вектор, приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);

c^N =() –n-мерный вектор, определяющий средний накопленный выигрыш на N-шаге.

Зададим начальные условия. Пусть на 0-шаге с⁰ =, x ⁰ =(0,…, 1,…, 0), где 1 занимает i₀ -ю позицию.

Определим итеративный процесс следующим образом: по известным векторам x^{N -1} , c^{N -1} находим векторы x^N и c^N , которые вычисляются по следующим формулам:

где параметр 0£e_N £1, а векторы вводятся далее.

Как отмечалось, вектор с ^N определяет средний накопленный выигрыш игрока 1 на N шаге. Компоненты этого вектора – это числа. В худшем случае игрок 1 может получить минимальное из этих чисел. Примем его за нижнюю оценку цену игры, которую обозначим:

. (4)

Запомним множество индексов J^{N -1} =(), (k<n), на которых будет достигается этот минимум, т. е.

.

Далее рассмотрим подыгру Г^N игрыГ_А с матрицей выигрышей А^N ={}, i=1,…,m, j^{N -1} ÎJ^{N -1} . Матрица выигрышей состоит из столбцов данной матрицы, номера которых определяются множеством индексов J^{N -1} . В этой подыгре Г^N находим одну из оптимальных смешанных стратегий игрока 1: .

После нахождения , находим вектор по правилу:

.

И рассмотрим игру (2´n), в которой у игрока 1 две чистые стратегии, а у игрока 2 – n чистых стратегий. Эта игра задаётся матрицей , решая которую, находим вероятность использования игроком 1 своей стратегии. Это даёт нам коэффициент e_N .

Далее вычисляем x^N , с ^N и переходим к следующему шагу. Процесс продолжаем до тех пор, пока не выполнится равенство e_N =0, потому что по теореме о минимаксе , а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.

Сходимость алгоритма гарантируется теоремой.

Теорема. Пусть { x^N }, { n ^N } – последовательности, определяемые равенствами (3), (4) . Тогда справедливы следующие утверждения:

1. т. е. последовательность { n ^{N -1} } строго монотонно возрастает.

2.

3. , где x ^* Î X * – оптимальная стратегия игрока 1.

Доказательства этой теоремы достаточно рутинно. Его можно посмотреть в [15].

Рассмотрим применение этого алгоритма к решению конкретной задачи.

Пример. Решить игру с матрицей А=.

Итерация 0. 1. Пусть игрок 1 выбрал свою 1-ю стратегию, т. е. А⁰ =[0, 1, 2]. Тогда за начальные условия примем следующие: x ⁰ =(1, 0, 0) – приближение оптимальной стратегии игрока 1; c ⁰ = a ₁ =(0, 1, 2) – возможный выигрыш игрока 1.

Найдём множество индексов , на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: , значит множество индексов J⁰ ={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т. е. .

2. На этом шаге определим, пользуясь начальными значениями, компоненты векторов . Для этого рассмотрим подыгру . Для этой подыгры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.

Обозначим её через : =(0, 1, 0). Зная , можем вычислить =0а₁ +1а₂ +0а₃ =а₂ =(4, 2, 1).

3. Найдём e₁ . Для этого рассмотрим подыгру (2´3) с матрицей . Решая матрицу графическим способом, получаем, что e₁ =1/2.

4. Проведённые вычисления позволяют найти значения векторов x ¹ , c ¹ :

x ¹ =1/2 x ⁰ +1/2 =1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);

c ¹ =1/2 c ⁰ +1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).