Кафедра ИСиТ УО ВГТУ
  • Специальности
    • Экономика электронного бизнеса
    • Информационные системы
    • Information Control Systems
  • Каталог
  • Сайт кафедры
  • Сервисы
    • GitLab
    • ownCloud
    • JupyterHub
    • JupyterHub 2
    • VNC
    • Soft
  1. ИСиТ
  2. РиОИИС
  3. Теория
  4. Теория игр
  • ИСиТ
    • АОС
      • Теория
        • Введение в операционные системы
        • Управление памятью
        • Управление процессами
        • Система ввода-вывода
        • Информационная безопасность
        • Виртуализация
      • Практика
    • РВПсИПП
      • Теория
        • Настройка среды разработки для PHP
        • Разработка web-приложений на базе фреймворков
        • Основы Laravel
        • Шаблоны в Laravel
        • Модели и базы данных в Laravel
        • Формы и валидация в Laravel
        • Аутентификация и авторизация в Laravel
        • Создание REST API в Laravel
        • Работа с файлами и изображениями в Laravel
        • Тестирование и отладка в Laravel
        • Введение в фреймворк Symfony
        • Маршруты и контроллеры в Symfony
        • Шаблоны и Twig в Symfony
        • Формы и валидация в Symfony
        • Доступ к базам данных в Symfony
        • Аутентификация и авторизация в Symfony
        • Сервисы и зависимости в Symfony
        • Создание REST API в Symfony
        • Работа с файлами и медиа в Symfony
        • Сравнение и выбор фреймворка
        • Развертывание веб-приложения
      • Практика
        • Лаб. работа 1 “Создание нового приложения Laravel”
        • Лаб. работа 2 “Добавление главной страницы и базовых маршрутов”
        • Лаб. работа 3 “Создание моделей, миграций и сидеров”
        • Лаб. работа 4 “Создание индексных страниц и пагинация”
        • Лаб. работа 5 “Создание форм для работы с сущностями”
        • Лаб. работа 6 “Работа с файлами (эмуляция S3-хранилища)”
        • Лаб. работа “Создание маршрутов в Laravel”
        • Лаб. работа “Работа с базами данных в Laravel”
        • Лаб. работа “Работа с формами в Laravel”
        • Лаб. работа “Аутентификация и авторизация в Laravel”
        • Лаб. работа “Работа с файлами в Laravel”
        • Лаб. работа “Тестирование и оптимизация в Laravel”
        • Лаб. работа “Создание REST API в Laravel”
        • Лаб. работа “Основы Symfony”
        • Лаб. работа “Шаблоны и представления в Symfony”
        • Лаб. работа “Работа с базами данных в Symfony”
        • Лаб. работа “Фомы и аутентификация в Symfony”
        • Лаб. работа “Сервисы и зависимости в Symfony”
        • Лаб. работа “REST API в Symfony”
        • Лаб. работа “Работа с медиа контентом в Symfony”
        • Лаб. работа “Создание и развертывание проекта”
    • ПСП
      • Теория
        • Введение
        • Протокол HTTP
        • Программирование с использованием сокетов
        • Введение в PHP
        • Работа с базами данных в PHP
        • Объектно-ориентированные возможности PHP
        • Настройка среды разработки для PHP
        • Разработка web-приложений на базе фреймворков
      • Практика
        • Программное обеспечение
        • Регистрация в JupyterHub
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Основы PHP”
        • Лаб. работа “Массивы в PHP”
        • Лаб. работа “Создание веб-приложений с использованием Slim”
    • Компьютерные сети
      • Теория
        • Введение в компьютерные сети
        • Топологии сетей
        • Кодирование и мультиплексирование
        • Стеки протоколов
        • Адресация в компьютерных сетях
        • Система доменных имен (DNS)
        • Программирование с использованием сокетов
        • Введение в PHP
        • Протокол HTTP
        • Введение в компьютерные сети
      • Практика
        • Программное обеспечение
        • Регистрация в JupyterHub
        • Лаб. работа “Почтовые протоколы”
        • Лаб. работа “Протокол FTP”
        • Лаб. работа “Протокол HTTP”
        • Лаб. работа “Программирование сетевых приложений с использованием сокетов”
        • Лаб. работа “Основы PHP”
        • Лаб работа “Массивы в PHP”
    • РиОИИС
      • Теория
        • Классификация оптимизационных задач
        • Генетические алгоритмы
        • Системы массового обслуживания
        • Теория игр
        • Машинное обучение
        • Глубокое обучение (Deep learning)
        • Основы функционального программирования
        • Основы программирования на Haskell
        • Введение в логическое программирование
        • Инференция и рассуждения в логическом программировании
        • Разработка экспертных систем
        • Интеллектуальные системы и их архитектура
        • Веб-скрэйпинг
        • Сбор данных с открытых API
      • Практика
        • JupyterHub
        • Лаб. работа “Методы одномерной оптимизации”
        • Лаб. работа “Методы многомерной оптимизации”
        • Лаб. работа “Функции в Python”
        • Лаб. работа “Рекурсия в Python”
        • Лаб. работа “Итераторы в Python”
        • Лаб. работа “Генетические алгоритмы”
        • Лаб. работа “Haskell”
        • Лаб. работа “Логическое программирование”
        • Лаб. работа “Сбор данных с помощью веб-скрейпинга”
    • КСКР
      • Практика
        • Лаб. работа “Одномерные и двумерные массивы в C#”
        • Лаб. работа “Обращение матриц в C#”
    • Системное программирование
      • Теория
        • Управление памятью в Windows
        • Файловые операции в Windows
        • Управление процессами в Windows
        • Графический интерфейс Windows
        • ОС Unix
      • Практика
        • Лаб. работа “Работа с динамической памятью в Windows”
        • Лаб. работа “Операции с файлами в Windows”
        • Лаб. работа “Управление процессами в Windows”
        • Лаб. работа “Работа с виртуальной машиной Linux”
        • Лаб. работа “Язык командного энтерпритатора Shell”
        • Лаб. работа “Работа с файлами в Linux”
        • Лаб. работа “Работа с процессами в Linux”

Содержание

  • Введение в теорию игр
  • Основные понятия в теории игр
  • Классификация игр
  • Решение игр
  • Матричные игры
  • Практические примеры и приложения
  • Основная критика и ограничения теории игр
  • Заключение
  • Значение теории игр в современном мире
  • Перспективы развития теории игр
  • Игры с природой

Другие форматы

  • RevealJS
  1. ИСиТ
  2. РиОИИС
  3. Теория
  4. Теория игр

Теория игр

Разработка и оптимизация интеллектуальных информационных систем
Теория
Автор
принадлежность

Бизюк Андрей

ВГТУ

Дата публикации

3 декабря 2024 г.

Введение в теорию игр

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

Основные понятия в теории игр:

  1. Игроки: В теории игр предполагается наличие хотя бы двух игроков, которые участвуют в игре и принимают стратегические решения.

  2. Стратегии: Каждый игрок имеет определенное множество стратегий, которые определяют его действия в игре. Выбор конкретной стратегии влияет на исход игры.

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

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

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

Применение теории игр:

Теория игр имеет широкое применение в различных областях, включая:

  1. Экономика: Исследование конкуренции, ценообразования, аукционов и стратегий на рынке.

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

  3. Биология: Изучение эволюции стратегий в биологических популяциях и сотрудничества в живых системах.

  4. Социология: Исследование социальных конфликтов, кооперации и взаимодействия в обществе.

  5. Искусственный интеллект: Применение теории игр в разработке алгоритмов и стратегий для компьютерных программ.

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

Основные понятия в теории игр

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

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

  2. Стратегии: Стратегии определяют действия, которые игрок может предпринять в рамках игры. Каждый игрок имеет свое множество стратегий. Выбор конкретной стратегии влияет на исход игры.

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

  4. Выигрышная функция: Это математическая функция, которая связывает выбор стратегий игроков с их выигрышами. Она описывает, как изменение стратегий влияет на результаты игры.

  5. Нормальная форма игры: В нормальной форме игры представлены все возможные стратегии для каждого игрока и их соответствующие выигрыши. Это один из способов формализации игры.

  6. Расширенная форма игры: В расширенной форме игры описывается последовательность ходов, информация, доступная игрокам, и определение того, какие ходы являются допустимыми.

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

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

  9. Доминирующие и доминируемые стратегии: Доминирующая стратегия - это стратегия, которая всегда приносит игроку больший выигрыш независимо от выбора стратегии других игроков. Доминируемая стратегия - это стратегия, которая всегда приносит игроку меньший выигрыш.

  10. Смешанные стратегии: Иногда игроки могут смешивать свои стратегии с некоторой вероятностью. Смешанные стратегии позволяют моделировать случайные или неразрешимые ситуации.

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

Классификация игр

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

  1. По сумме выигрышей:
    • Игры с нулевой суммой: В таких играх выигрыши одного игрока равны убыткам другого игрока. Сумма выигрышей всех игроков равна нулю.
    • Игры с ненулевой суммой: Здесь сумма выигрышей игроков может быть как положительной, так и отрицательной, и выигрыши одного игрока не обязательно равны убыткам другого.
  2. По кооперативности:
    • Кооперативные игры: Игроки могут сотрудничать друг с другом для достижения общей цели. В кооперативных играх возможно соглашение между игроками о распределении выигрышей.
    • Некооперативные игры: Игроки действуют независимо друг от друга и не могут заключать формальные соглашения о распределении выигрышей.
  3. По информации и времени:
    • Игры с полной информацией: Игроки знают все о стратегиях и выигрышах других игроков.
    • Игры с неполной информацией: Игроки не имеют полной информации о стратегиях и выигрышах других игроков.
    • Игры в реальном времени: Игроки принимают решения одновременно или быстро, без возможности наблюдения за ходами других игроков.
    • Игры с последовательными ходами: Игроки делают ходы поочередно, и каждый игрок видит ходы предыдущих.
  4. По числу игроков:
    • Двухигровые игры: В игре участвуют только два игрока.
    • Многопользовательские игры: В игре участвует более двух игроков.
  5. По стратегическим характеристикам:
    • Симметричные игры: Игроки имеют одинаковые стратегические возможности и интересы.
    • Асимметричные игры: Игроки имеют различные стратегические возможности и интересы.
  6. По характеру действий:
    • Дискретные игры: Игроки делают конечное число дискретных ходов.
    • Непрерывные игры: Игроки могут совершать бесконечное число действий в течение определенного интервала времени.
  7. По времени итераций:
    • Одноразовые игры: Игра происходит только один раз, и игроки не имеют возможности изменить свои стратегии в будущем.
    • Повторяющиеся игры: Игра происходит несколько раз, и игроки могут учитывать результаты предыдущих итераций при принятии решений.

Это основные способы классификации игр, и каждый из них может быть дополнен или адаптирован в зависимости от конкретных аспектов, которые вы хотите выделить при анализе определенной игры.

Решение игр

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

  1. Доминирующие стратегии: Этот метод заключается в поиске стратегий, которые всегда приносят игроку больший выигрыш, независимо от выбора стратегий других игроков. Если найдены доминирующие стратегии, они могут быть использованы в качестве оптимальных стратегий.

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

  3. Смешанные стратегии: В случае, если игроки не имеют доминирующих стратегий или не существует РПН в чистых стратегиях, можно исследовать смешанные стратегии. Это означает, что игроки могут смешивать свои стратегии с некоторой вероятностью. Решение сводится к нахождению оптимальных вероятностных распределений стратегий.

  4. Методы решения конкретных видов игр:

    • Для игр с нулевой суммой часто используется симплекс-метод для нахождения оптимальных стратегий.
    • Игры в форме матрицы могут быть решены с помощью методов линейного программирования.
    • В повторяющихся играх могут применяться эволюционные методы.
  5. Алгоритмические и численные методы: Для сложных игр, особенно с большим числом стратегий и игроков, могут применяться численные методы, такие как метод Монте-Карло, метод динамического программирования или методы оптимизации.

  6. Экспериментальные методы: В реальных ситуациях и экспериментах можно определить оптимальные стратегии путем анализа поведения игроков в контролируемых условиях.

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

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

Матричные игры

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

Основные характеристики матричных игр:

  1. Игроки: В матричной игре обычно участвуют два игрока, но она также может быть обобщена до случая большего числа игроков.

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

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

  4. Цель: Целью игроков является максимизация своего выигрыша или минимизация своих потерь, в зависимости от конкретных правил игры.

Пример матричной игры (игра в нулевой сумме):

Стратегия A Стратегия B Стратегия C
Игрок 1 2 3 -1
Игрок 2 0 4 2

В этом примере игрок 1 имеет 3 стратегии (A, B, C), а игрок 2 имеет 3 стратегии (A, B, C). Каждый элемент матрицы указывает, сколько выигрыша (положительного или отрицательного) получит игрок 1, если оба игрока выберут соответствующие стратегии.

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

Практические примеры и приложения

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

  1. Экономика:
    • Конкуренция и монополия: Теория игр используется для анализа стратегий компаний на рынке, определения цен и объемов производства.
    • Аукционы: Торговые аукционы и аукционы с ограниченной информацией изучаются с использованием теории игр.
    • Стратегии ценообразования: Фирмы могут применять теорию игр для оптимизации стратегий ценообразования и продвижения товаров.
  2. Политика:
    • Международные отношения: Теория игр используется для анализа конфликтов, договоров, переговоров и стратегий государств в мировой политике.
    • Выборы: Исследования выборов и политических кампаний могут быть проведены с использованием теории игр для моделирования поведения избирателей и кандидатов.
  3. Биология:
    • Эволюционная биология: Теория игр применяется для исследования стратегических взаимодействий в биологических популяциях, таких как борьба за ресурсы и сотрудничество между организмами.
    • Экология: Взаимодействие между видами и распределение ресурсов может быть исследовано с использованием теории игр.
  4. Социология:
    • Социальные сети: Анализ социальных сетей и влияния в них может быть выполнен с помощью теории игр.
    • Конфликты и сотрудничество: Исследование социальных конфликтов и сотрудничества между индивидами и группами.
  5. Искусственный интеллект:
    • Игры и робототехника: Теория игр используется для разработки стратегий и управления взаимодействием между роботами и искусственными агентами.
    • Обучение машин: Разработка алгоритмов обучения машин и искусственного интеллекта на основе теории игр.
  6. Социальные науки:
    • Эксперименты и исследования: Теория игр используется в психологии, экономической и социологической науке для проведения экспериментов и анализа социального поведения.
  7. Философия:
    • Этика и принятие решений: Исследование этических дилемм и принятия решений с использованием теории игр для анализа моральных и этических вопросов.

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

Основная критика и ограничения теории игр

Теория игр - мощный инструмент для анализа стратегических ситуаций, но она также имеет свои ограничения и критику. Вот некоторые из основных ограничений и критик:

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

  2. Информационные ограничения: В реальных ситуациях часто существуют ограничения на доступ к информации, и игроки могут не иметь полной информации о стратегиях и выигрышах других игроков. Теория игр, предполагающая полную информацию, не всегда применима.

  3. Неполная спецификация модели: Определение выигрышей и стратегий в игре может быть сложным и часто зависит от субъективных оценок. Это может создавать неопределенность и споры при анализе игры.

  4. Игнорирование эволюции стратегий: Теория игр фокусируется на статических равновесиях и не учитывает процесс изменения стратегий и адаптации игроков с течением времени.

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

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

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

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

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

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

Заключение

Значение теории игр в современном мире

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

  1. Экономика:
    • Конкуренция и ценообразование: В бизнесе теория игр помогает предсказывать и анализировать стратегии конкурентов и оптимизировать ценообразование.
    • Аукционы: В аукционной торговле теория игр используется для определения стратегий участников и оптимизации результатов.
  2. Политика:
    • Международные отношения: Теория игр помогает анализировать стратегии государств и прогнозировать результаты международных конфликтов и договоров.
    • Голосование и выборы: Исследования в области теории игр могут предсказывать и анализировать стратегии кандидатов и избирателей.
  3. Биология:
    • Эволюция и поведение вида: Теория игр используется для изучения стратегических взаимодействий в биологических популяциях, включая сотрудничество и конкуренцию между организмами.
  4. Искусственный интеллект:
    • Разработка алгоритмов: Теория игр помогает создавать алгоритмы для роботов и искусственных агентов, позволяя им принимать стратегические решения.
  5. Социология:
    • Социальные сети: Теория игр анализирует стратегические взаимодействия в социальных сетях и влияние в них.
    • Социальные конфликты и сотрудничество: Исследование стратегических действий и решений в конфликтных и сотруднических сценариях.
  6. Исследования поведения человека:
    • Экспериментальные исследования: Теория игр используется в экспериментах, чтобы понять, как люди и организации принимают решения и взаимодействуют в различных ситуациях.
  7. Безопасность и оборона:
    • Стратегии вооруженных конфликтов: Военные стратегии и сценарии анализируются с помощью теории игр для прогнозирования и оптимизации тактик.

Перспективы развития теории игр

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

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

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

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

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

  5. Экономика и финансы: В сфере экономики и финансов теория игр будет использоваться для анализа рисковых сценариев, рынков и стратегий инвестирования.

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

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

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

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

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

Игры с природой

Пример. Игра “Поставщик”.

Выпуск продукции фирмы существенно зависит от скоропортящегося материала, например, молока или ягод, поставляемого партиями стоимостью 100ед. Если поставка не прибывает в срок, фирма теряет 400 ед. от недовыпуска продукции. Фирма может послать к поставщику свой транспорт (расходы 50 ед.), однако опыт показывает, что в половине случаев транспорт возвращается ни с чем. Можно увеличить вероятность получения материала до 80%, если предварительно послать своего  представителя, но расходы увеличатся еще на 50 ед. Существует возможность приобретать более дорогой (на 50%) материал-заменитель у другого, вполне надежного поставщика, однако, кроме расходов на транспорт (50 ед.) возможны дополнительные издержки хранения материала в размере 30 ед., если его  количество на складе превысит допустимую норму, равную одной партии.

Какой стратегии должен придерживаться завод в сложившейся ситуации?

Формализация. У природы два состояния: поставщик надежный и поставщик ненадежный. У фирмы - четыре стратегии: 1) не осуществлять никаких дополнительных действий, 2) послать к поставщику свой транстпорт, 3) послать к поставщику представителя и транстпорт, 4) купить и привезти материал-заменитель от другого поставщика.

Составим таблицу расчетов:

Затраты и убытки фирмы-изготовителя

Ситуация Стоимость материала Недовыпуск продукции Транспорт Команди-ровочные расходы Издержки хранения Общая сумма
1 1 - 100 0 0 0 0 - 100
1 2 0 - 400 0 0 0 - 400
2 1 - 100 0 - 50 0 0 - 150
2 2 - 50 - 200 - 50 0 0 - 300
3 1 - 100 0 - 50 - 50 0 - 200
3 2 - 80 - 80 - 50 - 50 0 - 260
4 1 - 250 0 - 50 0 - 30 - 330
4 2 - 150 0 - 50 0 0 - 200

Решение. На основе полученных результатов вычислений можно составить платежную матрицу:

min max
- 100 - 400 - 400
- 150 - 300 - 300
- 200 - 260 - 260 - 260
- 330 - 200 - 330

 

Ответ. Нужно придерживаться третьей стратегии и затраты не превысят 260 ед., если послать к поставщику представителя и транстпорт.

1. Рассмотренный способ поиска оптимального решения называется критерием Вальда (Максиминный критерий принятия решения). Выбирается решение, гарантирующее получение выигрыша не меньше, чем maxmin:

vW = maxi minj aij = -260 ед.

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

2. Максимаксный критерий. Самый благоприятный случай:

vM = maximaxj aij = -100 ед.

Если фирма ничего не предпримет, то потратит не больше 100 единиц. Это критерий абсолютного оптимизма.

 

3. Критерий пессимизма-оптимизма Гурвица.

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

vH = maxi [a maxi aij + (1-a) minj aij ], где a - “степень оптимизма” , 0 <= a <= 1.

При  a = 0 критерий Гурвица тождественен критерию Вальда, а при a =1  совпадает с максиминным решением.

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

Влияние степени оптимизма на выбор решения в задаче “Поставщик”.

 

Решение

 Степень оптимизма

0,1

0,2

0,3

0,4

0,5

0,6

0,7

0,8

0,9

 

А1

1 стратегия

-370

-340

-310

-280

-250

-220

-190*

-160*

-130*

А2

2 стратегия

-285

-270

-255

-240

-225*

-210*

-195

-180

-165

А3

3 стратегия

-254*

-248*

-242*

-236*

-230

-224

-218

-212

-206

А4

4 стратегия

-317

-304

-281

-278

-265

-252

-239

-226

-213

 

Величина vH  для каждого значения  a отмечена*. При a <= 4/9 критерий Гурвица рекомендует в задаче “Поставщик” решение А3, при 4/9 <= a <= 2/3 - решение А2. В остальных случаях А1. А4 не выгодно во всех случаях.

 

4. Критерий Сэвиджа (критерий минимакса риска).

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

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

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

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

 

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

 

Если бы игрок знал заранее будущее состояние природы j, он выбрал бы стратегию, которой соответствует max элемент в данном столбце: maxi aij, тогда риск:   rij = maxi aij  - aij.

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

vS = mini maxj rij = mini maxj (maxi aij  - aij).

Для задачи “Поставщик” минимакс риска достигается сразу при двух стратегиях А2  и А3:

 

max min
0 200 200
50 100 100 100
100 60 100 100
230 0 130

 

5. Критерий Лапласа.

В ряде случаев представляется правдоподобным следующее рассуждение: поскольку неизвестны будущие состояния природы, постольку можно считать их равновероятными. Этот подход к решению используется в критерии “недостаточного основания” Лапласа.

Для решения задачи для каждого решения подсчитывается математическое ожидание выигрыша (вероятности состояний природы полагаются равными yj = 1/n, j = 1:n), и выбирается то решение, при котором величина этого выигрыша максимальна.

vL = maxi ∑ 1/n aij  = 1/n maxi ∑aij.

Решением игры “Поставщик” по критерию Лапласа является вторая стратегия:

max
-250
-225 -225
-230
-265

 

Гипотеза о равновероятности состояний природы является довольно искусственной, поэтому принципом Лапласа можно пользоваться лишь в ограниченных случаях. В более общем случае следует считать, что состояния природы не равновероятны и использовать для решения критерий Байеса-Лапласа.

 

6.Критерий Байеса-Лапласа.

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

vBL = maxi ∑ aij yj.

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

Возвращаясь к нашей игре “Поставщик” предположим, что руководители фирмы-потребителя, прежде чем принять решение, проанализировали, насколько точно поставщие ранее выполнял сроки поставок, и выяснили, что в 25 случаях из 100 сырье поступало с опозданием.

Исходя из этого, можно приписать вероятность наступления первого состояния природы вероятность yj = 0,75 = (1-0,25), второго - yj = 0,25. Тогда согласно критерию Байеса-Лапласа оптимальным является решение А1.

 

Стратегии ∑ aij yj
А1 - 175*
А2 -187,5
А3 - 215
А4 - 297,5

 

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

 

Решение Критерии
Стратегии Вальда maxmax Гурвица Сэвиджа Лапласа Байеса-Л
А1   * *     *
А2     * * *  
А3 *   * *    
А4            

 

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

Выбор критерия ( как и выбор принципа оптимальности) является наиболее трудной и ответственной задачей в теории принятия решений. Однако конкретная ситуация никогда не бывает настолько неопределенной,  чтобы нельзя было получить хоты-бы частичной информации отностительно вероятностного распределения состояний природы. В этом случае, оценив распределение вероятностей состояний природы применяют метод Байеса-Лапласа, либо проводяд эксперимент, позволяющий уточнить поведение природы.

Наверх
Системы массового обслуживания
Машинное обучение