Теоретико-игровые методы принятия решений (Еремеев А. П.) (Теоретико-игровые методы принятия решений (Еремеев А. П.))

Посмотреть архив целиком

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ

___________________________________________________________


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

___________________________________________________________


МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

___________________________________________________________




А.П. ЕРЕМЕЕВ







ТЕОРЕТИКО-ИГРОВЫЕ МЕТОДЫ
ПРИНЯТИЯ РЕШЕНИЙ






Учебное пособие
по курсам
«Теория игр и исследование операций», «Теория принятия решений»

для студентов, обучающихся по специальностям

«Прикладная математика и информатика»,
«Информатика и вычислительная техника»,
«Информационные системы и технологии»,
направлениям «Прикладная математика и информатика»,
«Информатика и вычислительная техника»











Москва Издательство МЭИ 2006

УДК

519

Е 70

УДК 007.681.518.5.001.63(072)


Утверждено учебным управлением МЭИ в качестве учебного пособия для студентов


Подготовлено на кафедре прикладной математики


Рецензенты:

доктор технических наук, профессор А.Б. Фролов;

зам. директора ГУ РосНИИИТ и АП, лауреат премии Президента РФ в области образования, действительный член РАЕН, д.т.н., проф. Э.В. Попов;

лауреат премии Президента РФ в области образования, действительный член РАЕН, д.т.н., проф. В.Н. Вагин.


Еремеев А.П.

Е70 Теоретико-игровые методы принятия решений: Учебное пособие / А.П. Еремеев – М.: Издательство МЭИ, 2006. – 50 с.

ISBN 5-7046-1383-7


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

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





ISBN 5-7046-1383-7 © Московский энергетический институт, 2006


«…существует строгий подход к вопросам, охватывающим проблемы совпадающих или противоположных интересов, полной или неполной информации, свободных разумных решений или случайных воздействий..»

Джон фон Нейман,

Оскар Моргенштерн

ВВЕДЕНИЕ

Теория игр – это математическая дисциплина, исследующая вопросы поиска решений в конфликтных ситуациях. Основы теории игр заложены в 1928 году Джоном фон Нейманом и Оскаром Моргенштерном, исследовавшим конфликтные ситуации в условиях рыночной экономики. Наиболее подробно теория игр изложена ими в фундаментальной работе «Theory of Games and Economic Behavior», Princeton, Princeton University Press, 1953 (русский перевод [1]), цитата из которой взята в качестве эпиграфа к данной книге. Теоретико-игровые методы и модели нашли достаточно широкое применение в области автоматизации процессов принятия решений (см., например, работы [24]), в том числе в интеллектуальных системах поддержки принятия решений, предназначенных для помощи лицам, принимающим решения, при управлении сложными объектами или процессами различного типа (техническими, экономическими, транспортными и т.д.) [4].

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

В разделе 1 даются определения основных понятий теории игр, и приводится классификация игровых моделей, основываясь на работах [13, 5, 6].

В разделе 2 рассматривается игра двух лиц с нулевой суммой (антагонистическая игра) при ее наиболее общем (универсальном) представлении в виде дерева игры (дерева решений) и методы поиска решения на дереве. Более подробно с методами поиска (как строгими, так и эвристическими) на деревьях решений можно ознакомиться по работам [7, 8].

В разделе 3 описываются методы решения антагонистической игры, представленной в матричной форме. Рассматриваются ситуации поиска решения в чистых стратегиях при наличии в матрице игры седловой точки и в смешанных стратегиях, когда седловая точка отсутствует. Приводятся строгие методы, гарантирующие нахождение оптимального решения, и приближенные методы, дающие некоторое приближение к оптимальному решению, но характеризующиеся существенно меньшей вычислительной сложностью. Класс антагонистических игр наиболее исследован в теории игр и интересующиеся могут найти дополнительную информацию, например, в работах [13, 5, 6, 9].

В разделе 4 рассматривается игра двух лиц с произвольной суммой (биматричная игра) и подходы к ее решению, в частности, на основе теории Нэша. Дополнительную информацию по биматричным играм, как некооперативным (некоалиционным), так и кооперативным (коалиционным), и методам их решения можно получить из работ [2, 3, 5, 6, 10].

Раздел 5 посвящен методам поиска решений в условиях неопределенности и риска на основе теории статистических решений или так называемым играм с «природой», где под «природой» понимается некоторая реальность (или условия), действия или состояния которой неизвестны, но могут оказывать влияние на результаты принимаемых решений. Описание данного класса игр можно найти в работах [3, 9, 11].

В разделе 6 рассмотрен класс игровых моделей в виде игр с упорядоченными исходами [10], когда предпочтения игроков задаются в виде отношений порядка на множестве исходов (выигрышей, платежей).

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

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

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

  1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИГР.
    КЛАССИФИКАЦИЯ ИГРОВЫХ МОДЕЛЕЙ

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

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

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

Однократный розыгрыш игры от начала и до конца называется партией игры.

Результатом партии являются платежи (выигрыши или проигрыши игроков).

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

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

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

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

Чисто азартные игры относятся к компетенции теории вероятностей и математической статистики.

Определение 1.1. Стратегическая игра n лиц (сторон) может быть задана набором {A1, …, An, H(A1, …, An)}, где – Ai, i = 1, …, n, – стратегия i‑го игрока, H – платёж игры, т.е. выигрыши (или проигрыши) игроков.

    1. Классификация игровых моделей

Классификация теоретико-игровых моделей представлена на рис. 1.1.

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

В зависимости от числа участвующих в игре игроков игры бывают N лиц, которые в зависимости от того, разрешены коалиции (кооперации) игроков или нет, могут быть соответственно коалиционными (кооперативными) или некоалиционными (некооперативными), или 2-х лиц (парными), которые в зависимости от суммарной величины платежа могут быть антагонистическими, если суммарный платеж игроков равен нулю, или неантагонистическими, если суммарный платеж не равен нулю. Заметим, что в антагонистической игре интересы игроков строго противоположны, т.е. выигрыш одного игрока в точности равен проигрышу другого, а в неантагонистической – просто не совпадают, что ведет к ситуации, когда увеличение выигрыша одного игрока ведет к уменьшению выигрыша другого.






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