Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • В играх, не имеющих седловой точки, нижняя цена игры a всегда меньше верхней b.






    Установленный факт означает, что если игра одноходовая, то есть партнеры играют один раз, выбирая по одной чистой стратегии, то в расчете на разумно играющего про­тивника они должны придерживаться принципа минимакса, это гарантирует выигрыш V ³ a игроку А и проигрыш V £ b игроку В. Следовательно, при применении минимаксных стра­тегий величина платежа V ограничена неравенством

    a < V < b.

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

    Таким образом, мы приходим к выводу, что при неоднок­ратном повторении игры обоим игрокам следует менять свои стратегии. Тогда возникает вопрос: каким образом их ме­нять, чтобы в среднем выигрыш одного и проигрыш другого был аналогично одноходовой игре ограниченным снизу и сверху соответственно?

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

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

    Таким образом, смешанной стратегией SA игрока А называется применение чистых стратегий Al, А2,..., Ат с вероятностями p1, p2 ..., pm, причем сумма вероятностей равна 1, т.е.

    Смешанные стратегии игрока А записываются в виде строки РA = (p1, p2,.., pт).

    Аналогично смешан­ные стратегии игрока В обозначаются: QB = (q1, q2, …, qn).

    Сумма вероятностей появления стратегий также равна 1, т.е. ­

    Чистые стратегии можно считать частным случаем смешанных, и задавать строкой, в которой индекс i соответствует чистой стратегии.

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

    Таблица 3 – Общий вид платежной матрицы игры без седловой точки

      Стратегии игрока А   Вероятность выбора стратегии   Стратегии игрока В
    S1 S2 S3 Sn
    q1 q2 q3 qn
    R1 p1 a11 a12 a13   a1n
    R2 p1 a21 a22 a23   a2n
    R3 p1 a31 a32 a33   a3n
    Rm pm am1 am2 am3   amn

     

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

    Математически критерий минимакса при смешанных стратегиях записывается следующим образом:

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

     

    (2)

     

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

     

    (3)

     

    По существу игрок А стремится выбрать ту смешанную стратегию, которая обеспечивает максимум математического ожидания выигрыша, а игрок В – ту стратегию, которая обращает в минимум математическое ожидание проигрыша.

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

    Этот вывод следует из теоремы фон Неймана и минимаксе. Основная теорема теории игр (доказана фон Нейманом в 1928году) утверждает:

    каждая матричная игра с нулевой суммой имеет, по край­ней мере, одно решение, возможно, в области смешанных стратегий, то есть существуют стратегии R* и S*, оптималь­ные для обоих игроков, причем max min M(R; S) = min max M(R; S) и равен M(R*; S*).

    Примечание. Нулевая сумма означает, что выигрыш од­ного игрока равен проигрышу другого.

    Данная теорема утверждает, что выражения (1) и (2) при оптимальных стратегиях получают одно и тоже значение (число) V = M(R*; S*), называемое ценой игры.

    Если Ri* и Sj* - оптимальные решения для обоих игроков, то каждому элементу платежной матрицы aij соответствует вероятность, вычисляемая, как

    pi* x qj*.

    Следовательно, оптимальное ожидаемое значение игры

     

    .

     

    Из основной теоремы следует, что каждая конечная игра имеет цену и она лежит между нижней и верхней ценами игры

    a ≤ V b.

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

    Пусть R А* = (p1, p2,..., Pт) И SВ* = (q1, q2,..., qn) - пара опти­мальных стратегий. Если чистая стратегия входит в оптимальную смешанную стратегию с отличной от нуля вероятностью, то она называется активной.

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

    Эта теорема имеет большое практическое значение - она дает конкретные модели вычисления оптимальных стратегий при от­сутствии седловой точки.

    Решить конечную игру в смешанных стратегиях - получить векторы Р* = (p1, p2,..., Pт) и Q*= (q1, q2,..., qn) (получить оптимальные стратегии), удовлетворяющие теореме о минимаксе, и вычислить величину ожидаемого платежа M(R*; S*).,

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

    - аналитический метод;

    - графический метод;

    - метод сведения к задаче линейного программирования.

    Наиболее простое решение имеют игры с размерностью платежной матрицы 2 х 2.






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.