К Лекции Теория игр. Геометрический метод решения матричных конечных игр

Название	Геометрический метод решения матричных конечных игр
Дата	26.05.2020
Размер	0.5 Mb.
Формат файла
Имя файла	К Лекции Теория игр.ppt
Тип	Решение #125708

Лекция ТЕОРИЯ ИГР И ИГРОВОЕ МОДЕЛИРОВАНИЕ. МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР

Учебные вопросы:
1. Элементы теории игр (классификация игр).
2. Геометрический метод решения матричных конечных игр (решение игр в смешанных стратегиях; геометрическая интерпретация решения игры 2х2, 2xn, mx2).
3. Решение матричной конечной игры методом сведения игры к задаче линейного программирования (решение матричной конечной игры методом сведения игры к задаче линейного программирования).

1. Элементы теории игр

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

Рассмотрим основные понятия теории игр. Математическая модель конфликтной ситуации называется игрой, стороны, участвующие в конфликте - игроками, а исход конфликта- выигрышем.
Для каждой игры вводятся правила, т.е. система условий, определяющая:
варианты действий игроков;
объем информации каждого игрока о поведении партнёров;
выигрыш, к которому приводит каждая совокупность действий.

Игры подразделяются:

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

По характеру выигрышей на игры с нулевой и ненулевой суммой. Игра с нулевой суммой предусматривает условие: «сумма выигрышей всех игроков в каждой партии равна нулю». Игры двух игроков с нулевой суммой называют антагонистическими. Выигрыш одного игрока при этом равен проигрышу другого.
Примером игр с нулевой суммой служат многие экономические задачи. В них общий капитал всех игроков перераспределяется между игроками, но не меняется.
Большое количество экономических задач – это игры с ненулевой суммой. Например, в результате торговых взаимоотношений стран все участники могут оказаться в выигрыше. Игра, в которой нужно вносить взнос на право участия в ней является игрой с ненулевой суммой.

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

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

Решение матричной игры в прямых стратегиях
Рассмотрим парную конечную стратегическую игру
с нулевой суммой.
Участников игры обозначим А и В. Под игрой будем понимать некоторую последовательность действий (ходов) игроков А и В, которая осуществляется по четко сформулированным правилам. Ход- выбор одного из предложенных правилами игры действий и его осуществление. Стратегией игрока называется план, по которому игрок совершает выбор хода.
Оптимальной называется стратегия, которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш.
Игрок А выбирает одну из возможных стратегий Аi (i=1,2,....m), а игрок В выбирает стратегию Bj (j=1,2,…, n), причем каждый выбор производится при полном незнании выбора другого игрока. В результате выигрыши а1(Ai, Bj) и –а1(Ai, Bj) каждого из игроков удовлетворяет соотношению а1(Ai,Bj) +(-а1)(Ai, Bj)=0.

Цель игрока А максимизировать функцию (Ai,Bj), цель игрока В- минимизировать эту функцию . Пусть (Ai,Bj)=аij.
Составим матрицу А=
Строки матрицы соответствуют стратегиям Ai игрока А, столбцы- стратегиям Bj игрока В. Матрица А называется платёжной матрицей или матрицей игры. Элемент аij матрицы – выигрыш игрока А, и проигрыш игрока В, если он выбрал стратегию Ai, а игрок В выбрал стратегию Bj
Пусть игрок А выбирает стратегию Ai, тогда в наихудшем случае (если выбор стратегии известен игроку В) он получит выигрыш, равный aij.

Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш, т.е. ,обозначим это значение .
Величина - гарантированный выигрыш игрока А- называется нижней ценой игры. Стратегия Аi0, обеспечивающая , называется максиминной.
Игрок В, выбирая стратегию, исходит из того, что при выборе стратегии Вj его проигрыш не превысит максимального из значений элементов j-го столбца матрицы, т.е. aij. Рассматривая множество для различных значений j, игрок В выберет такое значение j, при котором его максимальный проигрыш минимизируется,
т.е. , обозначим это значение .
Величина называется верхней ценой игры, а соответствующая выигрышу стратегия- минимаксной.
Если = , то игра называется определенной, а выигрыш называется значением игры или ценой игры и равен элементу матрицы ,
который называют седловой точкой матрицы.
Седловой точке соответствуют оптимальные стратегии игроков т.е. максиминная стратегия игрока А и минимаксная игрока В. В этом случае игра имеет решение в чистых (прямых) стратегиях.

.

Если же < , то игра имеет решение в смешанных стратегиях, цена < < .
Пример.
Найти и для игр, заданных платежными матрицами.
1) А1= ; 2) А2=
Решение:
Найдём нижнюю и верхнюю цены игры.

2. Геометрический метод решения матричных конечных игр
Решение игры, если ее матрица не содержит седловой точки, тем сложнее, чем больше значения m и n.
Поэтому в теории игр рассматриваются способы, с помощью которых решение одних игр сводится к решению других, более простых (в частности, с помощью сокращения размерности платёжной матрицы).
Сократить размерность матрицы можно, исключая дублирующие и заведомо невыгодные стратегии.
Дублирующими называются стратегии, которым соответствуют одинаковые значения элементов в платежной матрице, т.е. матрица содержит одинаковые строки или столбцы.
Если все элементы i-ой строки матрицы больше соответствующих элементов k-ой строки, то i-ая стратегия для игрока А называется доминирующей, а k-ую строку из матрицы можно исключить. Если же элементы r-го столбца матрицы меньше соответствующих элементов j-го столбца, то для игрока В стратегия Вr доминирующая и столбец с номером j из матрицы следует исключить.

Например:

Например:
А=
Пример показывает, что платежную матрицу можно свести к матрице 2 или .
Рассмотрим простейшую матричную игру в которой каждый из игроков имеет две стратегии:
А= (1)
Если Седловой точки в этой матрице нет, то решением игры являются смешанные стратегии, т.е. игрок А выбирает с некоторой вероятностью х1 первую стратегию А1, а затем с вероятностью х2 стратегию А2, т.е. имеем матрицу вероятностей игрока А: Х=(х1; х2) и аналогично для игрока В: Y=(y1;y2).

Для цены игры будем иметь систему уравнений х1+х2=1.
Методом подстановки х2=1- х1 и приравнивая левые части уравнений найдём решение этой системы:
а11х1+а21(1-х1)= а12х1+а22(1-х1) или а11х1+а21- а21х1= а12х1+а22- а22х1 или а11х1- а21х1 -а12х1+ а22х1= а22- а21 или
(а11 + а22- а12- а21) х1= а22- а21, тогда х1= х2=1 -

Итак, решение системы (1) имеет вид х1= , х2 (2)
Составим уравнения для игрока В:
у1+у2=1. (3)
Методом подстановки у1=1-у2 и приравнивая левые части уравнений найдём решение системы (3):
а11у1+а12(1-у1)= а21у1+а22(1-у1) или а11у1+а12- а21у1= а21у1+а22- а22у1 или а11у1- а12у1 –а21у1+ а22у1= а22- а12 или
(а11 + а22- а12- а21) у1= а22- а12, тогда у1= у2=1-

Итак, решение системы (3) имеет вид:
у1= , у2 (4)
Найдём теперь цену игры , подставив в 1-ое уравнение системы (1) значения х1 и х2:
а11
=
Итак, = - цена игры. (5)

Рассмотрим теперь игры с матрицами 2 и . Такие игры сводятся к игре с матрицей 2 . Для этого у матриц 2 и геометрически находят две активные стратегии.
Пусть платежная матрица имеет вид Н= , для игрока А матрица вероятностей имеет вид Х=(х1 , х2, …, хm), а игрока В: Y=(y1 , y2).
Из m стратегий игрока А геометрически выделяют две активные стратегии, для остальных неактивных стратегий вероятности их применения будут равны нулю. В системе xOy строим прямые соответствующие стратегиям игрока А, находим верхнюю границу этой совокупности прямых. Стратегии, образующие эту границу и будут активными стратегиями. Ордината самой нижней точки этой границы (точка К) равна цене игры .

Активные стратегии А3 и Аm, матрица А=
или а31=а/11, а32=а/12 и аm1=а/21, аm2=а/22 и матрица
А=
Х=(0,0,х3,0, …,хm), Y=(y1, y2).
Цена игры и элементы матриц Х и Y вычисляются по формулам (5), (2) и (4).

Пусть теперь платёжная матрица имеет вид: Н=
для игрока А матрица вероятностей имеет вид
Х=(х1, х2), а игрока В :
Y=(y1, y2, ..., yn). Из n стратегий игрока В геометрически выделяют две активные стратегии, для остальных неактивных стратегий вероятности их применения будут равны нулю. В системе xOy строим прямые соответствующие стратегиям игрока В, находим нижнюю границу этой совокупности прямых. Стратегии, образующие эту границу и будут активными стратегиями игрока В. Ордината самой верхней точки этой границы (точка К) равна цене игры .

Активные стратегии игрока В: В1 и В2, матрица А= , Х=(х1, х2) ; Y=(y1, y2, 0,0, ... , 0).
Цена игры и элементы матриц Х и Y вычисляются по формулам (5), (2) и (4).

3. Сведение матричной игры к задаче линейного программирования.
Пусть матричная игра задана платежной матрицей размерности m n
A=
и пусть матрица А не содержит седловой точки. Тогда игра не имеет решение в прямых стратегиях.
В этой игре < и применение минимаксных стратегий для каждого из игроков обеспечивает выигрыш, не превышающий , и проигрыш, не меньший . Естественным для каждого игрока является вопрос увеличения выигрыша (уменьшения проигрыша). Поиски такого решения состоят в том, что игроки применяют не одну, а несколько стратегий. Выбор стратегий осуществляется случайным образом. Случайный выбор игроком своих стратегий называется смешанной стратегией.

Пусть игрок А применяет стратегию А1 с вероятностью х1, стратегию А2 с вероятностью х2 и т.д. Обозначим через Х=(х1, х2, …,хm) матрицу вероятностей игрока А, с которыми он применяет свои первоначальные стратегии. Причем
i=1,2,…,m. Аналогично для игрока В матрицу вероятностей применения первоначальных стратегий обозначим Y=(y1, y2, …, yn) и также
j=1,2,…,n.
Стратегии игроков А и В, для которых вероятности хi и yj отличны от нуля, называются активными.
В теории игр доказывается, что каждая конечная матричная игра имеет по крайней мере одно решение, которым может быть и определенная смешанная стратегия.

Если игрок А применяет оптимальную смешанную стратегию
Х*=( ) против любой чистой стратегии игрока Вj игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша aj=a1jx1+a2jx2+...+amjxj, j= (т.е. элементы j-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий А1 , А2 ,…, Аm и результаты складываются).
Для оптимальной стратегии Х* все средние выигрыши не меньше цены игры , поэтому получаем систему неравенств (1):

Преобразуем систему ограничений (1), разделив все члены неравенств на , получим:
(2)
где ti= , i=1,2,..,m.
Из условия x1+x2+...+xm=1 следует, что t1+t2+...+tm= .
Решение игры должно максимизировать значение значит функция должна принимать минимальное значение. Таким образом, получена задача линейного программирования:

Найти при ограничениях (2) и неотрицательности ti(i=1, ). Решив эту задачу найдём ti и величину , затем находим значения хi=
Аналогично для игрока В.Если игрок В применяет оптимальную смешанную стратегию Y*=() против любой чистой стратегии игрока Ai игрока A, то он получает средний проигрыш, или математическое ожидание проигрыша bi=a1iy1+a2iy2+...+aniyn, i=(т.е. элементы i-ой строки платежной матрицы почленно умножаются на соответствующие вероятности стратегий В1 , В2 ,…, Вn и результаты складываются).