Теория игр.


Во многих областях человеческой деятельности встречаются ситуации принятия управленческих решений в условиях неопределенности. При этом неопределенность может быть связана как с сознательными действиями, так и с другими факторами, влияниями на эффективность решения.
Опр.:Ситуации в которых эффективность принимает односторонние решения зависит от действий другой стороны, называются конфликтными.
Конфликт всегда связан с наличием разногласий.
Опр.: Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приведет к уменьшению выигрыша другой стороны на такую же величину, и наоборот.
Теория игр занимается выработкой рекомендаций по рациональному образу действий участников многократно повторяющегося конфликта.
Игра представляет собой математическую модель реальной конфликтной ситуации, анализ которой ведется по определенным правилам. Они позволяют установить последовательность, объем имеющейся информации у одной стороны о поведении другой, результат игры.
В зависимости от числа участников игры подразделяются на парные и многочисленные. Участники множественной игры могут образовывать коалиции. Множественная игра обращается в парную, если ее участники образуют две постоянные коалиции.
Стороны , участвующие в игре, называются игроками. Иногда под игроком понимается природа, формирующая условия, в которых необходимо принимать решения.
Стратегией игрока называется совокупность правил, определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от ситуации, оговаривается в процессе игры. Фактически, число стратегий совпадает с числом вариантов действий.
Игра называется конечной , если число стратегий игроков конечно и бесконечной , если хотя бы у одного из игроков число ситуаций является бесконечным.
Стратегия игрока называется оптимальной , если она обеспечивает данному игроку при многократном повторении игры максимально возможный средний выигрыш или минимально возможный средний проигрыш, независимо от поведения противника.
Выбор одной из предусмотренных правилами игры стратегий и ее осуществление называется ходом . Ходы бывают личные и случайные. Ход называется личным, если игрок сознательно выбирает один из возможных вариантов действий и осуществляет его (ход в шахмотах, шашках). Ход называется случайным, если выбор производится не игроком, каким-либо механизмом случайной выборки (бросание монеты).
В зависимости от цели исследования любую игру можно рассматривать в развернутой(позиционной) или в нормальной(частный случай - матричной) форме. В развернутой форме лучше раскрывается последовательность событий, она более наглядна для многоходовых игр. Здесь показываются очередности ходов игроков, их информативность и выигрыш. Недостатком этой формы представления является сложность решения. Нормальная форма игры менее наглядна. Однако, большинство методов нахождения решений разработано именно для этой формы.
Развернутая форма представляет игру в виде дерева, имеющего структуру:
  1. Начальная точка – исходная позиция игры;
  2. Ребра, исходящие из одной и той же вершины называются альтернативными. Каждое ребро соответствует ходу игрока;
  3. Вершины, имеющие хотя бы одну альтернативу, называются промежуточными;
  4. Вершины не имеющие ни одной альтернативы называются конечными и означают конец игры; возле каждой конечной вершины записывается вектор определяющий выигрыш игроков в данной позиции;
  5. Множество всех промежуточных вершин разбивается на N + 1 множество , которые называются множествами очередностей. В множестве – ходит i-ый игрок, – очередь хода случая. Для каждой позиции из указывается вероятность выбора альтернатив;
  6. Нециклический путь от начала дерева до любой окончательной позиции называется партией.
Пример 1: В игре в орлянку игрок I выбирает решетку (Р) или герб(Г).


Игрок II не зная выбора игрока I так же выбирает решку или герб. Если оба противника совершают одинаковый выбор, то игрок II выигрывает единицу у игрока I. В противном случае I выигрывает единицу у игрока II. На рисунке показано дерево игры.

Пример 2: Пусть игрок I имеет две, а игрок II – три фишки. Независимо и тайно друг от друга игроки откладывают произвольное число фишек.

Если при этом суммарное количество отложенных фишек окажется четным, то их выигрывает игрок I, в противном случае фишки выигрывает игрок II.
В данной задаче игрок I имеет две, а игрок II – три стратегии. Как и в предыдущем примере, здесь нет случайного хода.

Пример 3: Каждому из двух игроков сдается по три карты одинаковой масти. Три карты третьей масти тасуются и затем открываются по очереди. Каждый раз когда карта открыта, оба игрока по своему желанию открывают, наудачу какую-то одну из своих карт.

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

Hosted by uCoz