При решении многих задач теории игр их обычно сводят к матричной форме. После этого полученную матрицу можно попытаться упростить, используя соотношение превосходства, и лишь затем приступить к решению задачи. Существует ряд точных способов получения решений задач матричных игр [2], среди которых и методы линейного программирования [3].
Однако для матриц большого размера методы линейного программирования малопригодны, т.к. приводят к значительным трудностям при вычислениях. Зачастую при решении задач теории игр точные решения не требуются, к тому же выигрыши игроков в каждой конкретной ситуации могут не всегда определяться точными значениями. Например, исходная платежная матрица игроков может быть получена на основе некоторых исходных данных (в том числе экспериментальных), уже содержащих в себе некоторые ошибки (связанные с погрешностями измерений). В итоге, числа матрицы уже сами по себе не будут являться точными значениями, и поэтому точность в определении значения цены игры и распределении стратегий игроков не будет оправдана. Кроме того, некоторая погрешность в оценке игроком своего выигрыша на практике не будет приводить к каким-либо серьезным последствиям: небольшое отклонение игрока от его истинной оптимальной стратегии не приведет к заметному изменению в его выигрыше.
В таких случаях лучше использовать приближенные методы решения. Одним из таких методов является метод фиктивного разыгрывания игры [1, 2], или метод Брауна-Робинсона, относящийся к итеративным методам.
Данный метод использует некоторую последовательность партий игры, в каждой из которых игроки выбирают такие стратегии, которые дают им максимальный суммарный выигрыш с учетом всех предыдущих партий. С ростом количества партий игры средний выигрыш на одну партию будет постепенно приближаться к цене игры, а относительные частоты применения стратегий игроками приближаться к вероятностям применения стратегий в оптимальных смешанных стратегиях игроков.
К преимуществ такого метода относится его простота, однако имеется и недостаток — малая скорость сходимости (причем она сильно зависит от значений элементов матрицы). Стоит также отметить, что сложность и объем вычислений относительно слабо растут с ростом размера матрицы (примерно пропорционально числу строк и столбцов матрицы).
Таким образом, рассматриваемый метод приближенного решения матричных игр позволяет находить цену игры и оптимальные стратегии поведения игроков с какой угодно степенью точности, зависящей лишь от количества выполненных итераций.
Метод Брауна-Робинсона удобно реализовать программно для определения решений игры с использованием ЭВМ. Ниже в работе представлена программа для получения приближенного решения матричных игр, реализованная в системе программирования Delphi. Программа поддерживает работу с матрицами размером до 100×100, окно программы изображено на рис. 1.
В программе можно выбирать два варианта работы — указав или точность подсчета, или количество итераций до вывода полученных решений.
На рис. 2-4 показаны некоторые примеры работы с программой для матриц различных размеров.
Для рис. 2 точное решение имеет следующий вид: , , , для рис. 3: , , . Здесь X и Y — оптимальные стратегии первого и второго игроков соответственно, V — цена игры. Видно, что для рис. 2 требуемая точность достигается всего за 48 итераций, тогда как для рис. 3 — уже за 60030 итераций.
На рис. 4 рассмотрен пример для матрицы размером 7×8. Количество итераций для достижения указанной точности — более 10 млн.
Таким образом, описанная программа позволяет приближенно определять решения прямоугольных матричных игр и может быть использована при решении ряда практических задач в случаях, когда получение точных решений стандартными методами оказывается невозможным в силу значительной трудоемкости связанных с этим вычислений. Также программа может быть использована в учебных целях при изучении дисциплин, связанных с теорией игр.