Теория игр

ТЕОРИЯ ИГР В жизни часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, в условиях отсутствия информации об ответных реакциях на твои действия, т.е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации, возникающие при игре в шахматы, шашки, домино и т.д. относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнеров. Конфликтная ситуация Ситуация, в которой эффективность принимаемого одной стороной решения зависит от действий другой стороны, называется конфликтной. Конфликт всегда связан с определенного рода разногласиями (это не обязательно антагонистическое противоречие). Характерные особенности конфликтных ситуаций: Каждый из участников имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны) Методы принятия решений Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. Основные понятия теории игр Теория игр – математическая теория конфликтных ситуаций, целью которой является выработка рекомендаций по разумному поведению участников конфликта. Конфликтная ситуация – это столкновение интересов двух или более сторон. Игра – это математическая модель конфликтной ситуации Игра состоит из отдельных партий. Партия – это каждый вариант реализации игры. В партии игроки совершают ходы. Ход игрока – это выбор и осуществление одного из предусмотренных правилами игры действий. Суть игры состоит в том, что каждый участник принимает такое решение, которое, как он полагает, обеспечит ему наилучший исход. Исходом игры называется значение некоторой функции, называемой функцией выигрыша (платежной функцией), которая может задаваться в матричном или аналитическом виде. Величина выигрыша применяемой игроком. Стратегия зависит от стратегии, – это совокупность правил, однозначно определяющих последовательность действий игрока в каждой конкретной ситуации, складывающейся в процессе игры. Игра с нулевой суммой – это игра, в которой сумма выигрышей всех игроков равна нулю (т.е. каждый игрок выигрывает только за счет других). Парная игра с нулевой суммой называется антагонистической игрой, здесь два игрока четко играют друг против друга. Конечная антагонистическая игра называется матричной игрой. Матричные игры Пусть в игре участвуют два игрока. Игрок А имеет 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, а ИГРЫ С ПРИРОДОЙ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 Пример 30 10 12 13 31 32 33 34 35 36 а) б) 37 а) б) 38 Критерий Сэвиджа рекомендует выбирать в качестве оптимальной ту чистую стратегию Аi, при которой максимальный риск является минимальным Элемент матрицы рисков {rij} находится по формуле rij=maxaij – aij где maxaij – максимальный элемент в столбце исходной матрицы. 39 40 41 42 Пример 43 В каждом столбце матрицы доходности найдем максимальный элемент Применяя формулу rij=max aij – aij , построим матрицу рисков 20 18 15 S  min max rij  min 5;6;7  5 i j 44 При  0   H  max   max aij  1     min aij  j i  j  При   0 критерий превращается в критерий Вальде, при   1 – в критерий максимума  Замечание    H  max   min a  1   max a  j ij ij  i  j  45 46 47 48 49    H  max   max a  1   min a  ij ij  j i  j  H  max15;14;15.5  15.5 50 51 52 53 54 55 56 57 58 Решение: 59 60 61 62 63 64 65 1 n  L  max   aij , i  1,2,, m  n j 1  66 67 Решение: 1 n  L  max   aij   max15; 14; 15.33  15.33  n j 1  68 69 70 n   1 r L  min   rij  i  n j 1  71 72 73 74 75 76 77 78 79 80 81