Теория игр и их приложения

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего образования

«Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского»

(ННГУ)

Арзамасский филиал

Физико-математический факультет

Кафедра прикладной информатики

Выпускная квалификационная работа

бакалаврская работа

Теория игр и их приложения

Выполнил: Быков Д.В.

студент 5 курса

заочной формы обучения,

направление «Менеджмент»

Научный руководитель

Широков Л.В.

Арзамас 2017



Введение

Актуальность темы исследования. Теория игр, отрасль математики, усваивающая форму модели принятия наилучших решений в ситуациях конфликта. Теория приобрела своё название так, благодаря тому что, нетрудным образцом конфликта является игра (к примеру, шахматы). Как в игре, так и в конфликте игроки ставят перед собой цели и стараются их достичь, принимая различного рода стратегические решенияНечай, М.Н. Теория игр в экономике. Практикум с решением задач (для бакалавров) / М.Н. Нечай. - М.: КноРус, 2013. - 264 c.

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

Отдельные математические проблемы, связанные с конфликтами подвергать рассмотрению (с XVII века.) многими учеными. Систематическая является математической теорией игр, она была тщательно разработана американскими учеными Дж . Д. Нейман и Моргенштерн (1944) в качестве средства математического подхода к явлениям конкурентной экономики. В ходе своего развития, теория игр переросла эти рамки. Теория игр, сформированная для решения экономических и социальных условиях математической задачи, в целом не может быть сведено к классической математической теорий, созданных для решения физических и технических проблем. Тем не менее, во всех видах вопросов теории конкретной игры широко применяется весьма разнообразные классические математические методы. Кроме того, она связана с рядом математических дисциплин внутренне. В теории игр систематически и существенно используются понятия теории вероятностей. С точки зрения этой теории может быть выражено в различных задачах математической статистики, а также как он относится к теории принятия решений, она рассматривается как неотъемлемая часть математического аппарата исследования операций. В рамках теории игр, в принципе, поддаются математическому описанию военных и правовых конфликтов, спорта, "салон" игры, а также явлений, связанных с биологической борьбой за существование. Это позволяет математизировать индивидуально важные аспекты принятия решений в области машиностроения, сельского хозяйства, медицины и социологии.

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

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

Задачи:

- узнать историю рождения теории игр;

- определить понятие и сущность теории игр;

- охарактеризовать основные типы игр;

- рассмотреть вероятные сферы внедрения данной теории на практике.

Объект изучения- теория игр.

Предмет исследования - сущность и применение теории игр на практике.

Структура работы: введение, трех глав, выводов, заключение, списка литературы.



Глава 1. Сущность теории игр

1.1 История возникновения теории игр

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

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

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

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

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

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

Если история шахматных или карточных игр насчитывает уже несколько тысяч лет, первые наброски теории появились всего триста лет назад в работах Бернулли. Работы Пуанкаре и Борелем частично предоставляют информацию о характере теории игр. Обычное "семейное древо" представленное в виде дерева в смысле теории графов, в которых ветвление происходит от одного "корня". Зарождение теории игр начинается с книги Дж. Фон Неймана и О. Моргенштерна. Вследствие этого исторического хода, теория игр развивается как математическая дисциплина, и непосредственным образом разделяется на три этапа.

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

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

И, наконец, третий этап теории игр в своем подходе к изучаемого объекта мало, в отличие от других отраслей математики и развивались в значительной степени на общих законах с ними. В то же время, конечно, большое влияние на формирование направлений теории игр имеет специфику его практического применения, как фактическое и допустимое. Говорят, что первооткрыватель теории игр, выдающийся американский математик XX века. Джон фон Нейман пришел к идеям своей теории, наблюдая, как играют в покер. Отсюда и название "теории игр". Дж. Монография. Нейман и Моргенштерн, "Теория игр и экономическое поведение" был опубликован в 1944 году. Эта теория описывает поведение рационального принятия решений взаимосвязанных условий, помогая решить множество актуальных проблем в различных научных областях. Монография подчеркивала, что стратегическое поведение, конкуренция, сотрудничество, риск и неопределенность являются основными элементами теории игр и непосредственно связаны с целями управления. В электронной книге содержатся главным образом экономические примеры, поскольку экономические конфликты легче дать численную форму Шикин, Е.В. От игр к играм./Е.В. Шикин. - М.: УРСС, 2011. - 149с.. Во времена Второй мировой войны и после её окончания теорией игр основательно начали заниматься военные, которые увидели в большой потенциал для изучения стратегических решений. Дальше опять же, основное внимание было уделено экономическим вопросам. В настоящее время проводятся значительные работы, направленные на расширение использования среды теории игр. Прогресс в этой отрасли показал производительность игры в работе приложения. В последние годы эти методы проникли и практическое управление. В наше время, значение теории игр существенно возросло во многих областях экономических и социальных наук. В экономике, она применима не только для решения различных проблем общей экономической цели, но и для рассмотрения стратегических проблем предприятий, развитие структур управления и систем стимулирования. В течение с 1958-1959 года по 1965-1966 годы. Она была создана в советской школе теории игр, которая была характерна для исследования в области игр с нулевой суммой и строго в военных целях. Первоначально это было причиной отставания от американской школы, так как в то время главным открытием в антагонистических играх уже сделаны. В советских математиков до середины 1970-х годов не допускаются в сфере управления и экономики. И даже тогда, когда советская экономическая система стала разрушаться, экономика не стала основным направлением для теоретико-игрового исследования. Специализированные институты, занимающиеся по наш день теорией игр - Институт системного анализа РАН Громенко, Г.Н. Теория игр./Г.Н. Громенко. - М.: Издательство МГОУ, 2012. - 198с..

игра конфликт выигрыш решение

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

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

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

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

Для каждого формальные правила игры введены, т.е. условия системы, которая определяет:

1) действия игроков;

2) объем информации каждого игрока на поведение партнеров;

3) усиление, что приводит к каждому набору действий Дюбин, Г.Н. Введение в прикладную теорию игр./Г.Н. Дюмин, В.Г. Суздаль. - М.: Наука, 2009. - 310с..

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

Если мы пишем - выигрыш одного игрока, б - еще одну победу, то игра с нулевой суммой Ь = с, поэтому достаточно рассмотреть, например а. Выбор и реализация одного из запланированных действий, правила называются ходом игрока. Ходы могут быть личными и случайным. Частный курс - осознанный выбор игрока одного из возможных действий (например, двигаться в шахматной игре). Случайный поворот - он случайно обнаружил действие (например, выбор карты из колоды перемешиваются).

Стратегия игрока играть роль совокупности правил, устанавливающих выбор его действия для каждого отдельного курса, в зависимости от ситуации. Обычно во время игры для каждого игрока делает во время личного выбора в зависимости от конкретной ситуации. Тем не менее, вполне возможно, что все решения, принятые игроком заранее (в ответ на любой ситуации). Это означает, что игрок выбрал назначенную стратегию, которая может быть определена как список правил или программы. Игра называется конечной, если каждый игрок имеет последнее число стратегий, и бесконечной - в противном случае Оуэн, Г. Теория игр./Г. Оуэн. - М.: Изд-во ЛКИ, 2011. - 232с.

Название Матрица игры, осуществляется по следующим правилам:

1. Принимают участие два игрока;

2. Каждый игрок обладает последним набором стратегий;

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

4. Победу и поражение показывают числами.

Матрицей называется игра с нулевой суммой, если вы выиграете в этой игре один игрок называет потерю второго игрока.

Каждая матрица игра с нулевой суммой имеет матрицу выигрыша.

Для того, чтобы построить эту матрицу, обозначаемый одним из игроков символа А, а другой - символ B, и будем считать, что A1, А2, ... Am - стратегии, которые могут быть использованы, игрок A и B1, B2,. .. Bn - стратегии, которые могут использовать проигрыватель B (таблица 1).

Проведение каждой партии матричной игры сводится к выбору игрока Ai-го ряда и игроков В j-й столбец и приобретение игрока A ( за счет игроков B) выигрыша. Матрица игра, в которой игрок А имеет m стратегий, а также

Игрок B - n стратегий, такой тип игры называется м ? п. Элементы аij (i=1,2,…, m; j=1,2,…, n) имеют равные выигрыши игрока A (и поражением игрока B) при использовании игроками данной стратегий Ai и Bj соответственно.

Матрица C называется платежной матрицей игры Таблица 1

Стратегии	В1	В2	…	В n
А1	a11	a12	…	a1n
А2	a21	a22	…	a2n
…	…	…	…	…
Аm	am1	am2	…	amn

Обычно минимальные числа в каждой строке обозначаются ? i и выписываются в виде добавочного столбца матрицы (табл. 2).

Таблица 2

Стратегии	В1	В2	…	В n	? i
А1	a11	a12	…	a1n	? 1
А2	a21	a22	…	a2n	? 2
…	…	…	…	…	…
А m	am1	am2	…	amn	? i
?j	?1	?2	…	?n

Каждая строка будет иметь альфа ? i = minaij. Предпочтительными для игрока А является стратегия в которой ? i становится максимальным, т.е.

? = макс (minaij)

1?i? м 1?j? п

где ? - гарантированный результат (максимин).

Если мы будем придерживаться стратегии максимума, для любого поведения сторон B (противника) гарантирован выигрыш, во всяком случае, не меньше, чем ?. Таким образом, ? также называется нижней ценой игры - гарантированный минимум, который может быть достигнут при наиболее благоразумным (перестраховочной) стратегии. Если игрок А будет придерживаться стратегии максимума, то он уверен, чтобы выиграть не меньше, чем ?, для любого поведения игрока B. Обратимся к анализу матрицы выигрышей с точки зрения игрока B, обеспокоен тем, что игрок А выигрывает, как можно меньше. Она должна учитывать все свои стратегии, выделяя каждому из них максимальные значения выигрыша: ? = мин (maxaij),

1?i? m1?j? п

который дает минимаксный выигрыш или минимакс.

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

Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «принципом минимакса», и минимаксная стратегия и стратегия Максимин называется общим термином "минимаксные стратегии".

Игра называется игрой с седловой точкой, если его нижняя и верхняя значения совпадают, то есть выполняется равенство

? =maxminаij= minmaxаij= ?

1?i? m 1?j? n 1?i? m 1?j? n

Если элемент является одновременно минимальным в своей строке и максимальным в своем столбце, то такой элемент аi0j0 называется седловой точкой. Если нижняя цена игры отличается от верхней цены игры, то игра является игрой без седловой точки. Для любой игры без седловой точки сделали неравенство ?<?.

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

Действительно, в игре без седловой точке элемент матрицы выигрышей аі0ј0 соответствующая минимаксная стратегия игрока A, не требуется, чтобы быть минимальным в строке. Следовательно, игрок B, зная, что игроку в следующей игре будет использовать минимаксные стратегии ai0j0, может выбрать стратегию, отвечающую минимальному элементу строки значения. В итоге выигрыш игрока А уменьшится от значения аі0ј0 значение. Аналогичным образом можно ввести и игроку вдруг применяя стратегию против игрока Б соответствует максимальный элемент в j0 колонки. Кроме того, доказано, что в этой повторяющейся игре без седловой точки, игроку, чтобы обеспечить среднее значение превышает ?, следует чередовать свои стратегии А1, А2, ...,АМ. Игрок Б для достижения наилучших результатов, рекомендуется также чередовать свои стратегии В1, В2,...,БН(Рог, 1989).В играх, которые повторяются многократно, каждая из стратегий

A1, A2, …,Am называется чистой стратегией.

Стратегия игрока A, обозначаемая

SА= А1….Аm

Р 1 ….Рm

и состоящая в том, чтобы применять чистые стратегииA1, A2, …,Am, чередуя их по случайному закону с частотами р1, …., рm, называется смешанной стратегией. Частоты р1, ….,рm удовлетворяют соотношению

p1+ p2+…+pm= 1

Чистый и смешанная стратегия игрока B определяются аналогично.

Каждая чистая стратегия является частным случаем смешанных стратегий, когда одна из стратегий, применяемых на частоте 1, а все остальные - с частотой 0.

Смешанная стратегия, выбранные игроки называется оптимальным, если односторонний отказ от любого игрока от оптимальной стратегии может изменить средний прирост только в неблагоприятную для игрока. Для того, чтобы найти решение в игре для каждого игрока, вам нужно выбрать стратегию, которая отвечает оптимальные условия, то есть. Е. Один из игроков, чтобы получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальные потери, если первый придерживается своей стратегии. Оптимальные стратегии также должны удовлетворять условиям согласованности, т. E. Любой из игроков, чтобы быть прибыльным, чтобы отказаться от своей стратегии в этой игре. Для того, чтобы найти оптимальную стратегию, необходимо проанализировать все возможные стратегии и рассчитывать на то, что разумный противник для каждого из них ответ, в котором победитель и минимум Оуэн, Г. Теория игр./Г. Оуэн. - М.: Изд-во ЛКИ, 2011. - 232с.

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

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

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

1.3 Классификации игр

Распознают два высоких класса игровых моделей: модели в отсутствии противодействия (либо их еще называют «играми с природой») и модели с противодействием (действия конкурентов).

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

Классификацию игр с противодействием проводят, опираясь на различных принципах Протасов, И.Д. Теория игр и исследование операций./И.Д. Протасов. - М.: «Гелиос» АРВ, 2012. - 368с..

КЛАССИФИКАЦИИ ИГР

Рисунок 1. - Классификация игр

КОЛИЧЕСТВО ИГРОКОВ

Рисунок 2. - Количество игроков

Признает игру с двумя, тремя или большим числом участников в зависимости от количества игроков.

КОЛИЧЕСТВО СТРАТЕГИЙ

Рисунок 3. - Количество стратегий



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

ХАРАКТЕР ВЗАИМОДЕЙСТВИЯ

Рисунок 4. - Характер взаимодействия

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

ХАРАКТЕР ВЫИГРЫШЕЙ

Рисунок 5. - Характер выигрышей

Главным аспектом в теории игр, когда выигрыш одного из игроков является потеря другого, то есть, там можно увидеть прямой конфликт между игроками. Такие игры называются игры с нулевой суммой, или антагонистических игр. Примерами таких игр могут быть в покер, где выигрывает все ставки других; Реверси, которые захвачены чипсов противника; или банальное воровство. Многие игры, изучаемые математиков разного рода: в играх с ненулевой суммой выигрыша игрока с не обязательно означает потерю другого, и наоборот. Исход игры может быть меньше или больше нуля. Такие игры могут быть преобразованы в нулевой суммой - это делается путем введения фиктивного игрока, который "присваивает" избыток или нехватку средств. Кроме того, играя с ненулевой суммой является торговля, где каждый участник выгоды. К этому виду относятся такие игры, как шашки и шахматы; в последние два игрока могут превратить свой ранг и файл для формирования более сильной, получить преимущество. Во всех этих случаях сумма игры увеличивается. При постоянной разнице игр и игроков выиграть и проиграть в то же время, так что им выгодно действовать сообща. Между этими крайностями существует множество игр с ненулевой суммой, где есть конфликты и согласованные действия игроков Яновская, Е.Б. Антагонистические игры// Проблемы кибернетики./Е.Б. Яновская. - М.: Наука, 2008. - С. 221-246..

ВИДЫ ФУНКЦИЙ ВЫИГРЫША

Рисунок 6. - Виды функций выигрыша

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

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

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

Если функция выигрыша выпукло, то эта игра называется выпуклой. Игры также делятся на симметричные и асимметричные. Игра будет симметричным, когда соответствующие игроки стратегии будут иметь те же выплаты, т.е. будут равны. Те. если выигрыш для одних и тех же движений не меняются, несмотря на то, что игроки будут обменены. Многие изучили игру для двух игроков - симметричными. В частности, они заключаются в следующем: «Дилемма заключённого», «Охота на оленя», «Ястребы и голуби». «Ультиматум» или «Диктатор» можно привести в качестве ассиметричных игр.

СОСТОЯНИЕ ИНФОРМАЦИИ

Рисунок 7. - Состояние информации

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

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

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



КОЛИЧЕСТВО ХОДОВ

Рисунок 8. - Количество ходов

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

В большинстве изученных играх численность игроков, ходов, событий и результатов, конечно же, то есть, они - являются дискретными. Тем не менее, эти компоненты могут быть распространены на множество вещественных (материальных) чисел. Игры, которые включают в себя такие элементы, которые часто называют дифференциалом. Они всегда связаны с какой-то реальном масштабе (обычно с временным масштабом), хотя происходящие в этих событиях может быть дискретный характер. Дифференциальные игры находят свое применение в технике и технологии, физике Раскин, М.А. Введение в теорию игр.// Летняя школа «Современная математика»./М.А. Раскин. - Дубна: 2012. - 344с. .

Выводы по первой главе

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

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

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

3. Основные понятия теории игр: игра, конфликт, ситуация, коалиции действия, коалиции интересов, ход, стратегия, платёжная матрица, цена игры, седловая точка, принцип минимакса, выигрыш, решение игры.

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



Глава 2. Прикладное значение теории игр

2.1 Способы решения задач

Теоремы существования в теории игр доказано в основном те же неконструктивные означает, что в других темах по математике: с помощью теоремы о неподвижной точке, распределение бесконечной последовательности сходящейся под последовательности и т.д., или, в очень узком случае, интуитивным руководством тип решения и последующего нахождения решения в форме Краснов, М.Л. Высшая математика./М.Л. Краснов, А.И. Киселёв. - М.: Изд-во ЛКИ, 2011. - Т. 5. - 300с.

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

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

Следствие 1. Каждая игра имеет свою цену.

Следствие 2. Игры Цена ??V?? удовлетворяет неравенству.

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

Допустим, что существуют две соперничающие фирмы, изготовляющие одни и те же товары. Эти две компании разработали стратегию продажи товаров для обеспечения наибольшей прибыли. В общем, это можно записать в матричной форме. Пусть фирма А разработала четыре стратегии, а фирма В - пять стратегий. То есть фирма А- А1; А2; А3; А4 Аi, где i = 1,4.Фирма В соответственно - В1; В2; В3; В4; В5 Вj, где j = 1,5.Каждая фирма от реализации своей стратегии намеревается получить какой-то доход (табл. 3).



Таблица 3

Стратегии	В1	В2	В3	В4	В5
А1	5	8	7	5	4
А2	1	10	5	5	6
А3	2	4	3	6	2
А4	3	5	4	4	3

Если фирма А будет выбирать первую стратегию, минимальный доход составит 4. Минимальный доход от второй стратегии - 1; из третьего - 2; на четвертом - 3. Компания доступна в пяти стратегий. Использование первой стратегии превратит потери 1 единицы; второй (убыток) - 4; В-третьих - 3, четвертый - пятый и 4 - 2. На первый взгляд, компания А должна выбрать вторую стратегию (A2), чтобы получить выигрыш 10, но в ответ на второй фирмы, чтобы избрать первую стратегию (В1) и компания выигрыш будет только 1.Поэтому первая цель компании может быть сформулирована следующим образом: для получения максимального дохода возможного минимума. Введем таблицу 3 дополнительную строку и дополнительный столбец, в котором мы укажем возможную минимальную и максимальную прибыль (табл. 4)

Таблица 4

Стратегии	В1	В2	В3	В4	В5	Минимальная прибыль фирмы А
А1	5	8	7	5	4	4
А2	1	10	5	5	6	1
А3	2	4	3	6	2	2
А4	3	5	4	4	3	3
Максимальный убыток фирмы В	5	10	7	6	6

Истекая из данных (табл. 4) фирме А надо придерживаться стратегии А1, а фирме В - стратегии В1. Таким образом, гарантированный минимальный доход фирмы А составит 4, а минимально возможный убыток, который понесет фирма В, составит 5 (минимально возможный проигрыш).

Минимально гарантированный выигрыш игры именуется нижней игрой. При неудачной игре, выигрыш фирмы В может оставаться большим. Минимальная возможная потеря именуется верхней ценой игры. Для нашего примера, нижняя цена игры составляет 4 (минимальный гарантированный приз компании А), а верхняя цена игры - 5 (самая низкая возможная потеря компании B). Выше рассматриваемые рассуждения хороши, если соперничающая фирма не знает заранее, как себя поведет соперник. Если конкурирующая компания ознакомились с планами конкурентов, он может выбрать другую стратегию (кроме тщательной стратегии) и достичь большой прибыли (доход)

Таким образом, принимая во внимание осторожные стратегии являются неустойчивыми по отношению к дополнительной информации Хазанова, Л.Э. Математические методы в экономике./Л.Э. Хазанова. - М.: Изд-во БЕК, 2012. - 144с..

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

Таблица 5

Стратегии	В1	В2	В3	В4	В5	Минимальная прибыль фирмы А
А1	4	8	7	5	4	4
А2	1	10	5	5	6	1
А3	2	4	3	6	2	2
А4	3	5	4	4	3	3
Максимальный убыток фирмы В	4	10	7	6	6

Стратегия двух противников для задач с седловой точкой называются оптимальными и не зависят от полученной дополнительной информации. В литературе доказано, что если исследование игровой модели, как известно, все фона (все ранее сделанные ходы), то есть стратегии поведения лучшие (чистые) игроков (конкурентов).Если игровая задача не имеет седловой точки, то на практике конкурирующие фирмы (игроки) используют смешанные стратегии, т.е. попеременно используют две или более стратегий. В этом случае использование фирмой А нескольких стратегий можно записать как сумму вероятностей использования каждой стратегии Sa= p1+ p2+ …+ pm .

Соответственно, использование нескольких стратегий фирмой В можно записать Sb= q1+ q2+ …+ qn . Поэтому в общем случае исследование игровой модели сводится к определению вероятностей использования конкретных стратегий каждой фирмой (игроком).

Аналитический метод решения игры

Рассмотрим игру без седловой точки типа 2x2 с платежной матрицей

С= с11 с12

с21 … с22

и найдем оптимальную стратегию

SА= А1….А2

Р1 ….Р2

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

Отсюда вытекает, что неизвестные p1, p2, V удовлетворяют следующей системе из трех линейных уравнений:

с11р1+с21р2= V

с12р1+с22р2= V

р1+р2=1

решение которой имеет вид

Аналогичным образом можно найти оптимальную стратегию

SВ= В1….В2

q1….q2

игрока B. В этом случае неизвестные q1,q2,V удовлетворяют системе уравнений.

С11q1+с12q2=V

с21q1+с22q2=V

q1+q2=1

решение которой имеет вид

Графический метод.

Сущность графического метода состоит в том, что из матрицы удаляют дублирующие и поглощаемые строки и столбцы. Дублирующими называют полностью одинаковые строки или столбцы. Преобладающей строкой называется такая строка, которая содержит элементы, большие или равные соответствующим элементам другой строки, называемой поглощаемой. Преобладающим столбцом называется такой, который содержит элементы, меньше или равные соответствующим элементам другого столбца, который называется поглощаемым. Множество не преобладающих стратегий, полученных после уменьшения размерности платёжной матрицы, называется множеством Парето (по имени итальянского экономиста Вильфредо Парето, занимавшегося исследованиями в данной области). Воспользуемся таблицей 3.Строка (стратегия) А1 является доминирующей по отношению к строке (стратегии) А4 , так как содержит элементы, большие соответствующих элементов строки А4 . Соответственно строка А4 является поглощаемой и из дальнейшего рассмотрения удаляется (табл. 6).

Таблица 6. Первый шаг упрощения таблицы

Стратегии	В1	В2	В3	В4	В5
А1	5	8	7	5	4
А2	1	10	5	5	6
А3	2	4	3	6	2

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

Таблица 7. Второй шаг упрощения таблицы

Стратегии	В1	В5
А1	5	4
А2	1	6
А3	2	2

Еще раз рассматриваем строки. Первая строка поглощает третью строку. Поглощаемые строки (столбцы) содержат самые плохие стратегии. Окончательно получим (табл. 8).

Таблица 8. Третий шаг упрощения таблицы

Стратегии	В1	В5
А1	5	4
А2	1	6

Вероятность использования первой фирмой первой стратегии обозначим через p1. Тогда вероятность использования второй стратегии первым игроком будет p2 = 1- p1 . Ожидаемый выигрыш фирмы А от применения вторым игроком первой стратегии составит:

(1.1)

Аналогичным способом получим ожидаемый выигрыш фирмы А от применения вторым игроком:

(1.2)

В выражения (1.1) и (1.2) подставим конкретные значения.

На оси х отложим две точки 0 и 1. Через эти точки проведем прямые линии, параллельные оси у. Затем в первое выражение подставим 0 вместо p1, а потом - единицу. И по двум точкам построим прямую линию. Аналогично построим вторую прямую линию. Пересечение двух прямых линий и даст решение задачи (рис.9).

Рисунок 9. - Графический способ определения стратегий фирмы А:

4p1 + 1= - 2p1 + 6

4p1 + 2p1 = - 1 + 6

6p1 = 5

p1 = 0,83

Таким образом, вероятность использования первой компанией Стратегия является 0,83 (p1 = 0,83), в то время как вторая стратегия p2 = 1 - 0,83 - соответственно 0,17 (р2 = 0,17). Аналогичным образом, мы определяем оптимальную стратегию поведения в компании:

Пусть y1 - вероятность выбора игроком второй стратегии m1 y2 6 стратегии.

(p4 + p5 = 1, p5 = 1- p4)

(a11 - a12) · у1 + a12 = (5 - 4) у1 + 4 = у1 + 4;

(a21 - a22) · у1 + a22 = (1 - 6) у1 + 6 = -5 у1 + 6.



Рисунок 10. - Графический способ определения стратегий фирмы В:

у1 + 4 = -5 у1 + 6

6 у1 = 2

у1 = 0,33

Вероятность использования первой стратегии фирмой В составляет 0,33 (у1 = 0,33), а второй стратегии у2=1- 0,33 - соответственно 0,67 (у2 = 0,67) Конюховский, П.В. Теория игр: Учебник для бакалавров / П.В. Конюховский, А.С. Малова. - Люберцы: Юрайт, 2016. - 252 c..

Сведение задач теории игр к задачам линейного программирования

Для решения задач линейного программирования с использованием симплекс-метода. Предположим, что значение игры положительна (и> 0). Если это не так, то согласно свойству 6 всегда можно выбрать номер с, добавление которого ко всем элементам матрицы выигрышей дает матрицу с положительными элементами, и, следовательно, положительное значение цены игры. Оптимальная смешанная стратегия обоих игроков не изменяются. Свойство 1. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а - любое вещественное число, к > 0.

Свойство 2. Для того, чтобы хо = () была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

(j = ) (2.1)

Аналогично для игрока 2: чтобы yо = (, …,, …,) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

(i = ) (2.2)

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

, (2.3)

Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1, …, хm), y = (y1, …, yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.



(2.4)

(2.5)

Разделим все уравнения и неравенства в (2.4) и (2.5) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения:

,  ,

Тогда (1) и (2) перепишется в виде:

, , , ,

, , , .

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

, (2.6)

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

, (2.7)

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения pi, qj и u. Тогда смешанные стратегии, т.е. xi и yj получаются по формулам Барсов, А.С. Линейное программирование в технико-экономических задачах./А.С. Барсов. - М.: Наука, 1964. - 278с.:

(2.8)

Игры с природой

В играх с природой, есть несколько условий для оценки результатов исследования игровой модели.

1. Условие Вальде (пессимистический).

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

max (min a ij ) (3.1)

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

То есть, этот критерий совпадает с нижней ценой игры.

2. Условие максимума (оптимистический).

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

max (max a ij ) (3.2)

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

3. Условие Гурвица.

Условие Гурвица занимает промежуточное значение между тестом Вальда и критерию максимума. Игрок определяет вероятность его "удачи"

max (?minaij + (1- ?) maxaij ) (3.3)

Ответственное лицо, принимающее решение, определяет значение коэффициента а. Если потери могут быть очень значительными, то значение коэффициента ?, близка к единице, в противном случае 0.

4. Условие Сэвиджа

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

rij = maxaij-aij (3.4)

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

min (max (maxaij-aij) (3.5)

где выбирается максимальное значение в каждом столбце Малыхин, В.И. Теория принятия решений./В.И. Малыхин, А.В. Статкус. - М.: МИУ, 2012. - 382с.

В качестве примера возьмем таблицу стратегий (табл. 3) и составим для нее таблицу рисков (табл. 9).

Таблица 3. Таблица стратегий

Стратегии	В1	В2	В3	В4	В5
А1	5	8	7	5	4
А2	1	10	5	5	6
А3	2	4	3	6	2
А4	3	5	4	12	3
max a ij	5	10	7	12	6

Если компания (участник) выберет стратегию А1,а природа реализует стратегию В1 то фирма получит максимально возможную прибыль 5 (упущенная выгода будет 0). Компания угадала состояние природы. Но если природа реализует стратегию В4, компания вместо максимально возможной прибыли 12 получит 5 , недополученная прибыль составит 7.

Таблица 9. Таблица рисков

Стратегии	В1	В2	В3	В4	В5
А1	0	2	0	7	2
А2	4	0	2	7	0
А3	3	6	4	6	4
А4	2	5	3	0	3

Пример: Швейная фабрика на летний сезон может реализовать два вида костюмов: 1200 костюмов по цене 520 руб. и 200 костюмов по цене 1000 руб., если погода будет жаркой. Если погода будет холодной, то фабрика может реализовать 650 костюмов первого вида и 700 костюмов второго вида.

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

Решение:

Швейная фабрика располагает двумя стратегиями: А1- погода будет жаркой и А2 - погода будет холодной.

Если фабрика воспользуется первой стратегией и погода действительно будет жаркой, то прибыль фабрики составит:

1200 · 520 + 200 · 1000 = 624 000 + 200 000 = 824 000 руб.

Если фабрика воспользуется первой стратегией, но погода будет холодной, то прибыль фабрики составит:

650 · 520 + 200 · 1000 - (1200 - 650) · 520 = 338 000 + 200 000 - 286 000 = 252 000 руб.

Если фабрика воспользуется второй стратегией и погода действительно будет холодной, то прибыль фабрики составит:

650 · 520 + 700 · 1000 = 338 000 + 700 000 = 1 038 000 руб.

Если фабрика воспользуется второй стратегией, но погода будет жаркой, то прибыль фабрики составит:

650 · 520 + 200 · 1000 - (700 - 200) · 1000 = 338 000 + 200 000 - 500 000 = 38 000 руб.

Составим матрицу прибыли (таб. 10).

Таблица 10. Матрица прибыли

Стратегии	В1	В2
А1	824 000	252 000
А2	38 000	1 038 000

? = max (252 000; 38 000) = 252 000 руб.

? = min (824 000; 1 038 000) = 824 000 руб.

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

Определим план выпуска изделий швейной фабрикой. Вероятность выбора стратегии А1 обозначим через х1, а вероятность выбора стратегий А2 - через х2. Учитывая, что х2 = 1 - х1,можем записать:

(a11 - a12)· х1 + a12 = (824 000 - 38 000)· х1 + 38 000 = 786 000 х1 + 38 000;

(a21 - a22)· х1 + a22 = (252000 - 1038000)· х1 + 1038000 = -786000 х1 + 1038000;

786 000 х1 + 786 000 х1 = 1 038 000 - 38 000

1 572 000 х1 = 1 000 000

х1 = 0,64; х2 = 1 - 0,64х2 = 0,36;

0,64 (1200; 200) + 0,36 (650; 700) = (1002; 380).

Цена игры составит: 786 000 х1 + 38 000 = 541 040 руб.

Таким образом, план выпуска изделий таков: 1002 костюма первого вида и 380 костюмов второго вида, и при любых погодных условиях швейная фабрика получит прибыль не менее 541 000 руб.

Определим критерии.

1. Критерий Вальде:

max (min aij) = max (38 000; 252 000) = 252 000 руб.

Швейной фабрике целесообразно использовать стратегию А1.

2. Критерий максимума:

max (maxaij ) = max (824 000; 1 038 000) = 1 038 000 руб.

Швейной фабрике целесообразно использовать стратегию А2 .

3. Критерий Гурвица:

пусть ? = 0,4 , тогда для стратегии А1

? min a ij + (1 -?) max a ij = 0,4 · 252 000 + (1 - 0,4) · 824 000 = 595 200 руб.

Для стратегии А2

? min a ij + (1 - ?) max a ij = 0,4 · 38 000 + (1 - 0,4) · 1 038 000 = 638 000 руб.

Швейной фабрике целесообразно использовать стратегию А2 .

4. Критерий Сэвиджа:

Максимальный элемент в первом столбце - 824 000, во втором столбце - 1 038 000.

Матрица рисков будет иметь вид:

Швейной фабрике целесообразно использовать стратегию А1 или А2.

Фактическое решение некоторых классов антагонистических игр сводится к решению дифференциальных и интегральных уравнений и матричных игр - к решению стандартной задачи линейного программирования. Разработаны приближенные и численные методы решения игр. Для многих игр оптимизированы так называемые смешанные стратегии, то есть стратегия, выбранная случайно (например, путем жеребьевки) Зайченко, Ю.П. Исследование операций./Ю.П. Зайченко. - Киев, 2009. - 278с..

2.2 Примеры решения задач

Задача №1. Найти оптимальный вариант работы электростанции по критериям Лапласа, Вальда, Гурвица с показателями 0,8 и 0,3 и Сэвиджа по заданной таблице эффективностей:

Таблица эффективностей

Среда Варианты	В1	В2	В3	В4
А1	10	8	4	11
А2	9	9	5	10
А3	8	10	3	14
А4	7	7	8	12

Критерий Лапласа. В основе критерия, основанного на предположении, что из-за условий ситуации неизвестно, их можно считать равновероятными. Соответственно, с использованием формулы:

K(Ai) = , i=1,…,m, Kоnm= max{K(Ai), i=1,…,m}

Получаем:

K(A1) = 0,25(10+8+4+11) = 8,25

K(A2) = 0,25(9+9+5+10) = 8,25

K(A3) = 0,25(8+10+3+14) = 8,75

K(A4) = 0,25(7+7+8+12) = 8,5

Лучшая стратегия по этому критерию A3.

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

Каждая строка матрицы является эффективность минимальных оценок для окружающей среды различных состояний K (Ai) = minkij, я = 1, ..., т.

Оптимальная система линий с максимальной эффективностью:

Kоnm = max{K(Ai), i=1,…,m}

Вычисляем :K(A1) = 4, K(A2) = 5, K(A3) = 3, K(A4) = 7

Лучшая стратегия по этому критерию A4.

Критерий Гурвиц...