Антагонистическая игра

Самая жёсткая модель конфликта: два игрока, и интересы противоположны до конца — сколько выиграл один, ровно столько проиграл другой. Антагонистическая игра — парная игра с нулевой суммой: платёжная матрица A задаёт выигрыш первого игрока, а второй получает $-a_{ij}$, поэтому отдельной матрицы для него не нужно. Решение ищется через границы гарантий: первый игрок берёт строку с максимумом из минимумов, второй — столбец с минимумом из максимумов; логика максимина и минимакса описывает поведение обеих сторон. Когда границы совпали, у матрицы есть седловая точка, и цена игры достигается в чистых стратегиях — так устроены задачи из урока о чистых стратегиях. Нулевая сумма и антагонизм совпадают потому, что участников двое: при трёх и более игроках общий нулевой баланс уже не делает интересы взаимно противоположными.

Дерево игры — рабочий инструмент антагонистической задачи: вершины — позиции, листья — платежи, уровни чередуют ходы сторон. Пример глубины 2 с ветвлением 2 даёт 4 листа со значениями 3, 5, 2, 8: на нижнем уровне ходит минимизирующий противник, его гарантии равны $3=\min (3,5)$ и $2=\min (2,8)$; корень выбирает максимум — цена игры 3, и первый игрок идёт в левую ветвь. Всего в дереве 7 узлов, а альфа-бета-отсечение, увидев в правой ветви лист 2, который уже хуже гарантированных 3, обрывает вторую ветку: проверены 3 листа из 4 — тот же ответ дешевле. Если седловой точки нет, чистые стратегии нестабильны: любой предсказуемый ход наказуем, и гарантию спасают смешанные стратегии — игроки рандомизируют ходы по вычисленным частотам, и цена игры существует уже всегда; это теорема фон Неймана, фундамент всей матричной ветви теории игр.