Реферат “Теория игр”

Министерство образования

Санкт-Петербургский Государственный

Электротехнический Университет

Кафедра математики

Реферат

“Теория игр”

Выполнил: Лесковец Юрий

Группа: 0552

Преподаватель:

Санкт – Петербург

2001

Теория игр – раздел математики предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта.

Оттельные математические соображения по поводу конфликтов высказывались (начиная с 17 века) многими учеными. Математическая теория игр была разработана американскими математиками Джоном Нейманом и Оскаром Моргенштерном в 1944 году, как средство математического подхода к явлениям конкурентной экономики.

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

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

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

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

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

Строны учавстующие в конфликтной ситуации – игроки.

Результат, как правило, можно условно преставить следующим образом:

+1 – выйгрыш;

-1 – проигрыш;

0 – ничья;

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

Ход – в теории игр – выбор одного из предусмотренных правилами игры вариантов.

Ходы:

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

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

Игры:

-  с полной информацией, когда каждый игрок при каждом ходе знает результаты всех предыдущих ходов. Например, шахматы, шашки, «крестики и нолики».

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

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

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

В играх состоящих только из случайных ходов, стратегии отсутствуют!

Игры по числу возможных стратегий делятся на конечные и бесконечные.

Конечная игра в которой игрок А имеет m стратегий, а игрок В – n стратегий, называется игрой m´n.

Рассмотрим игру m´n двух игроков А и В.

Стратегии

А: А1, А2, А3, А4, А5, А6, А7… …Аm;

B: B1, B2, B3, B4, B5, B6, B7… …Bn;

Каждая сторона выбрала определенную стратегию: Аi, Bj и пусть А – выигрывает, В – проигрывает. Если игра состоит только из личных ходов, то выбор стратегий Аi, Bj однозначно определяют исход игры aij – выирыш.

Если игра содержит случайные ходы, то выйгрыш при паре стретегий Аi, Bj есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае оценкой выйгрыша является его среднее значение (математическое ожидание). aij – так же выирыш (со случайными или без случайных ходов).

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

В А	B1	B2	...	Bn
А1	A11	A12	... ...	= ||aij||   A1n
А2	A21	a22	... ...	A2n
... ...	... ...	... ...	... ...	... ...
Аm	am1	am2	...	amn

Примеры.

Пример 1:

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

Проанализируем игру и составим ее матрицу.

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

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

У нас две стратегии: А1 – выбирать герб и А2 – выбирать цифру. У противника так же две стратегии: В1 – герб и В2 – цифра. Таким образом, данная игра есть игра 2´2. Пусть выигрыш – это +1;

Составим матрицу игры:

B A	B1	B2
A1	1	-1
A2	-1	1

На примере этой игры, можно понять многие существенные идеи теории игр.

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

Допустим, что мы (А) выбрали себе какую-то стратегию (скажем А1) и придерживаемся ее. Тогда уже по результатам первых ходов противник догадается о нашей стратегии и будет на нее отвечать наименее выгодным для нас образом, то есть выбирать цифру. Нам явно невыгодно всегда применять какую-то одну стратегию, мы должны иногда выбирать герб, иногда – цифру. Однако, если мы будем чередовать гербы и цифры в какой-то определенной последовательности (например, через один), противник тоже может догадаться об этом и ответить на эту стратегию наихудшим для нас образом. Следовательно, надежным способом, гарантирующим, что противник не будет знать нашей стратегии, будет такая стратегия, когда мы ее сами наперед не знаем. Это можно обеспечить, например, подбрасыванием монеты. Мы подошли к важному понятию теории игр – смешанной стратегии. (Ответ: А1 и А2 должны чередоваться с одинаковой частотой (в силу симметричности))

Смешанная стратегия [Игрок вместо того, чтобы выбрать какую-то одну стратегию, может предоставить выбор стратегии случаю, то есть он может выбрать распределение вероятностей по множеству своих стратегий, а после этого соответствующий случайный механизм выбирает конкретную стратегию для данной партии игры.] – это распределение вероятностей по всему множеству стратегий игрока. Назначение смешанной стратегии – помешать одному из игроков раскрыть стратегию своего противника.

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