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

___________________________________________________________

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

___________________________________________________________

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

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

___________________________________________________________

А.П. ЕРЕМЕЕВ

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

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

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

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

Москва Издательство МЭИ 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]), цитата из которой взята в качестве эпиграфа к данной книге. Теоретико-игровые методы и модели нашли достаточно широкое применение в области автоматизации процессов принятия решений (см., например, работы [24]), в том числе в интеллектуальных системах поддержки принятия решений, предназначенных для помощи лицам, принимающим решения, при управлении сложными объектами или процессами различного типа (техническими, экономическими, транспортными и т.д.) [4].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наиболее разработанными в теории игр являются модели игр 2-х лиц с нулевой суммой (антагонистических игр).

1.3.Контрольные вопросы к разделу 1

1. Сформулируйте понятие игры как модели конфликтной ситуации.

2. Сформулируйте основную задачу теории игр.

3. Дайте определение стратегической игры n лиц (сторон).

4. Приведите классификацию теоретико-игровых моделей.

5. Какие игры называются антагонистическими и неантагонистическими, с полной и неполной информацией?

6. Модели каких игр являются наиболее разработанными в теории игр?

2.АНТАГОНИСТИЧЕСКАЯ ИГРА.
ПОИСК РЕШЕНИЯ НА ДЕРЕВЕ ИГРЫ

2.1.Представление антагонистической игры

Рассмотрим антагонистическую игру G(mn), где у первого игрока A имеется множество стратегий {A_i}, i = 1, …, m, а у второго игрока B – множество стратегий {B_j}, j = 1, …, n.

Игра G(mn) может быть представлена в виде дерева игры и в виде матрицы (матрицы платежей).

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

Рассмотрим представление антагонистической игры G(mn) в виде дерева.

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

Проиллюстрируем процесс построения дерева игры на следующем примере.