В последовательных играх участники могут делать ходы в заранее установленном либо случайном порядке. Они знают некоторую информацию о предшествующих действиях других.
Дерево игры – это такая структура, которая используется для передачи информации о выйгрышах игроков при их конретных действиях. Плюс данной структуры в том, что она наглядно дает нам представление последовательности ходов игроками, их стратегии, а также конечный результат, который будет получен в ходе принятий данных стратегий.
Примером является Игра «Кредитор и Заемщик»; Игра «Деньги в шляпе».
Также при ответе на данный вопрос правильнее будет упомянуть термины «несовершенная и совершенная информация », термины которых указаны в Билете №2.
Обратная индукция»
Метод обратной индукции – это отыскание решений по принципу «чтобы выбрать действие 1 – ого игрока, надо просмотреть вперед, сделать вывод, какой ход совершил 2 – ой игрок, и затем снова вернуться к 1 – ому игроку.
или Тип процедуры, которая начинается с нахождения оптимального поведения «в конце игры», а затем определения оптимального поведения на более ранних шагах, в предвидении того, что будет происходить дальше. (относится к конечным играм с совершенной информацией – игра, в которой в каждом узле игрок, который осуществляет выбор, знает в каком он узле и как туда попал)
Правило: 1 игрок должен менять выигрыш 2 игрока, чтобы обеспечить мах своего выигрыша.
 | |||
 |
Решение=(R;a;r)
Теорема Цермелло.
Может быть применена при выполнении следующих условий:
· 2 игрока
· Совершенная информация
· 3 варианта выигрыша (W,T,L)
· Конечное число ходов
|
|
Выполняется, если:
Существует такая стратегия i-ого игрока (si), выигрыш от которой равен Wпри любых действиях соперника, либо существует такая стратегия i-ого игрока (si), выигрыш от которой равен Tпри любых действиях соперника,либо существует такая стратегия j-ого игрока (sj), выигрыш от которой равен Wпри любых действиях i-ого игрока.
Доказательство (мат. индукция):
/n – количество узлов; N – размерность игры/
n=1 – выполняется
n=N – предположительно выполняется
n=N+1
1. n=1
2. n=N
Игра размерности N: игрок 2 может найти Si
3. n=N+1
Если выполняется n=N, то выполняется и n=N+1
Чистые стратегии в последовательных играх.
Чистая стратегия игрока i -полный план действий, т.е. это выбор игрока i на каждом информационном множестве.
В разных типах игр определение чистой стратегии звучит немного по-разному:
Чистая стратегия для одновременной игры - конкретный выбор конкретного игрока для каждого информационного множества
В последовательных играх, в игре с совершенной информацией, чистая стратегия-это выбор игрока в каждом узле. В игре с несовершенной информацией, чистая стратегия-это выбор игрока в каждом информационном множестве.
Пример:
Чистые стратегии в данной игре будут выглядеть следующим образом:
Игрок 1: 
Игрок 2: 