Тест по предмету теория игр
2.2. Принцип максимина в антагонистических играх. Седловая точка
1. Матричная игра является антагонистической, поскольку выигрыш одного игрока равен проигрышу второго (выигрышу второго с обратным знаком).
2. Название "матричная игра” произошло из-за того, что такая игра описывает платежной функцией в виде матрицы.
3. В матричной игре каждый из игроков делает свой ход независимо от хода противника, предполагая лишь, что противник разумен, как и он сам.
4. Оптимальной стратегией игрока в матричной игре называется такая, которая обеспечивает ему максимальный средний выигрыш.
5. Принципом максимина руководствуются очень азартные и рискованные люди (оптимисты).
6. Принцип максимина предполагает выбор той стратегии, при которой минимальный выигрыш для различных стратегий максимален.
7. Стратегии, выбираемые из принципа максимина, называются максиминными.
8. Нижняя цена матричной игры всегда равна верхней цене.
9. Случай, когда нижняя цена матричной игры равна верхней цене, соответствует наличию у платежной матрицы седловой точки.
10. Платежная матрица игры не может иметь несколько седловых точек.
11. Если платежная матрица игры содержит седловую точку, то ее решение сразу находится по принципу максимина.
2.4. Основные теоремы матричных игр
1. В антагонистической игре пара стратегий (Ai, Bj) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.
2. Стратегии, соответствующие седловой точке платежной матрицы, не обладают свойством равновесия (устойчивости).
3. Игра решается в чистых стратегиях если платежная матрица имеет седловую точку.
4. Игра решается в чистых стратегиях, если нижняя цена платежной матрицы равна верхней.
5. Игры с полной информацией всегда имеют седловую точку.
6. Случайная величина, значениями которой являются чистые стратегии игрока, называется его смешанной стратегией.
7. Если игрок А применяет смешанную стратегию SA=||p1, p2, ..., pm||, а игрок В смешанную стратегию SB=||q1, q2, ..., qn||, то средний выигрыш игрока А определяется соотношением
8. Если матричная игра не имеет седловой точки, то игроки должны использовать оптимальные смешанные стратегии.
9. Оптимальные смешанные стратегии в отличие от оптимальных чистых стратегий не обладают свойством равновесия (устойчивости).
10. Те из чистых стратегий игроков, которые входят в их оптимальные смешанные стратегии с вероятностями, не равными нулю, называются активными стратегиями.
11. Любая, матричная игра имеет по крайней мере, одно оптимальное решение, в общем случае, в смешанных стратегиях и соответствующую цену .
12. Теорема о максимине утверждает, что.
13. При оптимальных смешанных стратегиях цена игры удовлетворяет условию .
14. Теорема об активных стратегиях утверждает, что если игрок придерживается свой оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, независимо от того, какие действия предпринимает другой игрок, если только тот не выходит за пределы своих активных стратегий.
2.7.Решение игр 2xn и mx2
1. Если в игре 2xn нет оптимального решения в чистых стратегиях, то оптимальное решение в смешанных стратегиях содержит две активные стратегии у каждого из игроков.
2. В игре mx2 число активных стратегий в оптимальной стратегии каждого из игроков может быть равно или единице, или двум.
3. Оптимальное решение в игре двух лиц с нулевой суммой всегда является устойчивым независимо от того, смешанные или чистые стратегии используют игроки.
4. Если оптимальная цена матричной игры отрицательна, то конечный результат игры будет убыточным для игрока А.
5. Прибавление одного и того же числа ко всем элементам платежной матрицы не влияет на цену игры.
6. Умножение всех элементов платежной матрицы на одно и тоже положительное число не изменяет оптимальных стратегий игроков.
7. Цена матричной игры изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям.
8. Любая матричная игра 2xn или mx2 может быть сведена к игре 2х2.
3.4. Нормализация позиционной игры
1. В позиционных играх каждый из игроков может делать по несколько ходов, причем информация о прошедшем может меняться от хода к ходу.
2. Позиционные игры не могут включать случайные ходы.
3. Дерево позиционной игры имеет не более одного корня и не менее одной вершины.
4. Из корня дерева позиционной игры к какой-нибудь его вершине могут быть несколько путей.
5. Если все классы информации позиционной игры содержат только по одной вершине, то такая игра является игрой с неполной информацией.
6. Классы информации должны содержать вершины только одного игрока.
7. Вершины класса информации могут соответствовать различным временным ходам.
8. Из всех вершин, составляющих класс информации, может выходить только одинаковое количество ветвей.
9. Любая позиционная игра может быть сведена к игре в нормальной форме.
10. Игры с полной информацией имеют седловую точку и решаются в чистых стратегиях.
11. Теорема Куна утверждает, что позиционная игра с полной информацией разрешима по доминированию.
12. Для нормализации позиционной игры необходимо перечислить все возможные стратегии каждого из игроков и определить все возможные исходы игры.
4.3. Примеры решения бесконечных антагонистических игр
1. Игры называются бесконечными, если у всех игроков множество чистых стратегий бесконечно.
2. Бесконечные антагонистические игры решать труднее, чем конечные.
3. В бесконечной антагонистической игре принципом оптимальности является принцип максимина.
4. Бесконечные антагонистические игры решаются только в чистых стратегиях.
5. Играми на единичном квадрате называются такие бесконечные антагонистические игры, для которых возможные стратегии двух игроков Х и У .
6. Для антагонистических симметричных игр оптимальные стратегии игроков 1 и 2 совпадают.
7. Для антагонистических симметричных игр цена игры v>0.
8. В строго выпуклой игре игрок 2 имеет единственно оптимальную стратегию, которая является чистой.
