Лекция 11 Теория игр и принятие решений

План

11.1. Общее представление о теории игр

11.2. Стратегии. Нормальная форма игры

11.3. Ситуации равновесия

11.4. Антагонистические игры. Игры с нулевой суммой

11.5. Нормальная форма

11.6. Теорема о минимаксе

11.7. Другие виды игр

11.1. Общее представление о теории игр

Теория игр есть теория моделей принятия решений, она не занимается этими решениями как психологическими, волевыми актами. Не занимается она и вопросами их практической реализации. В рамках теории игр принимаемые решения выступают как достаточно упрощенные и идеализированные схемы реальных явлений.

Наше представление об игре определяется наличием 3-х элементов:

1. Чередованием ходов, которые могут быть как личными, так и случайными.

2. Возможной недостаточностью информации.

3. Наличием функция выигрыша.

С позиционной игрой связывают понятие топологического дерева или дерева игры, представляющего собой конечную совокупность узлов, называемых вершинами, соединенных ребрами, притом так, что получается связанная фигура, не содержащая простых замкнутых фигур.

Под позиционной игрой n лиц понимают следующее:

1. Топологическое дерево Г с выделенной вершиной А, называемой начальной позицией игры.

2. Функция выигрыша, которая ставит в соответствие каждый окончательной позиции дерева некоторый n-мерный вектор (для n игроков).

3. Разбиение множества всех неокончательных позиций (т.е. неокончательных вершин) дерева Г на n+1 множество S₀ , S₁ , …, S_n, которые называют множествами очередности. Множество S₀ соответствует началу (может быть связано со случайностью), S₁ – множество очередности для 1-го игрока (1-ый уровень от А - см. рис. 11.1), и т.д.

4. Вероятное распределение для каждой позиции из S₀ на множестве непосредственно следующих за ней позиций (т.е. из каждой позиции S₀ следуют варианты позиций с некоторой вероятностью).

5. Подразбиение множества S_i для каждого i = на подмножества , называемые информационными множествами; при этом позиции из одного и того же информационного множества имеют одинаковое число непосредственно следующих за ними позиций, т.е., альтернатив, и никакая позиция не может следовать за другой позицией из того же самого информационного множества.

6. Для каждого информационного множества задано множество индексов , взаимно однозначно отображающее множество альтернатив (возможных ходов) для каждой позиции из .

А – начальная вершина (позиция), В, С – промежуточные вершины (позиции), Х – окончательная

Рис. 2.1. Дерево игры

В этом определении перечислены все элементы игры. Условие (1) устанавливает, что имеется начальная позиция. Условие (2) задает функцию выигрыша. Условие (3) разделяет множество неокончательных позиций на позиции с ходом случая (S₀) и личные позиции, соответствующие каждому из n игроков (S₁ , …, S_n ). Из позиции множества S_i очередь хода принадлежит игроку i. Условие (4) задает схему рандомизации в каждой позиции случая. Условие (5) разбивает позиции каждого игрока на информационные множества (игрок знает лишь, в каком информационном множестве он находится, но не знает, в какой именно позиции этого множества).

Следует отметить основные определения, характерные для задач теории игр:

Игра называется парной, если количество сторон (игроков) равно 2.

Игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу другого. В противном случае она называется игрой с ненулевой суммой.

Игра называется игрой с полной информацией, если результаты случайных ходов и предыдущих личных ходов полностью известны каждому игроку.

Игра называется конечной, если число стратегий всех игроков является конечным. Или. Игра называется конечной, если ее дерево содержит только конечное число вершин.