Теорема Цермело. Если есть игра, в которой 2 игрока, они обладают совершенной информацией, в игре конечное число ветвей и узлов, и выигрыш каждого игрока соответствует победе, поражению или ничьей, то
· Существует такая стратегия 1го игрока, которая обеспечивает ему победу
· Если такой стратегии нет, то есть другая стратегия 1го игрока, которая обеспечивает ему ничью.
· Если и таковой стратегии нет, то существует такая стратегия 2го игрока, которая обеспечивает ему победу.
Пример: игра «Кучки»
Есть 2 кучки, в которых лежат палочки. 2 игрока ходят по очереди и могут убрать любое количество палочек из одной кучки. Проигрывает тот, кто последний убирает 1 палочку.
Кучка А IIIIII кучка В IIII
Решение. Если количество палочек разное в кучках, то 1й игрок должен уравнивать их количество => есть преимущество первого хода: кто ходит первым, тот и выигрывает.
Если количество палочек в кучках одинаковое, то есть преимущество второго хода.
Таким образом,
1. Мы всегда знаем кто выиграет
2. Задачу можно решить обратной индукцией
3. Возможно разное преимущество в зависимости от постановки задачи (равное или нет количество палочек).
Позиционные игры с несовершенной информацией. Определение информационного множества. Определение несовершенной информации. Определение чистой стратегии в игре с НИ. Привести пример игры с несовершенной информацией. Найти решение.
Информационное множество – это множество узлов i-того игрока, которые для него неразличимы.
Несовершенная информация – ситуация в игре, когда есть хотя бы 1 информационное множество с более чем 1 узлом.
Чистая стратегия в игре с НИ – это полный план действий игрока в каждом информационном множестве.
запишем стратегии игроков: s1 ={L, R1, R2} s2= {A, B}
запишем игру в нормальной форме и найдем равновесия Нэша
| A | B | |
| L | 2; 2 | 2; 2 |
| R1 | 0; 0 | 5; 1 |
| R1 | 0; 0 | 1; 3 |
II
I
РН (L; A), (R1;B)
Совершенное подыгровое равновесие Нэша. Определение. Понятие подыгры. Привести пример позиционной игры и найти в ней множество.
Совершенное подыгровое равновесие Нэша (СПРН) – равновесие, которое содержит Равновесия Нэша во всех подыграх. Это стратегия, который определяет равновесие Нэша для каждой подыгры в заданном дереве.
Подыгра – часть игры, которая начинается с узла, соединяет все узлы, не разрывает информационных множеств и не совпадает со всей игрой.
Для нахождения равновесия СПРП в случае, когда нельзя применить метод обратной индукции требуется составить матрицу каждой подыгры.
Если подыгр нет, то любое равновесие по Нэшу является совершенным в
подыграх.
Несколько узлов одного игрока, соединенные пунктирной линией, – это
информационное множество, т.е. те узлы, которые игрок не умеет отличать. Попав в один из них, игрок не знает, где точно он находится, поэтому такая информация называется несовершенной.
Пример:
Методом Обратной индукции (ОИ) = (Uu; l)
S1 принадлежит { U;D} * {u;d} = {Uu; Ud; Du; Dd}
S2 принадлежит {l;r}
| l | r | |
| Uu | 4;3 | 1;2 |
| Ud | 3;1 | 1; 2 |
| Du | 2; 1 | 2;1 |
| Dd | 2; 1 | 2;1 |
(Uu; l) - СПРН
(Du; r) - X
(Dd; r) - X
Судя по ПИ1 и ПИ2 равновесия недостижимы.
ПИ1
| d | 4 |
| u |
Ø Выбираем U
ПИ2
| l | r | |
| u | 4;3 | 1;2 |
| d | 3;1 | 1;2 |
Ø Выбираем (U; l) и (d; r)
11. Повторяющиеся игры.
Эффект «хромой утки».
Если игра конечна и игроки это знают, то на последнем шаге у них не будет желания кооперироваться (на последнем шаге будет сыграно «плохое» равновесие).