Элементы теории игр

Важнейшим разделом исследования операций является теория игр.

Теория игр впервые была систематически изложена Нейманом и Моргенштерном в 1944 г., хотя отдельные результаты были опубликова­ны еще в 20-е годы. Наиболее широко теория игр применяется в эконо­мике, так как экономическим конфликтам легче всего придать численную форму.

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

Различают антагонистические игрыиигры с не противополож­ными интересами.Антагонистическими называются игры, в кото­рых интересы сторон противоположны.

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

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

Введем принятую в теории игр терминологию.

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

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

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

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

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

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

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

Некоторый набор из n стратегий называется равно­весным, если для каждого игрока i и для каждой его стратегии

.

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

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