Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики
 Скачать 1.32 Mb.
|
|
Тема 3. Стратегические игры Изучив данную тему, студент должен знать: • основные процессы исследования стратегических игр; • свойства игр двух лиц с противоположными интересами; уметь: • понимать связь матричных игр с линейным программирова- нием; • определять множество стратегий игроков в матричной игре; • определять оптимальные чистые и смешанные стратегии; • находить оптимальные стратегии в матричной игре со сторо- ны первого и второго игроков. При изучении данной темы необходимо акцентиро- вать внимание на следующих понятиях: • определение оптимальных чистых и смешанных стратегий; • связь нахождения оптимальных стратегий с линейным про- граммированием; • стратегические игры; • матрица игры. Для самопроверки по теме 3 необходимо ответить на вопросы: 1. Каковы основы теории матричных игр двух лиц с нулевой суммой. 2. Как определяется седловая точка. 3. Оптимальные чистые и смешанные стратегии. 4. Какова связь нахождения оптимальных стратегий с линей- ным программированием. 5. Что такое игра. Моделирование рисковых ситуаций 54 Основные понятия теории стратегических игр. Смешанные стратегии. Связь нахож- дения оптимальных стратегий с линейным программированием. Цели и задачи изучения темы: познакомить студента с одним из основных способов оценки рисковых ситуаций – матричными играми. 3.1. Основные понятия теории стратегических игр На практике часто появляется необходимость согласования действий фирм, объе- динений, министерств и других участников проектов в случаях, когда их интересы не совпадают. В таких ситуациях теория игр позволяет найти лучшее решение для поведе- ния участников, обязанных согласовывать действия при столкновении интересов. Теория игр все шире проникает в практику экономических решений и исследова- ний. Ее можно рассматривать как инструмент, помогающий повысить эффективность плановых и управленческих решений. Это имеет большое значение при решении задач в промышленности, сельском хозяйстве, на транспорте, в торговле, особенно при заключе- нии договоров с иностранными государствами на любых иерархических уровнях. Так, можно определить научно обоснованные уровни снижения розничных цен и оптималь- ный уровень товарных запасов, решать задачи экскурсионного обслуживания и выбора новых линий городского транспорта, задачу планирования порядка организации экс- плуатации месторождений полезных ископаемых в стране и др. Классической стала зада- ча выбора участков земли под сельскохозяйственные культуры. Метод теории игр можно применять при выборочных обследованиях конечных совокупностей, при проверке ста- тистических гипотез. Обычно теорию игр определяют как раздел математики для изучения конфликт- ных ситуаций. Это значит, что можно выработать оптимальные правила поведения каж- дой стороны, участвующей в решении конфликтной ситуации. В экономике, например, оказался недостаточным аппарат математического анали- за, занимающийся определением экстремумов функций. Появилась необходимость изу- чения так называемых оптимальных минимаксных и максиминных решений. Следова- тельно, теорию игр можно рассматривать как новый раздел оптимизационного подхода, позволяющего решать новые задачи при принятии решений. Игра — упрощенная формализованная модель реальной конфликтной си- туации. Математически формализация означает, что выработаны опреде- ленные правила действия сторон в процессе игры: варианты действия сто- рон; исход игры при данном варианте действия; объем информации каждой стороны о поведении всех других сторон. Одну играющую сторону при исследовании операций может представлять кол- лектив, преследующий некоторую общую цель. Однако разные члены коллектива могут быть по-разному информированы об обстановке проведения игры. Выигрыш или проигрыш сторон оценивается численно, другие случаи в теории игр не рассматриваются, хотя не всякий выигрыш в действительности можно оценивать количественно. Краткое содержание Определение Стратегические игры 55 Игрок — одна из сторон в игровой ситуации. Стратегия игрока — его правила дей- ствия в каждой из возможных ситуаций игры. Существуют игровые системы управления, если процесс управления в них рассматривается как игра. Платежная матрица (матрица эффективности, матрица игры) включает все значе- ния выигрышей (в конечной игре). Пусть игрок 1 имеет m стратегий A i , а игрок 2 — n стратегий j B ( n m , 1 = j ; , 1 = i ). Игра может быть названа игрой m × n. Представим матрицу эффективности игры двух лиц с нулевой суммой, сопроводив ее необходимыми обозна- чениями (табл. 1). Таблица 1 Игрок 2 Игрок 1 1 B 2 B … n B i α 1 A 11 a 12 a … n 1 a 1 α 2 A 21 a 22 a … n 2 a 2 α … … … … … m A 1 m a 2 m a … mn a m α j β 1 β 2 β … n β В данной матрице элементы ij a — значения выигрышей игрока 1 — могут озна- чать и математическое ожидание выигрыша (среднее значение), если выигрыш является случайной величиной. Величины , , 1 , m i i = α и n j j , 1 , = β — соответственно минимальные значения элементов ij a по строкам и максимальные — по столбцам. Их содержательный смысл будет отражен ниже. В теории игр не существует установившейся классификации видов игр. Однако по определенным критериям некоторые виды можно выделить. Количество игроков. Если в игре участвуют две стороны, то ее называют игрой двух лиц. Если число сторон больше двух, ее относят к игре n игроков. Наибольший ин- терес вызывают игры двух лиц. Они и математически более глубоко проработаны, и в практических приложениях имеют наиболее обширную библиографию [6, 10, 19, 20]. Количество стратегий игры. По этому критерию игры делятся на конечные и бесконечные. В конечной игре каждый из игроков имеет конечное число возможных стра- тегий. Если хотя бы один из игроков имеет бесконечное число возможных стратегий, иг- ра является бесконечной. Взаимоотношения сторон. Согласно данному критерию игры делятся на коопе- ративные, коалиционные и бескоалиционные. Если игроки не имеют право вступать в соглашения, образовывать коалиции, то такая игра относится к бескоалиционным; если иг- роки могут вступать в соглашения, создавать коалиции — коалиционной. Кооперативная игра — это игра, в которой заранее определены коалиции. Характер выигрышей. Этот критерий позволяет классифицировать игры с нуле- вой и с ненулевой суммой. Игра с нулевой суммой предусматривает условие: «сумма выиг- рышей всех игроков в каждой партии равна нулю». Игры двух игроков с нулевой суммой относят к классу антагонистических. Естественно, выигрыш одного игрока при этом ра- вен проигрышу другого. Примерами игр с нулевой суммой служат многие экономиче- ские задачи. В них общий капитал всех игроков перераспределяется между игроками, но не меняется. К играм с ненулевой суммой также можно отнести большое количество эко- Моделирование рисковых ситуаций 56 номических задач. Например, в результате торговых взаимоотношений стран, участвую- щих в игре, все участники могут оказаться в выигрыше. Игра, в которой нужно вносить взнос за право участия в ней, является игрой с ненулевой суммой. Вид функции выигрышей. По этому критерию игры подразделяются на мат- ричные, биматричные, непрерывные, выпуклые, сепарабельные и т.д. Поясним суть не- которых из них. Матричная игра— конечная игра двух игроков с нулевой суммой. В общем слу- чае ее платежная матрица является прямоугольной (см. табл. 1). Номер строки матрицы соответствует номеру стратегии, применяемой игроком 1. Номер столбца соответствует номеру стратегии игрока 2. Выигрыш игрока 1 является элементом матрицы. Выигрыш игрока 2 равен проигрышу игрока 1. Как показано в приложении, матричные игры все- гда имеют решения в смешанных стратегиях. Они могут быть решены методами линей- ного программирования. Биматричная игра— конечная игра двух игроков с ненулевой суммой. Выигрыши каждого игрока задаются своей матрицей, в которой строка соответствует стратегии игрока 1, а столбец – стратегии игрока 2. Однако элемент первой матрицы показывает выигрыш игрока 1, а элемент второй матрицы – выигрыш игрока 2. Для биматричных игр так же, как и для матричных, разработана теория оптимального поведения игроков. Если функция выигрышей каждого игрока в зависимости от стратегий является непрерывной, игра считается непрерывной. Если функция выигрышей выпуклая, то и игра – выпуклая. Если функция выигрышей может быть разделена на сумму произведений функ- ций одного аргумента, то игра относится к сепарабельной. Количество ходов. Согласно этому критерию игры можно разделить на одноша- говые и многошаговые. Одношаговые игры заканчиваются после одного хода каждого иг- рока. Так, в матричной игре после одного хода каждого из игроков происходит распре- деление выигрышей. Многошаговые игры бывают позиционными, стохастическими, диф- ференциальными и др. Информированность сторон. По данному критерию различают игры с полной и неполной информацией. Если каждый игрок на каждом ходу игры знает все ранее при- мененные другими игроками на предыдущих ходах стратегии, такая игра определяется как игра с полной информацией. Если игроку не все стратегии предыдущих ходов других игроков известны, то игра классифицируется как игра с неполной информацией. Мы далее убедимся, что игра с полной информацией имеет решение. Решением будет седловая точка при чистых стратегиях. Степень неполноты информации. По этому критерию игры подразделяются на статистические (в условиях частичной неопределенности) и стратегические (в условиях полной неопределенности, см. разд. 3.2). Игры с природой (см. гл. 3, 6) часто относят к статистическим играм. В статистической игре имеется возможность получения инфор- мации на основе статистического эксперимента, при котором вычисляется или оценива- ется распределение вероятностей состояний (стратегий) природы. С теорией статистиче- ских игр тесно связана теория принятия экономических решений. Получив некоторое представление о существующих подходах к классификации игр, можно остановиться на оценках игры. Рассмотрим матричную игру, представленную матрицей выигрышей m × n, где число строк m , 1 i = , а число столбцов n , 1 j = (см. табл. 1). Применим принцип получе- ния максимального гарантированного результата при наихудших условиях. Игрок 1 стремится принять такую стратегию, которая должна обеспечить максимальный проиг- Стратегические игры 57 рыш игрока 2. Соответственно игрок 2 стремится принять стратегию, обеспечивающую минимальный выигрыш игрока 1. Рассмотрим оба этих подхода. Подход игрока 1. Он должен получить максимальный гарантированный резуль- тат при наихудших условиях. Значит, при выборе отвечающей этим условиям своей чис- той i-й стратегии (в табл. 1 ей соответствует i-я строка выигрышей) он должен выбрать гарантированный результат в наихудших условиях, т.е. наименьшее значение своего вы- игрыша a ij , которое обозначим i α = j min ij a Чтобы этот гарантированный эффект в наихудших условиях был максимальным, нужно из всех α i выбрать наибольшее значение. Обозначим его α и назовем чистой нижней ценой игры («максимин»): α = i max i α j i min max = ij a Таким образом, максиминной стратегии отвечает строка матрицы, которой соот- ветствует элемент α. Какие бы стратегии ни применял игрок 2, игрок 1 максиминной чистой стратегией гарантировал себе выигрыш не меньший, чем α. Таково оптимальное поведение игрока 1. Подход игрока 2. Своими оптимальными стратегиями он стремится уменьшить выигрыш игрока 1, поэтому при каждой j-й чистой стратегии он отыскивает величину своего максимального проигрыша j β = i min ij a в каждом j-м столбце, т.е. определяет максимальный выигрыш игрока 1, если игрок 2 применит j-ю чистую стратегию. Из всех своих n j-х чистых стратегий он отыскивает та- кую, при которой игрок 1 получит минимальный выигрыш, т.е. определяет чистую верх- нюю цену игры («минимакс»): ij i j j j α β = β max min = min Чистая верхняя цена игры показывает, какой максимальный выигрыш может га- рантировать игрок 1, применяя свои чистые стратегии, – выигрыш, не меньший, чем α. Игрок 2 за счет указанного выше выбора своих чистых стратегий не допустит, чтобы иг- рок 1 мог получить выигрыш, больший, чем β . Таким образом, минимаксная стратегия отображается столбцом платежной матрицы, в котором находится элемент β (см. табл. 1). Она является оптимальной чистой гарантирующей стратегией игрока 2, если он ничего не знает о действиях игрока 1. Чистая цена игры v – цена данной игры, если нижняя и верхняя ее цены совпадают: υ α α = max min = min max ij i j ij j i В этом случае игра называется игрой с седловой точкой. Пример 1. Определить верхнюю и нижнюю цены при заданной матрице игры и указать максиминную и минимаксную стратегии. Представим матрицу игры с обозначе- ниями стратегий , j β i α (табл. 2). Таблица 2 B j A i B 1 B 2 B 3 i α A 1 1 2 3 1 A 2 4 5 6 4 j β 4 5 6 Моделирование рисковых ситуаций 58 Решение. Определим нижнюю цену игры : α 1 = 1; α 2 = 4; α = 4 (см. столбец α i ). Определим верхнюю цену игры: β 1 = 4 ; β 2 = 5; β 3 = 6; β = 4 (см. строку β j ). Таким образом, α = β = 4, т.е. 4 = max min = min max ij i j ij j i α α Значит, α = β = v = 4 – чистая цена игры при стратегиях А 2 и В 1 . Следовательно, имеем игру с седловой точкой. Пример 2. Определим максиминную и минимаксную стратегии при заданной матрице эффективности (табл. 3). Таблица 3 Игрок 2 Игрок 1 B 1 B 2 B 3 B 4 A 1 2 7 6 10 A 2 8 4 9 5 Решение. Определим максиминную стратегию: α 1 = 2; α 2 = 4; α= 4. Максиминная стратегия – строка А 2 Определим минимаксную стратегию: β 1 = 8 ; β 2 = 7; β 3 = 9; β 4 = 10; β = 7. Минимаксная стратегия – столбец В 2 . Здесь α< β , следовательно, седловой точки нет. Если матрица игры содержит элемент, минимальный в своей строке и максималь- ный в своем столбце, то он, как уже сказано выше, является седловой точкой. В этом слу- чае мы имеем игру с седловой точкой. Пусть в игре с седловой точкой один игрок придерживается седловой точки, тогда другой получит лучший результат, если также будет придерживаться этой точки. Луч- шее поведение игрока не должно повлечь уменьшение его выигрыша. Зато худшее пове- дение может привести к этому. В данном случае решением игры являются: • чистая стратегия игрока 1; • чистая стратегия игрока 2; • седловой элемент. Оптимальные чистые стратегии – это чистые стратегии, образующие седловую точку. В игре без седловой точки, если игрок 1 информирован о стратегии, принятой игро- ком 2, он сможет принять оптимальную стратегию, которая не совпадает с максиминной. Пример 3. Дана матрица игры = 9 7 12 4 8 11 6 8 5 3 A Стратегические игры 59 Допустим, что игроку 1 стало известно, что игрок 2 принял минимаксную страте- гию. Игрок 1 должен выбрать оптимальную стратегию при условии, что В 2 – стратегия игрока 2 ( β =5). Решение. Определим максиминную стратегию игрока 1: α 1 = 3; α 2 = 4; α= 4. Стратегия игрока 1 – А 2 — максиминная. Выберем оптимальную стратегию для игрока 1. Ею будет не максиминная А 2 , дающая игроку 1 выигрыш α = 4, а та стратегия, которая соответствует i max ij a . В этом случае его максимальный гарантированный выигрыш будет равен верхней цене игры β = 5, поэтому он выберет свою оптимальную стратегию А 1 , зная, что игрок 2 выбрал свою стратегию В 2 . Таким образом, рассмотренный пример дает результат, отличный от результата при игре с седловой точкой. Стратегия является оптимальной, если ее применение обеспечит игроку наи- больший гарантированный выигрыш при любых возможных стратегиях другого игрока. На примере 3 показано, что бывают ситуации, когда игрок 1 может получить вы- игрыш, превосходящий максиминный, если ему известны намерения игрока 2. При многократном повторении игры в сходных условиях можно добиться гаран- тированного среднего выигрыша, превосходящего для игрока 1 максиминный. 3.2. Смешанные стратегии Если в матричной игре отсутствует седловая точка в чистых стратегиях, то находят верхнюю и нижнюю цены игры. Они показывают, что игрок 1 не получит выигрыша, превосходящего верхнюю цену игры, и что игроку 1 гарантирован выигрыш, не мень- ший нижней цены игры. В примере 3 игрок 1 получил по своей оптимальной стратегии А 1 , отличной от максиминной, выигрыш, равный верхней цене игры. Такова плата за информированность о стратегии игрока 2. Это крайний случай. Не улучшится ли ре- зультат игрока 1, если информация о действиях противной стороны будет отсутствовать, но игрок будет многократно применять чистые стратегии случайным образом с опреде- ленной вероятностью? В такой ситуации, оказывается, можно получать выигрыши, в среднем большие нижней цены игры, но меньшие верхней. Смешанная стратегия игрока – это полный набор применения его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями. Подведем итоги сказанного и перечислим условия применения смешанных стратегий: • игра без седловой точки; • игроки используют случайную смесь чистых стратегий с заданными вероятностями; • игра многократно повторяется в сходных условиях; • при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком; • допускается осреднение результатов игр. Определение Моделирование рисковых ситуаций 60 |