Объектно-ориентированный подход к теории игр

Цель лекции: Рассмотреть объектно-ориентированое моделирование матричных игр. Реализовать проверку смешанных стратегий с помощью вычислительных экспериментов.

На прошлой лекции мы рассматривали игру в "крестики-нолики", в которой принимали участие два различных агента. В настоящей лекции мы рассмотрим элементы теории игр. Теория игр - это прикладная математическая дисциплина, в которой изучаются методы нахождения оптимальных решений в условиях неопределенности и ситуациях противодействия со стороны других игроков. Современную математическую форму теория игр приобрела после известного труда Дж. фон Неймана и О. Моргенштерна "Теория игр и экономическое поведение", вышедшего в 1944 году. В настоящее время теория игр находит свое применение в экономических науках, в социальных науках, биологии, а также и в математических дисциплинах, таких как, математическая статистика, функциональный анализ и других.

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

В теории игр рассматривается большое количество постановок различных игр. Мы рассмотрим подробно самую известную постановку в теории игр - антагонистичную игру двух лиц.

Обозначим через $$I$$ множество всех игроков. Мы будем рассматривать конечное число игроков. Мы будем различать игроков по номерам$$I=\{1,2,\dots,N\}.$$ Предположим, что каждый игрок $$i\in I$$ имеет в своем распоряжении определенное множество стратегий, которое мы обозначим через $$S_i$$.

Процедура игры происходит следующим образом: каждый игрок выбирает одну стратегию из своего множества стратегий $$s_i\in S_i$$. Вектор выбранных стратегий всех игроков обозначим через$$s=(s_1,s_2,\dots,s_N).$$ Вектор $$s$$ называется ситуацией в игре. Множество всех возможных ситуаций можно ввести по формуле$$S=\prod\limits_{i\in I}S_i.$$ В каждой сложившейся ситуации игроки получают определенные выигрыши. Договоримся считать, что выигрыш может быть и отрицательным, что означает проигрыш. Выигрыш игрока $$i$$ в ситуации $$s$$ обозначим через $$H_i(s)$$. Функция $$H_i$$, определенная на множестве всех ситуаций$$H_i:S\to\Bbb{R}$$ называется функцией выигрыша $$i$$ -го игрока. Мы будем измерять выигрыши действительными числами, хотя не всегда выигрыш может быть измерен числом.

Бескоалиционной игрой называется система$$\Gamma=\langle I,\{S\}_{i\in I},\{H_i\}_{i\in I}\rangle,$$ где $$I$$, $$S_i$$ являются множествами, а $$H_i$$ - функции на множестве $$S$$, принимающие вещественные значения.

Наиболее часто встречается ситуация, когда сумма выигрышей всех игроков во всех ситуациях является постоянной, что соответствует тому, что игроки по сути делят между собой фиксированную сумму. Игра называется игрой с постоянной суммой, если$$\sum\limits_{i\in I}H_i(s)=const$$ при всех ситуациях $$s\in S$$.

Мы будем рассматривать антагонистичные игры. Игра называется антагонистичной, если число игроков равно двум, т.е. $$I=\{1,2\}$$, а значения функций выигрыша в сумме равны нулю$$H_1(s)=-H_2(s),\ s\in S.$$

Если в теории оптимизации основной задачей является нахождения оптимальных решений, то в теории игр аналогом этого является нахождения ситуации равновесия. Ситуация $$s^*\in S$$ называется ситуацией равновесия в игре, если ни одному из игроков не выгодно отступать от этой стратегии. формально это можно записать следующей формулой $$s^*=(s^*_1,s^*_2)$$$$H_1(s_1,s^*_2)\le H_1(s^*_1,s^*_2)\le H_1(s^*_1,s_2),\ s\in S.$$

Если множества стратегий конечны, то антагонистичные игры удобно записывать в матричном виде. Пусть множество стратегий первого игрока равно $$n>1$$, а второго - $$m>1$$, тогда запишем в виде матрицы значения функции выигрышей$$A=\left(% \begin{array}{cccc} a_{11} a_{12} \dots a_{1n} \\ a_{21} a_{22} \dots a_{2n} \\ \dots \dots \dots \dots \\ a_{m1} a_{m2} \dots a_{mn} \\ \end{array}% \right)$$ Игра в этом случае состоит в том, что первый игрок выбирает строку, а второй игрок (одновременно!) выбирает столбец. Число, стоящее на пересечении выбранных строки и столбца, означает выигрыш первого игрока и проигрыш второго игрока.

В матричной игре ситуация $$(i^*,j^*)$$ называется равновесной, если$$a_{ij^*}\le a_{i^*j^*}\le a_{i^*j}$$ для всех $$i=1,\dots,m$$ и $$j=1,\dots,n$$. В теории игр доказывается, что для существования ситуации равновесия необходимо и достаточно, чтобы было выполнено равенство$$\max\limits_i\min\limits_j a_{ij}=\min\limits_{j}\max\limits_ia_{ij}=c.$$ Число $$c$$ в этом случае называется ценой игры. Если бы в каждой игре существовала бы ситуация равновесия, то игры бы не имели смысл. К счастью или к сожалению, но во многих играх ситуации равновесия не существует. Самый простой пример - игра в "чет--нечет". Матрица этой игры такова$$A=\left(% \begin{array}{cc} 0 1 \\ 1 0 \\ \end{array}% \right).$$ Фундаментальным результатом теории игр является тот факт, что любая матричная игра имеет ситуацию равновесия в смешанных стратегиях. Смешанной стратегией называется случайная величина, значениями которой являются стратегии игрока. Смешанная стратегия - это распределение вероятностей на множестве допустимых стратегий, которую можно представить вектором с неотрицательными компонентами, сумма которых равна единице.

При смешанном расширении понятия матричной игры, игроки выбирают свои смешанные стратегии: первый игрок$$X=(x_1,\dots,x_m),\ x_i\ge0,\ \sum\limits_{i=1}^mx_i=1,$$ $$Y=(y_1,\dots,y_m),\ y_i\ge0,\ \sum\limits_{i=1}^my_i=1,$$ Выигрыш в смешанных расширениях рассчитывается как математическое ожидание. Выигрыш первого игрока равен$$\sum\limits_{i=1}^m\sum\limits_{j=1}^na_{ij}x_iy_j$$