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

Основные понятия теории игр Содержание лекции Понятия об игровых моделях История теории игр Основные понятия теории игр Классификация игр Матричные игры РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА  Прокофьева С.И. Основы теории игр [Электронный ресурс]: учебное пособие/ Прокофьева С.И., Пак Э.Е.— Электрон. текстовые данные.— СПб.: Санкт-Петербургский государственный архитектурно-строительный университет, ЭБС АСВ, 2017.— 72 c.— Режим доступа: http://www.iprbookshop.ru/ 74340.html. — ЭБС «IPRbooks»  Салмина Н.Ю. Теория игр [Электронный ресурс]: учебное пособие/ Салмина Н.Ю.— Электрон. текстовые данные.— Томск: Томский государственный университет систем управления и радиоэлектроники, Эль Контент, 2015.— 107 c.— Режим доступа: http://www.iprbookshop.ru/ 69994.html. — ЭБС «IPRbooks» Понятия об игровых моделях В жизни часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, в условиях отсутствия информации об ответных реакциях на твои действия, т.е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации, возникающие при игре в шахматы, шашки, домино и т.д. относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнеров. Конфликтная ситуация Ситуация, в которой эффективность принимаемого одной стороной решения зависит от действий другой стороны, называется конфликтной. Конфликт всегда связан с определенного рода разногласиями (это не обязательно антагонистическое противоречие). Характерные особенности конфликтных ситуаций: Каждый из участников имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны) Методы принятия решений Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. История теории игр Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Задачи производства и ценообразования в условиях олигополии, которые стали позже хрестоматийными примерами теории игр, рассматривались в XIX в. А. Курно и Ж. Бертраном. Антуа́н Огюсте́н Курно (28.08.1801 — 30.03.1877) французский математик, философ и экономист . Опубликовал ряд работ, в том числе «Исследования математических принципов теории богатства» (1838), которая явилась одной из первых попыток исследования экономических явлений с помощью математических методов. Его философия эклектически объединяет идеи И.Канта и позитивистов. Взгляды Курно получили распространение в последней трети 19 в., когда математическая школа сложилась в особое направление буржуазной политической экономии Жозеф Луи Франсуа Бертран французский математик В начале XX в. Эмануэль Ласкер, Эрнст Цермело и Эмиль Борель выдвигают идею математической теории конфликта интересов. Эрнст Фри́дрих Фердина́нд Церме́ло (27.07.1871 — 21.05.1953) немецкий математик Эмануэль Ласкер (24.12.1868 — 11.01.1941) немецкий шахматист и математик Фели́кс Эдуа́р Жюсте́н Эми́ль Боре́ль (7.01.1871 — 3.02.1956) французский математик и политический деятель Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна Оскар Моргенштерн (нем. Oskar Morgenstern; 24 января 1902 — 26 июля 1977) американский экономист немецкого происхождения, один из создателей теории игр Theory of Games and Economic Behavior, 1944 (русск. «Теория игр и экономическое поведение», 1970г.) В сороковых годах двадцатого века американский математик Джон Форбс Нэш (англ. John Forbes Nash, Jr.; 13 июня 1928 — 23 мая 2015) — американский математик В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Форбса Нэша Большим вкладом в применение теории игр стала работа Томаса Шеллинга, нобелевского лауреата по экономике 2005 г. «Стратегия конфликта». Т.Шеллинг рассматривает различные «стратегии» поведения участников конфликта. Эти стратегии совпадают с тактиками управления конфликтами и принципами анализа конфликтов в конфликтологии и в управлении конфликтами в организации. Томас Кромби Шеллинг (14.04. 1921— 13.12. 2016) американский экономист, лауреат Нобелевской премии 2005 года «За расширение понимания проблем конфликта и кооперации с помощью анализа в рамках теории игр». Профессор Мэрилендского университета. ПрезидентАмериканской экономической ассоциации в 1991 г. Лауреат премии Фрэнка Сейдмана (1977). Основные понятия теории игр Теория игр – математическая теория конфликтных ситуаций, целью которой является выработка рекомендаций по разумному поведению участников конфликта. Конфликтная ситуация – это столкновение интересов двух или более сторон. Игра – это математическая модель конфликтной ситуации Игра состоит из отдельных партий. Партия – это каждый вариант реализации игры. В партии игроки совершают ходы. Ход игрока – это выбор и осуществление одного из предусмотренных правилами игры действий. Ходы бывают: личными – когда игрок сознательно выбирает и осуществляет тот или другой вариант действия (пример –– любой ход в шахматах); случайными – когда выбор осуществляется не волей игрока, а каким-то механизмом случайного выбора (бросание монеты, игральной кости). Суть игры состоит в том, что каждый участник принимает такое решение, которое, как он полагает, обеспечит ему наилучший исход. Исходом игры называется значение некоторой функции, называемой функцией выигрыша (платежной функцией), которая может задаваться в матричном или аналитическом виде. Величина выигрыша применяемой игроком. Стратегия зависит от стратегии, – это совокупность правил, однозначно определяющих последовательность действий игрока в каждой конкретной ситуации, складывающейся в процессе игры. Классификация игр В зависимости от видов ходов: стратегические и азартные. Азартные игры состоят только из случайных ходов ими теория игр не занимается. Если наряду со случайными ходами есть личные ходы, или все ходы личные, то такие игры называются стратегическими.  В зависимости от числа участников: парные и множественные. В парной игре число участников равно двум, в множественной - более двух.  Классификация игр Участники множественной игры могут образовывать коалиции, как постоянные, так и временные.  По характеру взаимоотношений игроков игры делятся на бескоалиционные, коалиционные и кооперативные. Бескоалиционными называются игры, в которых игроки не имеют право вступать в соглашения, образовывать коалиции, и целью каждого игрока является получение по возможности наибольшего индивидуального выигрыша. Классификация игр Игры, в которых действия игроков направлены на максимизацию выигрышей коллективов (коалиций) без последующего их разделения между игроками, называются коалиционными. Исходом кооперативной игры является дележ выигрыша коалиции, который возникает не как следствие тех или иных действий игроков, а как результат их наперед определенных соглашений. В соответствии с этим в кооперативных играх сравниваются по предпочтительности не ситуации, как это имеет место в бескоалиционных играх, а дележи; и сравнение это не ограничивается рассмотрением индивидуальных выигрышей, а носит более сложный характер. Классификация игр  По количеству стратегий каждого игрока: конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно). По количеству информации, имеющейся у игроков относительно прошлых ходов: игры с полной информацией (имеется вся информация о предыдущих ходах) и неполной информацией.  Примерами игр с полной информацией могут быть шахматы, шашки и т.п. Классификация игр  По виду описания игры: позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Классификация игр Дифференциальные игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями. Существуют также рефлексивные игры, которые рассматривают ситуации с учетом мысленного воспроизведения возможного образа действий и поведения противника. КЛАССИФИКАЦИЯ ИГРОВЫХ ЗАДАЧ Игра с нулевой суммой – это игра, в которой сумма выигрышей всех игроков равна нулю (т.е. каждый игрок выигрывает только за счет других). Парная игра с нулевой суммой называется антагонистической игрой, здесь два игрока четко играют друг против друга. Конечная антагонистическая игра называется матричной игрой. Матричная игра описывается платежной матрицей, в которой задаются выигрыши первого игрока. Номер строки матрицы соответствует номеру применяемой стратегии первого игрока, столбец номеру применяемой стратегии второго игрока; на пересечении строки и столбца находится соответствующий выигрыш первого игрока (проигрыш второго игрока). Конечная парная игра с ненулевой суммой называется биматричной игрой. Такая игра описывается двумя платежными матрицами, каждая для соответствующего игрока. Матричные игры Пусть в игре участвуют два игрока. Игрок А имеет m стратегий: A1 , A2 ,, Am ; а игрок В – n стратегий: B1 , B2 ,, Bn . Если игрок А выбрал стратегию Ai , а игрок В – стратегию B j , то выигрыш игрока А составит а игрока В – bij , причем aij  bij aij (*) Поэтому при анализе такой игры достаточно рассмотреть выигрыш только одного игрока, например, выигрыш aij игрока А. Зная выигрыш по формуле (*) легко определить выигрыш bij . aij Матричные игры – парные игры с нулевой суммой, в которых выигрыш одного игрока равен проигрышу другого, т.е. относятся к разряду антагонистических. Если известны все значения выигрышей aij для каждой пары стратегий Ai B j , i=1,2,…,m; j=1,2,…,n, то их удобно записать в виде прямоугольной таблицы, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В   Эту матрицу называют платежной матрицы размера игры – матричными играми m  n m n, а Пример антагонистической игры Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 6, 7, 9, а игрок B записывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока А. Если сумма чисел нечётная, то это выигрыш игрока В (проигрыш игрока А). Найти платёжную матрицу игры А. Имеем три стратегии первого игрока: А1 = 6, А2 = 7, А3 = 9 и две стратегии второго В1 = 4, В2 = 5. Матрица игры: А=