Презентация на тему "Алгоритмы теории игр"

Содержание

• 
  Слайд 1

  Алгоритмы теории игр

  Михаил Лукин, гр. 3539

• 
  Слайд 2

  План лекции

  Введение Матричные игры Игры с седловой точкой Смешанные стратегии Применение Итоги Литература

• 
  Слайд 3

  Введение

  Первая значительная книга по теории игр появилась в 1944г (Дж. фон Нейман, С. Моргенштерн «Теория игр и экономическое поведение»). Предмет оказался чрезвычайно сложным, даже для математики . Теория игр она нашла свое применение, прежде всего, в военном деле и экономике.

• 
  Слайд 4

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

  Этот раздел теории игр является наиболее полно изученным.

• 
  Слайд 5

  Определения

  Система Г = (X, Y, K), где X и Y – непустые мно-жества, и функция , называется антагонистической игрой в нормальной форме. Элементы и называются стратегиями игроков 1 и 2 соответственно. Антагонистические игры, в которых оба игрока имеют конченые множества стратегий, называются матричными.

• 
  Слайд 6
  

  Пусть игрок 1 имеет всего m стратегий, а игрок 2 – n стратегий. Установим биекцию между множест-вами: X и M = {1, …, m}; Y и N = {1, …, n}. Тогда игра Г полностью задается матрицей ,где

• 
  Слайд 7

  Примеры

  «Игра на уклонение». Дискретная игра типа дуэли. ,i

• 
  Слайд 8

  Игры с седловой точкой

  Теорема. Пусть имеются два числовых множества A и B и функция . Тогда . Пусть дана . Точка (x0,y0) называется седловой точкой функции f, если 1. 2.

• 
  Слайд 9

  Игры с седловой точкой 2

  Теорема 2. Пусть и существу-ют . Тогда равносильно тому, что f имеет седловую точку. Может ли у матрицы быть несколько седловых точек? Все ли матрицы имеют седловую точку?

• 
  Слайд 10

  Смешанные стратегии

  Основная теорема матричных игр. В смешанных стратегиях игра двух лиц с нулевой суммой имеет седловую точку.

• 
  Слайд 11

  Итеративный метод Брауна – Робинсона

  Идея метода – многократное фиктивное разыгрывание игры с заданной матрицей выигрыша. Недостаток: малая скорость сходимости.

• 
  Слайд 12

  Монотонный итеративный алгоритм

• 
  Слайд 13

  Пример применения

  Выбор оптимальной стратегии в условиях неопределенности.

• 
  Слайд 14

  Итоги

  Матричные игры – наиболее изученный раздел теории игр. Основное применение теории игр – – экономика.

• 
  Слайд 15

  Литература

  Петросян, Зенкевич, Семина «Теория игр» http://fmi.asf.ru/vavilov/Tiv.htm http://vvo.psati.ru/files/RPU/page2.files/index10.html http://www.dvo.ru/studio/linpro/buka/node20.html – основная теорема двойственности Робинсон Дж. «Итеративный метод решения игр»