Как найти максиминную стратегию

В первом примере наибольший выигрыш
игрока 1, равный 52, находится в первой
строке. Однако, если игрок 2 выберет
второй или третий столбец, то результатом
партии будет не выигрыш, а проигрыш
игрока 1. Поэтому игроку 1, принимая
решение о выборе своей стратегии
(строки), необходимо учитывать возможность
наиболее неблагоприятного развития
событий.

Максиминная стратегия, принцип максимина

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

Пусть игрок 1 выбрал некоторую чистую
стратегию. Посмотрим, какой выигрыш он
может себе обеспечить при любом поведении
противника.

Если игрок 1 выбирает i-ю
строку, то его выигрышем в зависимости
от ответа противника может быть любое
из чисел в этой строке, т.е. он гарантирует
себе выигрыш

.
Так как игрок 1 стремится максимизировать
свой выигрыш, то ясно, что ему следует
выбирать свою строку так, чтобы его
минимальный выигрыш был максимальным,
т.е. равен

=

. (2.1)

Таким образом, α ≥ α_i
для всех

Стратегия

соответствующая выбору строки

матрицы А, минимальное значение в
которой равно α, называется максиминной
чистой стратегией, а величина α,
вычисляемая по формуле (2.1), называется
нижней ценой игры или максимином.

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

Минимаксная стратегия

Аналогично игрок 2 может определить
стратегию, обеспечивающую ему минимальный
проигрыш при любом ответе игрока 1. Для
этого ему нужно найти в каждом столбце
максимальное значение, равное его
проигрышу при наиболее неблагоприятном
для него ответе противника, т.е. величину

для всех

.
Тогда величина

(2.2)

будет минимальным проигрышем игрока
2, который он обеспечивает себе при любом
ходе игрока 1. Ясно, что β ≤ β_j
для всех

.

Величина β, вычисляемая по формуле
(2.2), называется верхней ценой игры
или минимаксом. Стратегия

,
соответствующая выбору столбца

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

Замечание.
Если рассмотреть матрицу выигрышей В
= (b_ij)
игрока 2, где b_ij
= —a_ij,
то легко проверить, что определенная
выше минимаксная стратегия

будет максиминной для матрицы В.
Таким образом, игрок 2 также действует
в соответствии с принципом максимина.

Определим максиминную и минимаксную
стратегию игроков в примерах.

В первом примере α₁ = -30, α₂
= 10, α₃ = -30; значит, α = 10.
Максиминной является стратегия А₂
игрока 1, соответствующая выбору
второй строки матрицы А. Выбрав ее,
он обеспечивает себе выигрыш, равный
10, независимо от того, какую стратегию
выберет игрок 2.

Соответственно, β₁ = 52, β₂
= 10, β₃ = 25, β₄ = 34 и,
следовательно, β = 10. Минимаксной
является стратегия В₂ игрока
2, соответствующая выбору второго столбца
матрицы А (см. таблицу 2.1).

Таблица
2.1

В примере 2 α₁ = 15, α₂
= 26, α₃ = 26 и, значит, α = 26.
Максиминными являются стратегии А₂
и А₃ игрока 1, соответствующие
выбору второй или третьей строки матрицы
А. Выбрав любую из этих строк, игрок
обеспечивает себе выигрыш, равный 26,
независимо от выбора стратегии игроком
2.

Соответственно, β₁ = 35, β₂
= 26, β₃ = 32, β₄ = 27 и,
следовательно, β = 26. Минимаксной
является стратегия В₂ игрока
2, соответствующая выбору второго столбца
матрицы А (см. таблицу 2.2).

Таблица
2.2

В примере 3 (игра в орлянку) α₁
= α₂ = -1 и, следовательно α =
-1. В качестве максиминной стратегии
игрока 1 может выступать любая из двух
его чистых стратегий А₁ и А₂.
Соответственно, β₁ = β₂
= 1 и, значит, β = 1. Минимаксной
стратегией игрока 2 также будет любая
из двух его чистых стратегий В₁
и В₂.

Таблица
2.3

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Как отмечалось, важнейшим вопросом в теории игр (в том числе и матричных) является вопрос о выборе оптимальных стратегий для каждого из игроков.

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

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

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

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

Как видно, принцип максимина — это принцип крайне осторожного игрока, но именно он является основным принципом теории матричных игр.

Для пояснения принципа максимина рассмотрим пример 1 матричной игры G (4х5) с платежной матрицей, приведенной на рис. 2.2.

Пример 1.

Рис. 2.2

Какой стратегией игроку А воспользоваться? Есть соблазнительный выигрыш 12, при применении стратегии А3. Но при этом противник может выбрать стратегию В3, и игрок А получит выигрыш, равный всего трем.

Для определения оптимальной стратегии в соответствии с принципом максимина, запишем в правом добавочном столбце платежной матрицы минимальное значение AI в каждой строке (минимум строки). Из всех значений AI (правый столбец) выделим наибольшее. Ему соответствует стратегия А4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что при любом поведении противника выигрыш будет не менее пяти.

Эта величина — наш гарантированный выигрыш. Он называется Нижней ценой игры (или «максимином» — максимальный из минимальных выигрышей). Будем обозначать его A. В нашем примере a = Aij =5.

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

Припишем к платежной матрице (рис.2.2) нижнюю строку и в ней запишем наихудшее для игрока В возможные результаты (максимумы столбцов BJ.

Очевидно, осторожный противник должен выбрать стратегию, при которой величина BJ минимальна. Эта величина называется Верхней ценой игры (или “минимаксом” — минимальный из максимальных проигрышей). Будем обозначать ее B. В нашем примере b = Aij = 7.

Итак, исходя из принципа осторожности, игрок А должен выбрать стратегию А4, а его противник — В3. Такие стратегии называются максиминными или минимаксными стратегиями (вытекающие из принципа максимина).

До тех пор, пока обе стороны в нашем примере будут придерживаться своих максиминных стратегий, выигрыш игрока А и проигрыш игрока В будет равен А43=5.

Легко показать, что нижняя цена игры никогда не превосходит верхней цены игры.

Лемма 1. Пусть задана матрица выигрышей

А = êêaijêêи определены b= и a= .

Тогда .

Доказательство. По определению максимума и минимума для любых фиксированных значений I и J имеем

(2.1)

Поскольку левая часть неравенства (2.1) не зависит от I, то можем записать

(2.2)

Так как правая часть неравенства (2.1) не зависит от J, то

(2.3)

Объединяя неравенства (2.2) и (2.3), получаем неравенство (2.1), что и требовалось доказать. Итак, всегда B³A.

Случай B=A, соответствует наличию у платежной матрицы так называемой Седловой точки.

Определение. Точка (I*, J*) называется седловой точкой платежной матрицы ||AIj||, если для всех остальных i и j этой матрицы выполняется условие

Ai*j ³ai*j*³ aij*,

Т. е. Аij является одновременно минимумом своей строки и максимумом своего столбца.

Приведем без доказательства следующую теорему.

Теорема 1. Для того чтобы

Необходимо и достаточно, чтобы матрица ||AIj|| имела седловую точку. Кроме того, если (I*, J*) — седловая точка матрицы ||AIj||, то

(2.4)

Говорят, что матричная игра имеет седловую точку, если соответствующая ей матрица выигрышей (платежная матрица) имеет седловую точку.

Пример 2. Найти решение игры G (3х3), платежная матрица которой имеет следующий вид:

Определим и И запишем их в таблицу.

Нижняя цена игры

Верхняя цена игры

Так как a=b=0, то платежная матрица и матричная игра имеют седловую точку. Оптимальными стратегиями для игрока А является стратегия А3, а для игрока В — В3.

Легко заметить, что отклонение игрока А от оптимальной стратегии приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В — к увеличению его проигрыша.

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

Пример 3. Найти решение игры G (3х4), платежная матрица которой имеет вид:

Определим aI и bj и запишем их в таблицу.

Находим нижнюю и верхнюю цену игры:

; . Видно, что игра имеет четыре седловые точки с соответствующими парами оптимальных стратегий: А1В2; А1В4; А3В2 и А3В4. Цена игры равна 6.

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

Введение

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

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

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

• Исследование принципов максимина и минимакса

• Наблюдение динамики решения задач: упрощается или усложняется экономическое решение с применением теории игр

• Применение методов теории игр в экономике: рассмотреть конкретные примеры

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

1. Понятие игры. Максиминные и минимаксные решения.

Цель теории игр – выработка рекомендаций для различного поведения игроков в конфликтной ситуации, т.е. выбор оптимальной стратегии для каждого из них. Игровая модель, в отличии от конфликтной ситуации, строится по определенным законам, а игроки придерживаются определенных правил.

Участниками игры (конфликтной ситуации) могут быть минимум два человека (парная игра) или несколько человек (множественная игра). Игра развивается по оговоренным правилами. Игроки по очереди делают свои ходы. Естественно, перед каждым ходом игрок может или сохранить предыдущую стратегию или применить новую стратегию. Если игрок при выборе очередного хода придерживаются каких-либо правил, то такая игра носит название стратегической.

Возможные варианты (исходы) игры сводятся в прямоугольную таблицу (табл. 1) – платежную матрицу, в которой строки соответствуют различным стратегиям игрока А, столбцы – стратегиям игрока В, a_ij называется выигрыш первого игрока.

Таблица 1

Если игра содержит ограниченное количество стратегий, то такая игра называется конечной. В противном случае – бесконечной.

Стратегия, приносящая игроку максимальный выигрыш, называется оптимальной. Для нахождения оптимальной стратегии необходимо проанализировать все возможные стратегии и рассчитывать на то, что разумный противник на каждую из них будет отвечать такой, при которой выигрыш игрока А минимален. Обычно минимальные числа в каждой строке обозначаются αi и выписываются в виде добавочного столбца матрицы (табл 2). В каждой строке будет свое α_i = min a_ij . Предпочтительной для игрока А является стратегия, при которой α_i обращается в максимум, т.е.

α = max(mina_ij), где α – гарантированный выигрыш (максимин).

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

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

β = min(maxaij), дает минимаксный выигрыш, или минимакс.

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

Если α = β = С, то число С называют чистой ценой игры или седловой точкой. Для игры с седловой точкой нахождение решения состоит в выборе пары максиминной и минимаксной стратегий, которые являются оптимальными, так как любое отклонение от этих стратегий приводит к уменьшению выигрыша первого игрока и увеличению проигрыша второго игрока по сравнению с ценой игры С.

Таблица 2

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

Результатом исследования игровой модели является определение наиболее осторожной стратегии поведение игрока, либо обеспечение гарантированного выигрыша (как правило, минимального), либо сведение к минимуму проигрыша. Риски при получении большого выигрыша не учитываются и не оцениваются.

Таким образом, результаты исследования игровых моделей указывают на оптимальную стратегию поведения (гарантированный выигрыш), а какой стратегией воспользуется игрок в реальной жизни – дело самого игрока.

1. Практическое применение теории игр в задачах моделирования экономических процессах

Пример №1

На базе торговой фирмы имеется n типов товара ассортиментного минимума. В магазин фирмы должен быть завезен только один из этих типов товара. Если товар типа j будет пользоваться спросом, то магазин от его реализации получит прибыль . Если же этот товар не будет пользоваться спросом, то издержки на его хранение принесут магазину убыток .Требуется выбрать тип товара, который целесообразно завезти в магазин.

В условиях неопределенного покупательского спроса конфликтная ситуация товароснабжения формализуется матричной игрой. Пусть первый игрок — магазин, второй игрок — покупательский спрос. Каждый из игроков имеет по n стратегий. Завоз i-го товара — i-я. стратегия первого игрока, спрос на j-й товар — j-я стратегия второго игрока. Тогда матрица выигрышей первого игрока имеет вид квадратной матрицы n-го порядка:

Пример №2

Матрица игры имеет вид:

Составим платежную матрицу и найдем в ней максимин и минимакс

Следовательно, данная игра имеет седловую точку (2, 3) и задача разрешима в чистых стратегиях. Придерживаясь чисто второй стратегии, первый игрок обеспечивает себе выигрыш, не меньший 5; второй игрок, применяя чистую третью стратегию, проигрывает не более 5. Обе стратегии j = 2 и j = 3 являются оптимальными для первого и второго игроков, при этом цена игры V = 5.

Пример №3

Диспетчер автобусного парка (ЛПР) в месяцы в конце каждой недели должен принять решение о целесообразности выделения дополнительных автобусов на загородный маршрут. ЛПР имеет три варианта решений: увеличить количество автобусов на 10 (стратегия ) увеличить это количество на 5 (стратегия Р₂) или оставить без изменения обычное число автобусов на линии (стратегия Р₃). Возможны два состояния погоды: —Q₁ плохая погода,Q₂ — хорошая погода, причем в момент принятия решения нет возможности определить ожидаемое состояние погоды. Если в выходные дни будет хорошая погода и много желающих выехать за город, а выделено мало автобусов, то парк понесет убытки, связанные с недополученной прибылью. Если же выделены дополнительные автобусы, а погода окажется плохой, то возникнут потери вследствие эксплуатации незаполненных автобусов.

Пусть, на основе анализа статистических данных за определенный период установлена функция потерь для возможных комбинаций состояний природы и решений ЛПР в виде матрицы игры А (Р_i,Q_i), в которой отрицательные значения показывают дополнительную прибыль, а положительные – потери: Q₁ Q₂

Если нет сведений о вероятностях различных состояний погоды, то по критерию Вальда и по критерию Сэвиджа оптимальной является стратегия Р₂. По критерию Гурвица при “коэффициенте пессимизма” q=1 оптимальной окажется стратегия Р₂, а при q=0 — стратегия Р₁.

Пример №4

Швейное предприятие, выпускающее детские платья и костюмы, реализует свою продукцию через фирменный магазин. Сбыт продукции зависит от состояния погоды. Но данным прошлых наблюдений предприятие в течении апреля — мая в условиях теплой погоды может реализовать 600 костюмов и 1975 платьев, а при прохладной погоде 1000 костюмов и 625 платьев. Известно, что затраты на единицу продукции в течение указанных месяцев составили для костюмов 27 руб., для платьев 8 руб., а цена реализации равна соответственно 48 руб. и 16 руб. (цифры условные).

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

Предприятие располагает в этих условиях двумя чистыми стратегиями: стратегия А — в расчете на теплую погоду и стратегия Б — в расчете на холодную погоду. Природу будим рассматривать как второго игрока также с двумя стратегиями: прохладная погода (стратегия В) и теплая погода (стратегия Г).

Если предприятие выберет стратегию А, то в случае прохладной погоды (стратегия природы В) доход составит: 600(48 — 27) + 625(16 — — (1975 — 625)8 = 6 800 руб., а в случае теплой погоды (стратегия природы Г) доход равен: 600(48 — 27) + 1 975(16 — = 28 400 руб.

Если предприятие выберет стратегию Б, то реализация продукции в условиях прохладной погоды даст доход: 1 000(48 — 27) + 625(16 — = 26 000 руб., а в условиях теплой погоды: 600(48 — 27) + 625(16 — — (1 000 — 600)27 = 6 800

Следовательно, матрица данной игры (платежная матица) имеет вид:

Первая и вторая строки этой матрицы соответствуют стратегиям А и Б предприятия, а первый и второй стратегиям В и Г природы.

По платежной матрице видно, что первый игрок (предприятие) никогда не получит доход меньше 6800. Но если погодные условия совпадают с выбранной стратегией, то выручка (выигрыш) составит 26 000 или 28 400. Отсюда можно сделать вывод, что в условиях неопределенности погоды наибольший гарантированный доход предприятие обеспечит, если будет попеременно применять то А, то стратегию Б. Такая стратегия называется смешанной. Оптимизация смешанной стратегии позволит первому игроку всегда получать выигрыша независимо от стратегии второго игрока.

Пусть х означает частоту применения первым игроком стратегии А, тогда частота применения им стратегии Б равна (1 — х). В случае оптимальной смешанной стратегии первый игрок (предприятие) получит и при стратегии В (холодная погода), и при стратегии Г (теплая погода) второго игрока одинаковый средний доход: 6800х + 26 000(1 — х) = 28 400х + 6800(1 — х). Отсюда можно найти, что х — 8/17; 1 — х = 9/17.

Следовательно, первый игрок, применяя чистые стратеги А и Б в соотношении 8:9, будет иметь оптимальную смешанную стратегию, обеспечивающую ему в любом случае средний доход в сумме: 6800-8/17 + 26000-9/17 16965 руб.; эта величина и будет в данном случае ценой игры.

Легко рассчитать, какое количество костюмов и платьев должно выпускать предприятие при оптимальной стратегии: (600 костюмов + 1975 платьев)*8/17 + (1000 костюмов + 625 платьев)*9/17 = 812 костюмов + 1260 платьев.

Следовательно, оптимальная стратегия предприятия заключи в выпуске 812 костюмов и 1260 платьев, что обеспечит три любой погоде средний доход в сумме 16 965 руб.

Заключение

На основании выше изложенного материала можно сделать вывод о том, что особое внимание при исследовании экономико-математических методов необходимо уделять принципам максимина и минимакса, ведь именно они могут упростить ряд экономических задач:

• снизить фактор сезонности в экономических процессах;

• приведению формул и примеров расчетов;

• рассмотрению ряда прикладных задач маркетинга, менеджмента и других областей управления в экономике;

• моделированию спроса и потребления;

• научному управлению запасами;

• анализу сетевого планирования и управления;

• аналитическому моделированию систем массового обслуживания;

• принятию решений на основе теории игр.

Так как я в своей работе особое внимание уделила теории игр, то, после рассмотрения ее более подробно, и в этой конкретной области можно сделать определенные выводы. Здесь представлены, на мой взгляд, более актуальные задачи:

• как получить набольшую выгоду или учет твоих интересов конкурентом, или поставщиком;

• какой товар лучше производить и т.д.

Список используемой литературы

1. Экономико-математические методы и прикладное моделирование / В.В. Федосеев. – М.: ЮНИТИ, 2002. — 391 с.

2. Математическое моделирование макроэкономических процессов / А.Н. Котов. – Л.: ЛГУ, 1980

3. Основы экономико-математического моделирования / Ю.Г. Семенов.1976

4. Экономико-математические методы / Л.Л. Терехов.– М.: Статистика–1972

5. Зенкевич Н.А., Петросян Л. А., Янг Д.В.К. Динамические игры и их приложения в менеджменте: учеб. Пособие / Н.А. Зенкевич, Л.А. Петросян, Д.В.К. Янг; Высшая школа менеджмента СпбГУ. — Спб.: Изд-во «Высшая школа менеджмента», 2009. — 415 с.

6. Лефевр Владимир Александрович, Смолян Георгий Львович Алгебра конфликта / Предисл. В.Н. Цыгичко. Изд. 5-е. М.: Книжный дом «ЛИБРОКОМ», 2013. — 72 с.

7. Hagen Lindstädt, Jürgen Müller. Making game theory work for managers — [Электронный ресурс] — Режим доступа. — URL: https://www.mckinseyquarterly.com/Making_game_theory_work_for_managers_2493# (дата обращения 22.02.13)