Формальное представление игр. Понятие матричной игры

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

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

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

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

Рассмотрим основные элементы, с помощью которых описывается любая игра (любой конфликт).

Пусть в игре участвуют n конфликтующих сторон P ₁, P ₂,…, P _n, называемых обычно игроками. Обозначим через I множество всех таких игроков: I ={ P ₁, P ₂,…, P_n }.

В течение одной партии (однократном осуществлении игры) каждый игрок P_i может придерживаться одной из возможных линий своего поведения s_i, называемых стратегиями, выбирая s_i из некоторого заданного множества S_i. В результате таких выборов складывается некоторый набор стратегий всех игроков ={ s ₁, s ₂,…, s_n }, называемый ситуацией.

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

Таким образом, формальное определение игры сводится к заданию трех классов множеств:

а) множества игроков;

б) совокупности множеств стратегий каждого из игроков { S_i } _{iÎ I};

в) совокупности функций выигрыша каждого из игроков { H_i } _{iÎ I}.

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

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

Матричная игра описывается следующим образом.

· В игре участвуют 2 игрока: допустим, игроки А и В.

· Каждый из игроков располагает конечным набором стратегий: А ₁,…, А_m и В ₁,…, В_n - возможные стратегии игроков А и В (в этом случае говорят, что игра имеет размерность m х n).

· Значения функций выигрыша Н_А и Н_В игроков в каждой ситуации (А_i, B_j) равны по величине и противоположны по знаку, то есть

Н_А (А_i, B_j)=- H_B (A_i, B_j) = a_ij

для всех i =1,…, m, j =1,…, n (выигрыш одного из игроков равен проигрышу другого).

Очевидно, задание такой игры эквивалентно заданию всех значений функции выигрыша одного из игроков (например, игрока А) в виде так называемой платежной матрицы или матрицы игры:

(2.1)

Строки этой матрицы соответствуют стратегиям игрока А, а столбцы - стратегиям игрока В; элементы а_ij задают выигрыш игрока А в ситуации, когда А выбирает стратегию А _i, а В – стратегию В_j.

Пример 2.1. Каждый из двух игроков А и В независимо друг от друга кладет на стол монету в 1 рубль или в 2 рубля. Если монеты одинаковые, то выигрывает игрок А, если разные - игрок В. Выигрыш равен сумме достоинств монет. Необходимо построить платежную матрицу игры.

Решение. Проанализируем поведение каждого из игроков. Игрок А может положить монету 1 руб. (обозначим эту стратегию через А ₁) или монету 2 руб. (стратегия А ₂). Точно также игрок В может положить монету 1 руб. (стратегия В ₁) или монету 2 руб. (стратегия В ₂).

Если игрок А положит 1 руб. и игрок В тоже положит 1 руб., то есть осуществится ситуация (А ₁, В ₁), то в силу одинаковости монет выигрывает игрок А, и его выигрыш равен а ₁₁= Н_А (А ₁, В ₁)=1+1=2. Если игрок А положит 1 руб., а игрок В – 2 руб. (ситуация (А ₁, В ₂)), то игрок А проигрывает В 1+2=3 рубля, т. е. «выигрыш» А равен а ₁₂=-3. Аналогично находим а ₂₁=-(2+1)=-3, а ₂₂=2+2=4. Таким образом, для заданной игры получим следующую платежную матрицу