Автор работы: Пользователь скрыл имя, 25 Февраля 2010 в 09:45, Не определен
1. Ознакомление с теорией игр
2. Постановка задачи с позиции теории игр
3. Исследование методов теории игр
4. Обзор программных средств для решения задач теорией игр
5. Решение задач методами теории игр в примера
Теория игр нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума». (Таким образом, теория игр — одна из немногих областей математики, за достижения в которой можно получить нобелевскую премию.) Некоторые американские телевизионные шоу периодически ссылаются на теорию в своих эпизодах.
Нематематический вариант теории игр представлен в работах Томаса Шеллинга, нобелевского лауреата по экономике 2005 г..
Нобелевскими лауреатами по экономике за достижения в области теории игр стали: Роберт Ауманн, Райнхард Зелтен, Джон Нэш, Джон Харсаньи, Томас Шеллинг [7].
В ходе своего развития теория игр переросла эти рамки и превратилась в общую математическую теорию конфликтов. В рамках теории игр в принципе поддаются математическому описанию военные и правовые конфликты, спортивные состязания, «салонные» игры, а также явления, связанные с биологической борьбой за существование.
Применение теории игр:
Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики [8].
Основным в теории игр является понятие игры, являющееся формализованным представлением о конфликте. Точное описание конфликта в виде игры состоит поэтому в указании того, кто и как участвует в конфликте, каковы возможные исходы конфликта, а также кто и в какой форме заинтересован в этих исходах [9].
Лица, принимающие решения, называются игроками (деловые партнеры, фирмы, страны), а целевая функция — платежной функцией. В теории игр рассматриваются задачи принятия решений с несколькими участниками. Выигрыш каждого игрока и определяется этой платежной функцией.
Ход - это момент игры, когда игроки должны произвести выбор одного из возможных вариантов.
Периоды, в течение которых игроки делают свои ходы, называются этапами игры. Выбранные на каждом этапе ходы в конечном счете определяют “платежи” (выигрыш или убыток) каждого игрока, которые могут выражаться в материальных ценностях или деньгах. Партией игры называется некоторая определенная совокупность ходов и выборов совершающихся для достижения цели игры. Существенной чертой любой игры является то, что выигрыш каждого игрока зависит обычно не только от сделанного им самим выбора, но и от выбора других игроков.
Еще одним основным понятием данной теории является стратегия игрока. Под ней понимаются возможные действия, позволяющие игроку на каждом этапе игры выбирать из определенного количества альтернативных вариантов такой ход, который представляется ему “лучшим ответом” на действия других игроков. Относительно концепции стратегии следует заметить, что игрок определяет свои действия не только для этапов, которых фактически достигла конкретная игра, но и для всех ситуаций, включая и те, которые могут и не возникнуть в ходе данной игры. То есть, стратегия - это набор правил, формулируемых до игры, которые определяют выбор варианта в любой из могущих возникнуть ситуаций. Наилучшие стратегии для каждого из игроков называют решением игры. Результат игры, на который рассчитывают оба игрока называют ценой игры - победа или поражение, которые не всегда имеют количественное выражение, можно выразить (условно) числами (например, в шахматах: 1, 0, 1/2 ) [11].
Различные виды игр можно классифицировать, основываясь на том или ином принципе: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д.
В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трёх и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения.
По количеству стратегий игры делятся на конечные и бесконечные. Если в игре все игроки имеют конечное число возможных стратегий, то она называется конечной. Если же хотя бы один из игроков имеет бесконечное количество возможных стратегий, игра называется бесконечной.
По характеру взаимодействия игры делятся на бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные (кооперативные) – могут вступать в коалиции и принимают взаимообязывающие соглашения о своих стратегиях. Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.
По характеру выигрышей игры делятся на: игры с нулевой суммой и игры с постоянной разностью.
Игры с нулевой суммой - общий капитал всех игроков не меняется, а перераспределяется между игроками. В игре с нулевой суммой и двумя участниками выигрыш одного из них равен проигрышу другого. Таким образом, в играх с нулевой суммой существует конфликт между игроками, и поэтому их называют также антагонистическими играми. Они отражают суть принципа: «мой проигрыш - ваш выигрыш мой выигрыш - ваш проигрыш» и представляют собой ситуации чистого конфликта без всяких элементов сотрудничества. Примерами таких игр может служить покер, где один выигрывает все ставки других; либо банальное воровство.
Игры с постоянной разностью, в которых игроки и выигрывают, и проигрывают одновременно, так что им выгодно действовать сообща. Игрой с отличной от нуля суммой является торговля, где каждый участник извлекает выгоду. Сюда также относятся го, шашки и шахматы; в двух последних игрок может превратить свою рядовую фигуру в более сильную, получив преимущество. Во всех этих случаях сумма игры увеличивается. Широко известным примером, где она уменьшается, является война.
По виду функций выигрыша игры делятся на: матричные, биматричные.
Матричная игра – это конечная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путём сведения игры к задаче линейного программирования.
Биматричная игра – это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец – стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице – выигрыш игрока 2.) [12].
Также существуют следующие типы игр:
Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные. В частности, таковой является: «Дилемма заключённого». В качестве несимметричных игр можно привести «Ультиматум».
В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других. Эта информация может быть даже не совсем полной, например, игрок может узнать, что его противник из десяти своих стратегий точно не выбрал пятую, ничего не узнав о других.
Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр — с неполной информацией. Например, вся «соль» «Дилеммы заключённого» или «Сравнения монеток» заключается в их неполноте.
В то же время есть интересные примеры игр с полной информацией: «Ультиматум», «Многоножка». Сюда же относятся шахматы, шашки и другие.
Часто понятие полной информации путают с похожим — совершенной информации. Для последнего достаточно лишь знание всех доступных противникам стратегий, знание всех их ходов необязательно [13].
Представить игру можно двумя следующими способами:
Первый способ предполагает следующее:
Игра «Ультиматум» в экстенсивной форме.
Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
На рисунке 1. 1 — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.
Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.
Рисунок
1.1 - Представление игр в экстенсивной
форме
Игру, описанную подобным образом, называют игрой в развернутой, или экстенсивной форме, а само описание, как правило, составляют в виде дерева игры, аналогичного дереву решений. Игры в развернутой форме называют также позиционными играми.
Информация о работе Применение алгоритмов теории игр в экономических системах