рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Теория игр

Теория игр - раздел Экономика, Конспект лекций ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ 8.5.1 Общие Понятия   В Конфликт­ных ...

8.5.1 Общие понятия

 

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

Игра — это совокупность правил, описывающих сущность кон­фликтной ситуации. Эти правила устанавливают:

─ выбор образа действия игроков на каждом этапе игры;

─ информацию, которой обладает каждый игрок при осуществлении таких выборов;

─ плату для каждого игрока после завершения любого этапа игры.

Игру можно определить следующим образом:

─ имеются n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;

─ сформулированы правила выбора допустимых стратегий, извест­ные игрокам;

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

─ всем игрокам (участникам игры) заранее известны платежи, со­ответствующие каждому возможному конечному состоянию.
Платежи задаются в виде матрицы

 

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

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

 

8.5.2 Игры двух лиц с нулевой сум­мой

 

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

Если первый игрок имеет m стратегий, а второй — n стратегий, то говорят, что имеют дело с игрой m×n. Рассмотрим игру m×n. Пусть заданы множество стратегий: для первого игрока {АI}, для второго игрока {Bj}, платежная матрица , где аij — выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi и Вj соответственно. Каждый из игроков выбирает однозначно с вероятностью 1 некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры бу­дет в чистых стратегиях. Поскольку интересы игроков противопо­ложны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш.

Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком про­водится при полном отсутствии информации о принимаемом ре­шении вторым игроком. И первый, и второй игрок являются разумными противниками, которые находятся в состоянии конфликта. Поэтому для решения игры двух лиц с нуле­вой суммой используется очень «пессимистичный» критерий, так называемый критерий минимакса-максимина. Основная особенность заключается в том, что ранее «природа» не рассматривалась как активный противник, тогда как в теории игр каждый игрок действует разумно и, следовательно, пытается активно помешать своему противнику. Так, если первый игрок применяет стратегию Ai то второй будет стремиться к тому, чтобы выбором соответствующей стратегии Bj свести выигрыш пер­вого игрока к минимуму, что равнозначно сведению своего проиг­рыша к минимуму. Величина этого минимума

. (32)

 

Первый игрок (при любых ответах противника) будет стремить­ся найти такую стратегию, при которой αi, обращается в максимум:

(33)

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

Аналогично определим по каждому столбцу матрицы , найдем минимальное значение β j:

(34)

 

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

Пример. Дана платежная матрица 3x4, которая определяет выигрыши игрока А. Вычислить нижнюю и верхнюю цены задан­ной игры.

Решение Представим нашу игру в виде следующей таблицы:

Если игрок А выбирает первую стратегию, он может получить выигрыш в размере 10, 4, 11 или 7 д. е. в зависимости от выбранной стратегии игроком В. При этом выигрыш игрока будет не меньше α1 = min{10; 4; 11; 7} = 4 д. е. независимо от поведения игрока В. Аналогично при выборе игроком А второй стратегии гарантирован­ный выигрыш α2 = min{7; 6; 8; 20} = 6 д. е. При выборе игроком А третьей стратегии выигрыш α3 = min{6; 23; 1; 11} = 1 д. е.

Таким образом, минимальные значения аi, i = 1,3 опреде­ляют минимально гарантированный выигрыш для игрока А, если он выбирает соответствующую стратегию i. Величина д.е. будет гарантированным выигрышем игрока А при любых стратегиях игрока В. Выбранная игроком А вторая стратегия называется максиминной стратегией, а соответствующее ее значение выигрыша α2 = 6 д. е. будет нижней ценой игры.

Второй игрок стремится минимизировать свой проигрыш. Вы­брав первую стратегию β1, игрок В может проиграть не более чем β1 = max{10; 7; 6} = 10 д. е. независимо от выбора стратегии игроком А. Аналогично рассуждая, получим следующие результаты (д. е.):

β2 = max{4; 6; 2} = 6; β3 = max{11; 8; 1} = 11;

β4 = max{7; 20; 11} = 20/

 

Игрок В выбирает стратегию β2, которая минимизирует его мак­симальные проигрыши:

Величина β = 6 д. е. будет гарантированным проигрышем игро­ка В при любых стратегиях игрока A. Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проигрыша β2 = 6 д. е. будет верхней ценой игры.

Следует отметить, что для любой матрицы выполняет­ся неравенство β ≥ α

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

Величина С = β = α называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при ис­пользовании ими оптимальных стратегий. В нашем примере цена игры С = 6 д. е., оптимальная пара стратегий — А2 и В2.

 

8.5.3 Понятия «доминирующий столбец» и «доминируе­мая строка»

 

Если в платежной матрице А все элементы строки Аi = (аi1, аi2, ..., ain) не меньше соответствующих элементов строки Ak = (ak1, ak2,…, akn), a no крайней мере один строго больше, то строка Ai- назы­вается доминирующей, а строка Ak доминируемой.

Аналогичны понятия «доминирующий столбец» и «доминируе­мая строка».

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

Пример Для игры с платежной матрицей A найдите стратегии игроков и цену игры.

 

Решение

Элемент a32 = -1 является наименьшим в третьей строке и на­ибольшим во втором столбце, т. е. он является седловой точкой. Поэтому цена игры С= -1, а оптимальные стратегии игроков: первого — А3, а второго — B2.

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

В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате полу­чится матрица

В матрице A1 первый и третий столбцы доминируют над вто­рым, следовательно, их можно изъять. В результате платежная ма­трица принимает вид

В матрице А2 вторая строка доминирует. После вычеркивания получится матрица A3, состоящая из одного элемента:

А3 = (-1). Элемент матрицы А3 и определяет решение задачи.

 

8.5.4 Понятие смешан­ной стратегии

 

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

(35)

где Pj — вероятность выбора i-й стратегии игроком и удовлетворяет следу­ющим условиям:

(36)

Аналогично смешанная стратегия игрока В представляет собой вектор

(37)

где qj — вероятность выбора j-й стратегии игроком В — удовлетворяет дующим условиям;

Платежная матрица игры имеет следующий вид:

Игрок А выбирает стратегию Pi, так, чтобы максимизировать на­именьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически критерий минимакса при смешанных стратегиях может быть опи­сан следующим образом. Игрок А выбирает стратегию Pi дающую

(38)

Игрок В выбирает стратегию qj, дающую

(39)

 

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

Этот вывод следует из теоремы фон Неймана о минимаксе. Те­орема утверждает, что выражения (38), (39) имеют одно и то же значение M(P0,Q0), называемое ценой игры. Если и — опти­мальные решения для обоих игроков, каждому элементу платежной матрицы aij соответствует вероятность *. Следовательно, оп­тимальное ожидаемое значение игры

(40)

Цена игры заключена между нижней и верхней ценами, т. е. α≤М(Р0, Q0) ≤β.

Решить конечную игру — это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимак­се, а следовательно, получить величину ожидаемого платежа М(Р0, Q0) – цену игры.

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

Решение игры обладает одним важным свойством: если игрок А использует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока А не уменьшается. Стратегии, которые смешиваются для получе­ния оптимальной стратегии, будем называть полезными. Доказано, что у игры m×n существует такое оптимальное решение, что чис­ло полезных стратегий с каждой стороны не превосходит мини­мального из чисел тип. Известно несколько методов нахождения оптимальных стратегий в играх двух лиц с нулевой суммой. Рас­смотрим один из методов — метод линейного программирования для нахождения решения игр.

 

– Конец работы –

Эта тема принадлежит разделу:

Конспект лекций ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ

ГОУ ВПО КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ... УНИВЕРСИСТЕТ Кафедра вычислительной техники и АСУ...

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Понятие имитационного моделирования
  Имитационное моделирование (ИМ) – распространённая разновидность аналогов моделирования, реализуемого с помощью набора математических инструментальных средств, специальных имитирующ

Основные функции ИМ
  Для создания ИМ необходима специальная система моделирования, имеющая набор языковых средств, сервисные подпрограммы, приёмы и технологии программирования. ИМ должна отражать большо

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

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

Определение параметров линейного однофакторного уравнения регрессии
Пусть у нас имеются данные о доходах ( x ) и спросе на некоторый товар ( y ) за ряд лет ( n ): Год i Доход x

Оценка величины погрешности линейного однофакторного уравнения
  1. Обозначим разность между фактическим значением результативного признака и его расчетным значением как u i :

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

Двухфакторные и многофакторные уравнения регрессии
  Линейное двухфакторное уравнение регрессии имеет вид где a , b 1 , b

Конструирования целевой функции
  Допустим, объект оптимизации описывается следующей системой уравнений: х2 + у2 = 1 х + у = 1 Графически эту систему можно представит

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

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

Оптимизационные задачи с линейной зависимостью между переменными
  Пусть: b i количество ресурса вида i ( i = 1, 2, ..., m ); a i , j норма расхода

Геометрическая интерпретация ОЗЛП
  Пусть необходимо найти оптимальный план производства двух видов продукции ( x 1 и x 2 ), т.е. такой план, при котором целевая функция (общая приб

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

Решение двойственной задачи ЛП
  Оптимизационная модель прямой задачи линейного программирования выглядит так: В системе неравенств должны

Общие понятия систем массового обслуживания
  Системы массового обслуживания — это такие системы, в кото­рые в случайные моменты времени поступают заявки на обслужи­вание, при этом поступившие заявки обслуживаются с помощью име

Одноканальная СМО с ожиданием
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивно­стью λ,. Интенсивность потока обслуживания равна μ, (т. е. в сред­не

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

Непрерывное моделирование
  Непрерывное моделирование — это моделирование системы по времени с помо­щью представления, в котором переменные состояния меняются непрерывно по отношению ко времени. Как правило, в

Теоретические основы метода
  Метод статистического моделирования (или метод Монте-Кар­ло) — это способ исследования поведения вероятностных систем (экономических, технических и т. д.) в условиях, когда не извес

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

Постановка задачи
  Компании, продающей один вид продукции, необходимо определить, какое коли­чество товара она должна иметь в запасе на каждый из последующих n мес. (n — заданный входной параметр). Пр

Постановка задачи
Под термином «транспортные задачи» понимается широкий круг задач не только транспортного характера. Общим для них яв­ляется, как правило, распределение ресурсов, находящихся у т производител

Алгоритм метода потенциалов
  Наиболее распространенным методом решения транспортных задач является метод потенциалов. Решение задачи методом потенциалов включает следующие этапы: 1. разработку

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

Принятие решений в условиях риска
  Основными критериями оценки принимаемых решений в усло­виях риска являются: - ожидаемое значение результата; - ожидаемое значение результата в сочетании с минимиза

Принятие решений в условиях неопределенности
    Неопределенность является характеристикой внешней среды (природы), в которой принимается управленческое решение о раз­ витии (или функционировании) экономиче

Критерий Лапласа.
Этот критерий опирается на «принцип недостаточного основания» Лапласа, согласно которому все состояния «природы» Si, i = 1,n полагаются равновероятными. В соответствии с этим прин­ципом каждому сос

Метод линейного программирования для нахождения оптимальных стратегий в играх двух лиц с нулевой суммой
  Пусть игра m×n не имеет оптимального решения непосредст­венно в чистых стратегиях, т. е. отсутствует седловая точка (α ≠ β). Оптимальное решение необходимо иск

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги