- •2. Критерий Макси Макса. Максиминный критерий Вальда.
- •3. Критерий оптимизма и пессимизма Гурвица.
- •5. Критерий Севиджа.
- •8. Нижняя и верхняя цена игры. Максиминные и минимаксные стратегии.
- •9. Решение матричных игр с седловой точкой.
- •10. Решение игры в смешанных стратегиях для платежной матрицы 2х2.
- •11. Принцип доминирования. Доминирующие и дублирующие стратегии.
- •12. Геометрическое решение игры в смешанных стратегиях(2х n)
- •17. Симплексный метод решения задачи линейного программирования.
- •13. Геометрическое решение игры в смешанных стратегиях (nх2).
- •18. Алгоритм составления симплексной таблицы. Преобразование симплексной таблицы.
- •19. Двойственные задачи линейного программирования.
- •20. Биматричные игры. Основные понятия.
- •23. Решение биматричной игры .
- •Раздел II .
- •24. Кооперативные игры.
- •25. Определение характеристической функции. Её свойства.
- •26. Дележи в кооперативных играх.
- •30. Решение игры по Нейману Моргенштерну.
- •31. Вектор Шепли.
- •32. Позиционные игры.
- •34. Информационные множества. Нормализация игры.
- •35. Позиционные игры с полной информацией.
- •37. Дифференциальные игры. Определение дифференциальной игры преследования.
30. Решение игры по Нейману Моргенштерну.
Если никакие два дележа внутри множества M не доминирует друг друга, а любой дележ вне множества M доминирует дележ их множества М
1)
х,у
выполенно
х не доминирует у и уне доминирует х
2)
для любого
,
Теорема
НМ – решение содержит С- ядро
Доказательство:
Предложим противное тогда найдется дележ принадлежащий ядру, но не принадлежит НМ
х не принадлежит НМ
в определении НМ найдётся дележ У , который доминирует дележ Х. Но это противоречит определения С-ядро.
Теорема доказана.
Как проверить, что С – ядро не пусто?
Теорема:
Пусть задана игра в 0-1 редуцированной форме, тогда если выполняется неравенство.
V(S)
/n-|S|+1,
где n – число всех участников игры.
|S|- число участников коалиции.
Причем это неравенство выполняется для всех коалиций, тогда С-ядро коалиции не пусто.
31. Вектор Шепли.
-вектор-функция
заданная
на множестве характеристич. функций
игр плиц и удовлетворяющая следующим
аксиомам: 1) (эффективность)
если коалиция Ттакова,
что для любой коалиции Sвыполняется
равенство
то
2)
(симметричность)
если
-перестановка
множества J== {1, . . ., n} и для любой коалиции
Sимеет место
3)
(линейность)
Эти
аксиомы были введены Л. Шелли [1] для
аксиоматич. определения ожидаемого
выигрыша игрока в кооперативной
игре. Было показано, что аксиомам
1)-3) удовлетворяет единственная
вектор-функция
32. Позиционные игры.
Позиционные игры – это бескоалиционные игры, в которых принятие решений рассматривается как многошаговый процесс. В позиционных играх в процессе принятия решений игрок проходит последовательность состояний, в которых приходится принимать решения.В позиционных играх стратегию можно рассматривать как функции ставящие в соответствии информационному состоянию игрока выбор возможной альтернативы. Переходы из одного информационного состояния в другое сопровождается получением или утратой информации игроком. В информационных играх число игроков может быть больше двух.
Пример: 3 игрока выбирают 1 из 4 кандидатов в претенденты.
Правила выбора следующие: начиная с 1 каждый игрок налагает вето на выбор кандидатов единственно оставшийся кандидат считается избранным в результате выбора каждый игрок получает выигрыш:
V1=(5,4,3,7)
V2=(6,7,5,4)
V3=(3,8,5,4)
Рис 2.
Дерево содержит одну единственную нормальную вершину (корень дерева)
Корень дерева не идет ни одна ветвь
Дерево имеет не менее 1-ой вершины из которой не выходит ни одна ветвь
Эти вершины называются конечными
Из корня дерева имеется единственный путь к каждой из остальных вершин дерева.
Вершина соответствует определенному состоянию игры перед очередным ходом
Каждую вершину занимает только один игрок.
Вершине присваивается номер равный номеру игрока.
Ходы игроков могут быть личными и случайными.
В описании игры указано какие выборы делает игрок при линейно ходе.
Если ходить случайно, то задается вероятность этих ходов.
Информация игрока задается разбиением вершин на множество.
Рассмотрим решение игры на Рис1 – это игра с полной информацией. Согласно теории игр, такая игра разрешима. И решается эта игра по принципу «доминирования»:
Каждый игрок имеет доминирующие стратегии, которые ему необходимо применять.
Рассмотрим принцип «доминирования» на этом примере.
Из всех вершин предшествующих конечным ходит 3 игрок.
Остальные
игроки знают функцию выигрыша 3-го
игрока, поэтому они могут предвидеть
его решение. С учетом того что шаг 3-го
однозначно определен, имеем следующую
схему:
Получили новое дерево, здесь 3-ий игрок по сути не принимает решение.
Финальная вершина определяется ходами игрока 2.
Игрок ,1 зная функцию решения 2-го игрока, может предвидеть его ход.
С учетом этого приходим к новому дереву.
В результате если 1-ый игрок отклонит 3-го, то 2-ой игрок вынужден будет отклонить 2-го, а 3-ий 1-го.
Процесс сведения игры к матричной называется нормализацией.
Для нормализации игры нужно перечислить все возможные стратегии игроков и для каждой совокупности стратегий определить выигрыш игроков.
Первый игрок делает свой 1-ый ход выбирая первую или вторую ветвь, затем ход делает 2-ой игрок, у него в каждой вершине имеется два выбора.
Стратегии игроков:
1-ый:
А1- выбирает левую ветвь
А2 – выбирает правую ветвь
2-ой:
В1 – всегда левая ветвь
В2 – всегда правая ветвь
В3 – выбирать ветвь, которую выбрал 1-ый игрок
В4 – выбирать ветвь противоположную той, что выбрал 1-ый игрок
33. Понятие графов. Дерево игры. В теории игр используется такое понятие как граф. Граф называется совокупность точек, называющихся вершинами, и соединяющих их линией (ребрами)
Ребра, имеющие одинаковые кольцевые решения называются параллельными.
Ребро, кольцевая решения, которых совпадают, называются петлей.
Если вершина является кольцевой точкой для ребра, то вершина и ребро инцидентные друг к другу.
Маршрут – последовательность ребер ведущих от одной вершины к другой.
Если составляющие ребра маршрута различны, то это путь
Цикл
– путь, начальная коими вершины которого
совпадают. Р
ебра(е1,е2,е4)
образуют цифру, т.к. начальные и конечные
вершины совпадают. Граф называется
связным, если для любых двух его вершин
существует путь их соединяющие.Деревом
называется связный граф несодержащий
циклов. Позиционные игры изображаются
с помощью деревьев.
