Предмет и задачи теории игр

Методические указания к проведению лекционного занятия

Тема № 9.7. Понятие об игровых моделях

План:

1. Предмет и задачи теории игр

2. Решение матричных игр в чистых стратегиях

3. Решение матричных игр в смешанных стратегиях

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

5. Кооперативные игры

6. Игры «с природой»

Предмет и задачи теории игр

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

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

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

Формализо­ванная (схематизированная) модель конфликтной си­туации называется игрой.

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

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

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

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

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

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

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

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

Классификация игр:

- по количеству игроков;

- по количеству стратегий (конечные или бесконеч­ные);

- в зависимости от взаимоотношений участников (бескоалиционные или некооперативные – участники не имеют права заключать соглашения, и коали­ционные или кооперативные);

- по характеру выигрышей (игры с нулевой суммой – если один из игроков выигрывает ровно столько, сколько проиг­рывает другой и с ненулевой суммой);

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

- по количеству ходов игры (одноходовые – выигрыш распределяется после одного хода каждого игрока и многоходовые – выигрыш распределяется после несколь­ких ходов);

- в зависимости от объема имеющейся информации (игры с полной и неполной информацией).

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

Решение матричных игр в чистых стратегиях

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

Для нахождения оптимальной стратегии необходимо проанализировать все возможные стратегии и рассчи­тывать на то, что разумный противник на каждую из них будет отвечать такой, при которой выигрыш игрока А минимален. Обычно минимальные числа в каждой стро­ке обозначаются α_i и выписываются в виде добавочного столбца матрицы (табл.1).

Таблица 1.

	В1	В2	…	Вn	αi
А1	q11	q12	…	q1n	α1
А2	q21	q22	…	q2n	α2
…	…	…	…	…	…
Аm	qm1	qm2	…	qmn	αi
βj	β1	β2	…	βj

В каждой строке будет свое . Предпочтительной для игрока А является стратегия, при которой α_i обращается в максимум, то есть:

или ,

где α – максиминный выигрыш (максимин), а соот­ветствующая ей стратегия – максиминная.

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

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

(последняя строка матрицы). Из всех значений β_j находят минимальное:

,

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

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

Если α = β = С, то число С называют чистой ценой игры или седловой точкой.

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

Пример. Конструктор получил задание разработать определен­ное новое изделие. В результате исследований он определил три возможных варианта изделия У₁, У₂, У₃, каждый из которых может быть реализован каким-либо из трех техпроцессов Т₁, Т₂, Т₃.

Если первый вариант конструкции У₁ реализуется по первой технологии Т₁, то внешний вид изделия оказыва­ется наилучшим и оценивается экспертами в 9 баллов, а при реализации по второй технологии – в 6 баллов, по третьей – в 5 баллов и т. д. (табл.2).

Таблица 2.

Матрица игры для конструктивного и технологического вариантов

Конструкция	Технология
Т1	Т2	Т3
У1 У2 У3				5(Т3) 7 (Т2 или Т3) 5(Т2)

Решение.

Конфликтная ситуация возникает из-за того, что затраты на реализацию каждого конструкторско-технологического решения (варианта) не одинаковы. Для простоты полагаем, что затраты пропорциональны внеш­нему виду (чем выше балл, тем больше затраты).

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

Если конструктор выберет У₁, то экономисты будут настаивать на технологии Т₃. На вариант У₂ будет ответ Т₂ или Т₃ и т. д.

Очевидно, что с точки зрения конструктора пре­имущество имеет вариант У₂, но даже при неблагоприятных обстоятельствах получится изделие, оцениваемое в 7 баллов (выигрыш 7), а может быть даже 8, если удается уговорить экономистов на ва­риант Т₁.

С точки зрения экономистов в смысле снижения затрат: при выборе технологии Т₁ в варианте У₁ затраты наи­большие — 9 баллов, при Т₂ в У₂ (7), при Т₃ в У₃ (8).

То есть для экономистов оптимальным является техпроцесс Т₂, так как он требует меньших затрат при различных вариантах конструкции. Следовательно, стра­тегия Т₂У₂ с выигрышем 7 – наиболее выгодная сразу для обеих сторон – максимальный выигрыш У совпадает с минимальным проигрышем Т.

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