Основные понятия и теории игр

Основные понятия  теории игр. Классификация и описание игр

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

 

теория игр – это математическая теория, изучающая конфликтные ситуации.

 

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

При выборе ходов  игрок руководствуется стратегией, – набором правил, формулируемых до игры и однозначно определяющих выбор действий при каждом ходе в зависимости от сложившейся ситуации ("Если ситуация сложится такая-то, то я поступлю так-то…"). Иначе говоря, стратегия – это полный набор указаний (инструкция), как нужно поступать во всех ситуациях в данной партии. Оптимальная стратегия – это стратегия, обеспечивающая при многократном повторении игры данному игроку максимальный средний выигрыш. При выборе оптимальной стратегии предполагается, что противник в игре не глупее нас.

В теории игр имеется  некоторое ограничение: не предполагается наличие множества целей, – целевая функция только одна.

Математическая  модель игры предполагает, что каждый игрок до игры выбирает свою стратегию (сознательно или случайным образом, но в последнем случае с известным  распределением вероятностей) и строго придерживается выбранной стратегии  на протяжении всей игры. Это означает, что после осуществления выбора стратегий всеми игроками игра может  осуществляться без участия самих  игроков. При этом результат игры будет либо полностью предопределён (если не используются случайные ходы), либо зависит от разыгрывания "случайности", распределение вероятностей которых  считается известным и поэтому  может также осуществляться без  участия самих игроков.

Иногда возникает  путаница между понятиями стратегии и хода в игре. Если игра заканчивается только одним ходом, то выбор стратегии определяет выбор хода. И тогда мы можем сказать, что "если я пойду так-то, а мой противник эдак, то мой выигрыш составит столько-то". В этой "одноходовке" стратегия определяет ход.

В общем случае стратегия определяет не ход, а правило выбора ходов. После того, как игрок выбрал стратегию, он может и не участвовать сам  в игре, а поручить кому-то, кто может сделать за него выбор, соответствующий выбранным им правилам. Это может быть и компьютер, который будет слепо следовать правилам и в соответствии с ними и с действиями остальных игроков делать ходы. И только в самом конце игры можно определить выигрыш игрока, соответствующий выбранным им и другими игроками стратегиям. Иными словами, стратегия – это инструкция, указывающая какой ход нужно выбирать в каждом узле (информационном множестве). Стратегия позволяет игроку продолжить игру с любой позиции, не только с начальной. Профиль стратегий (синонимы: исход, ситуация) - набор стратегий по одной от каждого игрока.

Игра с совершенной  информацией - игра, где каждый игрок  знает всю предысторию игры; т.е. на дереве есть только одноточечные информационные множества

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

Антагонистическая игра - игра двух игроков, в которой выигрыш  одного игрока равен проигрышу другого

Природа или Случай - особый игрок, у которого изначально заданы вероятности ходов (буква N на дереве).

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

1. Классификация игр

- По числу игроков: два, три и более.

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

- По количеству стратегий – конечные и бесконечные игры. В конечных играх множество игроков и количество стратегий каждого игрока конечны.

- По наличию элементов случайности при выборе стратегий: а) чистые стратегии – каждый игрок выбирает одну чистую стратегию на всю игру;  б) смешанные стратегии – выбор стратегии перед партией осуществляется случайным образом с определённым распределением вероятностей этого выбора, причём распределение вероятностей определяет сам игрок и не отступает от него в течение всей игры.

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

- По правилам  осуществления ходов. Игроки могут  делать ходы одновременно. Такие игры называются статическими. Примером статической игры являются игра в "орлянку"  при одновременном выбрасывании монеты или игра в "чёт–нечет" при одновременном выбрасывании пальцев. Альтернативой являются динамические игры, в которых игроки выполняют ходы последовательно. Например, сначала первый  игрок делает ход, затем второй игрок, проанализировав ход первого игрока, делает свой ход и так далее.

- По информации, которой располагают игроки.

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

б) В играх с неполной информацией некоторые из игроков (по крайней мере, один) не располагают полной информацией о платежных функциях всех других игроков. Тогда они ориентируются на свою функцию выигрыша и на вероятностное распределение на множестве возможных функций выигрыша других игроков. Полезность информации приводит к вопросу о возможности её приобретения, например, покупки.

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

г) В играх с несовершенной информацией хотя бы один из игроков при осуществлении какого-то своего хода не знает всю предысторию развития игры. Например, игрок на четвертом ходе не знает, каков выбор сделал его противник на предыдущем ходе. Или, например, он забыл, как он сам пошел на первом ходе и т. д.

2. Формы описания игры

В теории игр различают  две формы описания игры: развёрнутую и нормальную.

Развёрнутая форма описания игры

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

Определение. Развернутая форма представления игры предполагает:

1) множество игроков;

2а) определение  очередности ходов (в какой  последовательности игроки принимают  решения);

2б) каково множество  возможных решений каждого из  игроков в момент их хода;

2в) какой информацией  располагает каждый из игроков  в моменты принятия решений;

3) платежные функции  каждого игрока, определенные на  всевозможных комбинациях выбираемых  игроками ходов.

 

Нормальная форма описания игры

Рассматриваются все  возможные стратегии каждого  игрока и определяются платежи, соответствующие  любой возможной комбинации стратегий  всех игроков. В случае двух игроков  и конечного числа возможных  стратегий нормальная форма представима  в виде двух платёжных матриц, показывающих, какую сумму получит каждый из игроков при всех возможных стратегиях. Можно представить эти две  матрицы в виде одной матрицы, с элементами в виде пары чисел, –  выигрышей 1-го и 2-го игроков:

Здесь и – элементы платёжных матриц первого и второго игроков; и – их стратегии. Такие игры называются биматричными играми.

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

• множество стратегий с элементами :  (это может быть как конечное, так и бесконечное множество стратегий);

• функцию выигрыша (функцию полезности) , являющейся отображением декартова произведения   в R. Элемент из множества S назовём исходом игры, или ситуацией, или профилем стратегий.

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

3. Доминирующие  и недоминируемые стратегии

Рассмотрим игру N игроков в нормальной форме . Часто нам придется рассматривать стратегию одного игрока (i – го) при фиксированных стратегиях других игроков. Для этого удобно воспользоваться следующими обозначениями.

Определение 1. В игре в нормальной форме стратегия игрока i доминирует стратегию (обозначим это в виде ), если

Стратегия игрока i доминирует стратегию , если независимо от стратегии всех остальных игроков ( ) стратегия "не хуже" стратегии , а кое – где (хотя бы в одном из случаев выбора стратегий остальными игроками ) лучше. Стратегия называется доминируемой стратегией (или слабо доминируемой стратегией).

Определение 2. В игре в нормальной форме стратегия игрока i строго доминирует стратегию (обозначим это в виде или ), если . Стратегию в этом случае назовем строго доминируемой стратегией.

Очевидно, если стратегии  выбираются независимо друг от друга, то игроку i не имеет смысла выбирать строго доминируемые стратегии.

Назовём стратегию недоминируемой, если её не доминирует никакая другая стратегия.

Стратегия игрока i в игре в нормальной форме   называется доминирующей стратегией, если  .

Исход игры называется равновесием в доминирующих стратегиях, если является доминирующей стратегией i–ого игрока для всех i.

Стратегии и i – ого игрока называются эквивалентными, если

.

Пример 3. Рассмотрим игру двух игроков с платёжной матрицей:

Сравним стратегии  первого игрока. Поскольку 3>2 и 1>0, то вторая стратегия первого игрока строго доминирует первую .

То же самое можно  сказать и в отношении второго  игрока .

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

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

1. Игры  двух участников с противоположными интересами. Осторожные (минимаксные и максминные) стратегии. Нижняя и верхняя цена игры. Седловая точка

Игру двух игроков с нулевой суммой назовём игрой с противоположными интересами (или антагонистической игрой). Она имеет следующий вид: . Игроки являются чистыми антагонистами. В случае конечной игры с нулевой суммой достаточно знать одну из матриц, – вторая матрица равна платёжной матрице 1-го игрока, умноженной на -1: . Такую игру можно описать одной матрицей:

Очевидно, антагонистические  игры относятся к играм с полной информацией.

Игра с постоянной суммой: . Такую игру всегда можно свести к игре с нулевой суммой с новыми платёжными матрицами:

.

Пример 6. Рассмотрим антагонистическую игру двух игроков. Пусть матрица первого игрока имеет вид:

Очевидно, какую  бы стратегию не выбрал второй игрок (верхний индекс равен 2), первому  игроку первая стратегия более выгодна, чем третья . Поэтому достаточно рассмотреть только первые две строки матрицы:

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