VI Международная студенческая научная конференция Студенческий научный форум - 2014

Введение

Теория игр – раздел математики, предметом которого является анализ принятия оптимальных решений в условиях конфликта. Возникнув из задач классической теории вероятностей, теория игр превратилась в самостоятельный раздел в 1945-1955. Таким образом, теория игр - один из новейших разделов математики. Наиболее полное изложение идей и методов теории игр впервые появилось в 1944 в труде Теория игр и экономическое поведение(Theory of Games and Economic Behavior) математика Дж. фон Неймана (1903-1957) и экономиста О. Моргенштерна (1902-1977). Фон Нейман опубликовал несколько работ по теории игр в 1928 и 1935; другим предшественником теории игр по праву считается французский математик Э. Борель (1871-1956). Некоторые фундаментальные идеи были независимо предложены А. Вальдом (1902-1950), заложившим основы нового подхода к статистической теории принятия решений.

В данной работе рассматриваются общие понятия в теории игр с более детальным описанием и примером задачи метода Шепли-Сноу.

1. Теоретическая часть 1.1. Общие понятия теории игр

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

U₁={₁, ₂,..., _m} – множество стратегий первого игрока;

U₂={₁, ₂, ... n} – множество стратегий второго игрока.

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

Множество U₁ЧU₂ – декартово произведение множеств стратегий игроков называется множеством ситуаций в игре. Для каждой ситуации должен быть определён итог игры. Так как игра антагонистическая достаточно определить выигрыш а одного из игроков, скажем первого. Тогда выигрыш второго игрока будет равен (-а). Таким образом, имеем матрицу выигрышей первого игрока (для второго игрока матрица выигрышей будет -А):

Определение. Система Г={U₁, U₂, A} называется матричной игрой двух лиц.

Разыгрывание матричной игры сводится к выбору игроком 1 i-ой строчки матрицы выигрышей, а игроком 2 - j-го столбца. После этого игрок 1 получает выигрыш равный а_ij, а игрок 2 – (-а_ij).

При правильной игре игрок 1 может всегда гарантировать себе выигрыш, который назовём нижним значением цены игры. Обозначим его: .

В свою очередь, игрок 2 может гарантировать себе проигрыш, который назовём верхним значением цены игры. Обозначим его .

Чистые стратегии i^* и j^*, соответствующие называются максиминной и минимаксной стратегиями.

Определение. Ситуация (i^*, j^*) называется ситуацией равновесия, если для i1,2,…,m, j1,2,…,n выполняется неравенство:

.

Ситуация равновесия это такая ситуация, от которой ни одному из игроков не выгодно отклоняться. В этом случае стратегии i^*, j^* называют оптимальными стратегиями игроков.

Чтобы такая ситуация существовала необходимо и достаточно равенство верхней и нижней цен игры, т. е. .[17]

Определение. Пусть(i^*, j^*) - ситуацией равновесия в матричной игре. Тогда число называется значением или ценой игры.

Например, в игре Г_А с матрицей А= существует не одна ситуация равновесия. В данной игре их две: (1, 1) и (1, 3).

Множество всех ситуаций равновесия в матричной игре обозначим через Z(Г).

Лемма о масштабе 1. Пусть Г и Г^/ - две матричные игры с матрицей выигрышей А={a_ij} и A^/={a^/_ij}, причём А^/=А+ , =const, =const.

Тогда Z(Г)=Z(Г^/) и ^/= + (где ^/ - значение цены игры Г^/,  - значение цены игры Г). [17]

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

1.2. Метод Шепли-Сноу

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

Теорема 1. (Шепли-Сноу). Все крайние оптимальные стратегии р° и q° обоих игроков в игре с платежной матрицей и цена игры v должны удов­летворять какой-либо из систем уравнений:

(1)

(2)

где - квадратная матрица, полученная из матрицы вычеркиванием не­которого количества строк и столбцов. Все остальные р° и q° с индексами, со­ответствующими вычеркнутым строкам и столбцам, равны нулю. При этом, если v≠0, то матрица невырождена.

Доказательство. Пусть р° и q° - произвольные крайние оптимальные стра­тегии, ν- цена игры. По теореме о свойствах оптимальных стратегий

(3)

Перенумеруем строки и столбцы матрицы так, чтобы индексы iиj, на которых достигаются минимум и максимум, в (3) были на первых местах, т.е.

Тогда по теореме о свойствах оптимальных стратегий

Таким образом, для определения р° и q° имеем систему уравнений

(4)

(5)

Кроме того, существует ε>0 такое, что

(6)

Докажем сначала, что r = k. Предположим противное, т.е. r ≠ k; пусть для оп­ределенности k > r (при k < r все аналогично).

Рассмотрим систему однородных уравнений относительно неизвестных

(7)

Матрица системы (7) имеет вид

(8)

Из (5) вытекает векторное равенство

(9)

Так как хотя бы одно , то строки матрицы (8) линейно зависимы. Сле­довательно, число независимых уравнений в системе (7) не больше r, а число неизвестных k>r, т.е. система (7) имеет нетривиальное решение . Так как множество решений однородной системы является под­пространством, то также есть решение системы (7) и можно сделать сколь угодно малым.

Возьмем такое , что .

Тогда и в силу (6) справедливо неравенство

В то же время из (4) и (7) вытекают равенства

Значит, по теореме о необходимых и достаточных условиях оптимальности стратегии векторы

являются оптимальными для игрока 1. Но p° = (1/2)(p¹ + p² ), т.е. пришли к противоречию, так как р° - крайняя оптимальная стратегия.

Аналогично, если предположить, что k< r, то придем к противоречию для q°. Итак, k =r.

Покажем теперь, что если ν ≠ 0, то

Доказательство снова от противного. Предположим, что

Так как v ≠0, то из (9) следует, что последняя строка матрицы (8) является линейной комбинацией остальных строк. Если справедливо (10), то чис­ло независимых строк матрицы (8),где k = r, не больше r-1. Тогда в системе (7) при k = r число неизвестных r больше числа независимых уравнений и, сле­довательно, существует нетривиальное решение. Далее приходим к про­тиворечию совершенно так же, как при предположении k > r. Если учесть, что системы (4), (5) получены после соответствующей перестановки строк и столбцов матрицы , то все утверждения теоремы доказаны.

По теореме Шепли-Сноу полное решение матричной игры сводится к пере­бору всех квадратных подматриц матрицы игры и решению соответствующих систем линейных уравнений (1),(2). Если v≠0, то эти системы, очевидно, либо имеют единственное решение, либо не имеют решения. Полученное решение на­до проверить на неотрицательность и на выполнение условий оптимальности для вычеркнутых строк и столбцов. Если условия выполнены, то ре­шения системы, дополненные нулями на местах, соответствующих вычеркнутым строкам и столбцам, являются оптимальными стратегиями (но необязательно крайними, так как условия теоремы необходимые, но не достаточные). Полный перебор приведет к нахождению всех крайних оптимальных стратегий. Так как трудоемкость решения по методу Шепли-Сноу растет с увеличением размерности матрицы игры, то имеет смысл предварительно вычеркнуть в соответствии с принципом доминирования лишние строки и столбцы (если ищется полное реше­ние, то при строгом доминировании), которые входят в оптимальные стратегии с нулевой вероятностью; цена игры при этом, очевидно, не меняется. Так как при решении системы линейных уравнений (1), (2) удобнее оперировать с невы­рожденной подматрицей , то исходную игру следует свести к игре с заведо­мо не равной нулю ценой. Проще всего это сделать следующим образом: приба­вить к каждому элементу матрицы одну ту же достаточно большую кон­станту так, чтобы исходная матрица была положительной; тогда в новой игре цена, очевидно, больше ну­ля, причем она отличается от цены исходной игры на величину этой константы, а множества оптимальных стратегий игроков в обеих играх совпадают.

2. практическая часть

Решить игру с платежной матрицей .

1) Составим системы:

Решив системы, получим:

, , , , , то есть , , – решение игры.

2) Найдем решение по формулам:

; ;

; ; .

3) Найдем решение в матричном виде:

, , , , ;

, , .

Результаты совпадают.

Заключение

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

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

Часто теория игр находит практические применения совершенно не в той области, в которой ученые черпали примеры для своих исследований. Так, Ллойд Шепли занимался задачей составления “гармоничных пар” на примере мужчин и женщин (так называемая “проблема стабильного брака”). Но в жизни этим занимаются не математики, а господь бог, причем не очень успешно, если посмотреть на количество разводов. А вот в трансплантологии результаты Шепли играют очень важную роль: врачи пользуются ими для того, чтобы правильно подобрать орган для пересадки – иными словами, чтобы человек и его новая почка составили бы “гармоничную пару”.

Список использованной литературы

1. Лабскер Л.Г. Вероятностное моделирование в финансово-экономической области. - М.: Альпина Паблишер, 2002.

2. Лабскер Л.Г., Бабешко Л.О. Игровые методы в управлении экономикой и бизнесом. - М.: ДЕЛО, 2001

3. Моделирование рисковых ситуаций в экономике и бизнесе: Учеб. пособие /А.М. Дубров, Б.А. Лагоша, Е.Ю. Хрусталев, Т.П. Барановская; Под ред. Б.А. Лагоши. – 2-е изд., пере раб. и доп. – М.: Финансы и статистика, 2001.

4. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение: Пер. с англ. – М.: Наука, 1970.

5. Петросян Л.А., Зенкевич Н.А., Семен Е.А. Теория игр. М., 1989

6. Стронгин Р.Г. Исследование операций; Модели экономического поведения: учеб. для студ., обуч. по напр. 010500 "Прикл. мат. и информатика" и по спец. 010501 "Прикл. мат. и информатика"/ Р. Г. Стронгин. - Москва: БИНОМ. Лаборатория знаний, 2007

7. http://ru.wikipedia.org

8. Мак Киси Дж. Введение в теорию игр: Пер. с англ. – М.: Физматгиз, 1960.

9. Л.Г. Лабскер, Н.А. Ященко. Теория игр в экономике. Практикум с решениями задач. Кнорус, Москва 2012

Код для цитирования: Скопировать