Теория игр

Оглавление

Введение 3

1 Постановка  задачи. Описание модели 4

2 Описание  решения 6

3 Пример  из экономике, где появлялись  такие задачи. 12

4 Пример  математического решения 14

5 Основная  часть (программа) 16

5.1 Постановка задачи с  точки зрения программирования…………………...16

5.2 Структура  программы……………………………………………………….16

5.3 Текст программы…………………………………………………………….17

6 Тестирование 34

7 Руководство  пользователя 37

Заключение……………………………………………………………………….42

Список  литературы 43

 

 

 

 

Введение

 

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

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

 

 

1 Постановка задачи. Описание  модели

 

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

Матрицу игры в данном случае можно представить в виде:

	Солнечная погода	Дождливая погода
Взять зонт	Неудобство от лишнего  веса багажа	Комфорт во время дождя
Не брать зонт	Нет неудобств	Промокнуть и возможно простудится

 

С экономической точки  зрения эту же игру можно рассмотреть  со следующей матрицей игры:

	Солнечная погода	Дождливая погода
Взять зонт	Оплата лишнего веса багажа	Оплата только веса зонта
Не брать зонт	Экономия от оплаты лишнего  веса	Дополнительные траты  на сушку одежды и иммунные препараты

 

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

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

Рассмотрим простейшую математическую модель конечной конфликтной ситуации, в которой имеется два участника  и выигрыш одного равен проигрышу  другого. Такая модель называется антагонистической  игрой двух лиц с нулевой суммой. Игра состоит из двух ходов: игрок А выбирает одну из возможных стратегий , , а игрок В выбирает одну из возможных стратегий , . Каждый выбор производится при полном незнании выбора соперника. В результате выигрыш игроков составит соответственно и . Цель игрока А – максимизировать величину , а игрока В – минимизировать эту величину.

Матрица, составленная из величин

, , ,

 

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

 

2 Описание решения

 

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

Найдем наилучшую стратегию  первого игрока. Если игрок А выбрал стратегию , , то в худшем случае он получит выигрыш

a

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

aa

Величина a - гарантированный выигрыш игрока А называется нижней ценой игры. Стратегия , обеспечивающая получение выигрыша a, называется максиминной.

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

b

Он выбирает стратегию , при которой его проигрыш будет минимальным и составит

bb

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

Фактический выигрыш игрока А(проигрыш игрока В) при разумных действиях партнеров ограничен верхний и нижний ценой игры. Для матричной игры справедливо неравенство a≤b.

Если a=b=n, т.е.

n

то выигрыш игрока А (проигрыш В) определяется числом n. Оно называется ценой игры. Если a=b=n, то такая игра называется игрой с седловой точкой, элемент матрицы n, соответствующей пате оптимальных стратегий (), называется седловой точкой матрицы. Этот элемент является ценой игры.

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

Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях.

Если платежная матрица  не имеет седловой точки, т.е. a<b и a ≤ n ≤ b, то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами.

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

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

Эти наборы можно рассмотреть  как m-мерные векторы, для координат  которых выполняются условия

 

Аналогично для второго  игрока наборы вероятностей определяют n-мерные векторы  для координат которых выполняются условия

 

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

 

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

Применение оптимальной  стратегии позволяет получить выигрыш, равный цене игры:

a ≤ n ≤ b.

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

n

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

n

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

Применение методов линейного  программирования

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

Рассмотрим игру двух лиц  с нулевой суммой, заданной платежной  матрицей

 

Если платежная матрица  не имеет седловой точки, т.е. a<b и a≤n≤b, то решение игры представлено в смешанных стратегиях ,

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

 

Рассмотрим задачу оттискивания оптимальной стратегии игрока A, для которого имеют место ограничения

nnn

Величина n неизвестна, однако можно считать, что цена игры n > 0. Последнее условие выполняется всегда, если все элементы платежной матрицы неотрицательны, а этого можно достигнуть, прибавив ко всем элементам матрицы некоторое положительное число. Преобразуем систему ограничений, разделив все члены неравенства на n.

 

Где n (1.2)

По условию  Разделим обе части этого равенства на n.

n

Оптимальная стратегия  игрока А должна максимизировать величину n, следовательно, функция

 

должна принимать минимальное  значение.

Таким образом, получена задача линейного программирования:

найти минимум целевой  функции (1.3) при ограничениях (1.1), причем на переменные наложено условие неотрицательности (1.2). Решая ее, находим значения , i= и величину 1/n, затем отыскиваются значения n.

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

 

Рассмотрим задачу оттискивания оптимальной стратегии игрока B, для которого имеют место ограничения

nnn

Преобразуем систему ограничений, разделив все члены неравенства  на n.

 

Где n (1.5)

По условию  Разделим обе части этого равенства на n.

n

Оптимальная стратегия  игрока B должна минимизровать величину n, следовательно, функция

 

должна принимать максимальное значение.

Получена задача линейного  программирования: найти максимум целевой  функции (1.6) при ограничениях (1.4), причем на переменные наложено условие неотрицательности (1.5).

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

 

 

3 Пример из экономике,  где появлялись такие задачи

 

Первыми исследователями  в области теории игр были американский математик Дж.-Ф. Нейман и австро-американский экономист О. Моргенштерн («Теория  игр и экономическое поведение», 1944). Они распространили математические категории на экономическую жизнь  общества, вводя понятия оптимальных  стратегий, максимизации ожидаемой  полезности, доминирование в игре (на рынке), коалиционные соглашения. Эти  ученые оказали стимулирующее влияние  на развитие социальных наук в целом, математической статистики, экономической  мысли, в частности в области  практического использования теории вероятности и теории игр в  экономике.

 Ученые стремились  сформулировать основополагающие  критерии рационального поведения  участника рынка. Они различали  два вида игр. Первый - «с нулевой  суммой» - предусматривает такой  выигрыш, который формируется из издержек других игроков, то есть общая сумма выгоды и издержек всегда равна нулю. Другой вид - «игра с плюсовой суммой», когда индивидуальные игроки ведут борьбу за выигрыш, складывающийся из их ставок. Иногда этот выигрыш создается за счет наличия «выходного» (термин из карточной игры в бридж; так называют одного из игроков, который, делая ставки, не принимает участия в игре), совсем пассивного и часто такого, который служит объектом эксплуатации. И в том, и в другом случае игра неминуемо соединена с риском, поскольку каждый из ее участников, как считали Дж.-Ф. Нейман и О. Моргенштерн, «стремится максимально повысить функцию, переменные которой не контролируются». Если все игроки одинаково умелые, то решающим фактором становится случайность. Однако так происходит редко. Почти всегда важнейшую роль в игре играет хитрость, с помощью которой делаются попытки раскрыть замысел противника и завуалировать свои намерения, а потом занять выгодные позиции и вынудить противника действовать в убыток себе. Важная роль отводится и «контрхитрости».