Онлайн калькулятор теория игр: Онлайн-калькулятор по теории игр

Онлайн-калькулятор по теории игр

Примеры решенийМетод Брауна Системы массового обслуживанияМатрица рисков Седловая точка Платежная матрица Цена игрыСмешанные стратегии Матричная игра онлайн Чистые стратегии

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

Раздел «Теория игр» представлен тремя онлайн-калькуляторами:

  1. Оптимальные стратегии игроков. В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры. Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
    1. Минимакс. Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
    2. Симплекс-метод. Используется для решения игры в смешанных стратегиях методами линейного программирования.
    3. Графический метод. Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
    4. Итерационный метод Брауна-Робинсона. Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
    Например, задание может звучать как «указать оптимальные стратегии игроков для игры, заданной платежной матрицей».
    Во всех методах применяется проверка на доминирующие строки и столбцы.
  2. Биматричная игра. Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
  3. Игры с природой. Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда, Сэвиджа, Гурвица.
    Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
    Для критерия Гурвица укажите уровень оптимизма λ. Если в условиях данный параметр не задан можно использовать значения 0, 0.5 и 1.
  4. Аддитивный критерий оптимальности. Этот сервис используется, если требуется выбрать определенную стратегию среди множества других по заданным критериям с указанием их важности.
    Варианты (стратегии)Производительность. шт./часСтоимость оборудования. ден. ед.Энергоемкость. у.е.Надежность. у.е.
    Завода I5756
    Завода II3473
    Завода III4624
    Вес критерия, λj0. 40.20.10.3

Во многих задачах требуется находить решение средствами ЭВМ. Одним из инструментов служат вышеприведенные сервисы и функции Excel.

Задать свои вопросы или оставить замечания можно внизу страницы в разделе Disqus.
Можно также оставить заявку на помощь в решении своих задач у наших проверенных партнеров (здесь или здесь).

Теория игр. Матричные игры. Онлайн калькулятор

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

Очистить все ячейки?

Бывают ситуации, в которых сталкиваются интересы двух и более сторон. При этом эффективность принимаемого решения одной стороны зависит от действий другой стороны. Такие ситуации называются конфликтными. Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной стороны на определенную величину приводит к уменьшению выигрыша другой стороны на такую же величину. Математическая модель таких ситуаций описывается матричной игрой. Участники игры (т.е. лица, принимающие решение) называются игроками. Принятие игроком того или иного решения в процессе игры и его реализация называется ходом. Ходы могут быть личными (т.е. сознательными) и случайными. Стратегия игрока − осознанный выбор одного из множества вариантов его действий. Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока есть m чистых стратегий, а у второго игрока n чистых стратегий. Если множество стратегий игроков конечный, то игра называется конечной, а если хотя бы у одного игрока множество стратегий бесконечно, то игра называется бесконечной. Стратегия игрока называется оптимальной, если она обеспечивает данному игроку (при многократном повторении) максимально возможный средний выигрыш или минимально возможный средний проигрыш.

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

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

Рассмотрим матричную игру двух участников с нулевой суммой и конечным числом возможных ходов.

Решение матричной игры в чистых стратегиях

Пусть игроки A и B распологают конечным числом возможных действий (чистых стратегий). Обозначим их через и , соответственно. Игрок A может выбрать чистую стратегию . В ответ на этот выбор, игрок B может выбрать чистую стратегию . Выбор стратегии первого игрока и ответный выбор стратегии игрока B единственным образом определяет результат aij выигрыш игрока A или проигрыш игрока B.

Таким образом игра с нулевой суммой однозначно определяется матрицей

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

Игра проходит партиями. Партия начинается с первого игрока. Он выбирает некоторую строку i матрицы. В ответ на это второй игрок выбирает некоторый столбец j. На этом заканчивается партия и второй игрок платит первому сумму aij, если aij>0 или первый игрок платит сумму aij второму игроку, если aij<0. Цель каждого игрока − выиграть как можно большую (или проиграть как можно меньшую) сумму в результате большого числа партий.

Чтобы определить наилучшие стратегии игроков, мы предполагаем, что участники разумны, т.е. делают все, чтобы добится наилучшего результата для себя. Методом логических рассуждений найдем наилучшую стратегию игрока A. Для этого проанализируем по шагам все его стратегии. Выбирая стратегию Ai (строка i) игрок A должен рассчитывать, что игрок B должен ответить такой стратегией Bj (столбец j), чтобы выигрыш первого игрока был бы минимальным. Поэтому найдем для каждой строки минимальное число:

Зная для каждой строки число αi (i=1,2,…m) игрок A должен выбрать ту стратегию, при котором его выигрыш будет максимальным:

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

Рассмотрим, теперь, игру со стороны игрока B. Игрок B заинтересован уменьшить свой проигрыш (или минимизировать выигрыш игрока A. Поэтому для каждого столбца он оценивает свой максимальный проигрыш в связи с тем, какую стратегию i выберет игрок A:

Зная для каждого столбца число βj (j=1,2,…n), игрок B должен выбирать ту стратегию, при котором его проигрыш будет минимальным:

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

Теорема 1. В матричной игре нижняя цена игры не превосходит верхней цены, т.е. α ≤ β.

Действительно:

Если для чистых стратегий Ak и Bl игроков A и B имеет место равенство α = β, то пару чистых стратегий (Ak,Bl) называют седловой точкой матричной игры а γ=α = β чистой ценой игры. Элемент akl называют седловым элементом платежной матрицы.

Заметим, что отклонение игрока A от максимальной стратегии Ak ведет к уменьшению его выигрыша, а отклонение игрока B от минимальной стратегии Bl ведет к увеличению его проигрыша. Поэтому Ak и Bl являются оптимальными чистыми стратегиями игроков A и B, соответственно.

Тройку (Ak, Bl, γ) называют решением матричной игры. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Решение матричной игры в смешанных стратегиях

Если матричная игра не имеет седловой точки, то α ≠ β, и, Теорему 1, получим: α < β. Получается, что применение минимаксных стратегий приводит к тому, что выигрыш игрока A не больше α, а проигрыш игрока B не больше β. В этом случае решение матричных игр находят в смешанных стратегиях.

Смешанной стратегией игрока A называется вектор , где

pi− вероятность, с которой игрок A выбирает свою чистую стратегию Ai.

Смешанной стратегией игрока B называется вектор , где

qj− вероятность, с которой игрок B выбирает свою чистую стратегию Bj.

Замемим, что чистые стратегии являются частным случаем смешанных стратегий. Если, например игрок A выбрал чистую стратегию A3, то это означает, что вероятность ее выбора равна 1, т.е. . Средняя величина выигрыша игрока A (или проигрыша игрока B) определяется по формуле математического ожидания:

Функция M(p,q) называется платежной функцией матричной игры с матрицей. Смешанные стратегии p* и q* называются оптимальными, если они образуют седловую точку для платежной функции M(p,q), т.е.

Значение платежной функции при оптимальных смешанных стратегиях p* и q* называют ценой игры:

Теорема 2 (Основная теорема теории матричных игр). В любой матричной игре у игроков есть оптимальные смешанные стратегии.

Доказательство. Пусть игра имеет платежную матрицу

где все элементы положительны.

Пусть и − смешанные стратегии игроков A и B , соотвестстенно.

Математическое ожидание выигрыша игрока A равна:

При любом выборе игроками своих смешанных стратегий p и q, математическое ожидание будет положительным, так как все элементы aij платежной матрицы положительны, pi неотрицательные числа и среди них есть хотя бы одно положительное число, qj неотрицательные числа и среди них есть хотя бы одно положительное число.

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

так как aij >0, i=1,2,…m, j=1,2,…n. Поскольку α>0 и γ не может быть меньше нижней цены игры, то γ ≥ α, а так как α>0, то γ >0.

Пусть игрок A выбирает такую стратегию p, что математическое ожидание его выигрыша независимо от того, какую стратегию выбирает игрок B было не меньше некоторой величины γ:

где pi >0, i=1,2,…m, . Каждая строка в системе линейных неравенств (3) соотвесттвует определенной стратегии игрока B.

Преобразуем систему нерравенств (3), введя новые обозначения:

Разделим все неравенства системы (3) на положительное число γ. Тогда имеем:

yi >0, i=1,2,…m.

При этом

Цель игрока A − максимизировать свой гарантированный выигрыш γ или минимизировать величину

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

Сделав аналогичные рассуждения с позиции игрока B, получим следующую задачу линейного программирования:

Покажем, что задачи линейного программирования (4) и (5) имеют допустимые решения. Так как aij >0, то можно подобрать достаточно большие положительные числа yi, i=1,2,…m так, чтобы выполнялись неравенства (4b). Значит задача линейного программирования (4) имеет допустимое решение.

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

Цена игры равна:

Найдем оптимальные смешанные стратегии игроков:

Тогда

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

Если в матрице есть отрицательные элементы или нули, то можно сделать матрицу положительным, добавив к каждому элементу матрицы достаточно большое положительное число r. Тогда получим следующую матрицу A’(aij+r).

Математическое ожидание выигрыша игрока A с платежной матрицей A(aij):

Математическое ожидание игрока A с платежной матрицей A’(aij+r):

Тогда

Игра с платежной матрицей A’ имеет седловую точку в смешанных стратегиях:

Следовательно, игра с платежной матрицей A также имеет седловую точку в смешанных стратегиях а цена игры с платежной матрицей A равна:

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


Калькулятор Theory of Moves (ToM) — Обмен файлами

Теперь вы подписаны на эту передачу

  • Вы можете получать электронные письма, в зависимости от ваших предпочтений в общении
  • Версия 1.0.0.0 (390 КБ) от Enrique M. Quilis

    Определяет неблизорукое равновесие (NME) в порядковых играх 2×2 в соответствии с Теорией ходов (ToM).

    115 загрузок Все время: 115″>

    Обновлено 4 января 2017 г.

    Посмотреть лицензию

    • Обзор
    • Функции
    • История версий
    • Отзывы (0)
    • Обсуждения (0)

    Набор функций MATLAB, которые вычисляют (NME) порядковых игр 2×2 в соответствии с Теорией ходов (ToM), предложенной Брамсом (1994) «Теория ходов», гл. 1. Основная идея ToM состоит в том, что оба игрока делают ходы, проецируя достаточно вперед в будущее, но предполагая, что циклы следует пропустить, чтобы избежать блокировки игры. Чтобы принять решение, каждый игрок смотрит вперед и использует обратную индукцию, чтобы решить, будет ли ход выгодным или нет. Дополнительные сведения см. в прикрепленном pdf.

    Цитировать как

    Энрике М. Куилис (2023). Калькулятор теории ходов (ToM) (https://www.mathworks.com/matlabcentral/fileexchange/59).764-theory-of-moves-tom-calculator), MATLAB Central File Exchange. Проверено

    16 апреля 2023 г. .

    Совместимость версий MATLAB

    Created with R2013a

    Совместимость с любой версией

    Совместимость с платформами
    Windows macOS Linux

    Категории
    • Игры > Стратегия и логика >

    Узнайте больше на Стратегия и логика в Справочном центре и MATLAB Answers

    Охота за сокровищами сообщества

    Найдите сокровища в MATLAB Central и узнайте, как сообщество может вам помочь!

    На охоту!

    Версия Опубликовано Примечания к выпуску
    1. 0.0.0

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

    Выберите веб-сайт

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

    Вы также можете выбрать веб-сайт из следующего списка:

    Европа

    Обратитесь в местный офис

    Программные инструменты для теории игр вычисления в теории игр. С Gambit вы можете строить, анализировать, и исследовать игровые модели.

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

    Gambit — это кроссплатформенная версия : Получить для Microsoft Windows, Mac ОС Х или Линукс.

    Начало работы

    Гамбит 16

    Гамбит 16 — текущая версия Гамбита.

    Документация Gambit 16 · Скачать последняя (16.0.2)

    Расширение Python

    НОВИНКА! Gambit теперь доступен как расширение Python, пигамбит. Пользователи Python могут установить с помощью обычного pip install pygambit. Поддерживаются версии Python с 3.7 по 3.10 включительно.

    Исследователь теории игр

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

    документация по ГТД · Запустите в своем браузере

    Введение в учебник

    Доступны некоторые вводные руководства, основанные на учебник по практическим вычислениям в теория игр EC’16: 17-й ACM Конференция по экономике и вычислениям одновременно с GAMES 2016, Пятым Всемирным конгрессом Общества теории игр.

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

    Использование и цитирование Gambit

    Gambit — это бесплатное программное обеспечение с открытым исходным кодом, выпущенное в соответствии с условиями Стандартной общественной лицензии GNU.

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

    Если Гамбит был вам полезен при написании научной статьи, предлагаем ссылку вида:

    МакКелви, Ричард Д., МакЛеннан, Эндрю М. и Туроси, Теодор Л. (2016). Гамбит: программные инструменты для теории игр, версия 16.0.1. http://www.gambit-project.org.

    Замените номер версии и год, если вы используете разный выпуск.

    Благодарности

    Проект Gambit благодарит Университет Восточной Англии за текущее сопровождение проекта; Калифорнийский технологический институт и Национальный научный фонд за поддержку проекта с 1994 по 2001 год, а также в 2011, 2012 и 2014 годах выпуски Google Summer of Код.

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *