Алгоритмы теории игр Михаил Лукин, гр. 3539
План лекции Введение Матричные игры Игры с седловой точкой Смешанные стратегии Применение Итоги Литература
Введение Первая значительная книга по теории игр появилась в 1944г (Дж. фон Нейман, С. Моргенштерн «Теория игр и экономическое поведение»). Предмет оказался чрезвычайно сложным, даже для математики. Теория игр она нашла свое применение, прежде всего, в военном деле и экономике.
Матричные игры Этот раздел теории игр является наиболее полно изученным.
Определения Система Г = (X, Y, K), где X и Y – непустые мно- жества, и функция, называется антагонистической игрой в нормальной форме. Элементы и называются стратегиями игроков 1 и 2 соответственно. Антагонистические игры, в которых оба игрока имеют конченые множества стратегий, называются матричными.
Пусть игрок 1 имеет всего m стратегий, а игрок 2 – n стратегий. Установим биекцию между множест- вами: 1. X и M = {1, …, m}; 2. Y и N = {1, …, n}. Тогда игра Г полностью задается матрицей,где
Примеры 1.«Игра на уклонение». 2.Дискретная игра типа дуэли., i < j
Игры с седловой точкой Теорема. Пусть имеются два числовых множества A и B и функция. Тогда. Пусть дана. Точка (x 0,y 0 ) называется седловой точкой функции f, если 1. 2.
Игры с седловой точкой 2 Теорема 2. Пусть и существу- ют. Тогда равносильно тому, что f имеет седловую точку. Может ли у матрицы быть несколько седловых точек? Все ли матрицы имеют седловую точку?
Смешанные стратегии Основная теорема матричных игр. В смешанных стратегиях игра двух лиц с нулевой суммой имеет седловую точку.
Итеративный метод Брауна – Робинсона Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей выигрыша. Недостаток: малая скорость сходимости.
Монотонный итеративный алгоритм
Пример применения Выбор оптимальной стратегии в условиях неопределенности. A i \B j B1B1 B2B2 B3B3 A1A1 368 A2A2 942 A3A3 754
Итоги Матричные игры – наиболее изученный раздел теории игр. Основное применение теории игр – – экономика.
Литература 1.Петросян, Зенкевич, Семина «Теория игр» htmlhttp://vvo.psati.ru/files/RPU/page2.files/index 10.html 4. html – основная теорема двойственности html 5.Робинсон Дж. «Итеративный метод решения игр»