8.15. Описать свойства информационных множеств в позиционной игре.

6) Разбиением ветвящихся вершин на непересекающиеся (так называемые, информационные) множества со следующими свойствами:

а) все вершины, принадлежащие одному множеству, имеют одну и ту же пометку и одинаковое количество выходящих дуг;

б) каждое множество содержит не более одной вершины, принадлежащие любому пути от корня до висячей вершины;

в) множество, в котором имеется вершина с пометкой 0, состоит из одного элемента.

8.16. Дать определение стратегий каждого игрока в позиционной игре.

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

8.17. Что такое “нормализация” позиционной игры?

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

8.18. Как можно было бы найти решение позиционной двух игроков с нулевой суммой?

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

8.19. Описать коалиционную игру.

Можно выделить 3 уровня взаимодействия (сотрудничества):

1) обмен информацией о ходе игры и складывающейся обстановке;

2) совместный выбор стратегии на основе общей договоренности;

3) объединение активных средств (ресурсов) с соответствующей координацией предпринимаемых действий.

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

Нетрудно видеть, что число всевозможных коалиций равно(по числу всевозможных непустых подмножеств).

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

8.20. Дать определение характеристической функции и дележа в коалиционной игре.

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

Пусть x_i – выигрыш i-го игрока.

После реализации игры в коалициях должно произойти перераспределение выигрышей - дележ. Это перераспределение должно удовлетворять следующим условиям:

1) , для – условие индивидуальной рациональности;

2) – условие коллективной рациональности.

Вектор , удовлетворяющий этим условиям, называется дележом для характеристической функции v.

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

8.21. Дать определение существенных и несущественных коалиционных игр и описать их свойства.

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

Коалиционная игра называется несущественной, если

.

Справедливы следующие свойства:

1) для того, чтобы коалиционная игра была несущественной необходимо и достаточно, чтобы

;

2) в несущественной игре имеется только один дележ

;

3) в существенной игре множество дележей бесконечно и имеет вид:

,

где .