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

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

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

Павел, диванный эксперт

Такая стратегия - это, скорее, не ложь, а умалчивание.

Пример

Представьте ситуацию: мужчина и женщина встречаются несколько месяцев и однажды . У мужчины квартира небольшая, поэтому логично, что речь идёт о переезде в квартиру женщины.

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

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

Что делать

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

2. Игра на 90 баллов

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

Пример

Два студента попросили профессора отсрочить экзамен. Они рассказали душещипательную историю о том, как поехали на выходные в другой город, но на обратной дороге у них спустило шину. Помощь пришлось искать всю ночь, поэтому они не выспались и плохо себя чувствуют. (На самом деле друзья отмечали окончание сессии, а этот экзамен был заключительным и не самым тяжёлым.)

Профессор согласился. На следующий день он рассадил студентов в разные аудитории и раздал по листку, где было лишь два вопроса. Первый стоил всего 10 баллов, а второй - 90 и звучал так: «Какое колесо спустило?»

Если опираться на логику, то ответ будет «Правое переднее колесо»: именно справа, ближе к обочине чаще всего валяется всякий мусор, на который в первую очередь наезжает передняя шина. Но не спешите.

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

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

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

Что делать

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

3. Игра с собой

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

Пример

Некая Ольга решает, пробовать ей курить или нет.

Дерево игры

На рисунке представлено так называемое дерево игры: его полезно рисовать каждый раз, когда вам нужно принять какое-либо решение. Ветви этого дерева - варианты развития событий. Цифры (0, 1 и -1) - выигрыш, то есть будет ли игрок победителем, если изберёт тот или иной вариант.

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

Предположим, что Ольга решила попробовать курить. Что дальше? Бросит она или нет? Это уже будет решать Будущая Ольга, на рисунке она вступает в игру по ветке «Попробовать». Если у неё уже сформировалась зависимость, то бросать курить она не захочет, поэтому варианту «Продолжать» ставим выигрыш 1 (вторая цифра правой нижней ветки).

Что мы получаем? Нынешняя Ольга будет в выигрыше в том случае, если попробует курить, но не попадёт в зависимость. А это, в свою очередь, зависит от Будущей Ольги, для которой выгоднее курить (она уже курит довольно давно, значит, у неё есть зависимость, стало быть, бросать она не захочет). Так стоит ли так рисковать? Может, сыграть вничью: получить выигрыш 0 и вообще не пробовать курить?

Что делать

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

4. Игра в аукцион

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

Пример

В эпизоде с аукционом из «Двенадцати стульев» Остап Бендер допустил стратегическую ошибку. Вслед за предложением в 145 рублей за лот он поднял цену сразу до двухсот.

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

Что делать

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

5. Игра на обезличенном рынке

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

Пример

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

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

Что делать

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

Теория игр - новая наука, но её уже изучают в лучших университетах мира. В издательстве «МИФ» вышел учебник «Стратегические игры». Он пригодится, если вы хотите научиться анализировать каждое своё действие, принимать взвешенные решения, лучше понимать не только других, но и себя.

Из популярного американского блога Cracked.

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

1. Дилемма заключенного

Берто и Роберт были арестованы за ограбление банка, не сумев правильно использовать для побега угнанный автомобиль. Полиция не может доказать, что именно они ограбили банк, но поймала их с поличным в украденном автомобиле. Их развели по разным комнатам и каждому предложили сделку: сдать сообщника и отправить его за решетку на 10 лет, а самому выйти на свободу. Но если они оба сдадут друг друга, то каждый получит по 7 лет. Если же никто ничего не скажет, то оба сядут на 2 года только за угон автомобиля.

Получается, что, если Берто молчит, но Роберт сдает его, Берто садится в тюрьму на 10 лет, а Роберт выходит на свободу.

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

Практическое применение: Выявление социопатов

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

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

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

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

2. Доминирующая стратегия

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

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

3. Битва полов

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

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

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

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

Практическое применение: Избегайте острых углов

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

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

4. Равновесие Нэша

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

Давайте быстро поделим 100$. Вы и я решаем, сколько из сотни мы требуем и одновременно озвучиваем суммы. Если наша общая сумма меньше ста, каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги? Существует единственный выигрышный ход.

Требование 51 $ даст вам максимальную сумму независимо от того, что выберет ваш противник. Если он попросит больше, вы получите 51 $. Если он попросит 50 $ или 51 $, вы получите 50 $. И если он попросит меньше 50 $, вы получите 51 $. В любом случае нет никакого другого варианта, который принесет вам больше денег, чем этот. Равновесие Нэша - ситуация, в которой мы оба выбираем 51 $.

Практическое применение: сначала думайте

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

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

5. Игра в орлянку

В орлянке участвуют Игрок 1 и Игрок 2. Каждый игрок одновременно выбирает орла или решку. Если они угадывают, Игрок 1 получает пенс Игрока 2. Если же нет - Игрок 2 получает монету Игрока 1.

Выигрышная матрица проста…

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

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

Практическое применение: Пенальти

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

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

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

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

Муниципальное образовательное учреждение
средняя общеобразовательная школа №___

городского округа - город Волжский Волгоградской области

Городская конференция творческих и исследовательских работ обучающихся

«С математикой по жизни»

Научное направление – математика

«Теория игр и её практическое применение»

обучающаяся 9б класса

МОУ СОШ №2

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

учитель математики Григорьева Н.Д.

Введение

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

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

Цель проекта предопределила его задачи:

Ознакомиться с историей зарождения теории игр;

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

Дать характеристику основным типам игр;

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

Объектом проекта выступила теория игр.

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

Теоретической основой написания работы явилась экономическая литература таких авторов, как Дж. фон Нейман, Оуэн Г., Васин А.А., Морозов В.В., Замков О.О., Толстопятенко А.В., Черемных Ю.Н.

1. Введение в теорию игр

1.1 История

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

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

Принято считать монографию Дж. Неймана и О. Моргенштерна “Теория игр и экономическое поведение”, моментом рождения теории игр. После её публикации в 1944 г., многие ученые предсказали революцию в экономических науках благодаря использованию нового подхода. Эта теория описывала рациональное поведение принятия решений во взаимосвязанных ситуациях, помогая решать многие актуальные проблемы в разных научных областях. Монография подчеркивала, что стратегическое поведение, конкуренция, кооперация, риск и неопределенность, являются главными элементами в теории игр и непосредственно связаны с задачами управления.

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

В последнее время эти методы проникли и в практику управления. Следует отметить, что уже в конце 20 века М. Портер ввел в обиход некоторые понятия теории, такие, как “стратегический ход” и “игрок”, которые впоследствии стали одними из ключевых.

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

В 1958-1959 гг. к 1965-1966 гг. была создана советская школа в теории игр, для которой была характерно скопление усилий в области антагонистических игр и строго военных приложений. Изначально это стало причиной отставания от американской школы, так как в то время основные открытия в антагонистических играх уже были сделаны. В СССР математиков до середины 1970-х гг. не допускали в область управления и экономики. И даже тогда, когда советская экономическая система начала рушиться, экономика не стала главным направлением для теоретико-игровых исследований. Профильный институт, занимавшийся и сейчас занимающийся теорией игр - Институт системного анализа РАН.

1.2 Определение теории игр

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

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

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

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

1.3 Виды конфликтных ситуаций

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

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

Игра – математическая модель описания конфликта.

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

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

Итак, каждая математическая модель социально-экономического явления, должна иметь при­сущие ему черты конфликта, т.е. описывать:

а) множество заинтересованных сторон. В случае, если число игроков ограниченно (конечно), они различаются по своим номерам или по присваиваемым им именам;

б) возможные действия каждой из сторон, именуемые также стратегиями или ходами;

в) интересы сторон, представленные функциями выигрыша (платежа) для каждого из игроков.

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

2 Виды игр

2.1 Дилемма заключенного

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

Рассмотрим такую ситуацию. Двое подозреваемых находятся под следствием. У следствия недостаточно улик, поэтому разделив подозреваемых, каждому из них предложили сделку. Если один из них будет по-прежнему молчать, а другой свидетельствовать против него, то первый получит 10 лет, а второго отпустят за содействие следствию. Если они оба будут молчать, то получат по 6 месяцев. Наконец, если они оба заложат друг друга, то они получат по 2 года. Вопрос: какой выбор они сделают?

Таблица 1 – Матрица выигрышей в игре «Дилемма заключенного»

Предположим, что эти двое - рациональные люди, которые хотят минимизировать свои потери. Тогда первый может рассуждать так: если второй меня заложит, то мне лучше тоже его заложить: так мы получим по 2 года, а иначе я получу 10 лет. Но если второй меня не будет закладывать, то мне всё равно лучше его заложить - тогда меня отпустят сразу. Поэтому не зависимо от того, что будет делать другой, мне выгоднее его заложить. Второй также понимает, что в любом случае ему лучше заложить первого. В результате оба из них получают по два года. Хотя если бы они не свидетельствовали друг против друга, то получили бы только по 6 месяцев.

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

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

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

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

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

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

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

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

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

2.3 Типы игр

Симметричные и несимметричные

А	Б
А	1, 2	0, 0
Б	0, 0	1, 2
Несимметричная игра

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

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

С нулевой суммой и с ненулевой суммой

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

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

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

Кооперативные и некооперативные

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

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

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

Гибридные игры включают в себя элементы кооперативных и некооперативных игр.

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

Параллельные и последовательные

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

С полной или неполной информацией

Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация недоступна в параллельных играх, так как в них неизвестны текущие ходы противников. Большинство изучаемых в математике игр - с неполной информацией. Например, вся суть «Дилеммы заключённого» заключается в ее неполноте.

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

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

Игры с бесконечным числом шагов

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

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

Дискретные и непрерывные игры

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

3. Применение теории игр

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

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

Двумя основными областями применения являются военное дело и экономика. Теоретико-игровые разработки применяются при проектировании автоматических систем управления для ракетного/противоракетного оружия, выборе форм аукционов по продаже радиочастот, прикладном моделировании закономерностей денежного обращения в интересах центральных банков, и т.п. Международные отношения и стратегическая безопасность обязаны теории игр (и теории принятия решений) в первую очередь концепцией гарантированного взаимного уничтожения. Это заслуга плеяды блестящих умов (в том числе связанных с RAND Corporation в Санта Монике, Калиф.), дух которой до высших руководящих постов дошел в лице Роберта Макнамары. Следует, правда, признать, что сам Макнамара теорией игр не злоупотреблял.

3.1 В военном деле

Информация – один из наиболее значимых в настоящее время ресурсов. И сейчас все

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

Теория игр – математическая дисциплина, касающаяся конфликтных задач. Военное

дело, как ярко выраженное существо конфликта, стало одним из первых полигонов применения на практике разработок теории игр.

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

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

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

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

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

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

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

ЦРУ, Министерство обороны США и крупнейшие корпорации из списка Fortune 500 активно сотрудничают с футурологами. Разумеется, речь идёт о строго научной футурологии, то есть о математических вычислениях объективной вероятности будущих событий. Этим занимается теория игр - одна из новых областей математической науки, применимой практически ко всем областям человеческой жизни. Возможно, вычисления будущего, которые раньше велись в условиях строгой секретности для «элитных» клиентов, скоро выйдут на общедоступный коммерческий рынок. По крайней мере, об этом говорит то, что в одно время сразу два крупных американских журнала опубликовали материалы на данную тему, и оба напечатали интервью с профессором Нью-йоркского университета Брюсом Буэно де Мескита (BruceBuenodeMesquita). Профессору принадлежит консалтинговая фирма, которая занимается компьютерными вычислениями на основе теории игр. За двадцать лет сотрудничества с ЦРУ учёный точно вычислил несколько важных и неожиданных событий (например, приход Андропова к власти в СССР и захват Гонконга китайцами). В общей сложности он рассчитал более тысячи событий с точностью более 90%.Сейчас Брюс консультирует американские спецслужбы относительно политики в Иране. Например, его расчёты показывают, что США не имеет никаких шансов предотвратить запуск Ираном ядерного реактора для гражданских нужд .

3.2 В управлении

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

Какую пользу могут извлечь компании из анализа на базе теории игр? Известен, например, случай столкновения интересов компаний IВМ и Telex. Компания Telex объявила о вступлении на рынок продаж, в связи с этим состоялось “кризисное” совещание руководства IВМ, на котором были проанализированы действия, направленные на то, чтобы заставить нового конкурента отказаться от намерения проникнуть на новый рынок. Об этих действиях, видимо, стало известно компании Telex. Но проведенный анализ на базе теории игр показал, что угрозы IВМ из-за высоких затрат безосновательны. Это доказывает, что компаниям полезно обдумывать возможные реакции партнеров по игре. Изолированные хозяйственные расчеты, даже опирающиеся на теорию принятия решений, часто носят, как в изложенной ситуации, ограниченный характер. Так, компания-аутсайдер могла бы и выбрать ход “невступление”, если бы предварительный анализ убедил ее в том, что проникновение на рынок вызовет агрессивную реакцию компании-монополиста. В этой ситуации разумно выбрать ход “невступление” при вероятности агрессивного ответа 0,5, в соответствии с критерием ожидаемой стоимости.

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

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

3.3 Применение в прочих областях

В биологии

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

В компьютерных технологиях

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

В играх (шахматы)

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

Примеры из другой области

Теория игр используется при поиске подходящей пары донора и реципиента почки. Один человек хочет отдать почку другому, но оказывается, что их группы крови несовместимы. И что следует сделать в этом случае? Прежде всего – расширить список доноров и реципиентов, а потом применить методы подбора, которые дает теория игр. Это очень похоже на брак по расчету. Вернее, на брак это совсем не похоже, но математическая модель этих ситуаций одинакова, применяются те же методы и расчеты. Сейчас на идеях таких теоретиков, как Дэвид Гейл, Ллойд Шапли и другие, выросла настоящая индустрия – практические применения теории в кооперативных играх.

3.4 Почему теорию игр не применяют еще шире

И в политике, и в экономике, и в военном деле специалисты-практики натолкнулись на принципиальные ограничения фундамента современной теории игр – Нэшевской рациональности.

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

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

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

Примеры задач

Определения, необходимые для решения задач

1. Ситуация называется конфликтной, если в ней участвуют стороны, интересы которых полностью или частично противоположны.

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

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

4. Количественная оценка результатов игры называется платежом.

5. Игра называется парной, если в ней участвуют только две стороны (два лица).

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

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

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

Пусть имеются два игрока, один из которых может выбрать i-ю стратегию из m возможных стратегий (i=1,m), а второй, не зная выбора первого, выбирает j-ю стратегию из n возможных стратегий (j=1,n) В результате первый игрок выигрывает величину aij, а второй проигрывает эту величину.

Из чисел aij составим матрицу

Строки матрицы A соответствуют стратегиям первого игрока, а столбцы - стратегиям второго. Эти стратегии называются чистыми.

9. Матрица A называется платежной (или матрицей игры).

10. Игру, определяемую матрицей A, имеющей m строк и n столбцов, называют конечной игрой размерности m x n.

11. Число называется нижней ценой игры или максимином, а соответствующая ему стратегия (строка) - максиминной.

12. Число называется верхней ценой игры или минимаксом, а соответствующая ему стратегия (столбец) - минимаксной.

13. Если α=β=v, то число v называется ценой игры.

14. Игра, для которой α=β, называется игрой с седловой точкой.

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

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

1.Орлянка. Это игра с нулевой суммой. Принцип состоит в том, что, когда игроки выбирают одинаковые стратегии, то первый выигрывает один рубль, а когда разные – проигрывает один рубль.

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

2. Числа. Суть игры состоит, в том, что каждый из игроков загадывает целые числа от 1 до 4, причем выигрыш первого игрока равен разности загаданного им числа и числа, загаданного другим игроком.

имена	Игрок В
Игрок А	стратегии	1	2	3	4
	1	0	-1	-2	-3
	2	1	0	-1	-2
	3	2	1	0	-1
	4	3	2	1	0

Решаем задачу по теории maxmin и minmax, аналогично предыдущей задаче получается, что maxmin = 0, minmax = 0, появилась седловая точка, т.к. верхняя и нижняя цены равны. Стратегии обоих игроков равны 4.

3. Рассмотрим задачу эвакуации людей в пожарном случае.

Пожарная ситуация 1:Время возникновения пожара - 10 часов, лето.

Плотность людского потока D = 0,2 ч /м 2 , скорость движения потока v = 60

м /мин. Необходимое время эвакуации Tэв = 0,5 мин.

Пожарная ситуация 2:Время возникновения пожара 20 ч, лето. Плотность людского потока D = 0,83 ч /мин. скорость движения потока

v = 17 м /мин. Необходимое время эвакуации Tэв = 1,6 мин.

Возможны различные варианты эвакуации Li которые определяются

конструкционными и планировочными особенностями здания, наличием

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

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

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

Для ситуации 2, очевидно, подходят варианты эвакуации L1 и L2, хотя

L1 предпочтительней. Описание возможных пожарных ситуаций на объекте защиты и вариантов эвакуации оформляется в виде платежной матрицы, при этом:

N - возможные ситуации на пожаре:

L - варианты эвакуации;

а 11 – а nm результат эвакуации: "a" меняется от 0 (абсолютный проигрыш) - до 1 (максимальный выигрыш).

Например, при пожарных ситуациях:

N1- задымление общего коридора и охват его пламенем происходят

через 5 мин. после возникновения пожара;

N2 - задымление и охват пламенем коридора происходят через 7 мин;

N3 - задымление и охват коридора пламенем происходят через 10 мин.

Возможны следующие варианты эвакуации:

L1 - обеспечивающий эвакуацию за 6 мин;

L2 - обеспечивающий эвакуацию за 8 мин;

L3 - обеспечивающий эвакуацию за 12 мин.

а 11 = N1 / L1 = 5/ 6 = 0,83

а 12 = N1 / L2 = 5/ 8 = 0,62

а 13 = N1 / L3 = 5/ 12 = 0,42

а 21 = N2 / L1 = 7/ 6 = 1

а 22 = N2 / L2 = 7/ 8 = 0,87

а 23 = N2 / L3 = 7/ 12 = 0,58

а 31 = N3 / L1 = 10/ 6 = 1

а 32 = N3 / L2 = 10/ 8 = 1

а 33 = N3 / L3 = 10/ 12 = 0,83

Таблица. Платёжная матрица результатов эвакуации

L1	L2	L3
N1	0,83	0,6	0,42
N2	1	0,87	0,58
N3	1	1	0,83

Необходимое время эвакуации рассчитывать в процессе руководства

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

Данная матрица заносится в ЭВМ и по численному значению величины а ij подсистема автоматически подбирает оптимальный вариант эвакуации.

Заключение

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

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

Теория игр всегда имеет дело с особым типом мышления, стратегическим.

Библиографический список

1. Дж. фон Нейман, О. Моргенштерн. «Теория игр и экономическое поведение», Наука, 1970.

2. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. «Математические методы в экономике», Москва 1997, изд. «ДИС».

3. Оуэн Г. «Теория Игр». – М.: Мир, 1970.

4. Раскин М. А. «Введение в теорию игр» // Летняя школа «Современная математика». – Дубна: 2008.

5. http://ru.wikipedia.org/wiki

6. http://dic.academic.ru/dic.nsf/ruwiki/104891

7. http://ru.wikipedia.org/wiki

8. http://www.rae.ru/zk/arj/2007/12/Stepanenko.pdf

9. http://banzay-kz.livejournal.com/13890.html

10. http://propolis.com.ua/node/21

11. http://www.cfin.ru/management/game_theory.shtml

12. http://konflickt.ru/16/

13. http://www.krugosvet.ru/enc/nauka_i_tehnika/matematika/IGR_TEORIYA.html

14. http://matmodel.ru/article.php/20081126162627533

15. http://www.nsu.ru/ef/tsy/ec_cs/kokgames/prog3k.htm

Хотя я и закончил физико-технический факультет, в вузе мне не читали теорию игр. Но, поскольку я в студенческие годы много играл сначала в преферанс, а затем в бридж, теория игр меня интересовала, и я освоил небольшой учебник. А недавно читатель сайта Михаил решить задачу на теорию игр. Поняв, что сходу задача мне не дается, решил освежить в памяти мои знания по теории игр. Предлагаю вам небольшую книгу – популярное изложение элементов теории игр и некоторых способов решения матричных игр. Она почти не содержит доказательств и иллюстрирует основные положения теории примерами. Книгу написала математик и популяризатор науки Елена Сергеевна Вентцель. Несколько поколений советских инженеров учились по ее учебнику «Теория вероятностей». Елена Сергеевна также написала несколько литературных произведений под псевдонимом И. Грекова.

Елена Вентцель. Элементы теории игр. – М.: Физматгиз, 1961. – 68 с.

Скачать краткий конспект в формате или

§ 1. Предмет теории игр. Основные понятия

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

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

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

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

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

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

Начнем изложение элементарной теории игр с формулировки некоторых основных понятий. Будем рассматривать парную игру, в которой участвуют два игрока А и В с противоположными интересами. Под «игрой» будем понимать мероприятие, состоящее из ряда действий сторон А и В. Чтобы игра могла быть подвергнута математическому анализу, должны быть точно сформулированы правила игры. Под «правилами игры» разумеется система условий, регламентирующая возможные варианты действий обеих сторон, объем информации каждой стороны о поведении другой, последовательность чередования «ходов» (отдельных решений, принятых в процессе игры), а также результат или исход игры, к которому приводит данная совокупность ходов. Этот результат (выигрыш или проигрыш) не всегда имеет количественное выражение, но обычно можно, установив некоторую шкалу измерения, выразить его определенным числом. Например, в шахматной игре выигрышу можно условно приписать значение +1, проигрышу –1, ничьей 0.

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

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

При этом сторона А («мы») будет всегда рассматриваться как «выигрывающая», а сторона В («противник») как «проигрывающая». Это формальное условие, очевидно, не означает какого-либо реального преимущества для первого игрока; легко видеть, что оно заменяется противоположным, если знак выигрыша изменить на обратный.

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

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

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

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

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

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

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

В зависимости от числа возможных стратегий игры делятся на «конечные» и «бесконечные». Конечной называется игра, в которой у каждого игрока имеется только конечное число стратегий. Конечная игра, в которой игрок А имеет m стратегий, а игрок В - n стратегий, называется игрой mxn.

Рассмотрим игру mxn двух игроков А и В («мы» и «противник»). Будем обозначать наши стратегии A 1 , А 2 , …, А m стратегии противника B 1 , В 2 , …, В n . Пусть каждая сторона выбрала определенную стратегию; для нас это будет A i , для противника B j . Если игра состоит только из личных ходов, то выбор стратегий A i , B j однозначно определяет исход игры - наш выигрыш. Обозначим его а ij . Если игра содержит, кроме личных, случайные ходы, то выигрыш при паре стратегий A i , B j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является его среднее значение (математическое ожидание). Мы будем обозначать одним и тем же знаком как сам выигрыш (в игре без случайных ходов), так и его среднее значение (в игре со случайными ходами).

Пусть нам известны значения а ij выигрыша (или среднего выигрыша) при каждой паре стратегий. Значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют нашим стратегиям (A i), а столбцы - стратегиям противника (B j). Такая таблица называется платежной матрицей или просто матрицей игры. Матрица игры mxn представлена на рис. 1.

Рис. 1. Матрица mxn

Сокращенно мы будем обозначать матрицу игры ‖а ij ‖. Рассмотрим несколько элементарных примеров игр.

Пример 1. Два игрока A и В, не глядя друг на друга, кладут на стол по монете вверх гербом или решкой, по своему усмотрению. Если игроки выбрали одинаковые стороны (у обоих герб или у обоих решка), то игрок А забирает обе монеты; иначе их забирает игрок В. Требуется проанализировать игру и составить ее матрицу. Решение. Игра состоит только из двух ходов: наш ход и ход противника, оба личные. Игра не принадлежит к играм с полной информацией, так как в момент хода выполняющий его игрок не знает, что сделал другой. Так как у каждого из игроков имеется только один личный ход, то стратегия игрока представляет собой выбор при этом единственном личном ходе.

У нас две стратегии: А 1 - выбирать герб и А 2 - выбирать решку; у противника такие же две стратегии: В 1 - герб и В 2 - решка. Таким образом, данная игра есть игра 2×2. Будем считать выигрыш монеты за +1. Матрица игры:

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

Действительно, допустим, что мы (игрок А) выбрали себе какую-то стратегию (скажем, А 1) и придерживаемся ее. Тогда уже по результатам первых нескольких ходов противник догадается о нашей стратегии и будет на нее отвечать наименее выгодным для нас образом, т.е. выбирать решку. Нам явно невыгодно всегда применять какую-то одну стратегию; чтобы не оказаться в проигрыше, мы должны иногда выбирать герб, иногда - решку. Однако, если мы будем чередовать гербы и решки в какой-то определенной последовательности (например, через один), противник тоже может догадаться об этом и ответить на эту стратегию наихудшим для нас образом. Очевидно, надежным способом, гарантирующим, что противник не будет знать нашей стратегии, будет такая организация выбора при каждом ходе, когда мы его сами наперед не знаем (это можно обеспечить, например, подбрасыванием монеты). Таким образом, мы путем интуитивных рассуждений подходим к одному из существенных понятий теории игр – к понятию «смешанной стратегии», т.е. такой, когда «чистые» стратегии - в данном случае A 1 и А 2 – чередуются случайно с определенными частотами. В данном примере из соображений симметрии заранее ясно, что стратегии A 1 и А 2 должны чередоваться с одинаковой частотой; в более сложных играх решение может быть далеко не тривиальным.

Пример 2. Игроки А и В одновременно и независимо друг от друга записывают каждый одно из трех чисел: 1, 2 или 3. Если сумма написанных чисел четная, то В платит А эту сумму в рублях; если она нечетная, то, наоборот, А платит В эту сумму. Требуется проанализировать игру и составить ее матрицу.

Решение. Игра состоит из двух ходов; оба - личные. У нас (А) три стратегии: А 1 - писать 1; А 2 - писать 2; А 3 - писать 3. У противника (В) - те же три стратегии. Игра представляет собой игру 3×3:

Очевидно, как и в предыдущем случае, на любую выбранную нами стратегию противник может ответить наихудшим для нас образом. Действительно, если мы выберем, например, стратегию А 1 , противник будет всегда отвечать на нее стратегией В 2 ; на стратегию А 2 - стратегией В 3 ; на стратегию А 3 - стратегией В 2 ; таким образом, любой выбор определенной стратегии неизбежно приведет нас к проигрышу (не нужно, впрочем, забывать, что в столь же бедственной положении находится и противник). Решение этой игры (т.е. совокупность наивыгоднейших стратегий обоих игроков) будет дано в § 5.

Пример 3. В нашем распоряжении имеются три вида вооружения: А 1 , А 2 , А 3 ; у противника - три вида самолетов: B 1 , В 2 , В 3 . Наша задача - поразить самолет; задача противника- сохранить его непораженным. При применении вооружения А 1 самолеты B 1 , В 2 , В 3 поражаются соответственно с вероятностями 0,9, 0,4 и 0,2; при вооружении А 2 - с вероятностями 0,3, 0,6 и 0,8; при вооружении А 3 - с вероятностями 0,5, 0,7 и 0,2. Требуется сформулировать ситуацию в терминах теории игр.

Решение. Ситуация может рассматриваться как игра 3×3 с двумя личными ходами и одним случайным. Наш личный ход - выбор типа вооружения; личный ход противника - выбор самолета для участия в бою. Случайный ход - применение вооружения; этот ход может закончиться поражением или непоражением самолета. Наш выигрыш равен единице, если самолет поражен, и равен нулю в противном случае. Нашими стратегиями являются три варианта вооружения; стратегиями противника - три варианта самолетов. Среднее значение выигрыша при каждой заданной паре стратегий есть не что иное, как вероятность поражения данного самолета данным оружием. Матрица игры:

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

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

§ 2. Нижняя и верхняя цена игры. Принцип «минимакса»

Рассмотрим игру mxn с матрицей, как на рис. 1. Будем обозначать буквой i номер нашей стратегии; буквой j- номер стратегии противника. Поставим себе задачу: определить свою оптимальную стратегию. Проанализируем последовательно каждую из наших стратегий, начиная с A 1 .

Выбирая стратегию А i , мы всегда должны рассчитывать на то, что противник ответит на нее той из стратегий В j , для которой наш выигрыш а ij минимален. Определим это значение выигрыша, т.е. минимальное из чисел а ij в i -й строке. Обозначим его α i:

Здесь знаком min (минимум по j) обозначено минимальное из значений данного параметра при всех возможных j. Выпишем числа α i ; рядом с матрицей справа в виде добавочного столбца:

Выбирая какую-либо стратегию A i , мы должны рассчитывать на то, что в результате разумных действий противника мы не выиграем больше чем α i . Естественно, что, действуя наиболее осторожно и рассчитывая на наиболее разумного противника (т.е. избегая всякого риска), мы должны остановиться на той стратегии для которой число α i является максимальным. Обозначим это максимальное значение α:

или, принимая во внимание формулу (2.1),

Величина α называется нижней ценой игры, иначе - максиминным выигрышем или просто максимином. Число α лежит в определенной строчке матрицы; та стратегия игрока А, которая соответствует этой строчке, называется максиминной стратегией. Очевидно, если мы будем придерживаться максиминной стратегии, то нам при любом поведении противника гарантирован выигрыш, во всяком случае не меньший α. Поэтому величина α и называется «нижней ценой игры». Это - тот гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной («перестраховочной») стратегии.

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

и найдем минимальное из β j:

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

В качестве примеров определим нижнюю и верхнюю цену игры и минимаксные стратегии для примеров 1, 2 и 3 § 1.

Пример 1. В примере 1 § 1 дана игра со следующей матрицей:

Так как величины α i и β j постоянны и равны соответственно –1 и +1, нижняя и верхняя цена игры также равны –1 и +1: α = –1, β = +1. Любая стратегия игрока А является его максиминной, а любая стратегия игрока В - его минимаксной стратегией. Вывод тривиален: придерживаясь любой из своих стратегий, игрок А может гарантировать, что он проиграет не более 1; то же может гарантировать и игрок В.

Пример 2. В примере 2 § 1 дана игра с матрицей:

Нижняя цена игры α = –3; верхняя цена игры β = 4. Наша максиминная стратегия есть А 1 ; применяя ее систематически, мы можем твердо рассчитывать выиграть не менее –3 (проиграть не более 3). Минимаксная стратегия противника есть любая из стратегий В 1 и В 2 ; применяя их систематически, он, во всяком случае, может гарантировать, что проиграет не более 4. Если мы отступим от своей максиминной стратегии (например, выберем стратегию А 2), противник может нас «наказать» за это, применив стратегию В 3 и сведя наш выигрыш к –5; равным образом и отступление противника от своей минимаксной стратегии может увеличить его проигрыш до 6.

Пример 3. В примере 3 § 1 дана игра с матрицей:

Нижняя цена игры α = 0,3; верхняя ценя игры β = 0,7. Наша наиболее осторожная (максиминная) стратегия есть А 2 ; пользуясь вооружением А 2 , мы гарантируем, что будем поражать самолет в среднем не менее чем в 0,3 всех случаев. Наиболее осторожной (минимаксной) стратегией противника является В 2 ; применяя этот самолет, противник может быть уверен, что он будет поражаться не более чем в 0,7 всех случаев.

На последнем примере удобно продемонстрировать одно важное свойство минимаксных стратегий – их неустойчивость. Пусть мы применяем свою наиболее осторожную (максиминную) стратегию А 2 , а противник - свою наиболее осторожную (минимаксную) стратегию В 2 . До тех пор, пока оба противника придерживаются этих стратегий, средний выигрыш равен 0,6; он больше нижней, но меньше верхней цены игры. Теперь допустим, что противнику стало известно, что мы применяем стратегию А 2 ; он немедленно ответит на нее стратегией В 1 и сведет выигрыш к 0,3. В свою очередь, на стратегию B 1 у нас есть хороший ответ: стратегия A 1 , дающая нам выигрыш 0,9, и т.д.

Таким образом, положение, при котором оба игрока пользуются своими минимаксными стратегиями, является неустойчивым и может быть нарушено поступившими сведениями о стратегии противной стороны. Однако существуют некоторые игры, для которых минимаксные стратегии являются устойчивыми. Это те игры, для которых нижняя цена равна верхней: α = β. Если нижняя цена игры равна верхней, то их общее значение называется чистой ценой игры (иногда просто ценой игры), мы его будем обозначать буквой ν.

Рассмотрим пример. Пусть игра 4×4 задана матрицей:

Найдем нижнюю цену игры: α = 0,6. Найдем верхнюю цену игры: β = 0,6. Они оказались одинаковыми, следовательно, у игры есть чистая цена, равная α = β = ν = 0,6. Элемент 0,6, выделенный в платежной матрице, является одновременно минимальным в своей строке и максимальным в своем столбце. В геометрии точку на поверхности, обладающую аналогичным свойством (одновременный минимум по одной координате и максимум по другой), называют седловой точкой, по аналогии этот термин применяется и в теории игр. Элемент матрицы, обладающий этим свойством, называется седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.

Седловой точке соответствует пара минимаксных стратегий (в данном примере А 3 и В 2). Эти стратегии называются оптимальными, а их совокупность - решением игры. Решение игры обладает следующим замечательным свойством. Если один из игроков (например А) придерживается своей оптимальной стратегии, а другой игрок (В) будет любым способом отклоняться от своей оптимальной стратегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным, такое отклонение игрока В может в лучшем случае оставить выигрыш неизменным, а в худшем случае - увеличить его. Наоборот, если В придерживается своей оптимальной стратегии, а А отклоняется от своей, то это ни в коем случае не может быть выгодным для А.

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

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

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

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

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

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

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

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

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

Высказанное утверждение составляет содержание так называемой основной теоремы теории игр. Эта теорема была впервые доказана фон Нейманом в 1928 г. Известные доказательства теоремы сравнительно сложны; поэтому приведем только ее формулировку.

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

Выигрыш, получаемый в результате решения, называется ценой игры. Из основной теоремы следует, что каждая конечная игра имеет цену. Очевидно, что цена игры ν всегда лежит между нижней ценой игры α и верхней ценой игры β:

(3.1) α ≤ ν ≤ β

Действительно, α есть максимальный гарантированный выигрыш, который мы можем себе обеспечить, применяя только свои чистые стратегии. Так как смешанные стратегии включают в себя в качестве частного случая и все чистые, то, допуская, кроме чистых, еще и смешанные стратегии, мы, во всяком случае, не ухудшаем своих возможностей; следовательно, ν ≥ α. Аналогично, рассматривая возможности противника, покажем, что ν ≤ β, откуда следует доказываемое неравенство (3.1).

Введем специальное обозначение для смешанных стратегий. Если, например, наша смешанная стратегия состоит в применении стратегий А 1 , А 2 , А 3 с частотами p 1 , р 2 , р 3 , причем p 1 + р 2 + р 3 = 1, будем обозначать эту стратегию

Аналогично смешанную стратегию противника будем обозначать:

где q 1 , q 2 , q 3 - частоты, в которых смешиваются стратегии B 1 , В 2 , В 3 ; q 1 + q 2 + q 3 = 1.

Предположим, что нами найдено решение игры, состоящее из двух оптимальных смешанных стратегий S A *, S B *. В общем случае не все чистые стратегии, доступные данному игроку, входят в его оптимальную смешанную стратегию, а только некоторые. Будем называть стратегии, входящие в оптимальную смешанную стратегию игрока, его «полезными» стратегиями. Оказывается, что решение игры обладает еще одним замечательным свойством: если один из игроков придерживается своей оптимальной смешанной стратегии S A * (S B *), то выигрыш остается неизменным и равным цене игры ν, независимо от того, что делает другой игрок, если он только не выходит за пределы своих «полезных» стратегий. Он, например, может пользоваться любой из своих «полезных» стратегий в чистом виде, а также может смешивать их в любых пропорциях.

§ 4. Элементарные методы решения игр. Игры 2 x 2 и 2 x n

Если игра mxn не имеет седловой точки, то нахождение решения есть вообще довольно трудная задача, особенно при больших m и n. Иногда эту задачу удается упростить, если предварительно уменьшить число стратегий путем вычеркивания некоторых излишних. Излишние стратегии бывают а) дублирующие и б) заведомо невыгодные. Рассмотрим, например, игру с матрицей:

Нетрудно убедиться, что стратегия А 3 в точности повторяет («дублирует») стратегию А 1 , поэтому любую из этих двух стратегий можно вычеркнуть. Далее, сравнивая строки A 1 и А 2 , видим, что каждый элемент строки А 2 меньше (или равен) соответствующего элемента строки A 1 . Очевидно, что мы никогда не должны пользоваться стратегией А2, она является заведомо невыгодной. Вычеркивая А 3 и А 2 , приводим матрицу к более простому виду. Далее замечаем, что для противника стратегия В 3 заведомо невыгодна; вычеркивая ее, приводим матрицу к окончательному виду:

Таким образом, игра 4×4 вычеркиванием дублирующих и заведомо невыгодных стратегий сведена к игре 2×3.

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

Рассмотрим игру 2×2 с матрицей:

Здесь могут встретиться два случая: 1) игра имеет седловую точку; 2) игра не имеет седловой точки. В первом случае решение очевидно: это пара стратегий, пересекающихся в седловой точке. Заметим кстати, что в игре 2×2 наличие седловой точки всегда соответствует существованию заведомо невыгодных стратегий, которые должны быть вычеркнуты при предварительном анализе.

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

Она отличается тем свойством, что, каковы бы ни были действия противника (если только он не выходит за пределы своих «полезных» стратегий), выигрыш будет равен цене игры ν. В игре 2×2 обе стратегии противника являются «полезными», - иначе игра имела бы решение в области чистых стратегий (седловую точку). Значит, если мы придерживаемся своей оптимальной стратегии (4.1), то противник может пользоваться любой из своих чистых стратегий B 1 , В 2 , не изменяя среднего выигрыша ν. Отсюда имеем два уравнения:

из которых, принимая во внимание, что p 1 + p 2 = 1, получим:

Цену игры ν найдем, подставляя значения р 1 , р 2 в любое из уравнений (4.2).

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

достаточно одного уравнения, например:

откуда, учитывая, что q 1 + q 2 = 1, имеем:

Пример 1. Найдем решение игры 2×2, рассмотренной в примере 1 § 1, с матрицей:

Игра не имеет седловой точки (α = –1; β = +1), и, следовательно, решение должно лежать в области смешанных стратегий:

Нужно найти p 1 , р 2 , q 1 и q 2 . Для p 1 имеем уравнение

1*p 1 + (–1)(1 – p 1) = (–1)p 1 + 1(1 – p 1)

откуда p 1 = 1/2, p 2 = 1/2.

Аналогично найдем: q 1 = 1/2, q 2 = 1/2, ν = 0.

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

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

Пример 2. Игра состоит в следующем. Имеются две карты: туз и двойка. Игрок А наугад вынимает одну из них; В не видит, какую карту он вынул. Если А вынул туза, он заявляет: «у меня туз», и требует у противника 1 рубль. Если А вынул двойку, то он может либо А 1) сказать «у меня туз» и потребовать у противника 1 рубль, либо А 2) признаться, что у него двойка, и уплатить противнику 1 рубль.

Противник, если ему добровольно платят 1 рубль, может только принять его. Если же у него потребуют 1 рубль, то он может либо В 1) поверить игроку А, что у него туз, и отдать ему 1 рубль, либо В 2) потребовать проверки с тем, чтобы убедиться, верно ли утверждение А. Если в результате проверки окажется, что у А действительно туз, В должен уплатить А 2 рубля. Если же окажется, что А обманывает и у него двойка, игрок А уплачивает игроку В 2 рубля. Требуется проанализировать игру и найти оптимальную стратегию каждого из игроков.

Решение. Игра имеет сравнительно сложную структуру; она состоит из одного обязательного случайного хода - выбора игроком А одной из двух карт - и двух личных ходов, которые, однако, необязательно осуществляются. Действительно, если А вынул туза, то он не делает никакого личного хода: ему предоставлена только одна возможность - потребовать 1 рубль, что он и делает. В этом случае личный ход - верить или не верить (т.е. платить или не платить 1 рубль,) - передается игроку В. Если А в результате первого случайного хода получил двойку, то ему предоставляется личный ход: уплатить 1 рубль или попытаться обмануть противника и потребовать 1 рубль (короче: «не обманывать» или «обманывать»). Если А выбирает первое, то В остается только принять 1 рубль; если А выбрал второе, то игроку В предоставляется личный ход: верить или не верить А (т.е. уплатить А 1 рубль или требовать проверки).

Стратегии каждого из игроков представляют собой правила, указывающие, как поступить игроку, когда ему предоставляется личный ход. Очевидно, у А только две стратегии: А 1 - обманывать, А 2 - не обманывать. У В - тоже две стратегии: B 1 - верить, В 2 - не верить. Построим матрицу игры. Для этого вычислим средний выигрыш при каждой комбинации стратегий.

1. А 1 В 1 (А обманывает, В верит). Если А получил туза (вероятность этого ½, то ему не предоставляется личного хода; он требует 1 рубль, и игрок В верит ему; выигрыш А в рублях равен 1. Если А получил двойку (вероятность этого тоже ½), он согласно своей стратегии обманывает и требует 1 рубль; В ему верит и уплачивает; выигрыш А также равен 1. Средний выигрыш: а 11 = ½*1 + ½*1 = 1.

2. А 1 В 2 (А обманывает, В не верит). Если А получил туза, у него нет личного хода; он требует 1 рубль; В согласно своей стратегии не верит и в результате проверки уплачивает 2 рубля (выигрыш А равен +2). Если А получил двойку, он согласно своей стратегии требует 1 рубль; В, согласно своей, не верит; в результате А уплачивает 2 рубля (выигрыш А равен –2). Средний выигрыш равен: а 12 = ½*(+2) + ½*(–2) = 0.

3. A 2 В 1 (А не обманывает, В верит). Если А вынул туза, он требует 1 рубль; В согласно своей стратегии уплачивает; выигрыш А равен +1. Если А вынул двойку, он согласно своей стратегии платит 1 рубль; В остается только принять (выигрыш А равен –1). Средний выигрыш равен: а 21 = ½*(+1) + ½*(–1) = 0.

4. А 2 В 2 (А не обманывает, В не верит). Если А вынул туза, он требует 1 рубль; В проверяет и в результате проверки уплачивает 2 рубля (выигрыш равен +2). Если А вынул двойку, он уплачивает 1 рубль; В остается только принять (выигрыш равен 1). Средний выигрыш равен: а 22 = ½*(+2) + ½*(–1) = ½.

Строим матрицу игры:

Матрица не имеет седловой точки. Нижняя цена игры α = 0, верхняя цена игры β = ½. Найдем решение игры в области смешанных стратегий. Применяя формулу (4.3), получим:

т.е. игрок А должен в одной трети всех случаев пользоваться своей первой стратегией (обманывать), а в двух третях – второй (не обманывать). При этом он будет выигрывать в среднем цену игры ν = 1/3.

Значение ν = 1/3 свидетельствует о том, что в данных условиях игра выгодна для А и невыгодна для В. Пользуясь своей оптимальной стратегией, А всегда может себе обеспечить положительный средний выигрыш. Заметим, что, если бы А пользовался своей наиболее осторожной (максиминной) стратегией (в данном случае обе стратегии A 1 и А 2 являются максиминными), он имел бы средний выигрыш, равный нулю. Таким образом, применение смешанной стратегии дает А возможность реализовать свое преимущество над В, возникающее при данных правилах игры.

Определим оптимальную стратегию В. Имеем: q 1 *1 + q 2 *0 = 1/3, q 1 = 1/3, q 2 = 2/3. Откуда

т.e. игрок В должен в одной трети всех случаев верить А и уплачивать ему 1 рубль без проверки, а в двух третях случаев - проверять. Тогда он будет в среднем на каждую игру проигрывать 1/3. Если бы он пользовался своей минимаксной чистой стратегией В 2 (не верить), он на каждую игру проигрывал бы в среднем 1/2.

Решению игры 2×2 можно дать простую геометрическую интерпретацию. Пусть имеется игра 2×2 с матрицей

Возьмем участок оси абсцисс длиной 1 (рис. 4.1). Левый конец участка (точка с абсциссой х = 0) будет изображать стратегию А 1 ; правый конец участка (х = 1) - стратегию А 2 . Проведем через точки А 1 и А 2 два перпендикуляра к оси абсцисс: ось I –I и ось II–II . На оси I –I будем откладывать выигрыши при стратегии A 1 ; на оси II–II -выигрыши при стратегии А 2 . Рассмотрим стратегию противника B 1 ; она дает две точки на осях I –I и II–II с ординатами соответственно а 11 и а 21 . Проведем через эти точки прямую B 1 B 1 . Очевидно, если мы при стратегии противника B 1 будем применять смешанную стратегию

то наш средний выигрыш, равный в этом случае а 11 р 1 + а 21 р 2 , изобразится точкой М на прямой В 1 B 1 ; абсцисса этой точки равна р 2 . Прямую В 1 В 1 , изображающую выигрыш при стратегии В 1 , будем условно называть «стратегией В 1 ».

Очевидно, точно таким же способом может быть построена и стратегия В 2 (рис. 4.2).

Нам нужно найти оптимальную стратегию S A *, т. е. такую, для которой минимальный выигрыш (при любом поведении В) обращался бы в максимум. Для этого построим нижнюю границу выигрыша при стратегиях В 1 , В 2 , т.е. ломаную B 1 NB 2 , отмеченную на рис. 4.2 жирной линией. Эта нижняя граница будет выражать минимальный выигрыш игрока А при любых его смешанных стратегиях; точка N, в которой этот минимальный выигрыш достигает максимума, и определяет решение и цену игры. Нетрудно убедиться, что ордината точки N есть цена игры ν, а ее абсцисса равна р 2 - частоте применения стратегии А 2 в оптимальной смешанной стратегии S A *.

В нашем случае решение игры определялось точкой пересечения стратегий. Однако это не всегда будет так; на рис. 4.3 показан случай, когда, несмотря на наличие пересечения стратегий, решение дает для обоих игроков чистые стратегии (A 2 и В 2), а цена игры ν = а 22 . В данном случае матрица имеет седловую точку, и стратегия А 1 является заведомо невыгодной, т.к. при любой чистой стратегии противника она дает меньший выигрыш, чем А 2 .

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

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

Геометрическая интерпретация дает возможность представить наглядно также нижнюю и верхнюю цены игры (рис. 4.5).

Для иллюстрации построим геометрические интерпретации игр 2×2, рассмотренных в примерах 1 и 2 (рис. 4.6 и 4.7).

Мы убедились, что любая игра 2×2 может быть решена элементарными приемами. Совершенно аналогично может быть решена любая игра 2xn. где у нас имеются всего две стратегии, а у противника - произвольное число.

Пусть мы располагаем двумя стратегиями: А 1 , А 2 , а противник - n стратегиями: В 1 , В 2 , …, В n . Матрица ‖a ij ‖ задана; она состоит из двух строк и n столбцов. Аналогично случаю двух стратегий дадим задаче геометрическую интерпретацию; n стратегий противника изобразятся n прямыми (рис. 4.8). Строим нижнюю границу выигрыша (ломаную B 1 MNB 2) и находим на ней точку N с максимальной ординатой. Эта точка дает решение игры (стратегию ) ордината точки N равна цене игры ν, а абсцисса равна частоте р 2 стратегии A 2 .

В данном случае оптимальная стратегия противника получается применением смеси двух «полезных» стратегий: В 2 и В 4 , пересекающихся в точке N. Стратегия В 3 является заведомо невыгодной, а стратегия B 1 - невыгодной при оптимальной стратегии S A *. Если А будет придерживаться своей оптимальной стратегии, то выигрыш не изменится, какой бы из своих «полезных» стратегий ни пользовался В, однако, он изменится, если В перейдет к стратегиям B 1 или В 3 . В теории игр доказывается, что у любой конечной игры mxn имеется решение, в котором число «полезных» стратегий той и другой стороны не превосходит наименьшего из двух чисел m и n. В частности, из этого следует, что у игры 2xm всегда имеется решение, в котором с той и другой стороны участвует не более двух «полезных» стратегий.

Пользуясь геометрической интерпретацией, можно дать простой способ решения любой игры 2xm. Непосредственно по чертежу находим пару «полезных» стратегий противника B j и В k , пересекающиеся в точке N (если в точке N пересекается более двух стратегий, берем любые две из них). Мы знаем, что если игрок А придерживается своей оптимальной стратегии, то выигрыш не зависит от того, в какой пропорции применяет В свои «полезные» стратегии, следовательно,

Из этих уравнений и условия р 2 = 1 – p 1 , находим р1, р2 и цену игры ν. Зная цену игры, можно сразу определить оптимальную стратегию игрока В. Для этого решается, например, уравнение: q j a 1 j + q k a 1 k = ν, где q j + q k = 1. В случае, когда мы располагаем m стратегиями, а противник - всего двумя, очевидно, задача решается совершенно аналогичным способом; достаточно заметить, что, изменяя знак выигрыша на обратный, можно превратить игрока А из «выигрывающего» в «проигрывающего». Можно решить игру и без перемены знака выигрыша; тогда задача решается непосредственно для В, но строится не нижняя, а верхняя граница выигрыша (рис. 4.9). На границе ищется точка N с минимальной ординатой, которая и есть цена игры ν.

Рассмотрим и решим несколько примеров игр 2×2 и 2xm, являющихся упрощенными образчиками игр, имеющих практическое значение.

Пример 3. Сторона А посылает в район расположения противника В два бомбардировщика I и II ; I летит спереди, II – сзади. Один из бомбардировщиков – заранее неизвестно какой – должен нести бомбу, другой выполняет функцию сопровождения. В районе противника бомбардировщики подвергаются нападению истребителя стороны В. Бомбардировщики вооружены пушками различной скорострельности. Если истребитель атакует задний бомбардировщик II , то по нему ведут огонь пушки только этого бомбардировщика; если же он атакует передний бомбардировщик, то по нему ведут огонь пушки обоих бомбардировщиков. Вероятность поражения истребителя в первом случае 0,3, во втором 0,7.

Если истребитель не сбит оборонительным огнем бомбардировщиков, то он поражает выбранную им цель с вероятностью 0,6. Задача бомбардировщиков – донести бомбу до цели; задача истребителя – воспрепятствовать этому, т.е. сбить бомбардировщик-носитель. Требуется выбрать оптимальные стратегии сторон:

а) для стороны А: какой бомбардировщик сделать носителем?

б) для стороны В: какой бомбардировщик атаковать?

Решение. Имеем простой случай игры 2×2; выигрыш- вероятность непоражения носителя. Наши стратегии: А 1 - носитель - бомбардировщик I ; А 2 - носитель - бомбардировщик II . Стратегии противника: В 1 - атакуется бомбардировщик I ; В 2 -атакуется бомбардировщик II . Составим матрицу игры, т.е. найдем средний выигрыш при каждой комбинации стратегий.

1. А 1 В 1 (носитель I , атакуется I ). Носитель не будет поражен, если бомбардировщики собьют истребитель, или не собьют, но он не поразит свою цель: а 11 = 0,7 + 0,3 * 0,4 = 0,82.

2. А 2 В 1 (носитель II , атакуется I ). a 21 = 1

3. А 1 В 2 (носитель I , атакуется II ). A 12 = 1

4. А 2 В 2 (носитель II , атакуется II ). A 22 = 0,3 + 0,7*0,4 = 0,58

Матрица игры имеет вид:

Нижняя цена игры 0,82; верхняя цена 1. Матрица не имеет седловой точки; решение ищем в области смешанных стратегий. Имеем:

p 1 *0,82 + p 2 *1 = ν

p 1 *1 + p 2 *0,58 = ν

p 1 = 0,7; p 2 = 0,3

Наша оптимальная стратегия есть т. е. в качестве носителя нужно чаще выбирать I , чем II . Цена игры равна ν = 0,874. Зная ν, определяем q 1 и q 2 - частоты стратегий В 1 и В 2 в оптимальной стратегии противника S B *. Имеем: q 1 *0,82 + q 2 *1 = 0,874 и q 2 = 1 – q 1 , откуда q 1 = 0,7; q 2 = 0,3, т. е. оптимальная стратегия противника есть .

Пример 4. Сторона А нападает на объект, сторона В - обороняет его. У стороны А - два самолета; у стороны В - три зенитных орудия. Каждый самолет является носителем мощного поражающего средства; для того чтобы объект был поражен, достаточно, чтобы к нему прорвался хотя бы один самолет. Самолеты стороны А могут выбирать для подхода к объекту любое из трех направлений: I , II , III (рис. 4.10). Противник (сторона В) может разместить любое из своих орудий на любом направлении; при этом каждое орудие простреливает только область пространства, относящуюся к данному направлению, и не простреливает соседние направления. Каждое орудие может обстрелять только один самолет; обстрелянный самолет поражается с вероятностью 1. Сторона А не знает, где размещены орудия; сторона В не знает, откуда прилетят самолеты. Задача стороны А - поразить объект; задача стороны В - не допустить его поражения. Найти решение игры.

Решение. Игра представляет собой игру 2×3. Выигрыш - вероятность поражения объекта. Наши возможные стратегии: А 1 - послать по одному самолету на два различных направления. А 2 - послать оба самолета по одному направлению. Стратегии противника: В 1 - поставить по одному орудию на каждое направление; В 2 - поставить два орудия на одно направление и одно - на другое; В 3 - поставить все три орудия на одно направление. Составляем матрицу игры.

1. А 1 В 1 (самолеты летят по разным направлениям; орудия расставлены по одному). Очевидно, при этом ни один самолет не прорвется к объекту: а 11 = 0.

2. А 2 В 1 (самолеты летят вместе по одному направлению; орудия расставлены по одному). Очевидно, при этом один самолет пройдет к объекту необстрелянным: а 21 = 1.

3. А 1 В 2 (самолеты летят по одному; противник защищает два направления и оставляет незащищенным третье). Вероятность того, что хотя бы один самолет прорвется к объекту, равна вероятности того, что один из них выберет незащищенное направление: а 12 = 2/3.

4. А 2 В 2 (самолеты летят вместе по одному направлению; противник защищает одно направление двумя орудиями и одно - одним, т. е. фактически защищает одно направление и оставляет незащищенным два). Вероятность того, что хотя бы один самолет прорвется к объекту, равна вероятности выбора парой самолетов фактически незащищенного направления: а 22 = 2/3.

5. А 1 В 3 (самолеты летят по одному; противник защищает тремя орудиями только одно направление): а 13 = 1.

6. А 2 В 3 (самолеты летят оба вместе; противник защищает тремя орудиями только одно направление). Чтобы объект был поражен, самолеты должны выбрать незащищенное направление: а 23 = 2/3.

Матрица игры:

Из матрицы видно, что стратегия В 3 является заведомо невыгодной по сравнению с В 2 (это можно было решить и заранее). Вычеркиванием стратегии В 3 игра сводится к игре 2×2:

Матрица имеет седловую точку: нижняя цена игры 2/3 совпадает с верхней. Одновременно замечаем, что для нас (А) стратегия A 1 является заведомо невыгодной. Вывод: обе стороны А и В должны пользоваться всегда своими чистыми стратегиями А 2 и В 2 , т.е. мы должны посылать самолеты по 2, выбирая случайным образом направление, по которому посылается пара; противник должен ставить орудия так: два - на одно направление, одно- на другое, причем выбор этих направлений также должен производиться случайно (здесь, как мы видим, уже «чистые стратегии» включают элемент случайности). Применяя эти оптимальные стратегии, мы всегда будем получать постоянный средний выигрыш 2/3 (т.е. объект будет поражаться с вероятностью 2/3). Заметим, что найденное решение игры не является единственным; помимо решения в чистых стратегиях, существует целый участок смешанных стратегий игрока А, являющихся оптимальными, от р 1 = 0 до р 1 = 1/3 (рис. 4.11).

Легко, например, убедиться непосредственно, что тот же средний выигрыш 2/3 получится, если мы будем применять свои стратегии А 1 и А 2 в пропорции 1/3 и 2/3.

Пример 5. Те же условия, что в предыдущем примере, но для нас возможны четыре направления удара, а противник располагает четырьмя орудиями.

Решение. У нас по-прежнему две возможные стратегии: А 1 - посылать самолеты по одному, А 2 - посылать два самолета вместе. У противника пять возможных стратегий: В 1 - ставить по одному орудию на каждое направление; В 2 - ставить по два орудия на два различных направления; В 3 - ставить два орудия на одно направление и по одному - на два других; В 4 -ставить три орудия на одно направление и одно - на другое; В 5 - ставить все четыре орудия на одно направление. Стратегии В 4 , В 5 отбросим заранее как заведомо невыгодные. Рассуждая аналогично предыдущему примеру, строим матрицу игры:

Нижняя цена игры 1/2, верхняя 3/4. Матрица не имеет седловой точки; решение лежит в области смешанных стратегий. Пользуясь геометрической интерпретацией (рис. 4.12), выделим «полезные» стратегии противника: В 1 и В 2 .

Частоты р 1 и р 2 определим из уравнений: p 1 *0 + (1 – p 1)*1 = ν и p 1 *5/6 + (1 – p 1)*1/2 = ν; откуда p 1 = 3/8; p 2 = 5/8; ν = 5/8, т.е. наша оптимальная стратегия есть . Пользуясь ею, мы гарантируем себе средний выигрыш 5/8. Зная цену игры ν = 5/8, находим частоты q 1 и q 2 «полезных» стратегий противника: q 1 *0 + (1 – q 1)*5/6 = 5/8, q 1 = ¼, q 2 = ¾. Оптимальная стратегия противника будет: .

Пример 6. Сторона А располагает двумя стратегиями A 1 и А 2 , сторона В - четырьмя B 1 , В 2 , В 3 и В 4 . Матрица игры имеет вид:

Найти решение игры.

Решение. Нижняя цена игры 3; верхняя 4. Геометрическая интерпретация (рис. 4.13) показывает, что полезными стратегиями игрока В являются В 1 и В 2 или В 2 и В 4:

Игрок А имеет бесконечно много оптимальных смешанных стратегий: в оптимальной стратегии p 1 может изменяться от 1/5 до 4/5. Цена игры ν = 4. Игрок В имеет чистую оптимальную стратегию В 2 .

§ 5. Общие методы решения конечных игр

Мы рассматривали до сих пор только самые элементарные игры типа 2xn, которые могут быть весьма просто решены и допускают удобную и наглядную геометрическую интерпретацию. В общем случае решение игры mxn представляет довольно трудную задачу, причем сложность задачи и объем необходимых для решения вычислений резко возрастает с увеличением m и n. Однако эти трудности не носят принципиального характера и связаны только с очень большим объемом расчетов, который в ряде случаев может оказаться практически невыполнимым. Принципиальная сторона метода отыскания решения остается при любом m одной и той же.

Проиллюстрируем это на примере игры 3xn. Дадим ей геометрическую интерпретацию - уже пространственную. Три наши стратегии А 1 , A 2 и A 3 изобразим тремя точками на плоскости хОу ; первая лежит в начале координат (рис. 5.1), вторая и третья - на осях Ох и Оу на расстояниях 1 от начала.

Через точки A 1 , А 2 и А 3 проводятся оси I – I , II – II и III – III , перпендикулярные к плоскости хОу . На оси I – I откладываются выигрыши при стратегии А 1 на осях II – II и III – III - выигрыши при стратегиях А 2 , А 3 . Каждая стратегия противника B j изобразится плоскостью, отсекающей на осях I – I , II – II и III – III отрезки, равные выигрышам при соответствующих стратегиях A 1 , А 2 и А 3 и стратегии В j . Построив таким образом все стратегии противника, мы получим семейство плоскостей над треугольником A 1 , А 2 и А 3 (рис. 5.2). Для этого семейства также можно построить нижнюю границу выигрыша, как мы это делали в случае 2xn и найти на этой границе точку N с максимальной высотой над плоскостью хОу . Эта высота и будет ценой игры ν.

Частоты p 1 , р 2 , р 3 стратегий A 1 , А 2 и А 3 в оптимальной стратегии S A * будут определяться координатами (х, у) точки N, а именно: p 2 = x, p 3 = y, p 1 = 1 – p 2 – p 3 . Однако такое геометрическое построение даже для случая 3xn нелегко осуществимо и требует большой затраты времени и усилий воображения. В общем же случае игры оно переносится в m-мерное пространство и теряет всякую наглядность, хотя употребление геометрической терминологии в ряде случаев может оказаться полезным. При решении игр mxn на практике удобнее пользоваться не геометрическими аналогиями, а расчетными аналитическими методами, тем более, что для решения задачи на вычислительных машинах эти методы единственно пригодны.

Все эти методы по существу сводятся к решению задачи путем последовательных проб, но упорядочение последовательности проб позволяет построить алгоритм, приводящий к решению наиболее экономичным способом. Здесь мы вкратце остановимся на одном расчетном методе решения игр mxn - на так называемом методе «линейного программирования». Для этого дадим сначала общую постановку задачи о нахождении решения игры mxn. Пусть дана игра mxn с m стратегиями A 1 , А 2 , …, А m игрока А и n стратегиями B 1 , B 2 , …, B n игрока В и задана платежная матрица ‖a i j ‖. Требуется найти решение игры, т.е. две оптимальные смешанные стратегии игроков А и В

где p 1 + p 2 + … + p m = 1; q 1 + q 2 + … + q n = 1 (некоторые из чисел p i и q j могут быть равными нулю).

Наша оптимальная стратегия S A *должна обеспечивать нам выигрыш, не меньший ν, при любом поведении противника, и выигрыш, равный ν, при его оптимальном поведении (стратегия S B *). Аналогично стратегия S B * должна обеспечивать противнику проигрыш, не больший ν, при любом нашем поведении и равный ν при нашем оптимальном поведении (стратегия S A *).

Величина цены игры ν в данном случае нам неизвестна; будем считать, что она равна некоторому положительному числу. Полагая так, мы не нарушаем общности рассуждений; для того чтобы было ν > 0, очевидно, достаточно, чтобы все элементы матрицы ‖a i j ‖ были неотрицательными. Этого всегда можно добиться, прибавляя к элементам ‖a i j ‖ достаточно большую положительную величину L ; при этом цена игры увеличится на L , а решение не изменится.

Пусть мы выбрали свою оптимальную стратегию S A *. Тогда наш средний выигрыш при стратегии B j противника будет равен: a j = p 1 a 1j + p 2 a 2j + … + p m a mj . Наша оптимальная стратегия S A * обладает тем свойством, что при любом поведении противника обеспечивает выигрыш не меньший, чем ν; следовательно, любое из чисел a j не может быть меньше ν. Получаем ряд условий:

Разделим неравенства (5.1) на положительную величину ν и обозначим

Тогда условия (5.1) запишутся в виде

где ξ 1 , ξ 2 , …, ξ m - неотрицательные числа. Так как р 1 + p 2 + … + p m = 1, то величины ξ 1 , ξ 2 , …, ξ m удовлетворяют условию

(5.3) ξ 1 + ξ 2 + … + ξ m = 1/ν.

Мы хотим сделать свой гарантированный выигрыш максимально возможным; очевидно, при этом правая часть равенства (5.3) принимает минимальное значение. Таким образом, задача нахождения решения игры сводится к следующей математической задаче: определить неотрицательные величины ξ 1 , ξ 2 , …, ξ m , удовлетворяющие условиям (5.2), так, чтобы их сумма Φ = ξ 1 + ξ 2 + … + ξ m была минимальной.

Обычно при решении задач, связанных с нахождением экстремальных значений (максимумов и минимумов), функцию дифференцируют и приравнивают производные нулю. Но такой прием в данном случае бесполезен, так как функция Φ, которую нужно обратить в минимум, линейна, и ее производные по всем аргументам равны единице, т.е. нигде не обращаются в нуль. Следовательно, максимум функции достигается где-то на границе области изменения аргументов, которая определяется требованием неотрицательности аргументов и условиями (5.2). Прием нахождения экстремальных значений при помощи дифференцирования непригоден и в тех случаях, когда для решения игры определяется максимум нижней (или минимум верхней) границы выигрыша, как мы, например, делали при решении игр 2xn. Действительно, нижняя граница составлена из участков прямых линий, и максимум достигается не в точке, где производная равна нулю (такой точки вообще нет), а на границе интервала или в точке пересечения прямолинейных участков.

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

Требуется найти неотрицательные значения величин ξ 1 , ξ 2 , …, ξ m , удовлетворяющие условиям (5.4) и вместе с тем обращающие в минимум заданную однородную линейную функцию величин ξ 1 , ξ 2 , …, ξ m (линейную форму): Φ = c 1 ξ 1 + c 2 ξ 2 + … + c m ξ m

Легко убедиться, что поставленная выше задача теории игр является частным случаем задачи линейного программирования при с 1 = с 2 = … = с m = 1. С первого взгляда может показаться, что условия (5.2) не эквивалентны условиям (5.4), так как вместо знаков равенства они содержат знаки неравенства. Однако от знаков неравенства легко избавиться, вводя новые фиктивные неотрицательные переменные z 1 , z 2 , …, z n и записывая условия (5.2) в виде:

Форма Φ, которую нужно обратить в минимум, равна Φ = ξ 1 + ξ 2 + … + ξ m . Аппарат линейного программирования позволяет путем сравнительно небольшого числа последовательных проб подобрать величины ξ 1 , ξ 2 , …, ξ m , удовлетворяющие поставленным требованиям. Для большей ясности мы здесь продемонстрируем применение этого аппарата прямо на материале решения конкретных игр.

Пример 1. Требуется найти решение игры 3×3, данной в примере 2 § 1, с матрицей:

Чтобы сделать все а ij неотрицательными, прибавим ко всем элементам матрицы L = 5. Получим матрицу:

При этом цена игры увеличится на 5, а решение не изменится.

Определим оптимальную стратегию S A *. Условия (5.2) имеют вид:

где ξ 1 = p 1 /ν, ξ 2 = p 2 /ν, ξ 3 = p 3 /ν. Чтобы избавиться от знаков неравенства, введем фиктивные переменные z 1 , z 2 , z 3 ; условия (5.6) запишутся в виде:

Линейная форма Φ имеет вид: Φ = ξ 1 + ξ 2 + ξ 3 и должна быть сделана как можно меньше. Если все три стратегии В являются «полезными», то все три фиктивные переменные z 1 , z 2 , z 3 обратятся в нуль (т.е. выигрыш, равный цене игры ν, будет достигаться при каждой стратегии B j). Но мы пока не имеем оснований утверждать, что все три стратегии являются «полезными». Чтобы проверить это, попытаемся выразить форму Φ через фиктивные переменные z 1 , z 2 , z 3 и посмотрим, добьемся ли мы, полагая их равными нулю, минимума формы. Для этого разрешим уравнения (5.7) относительно переменных ξ 1 , ξ 2 , ξ 3 (т.е. выразим ξ 1 , ξ 2 , ξ 3 через фиктивные переменные z 1 , z 2 , z 3):

Складывая ξ 1 , ξ 2 , ξ 3 , получим: Φ = 1/5 + z 1 /20 + z 2 /10 + z 3 /20. Здесь коэффициенты при всех z положительны; значит, любое увеличение z 1 , z 2 , z 3 сверх нуля может привести только к увеличению формы Φ, а мы хотим, чтобы она была минимальна. Следовательно, значениями z 1 , z 2 , z 3 , обращающими форму Φ в минимум, являются z 1 = z 2 = z 3 = 0. Следовательно, минимальное значение формы Φ: 1/ν = 1/5, откуда цена игры ν = 5. Подставляя нулевые значения z 1 , z 2 , z 3 в формулы (5.8), находим: ξ 1 = 1/20, ξ 2 = 1/10, ξ 3 = 1/20, или, умножая их на ν, р 1 = 1/4, р 2 = 1/2, р 3 = 1/4. Таким образом, оптимальная стратегия А найдена: , т.е. мы должны в одной четверти всех случаев писать цифру 1, в половине случаев 2 и в остальной четверти случаев 3.

Зная цену игры ν = 5, можно уже известными способами найти оптимальную стратегию противника . Для этого воспользуемся нашими любыми двумя «полезными» стратегиями (например, А 2 и А 3) и напишем уравнения:

9q 1 + 11 (1-q 2 -q 1) = 5,

откуда q 1 = q3 = 1/4; q 2 = 1/2. Оптимальная стратегия противника будет такой же, как наша: . Теперь вернемся к первоначальной (не преобразованной) игре. Для этого нужно только от цены игры ν = 5 отнять величину L = 5, прибавленную к элементам матрицы. Получим цену исходной игры v 0 = 0. Следовательно, оптимальные стратегии обеих сторон обеспечивают средний выигрыш, равный нулю; игра в одинаковой мере выгодна или невыгодна для обеих сторон.

Пример 2. Спортивный клуб А располагает тремя вариантами состава команды А 1 , А 2 и А 3 . Клуб В - также тремя вариантами B 1 , В 2 и В 3 . Подавая заявку для участия в соревновании, ни один из клубов не знает, какой состав изберет противник. Вероятности выигрыша клуба А при различных вариантах составов команд, примерно известные из опыта прошлых встреч, заданы матрицей:

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

Решение. Нижняя цена игры 0,4; верхняя 0,6; решение ищем в области смешанных стратегий. Чтобы не иметь дела с дробями, умножим все элементы матрицы на 10; при этом цена игры увеличится в 10 раз, а решение не изменится. Получим матрицу:

Условия (5.5) имеют вид:

а условие минимума Φ = ξ 1 + ξ 2 + ξ 3 = min.

Проверяем, все ли три стратегии противника являются «полезными». В качестве гипотезы сначала предполагаем, что фиктивные переменные z 1 , z 2 , z 3 равны нулю, и для проверки решаем уравнения (5.10) относительно ξ 1 , ξ 2 , ξ 3:

(5.12) 136Φ = 30 +13z 1 +18z 2 – 51z 3

Формула (5.12) показывает, что увеличение переменных z 1 и z 2 по сравнению с их предполагаемым значением нуль может только увеличить Φ, тогда как увеличение z 3 может уменьшить Φ. Однако увеличение z 3 надо производить осторожно, чтобы величины ξ 1 , ξ 2 , ξ 3 , зависящие от z 3 , не стали при этом отрицательными. Поэтому положим в правых частях равенств (5.11) величины z 1 и z 2 равными нулю, а величину z 3 будем увеличивать до допустимых пределов (пока какая-нибудь из величин ξ 1 , ξ 2 , ξ 3 не обратится в нуль). Из второго равенства (5.11) видно, что увеличение z 3 «безопасно» для величины ξ 2 - она от этого только увеличивается. Что касается величин ξ 1 , и ξ 3 , то здесь увеличение z 3 возможно только до некоторого предела. Величина ξ 1 обращается в нуль при z 3 = 10/23; величина ξ 3 обращается в нуль раньше, уже при z 3 = 1/4. Следовательно, давая z 3 его максимально допустимое значение z 3 = 1/4, мы при этом обратим в нуль величину ξ 3 .

Чтобы проверить, обращается ли в минимум форма Φ при z 1 = 0, z 2 = 0, ξ 3 = 0, выразим остальные (не равные нулю) переменные через предположительно равные нулю z 1 , z 2 , ξ 3 . Разрешая уравнения (5.10) относительно ξ 1 , ξ 2 и z 3 , получим:

(5.13) 32Φ = 7 + Зz 1 + 4z 2 + ξ 3

Из формулы (5.13) видно, что любое увеличение z 1 , z 2 , ξ 3 сверх их предполагаемых нулевых значений может только увеличить форму Φ. Следовательно, решение игры найдено; оно определяется значениями z 1 = z 2 = ξ 3 = 0, откуда ξ 1 = 1/32, ξ 2 = 3/16, z 3 = 1/4. Подставляя в формулу (5.13), находим цену игры ν: 32Φ = 7 = 32/ν; ν = 32/7. Наша оптимальная стратегия: . «Полезные» стратегии (составы A 1 и A 2) должны применяться с частотами 1/7 и 6/7 ; состав A 3 - никогда не применяться.

Чтобы найти оптимальную стратегию противника, в общем случае можно поступать так: изменить знак выигрыша на обратный, прибавить к элементам матрицы постоянную величину L, чтобы сделать их неотрицательными, и решать задачу за противника так же, как мы решали ее за себя. Однако то, что нам уже известна цена игры ν, несколько упрощает задачу. К тому же в данном конкретном случае задача дополнительно упрощается тем, что в решении участвуют только две «полезные» стратегии противника В 1 и В 2 , так как величина z 3 не равна нулю, и, значит, при стратегии В 3 цена игры не достигается. Выбирая любую «полезную» стратегию игрока А, например A 1 можно найти частоты q 1 и q 2 . Для этого пишем уравнение 8q 1 + 2(1 – q 1) = 32/7, откуда q 1 = 3/7, q 2 = 4/7; оптимальная стратегия противника будет: , т.е. противник не должен пользоваться составом В 3 , а составы В 1 и В 2 должны применяться с частотами 3/7 и 4/7.

Возвращаясь к первоначальной матрице, определим истинную цену игры ν 0 = 32/7:10 = 0,457. Это значит, что при большом числе встреч число побед клуба А составит 0,457 всех встреч.

§ 6. Приближенные методы решения игр

Часто в практических задачах нет необходимости находить точное решение игры; достаточно найти приближенное решение, дающее средний выигрыш, близкий к цене игры. Ориентировочное знание цены игры ν может дать уже простой анализ матрицы и определение нижней (α) и верхней (β) цен игры. Если α и β близки, практически нет надобности заниматься поисками точного решения, а достаточно будет выбрать чистые минимаксные стратегии. В случаях, когда α и β не близки, можно получить приемлемое для практики решение с помощью численных методов решения игр, из которых мы вкратце осветим метод итераций.

Идея метода итераций сводится к следующему. Разыгрывается «мысленный эксперимент», в котором противники А и В применяют друг против друга свои стратегии. Эксперимент состоит из последовательности элементарных игр, каждая из которых имеет матрицу заданной игры. Начинается с того, что мы (игрок А) выбираем произвольно одну из своих стратегий, например А i . Противник на это отвечает той своей стратегией B j , которая наименее выгодна для нас, т.е. обращает выигрыш при стратегии А i в минимум. На этот ход мы отвечаем той своей стратегией А k , которая дает максимальный средний выигрыш при применении противником стратегии B j . Далее - снова очередь противника. Он отвечает на нашу пару ходов A i и А k той своей стратегией B j , которая дает нам наименьший средний выигрыш при этих двух стратегиях (A i , А к), и так далее. На каждом шаге итерационного процесса каждый игрок отвечает на любой ход другого игрока той своей стратегией, которая является оптимальной относительно всех его предыдущих ходов, рассматриваемых как некоторая смешанная стратегия, в которой чистые стратегии представлены в пропорциях, соответствующих частоте их применения.

Такой способ представляет собой как бы модель реального практического «обучения» игроков, когда каждый из них на опыте прощупывает способ поведения противника и старается отвечать на него выгодным для себя образом. Если такую имитацию процесса обучения продолжать достаточно долго, то средний выигрыш, приходящийся на одну пару ходов (элементарную игру), будет стремиться к цене игры, а частоты р 1 … р m ; q 1 … q n , с которыми встречаются стратегии игроков в этом розыгрыше, будут приближаться к частотам, определяющим оптимальные стратегии. Расчеты показывают, что сходимость метода очень медленная, однако для быстродействующих счетных машин это не является препятствием.

Проиллюстрируем применение итерационного метода на примере игры 3×3, решенной в примере 2 предыдущего параграфа. Игра задана матрицей:

В таблице 6.1 приведены первые 18 шагов итерационного процесса. В первом столбце дан номер элементарной игры (пары ходов) n ; во втором - номер i выбранной стратегии игрока А; в последующих трех - «накопленный выигрыш» за первые n игр при стратегиях противника B 1 , В 2 , В 3 . Минимальное из этих значений подчеркнуто. Далее идет номер j стратегии, выбранной противником, и соответственно накопленный выигрыш за n игр при стратегиях A 1 , А 2 , А 3 из этих значений подчеркнуто сверху максимальное. Подчеркнутые значения определяют выбор ответной стратегии другого игрока. В следующих графах последовательно приведены: минимальный средний выигрыш ν , равный минимальному накопленному выигрышу, деленному на число игр n ; максимальный средний выигрыш , равный максимальному накопленному выигрышу, деленному на n , и их среднее арифметическое ν* = (ν + )/2. При увеличении n все три величины ν , и ν* будут приближаться к цене игры ν, но величина ν*, естественно, будет приближаться к ней сравнительно быстрее.

Таблица 6.1.

Как видно из примера, сходимость итераций весьма медленная, но все же даже такой небольшой расчет дает возможность найти ориентировочное значение цены игры и выявить преобладание «полезных» стратегий. При пользовании счетными машинами ценность метода значительно увеличивается. Преимущество итерационного метода решения игр в том, что объем и сложность вычислений сравнительно слабо возрастают по мере увеличения числа стратегий m и n .

§ 7. Методы решения некоторых бесконечных игр

Бесконечной игрой называется игра, в которой по крайней мере одна из сторон имеет бесконечное множество стратегий. Общие методы решения таких игр еще мало разработаны. Однако для практики могут представлять интерес некоторые частные случаи, которые допускают сравнительно простое решение. Рассмотрим игру двух противников А и В, каждый из которых имеет бесконечное (несчетное) множество стратегий; эти стратегии для игрока А соответствуют различным значениям непрерывно меняющегося параметра х , а для В - параметра у . В данном случае вместо матрицы ‖a ij ‖ игру определяет некоторая функция двух непрерывно меняющихся аргументов а (х, у) , которую мы будем называть функцией выигрыша (заметим, что сама функция а (х, у) необязательно должна быть непрерывной). Функцию выигрыша а(х, у) можно представить геометрически некоторой поверхностью а (х, у) над областью изменения аргументов (х, у) (рис. 7.1)

Анализ функции выигрыша а(х, у) производится аналогично анализу платежной матрицы. Сначала находится нижняя цена игры α; для этого определяется для каждого х минимум функции а(х, у) по всем у : , затем ищется максимальное из этих значений по всем х (максимин):

Верхняя цена игры (минимакс) определяется аналогично:

Рассмотрим случай, когда α = β. Так как цена игры ν всегда заключена между α и β, то общее их значение и есть ν. Равенство α = β означает, что поверхность а(х, у) имеет седловую точку, т.е., такую точку с координатами х 0 , у 0 , в которой а(х, у) является одновременно минимальным по у и максимальным по х (рис. 7.2).

Значение а(х, у) в этой точке и есть цена игры ν: ν = а(х 0 , у 0). Наличие седловой точки означает, что данная бесконечная игра имеет решение в области чистых стратегий; х 0 , у 0 представляют собой оптимальные чистые стратегии А и В. В общем случае, когда α ≠ β, игра может иметь решение только в области смешанных стратегий (возможно, не единственное). Смешанная стратегия для бесконечных игр есть некоторое распределение вероятностей для стратегий х и у , рассматриваемых как случайные величины. Это распределение может быть непрерывным и определяться плотностями f 1 (х) и f 2 (у) ; может быть дискретным, и тогда оптимальные стратегии состоят из набора отдельных чистых стратегий, выбираемых с какими-то отличными от нуля вероятностями.

В случае, когда бесконечная игра не имеет седловой точки, можно дать наглядную геометрическую интерпретацию нижней и верхней цене игры. Рассмотрим бесконечную игру с функцией выигрыша а(х, у) и стратегиями х, у , заполняющими непрерывно отрезки осей (х 1 , х 2) и (у 1 , у 2) . Чтобы определить нижнюю цену игры α, нужно «посмотреть» на поверхность а(х, у) со стороны оси у , т.е. спроектировать ее на плоскость хОа (рис. 7.3). Получим некоторую фигуру, ограниченную с боков прямыми x = x 1 и х = х 2 , а сверху и снизу - кривыми К В и К Н. Нижняя цена игры α, очевидно, есть не что иное, как максимальная ордината кривой К Н.

Аналогично, чтобы найти верхнюю цену игры β, нужно «посмотреть» на поверхность а(х, у) со стороны оси х (спроектировать поверхность на плоскость уОа ) и найти минимальную ординату верхней границы К В проекции (рис, 7.4).

Рассмотрим два элементарных примера бесконечных игр.

Пример 1. Игроки А и В имеют каждый несчетное множество возможных стратегий х и у , причем 0 ≤ х ≤ 1; 0 ≤ у ≤ 1. Функция выигрыша за а дана выражением а (х, у) – (х – у) 2 . Найти решение игры.

Решение, Поверхность а(х, у) представляет собой параболический цилиндр (рис. 7.5) и не имеет седловой точки. Определим нижнюю цену игры; очевидно, для всех х ; отсюда = 0. Определим верхнюю цену игры. Для этого найдем при фиксированном у

В данном случае максимум достигается всегда на границе интервала (при х = 0 или х = 1), т.е. он равен той из величин у 2 ; (1 – у) 2 , которая больше. Изобразим графики этих функций (рис. 7.6), т.е. проекцию поверхности а(х, у) на плоскость уОа . Жирной линией на рис. 7.6 показана функция . Очевидно, ее минимальное значение достигается при у = 1/2 и равно 1/4. Следовательно, верхняя цена игры β = 1/4. В данном случае верхняя цена игры совпадает с ценой игры ν. Действительно, игрок А может применить смешанную стратегию S А =, в которую крайние значения х = 0 и х = 1 входят с одинаковыми частотами; тогда при любой стратегии у игрока В средний выигрыш игрока А будет равен: ½у 2 + ½(1 – у) 2 . Нетрудно убедиться, что эта величина при любых значениях у между 0 и 1 имеет значение не меньшее ¼: ½у 2 + ½(1 – у) 2 ≥ ¼.

Таким образом, игрок А применением данной смешанной стратегии может гарантировать себе выигрыш, равный верхней цене игры; так как цена игры не может быть больше верхней цены, то данная стратегия S A оптимальная: S A = S A *.

Остается найти оптимальную стратегию игрока В. Очевидно, что если цена игры ν равна верхней цене игры β, то оптимальной стратегией игрока В будет всегда его чистая минимаксная стратегия, гарантирующая ему верхнюю цену игры. В данном случае такой стратегией является у 0 = ½. Действительно, при этой стратегии, что бы ни делал игрок А, выигрыш его не будет больше ¼. Это следует из очевидного неравенства (x – ½) 2 = x(x –1) + ¼ ≤ ¼

Пример 2. Сторона А («мы») ведет стрельбу по самолету В противника. Для того чтобы уклониться от обстрела, противник может маневрировать с некоторой перегрузкой у , которой он по своему усмотрению может придавать значения от у = 0 (прямолинейное движение) до у = у max (полет по окружности максимальной кривизны). Будем считать у max единицей измерения, т.е. положим у max = 1. В борьбе с противником мы можем применять прицельные приспособления, основанные на той или иной гипотезе о движении цели за время полета снаряда. Перегрузка х при этом гипотетическом маневре может полагаться равной любому значению от 0 до 1. Наша задача - поразить противника; задача противника - остаться непораженным. Вероятность поражения для данных х и у приближенно выражается формулой: а(х, у) = , где у - перегрузка, применяемая противником; х - перегрузка, учтенная в прицеле. Требуется определить оптимальные стратегии обеих сторон.

Решение. Очевидно, решение игры не изменится, если мы положим р = 1. Функция выигрыша а(х, у) изображается поверхностью, представленной на рис. 7.7.

Это - цилиндрическая поверхность, образующие которой параллельны биссектрисе координатного угла хОу , а сечение плоскостью, перпендикулярной к образующей, есть кривая типа нормальной кривой распределения. Пользуясь предложенной выше геометрической интерпретацией нижней и верхней цены игры, находим β = 1 (рис. 7.8) и (рис. 7.9). Игра не имеет седловой точки; решение нужно искать в области смешанных стратегий. Задача до некоторой степени аналогична задаче предыдущего примера. Действительно, при малых значениях k функция ведет себя примерно как функция –(х – у) 2 , и решение игры получится, если в решении предыдущего примера поменять ролями игроков A и В; т.е. нашей оптимальной стратегией будет чистая стратегия х = 1/2, а оптимальная стратегия противника S B = будет состоять в том, чтобы с одинаковыми частотами применять крайние стратегии у = 0 и y = 1. Это значит, что мы должны во всех случаях применять прицел, рассчитанный на перегрузку x = 1/2, а противник должен в половине всех случаев вообще не применять маневра, а в половине - максимально возможный маневр.

Рис. 7.8 Рис. 7.9.

Легко доказать, что это решение будет справедливо для значений k ≤ 2. Действительно, средний выигрыш при стратегии противника S B = и при нашей стратегии х выражается функцией , которая для значений k ≤ 2 имеет один максимум при х = 1/2, равный нижней цене игры α. Следовательно, применение стратегии S B гарантирует противнику проигрыш, не больший α, из чего ясно, что α - нижняя цена игры - и есть цена игры ν.

При k > 2 функция а(х) имеет два максимума (рис. 7.10), расположенные симметрично относительно х = 1/2 в точках x 0 и 1 – х 0 , причем значение х 0 зависит от k.

Очевидно, при k = 2 х 0 = 1 – x 0 = ½; при увеличении k точки х 0 и 1 – х 0 раздвигаются, подходя ближе к крайним точкам (0 и 1). Следовательно, решение игры будет зависеть от k. Зададим конкретное значение k, например k = 3, и найдем решение игры; для этого определим абсциссу х 0 максимума кривой а(х). Приравнивая нулю производную функции а(х), напишем уравнение для определения x 0:

Это уравнение имеет три корня: х = 1/2 (где достигается минимум) и х 0 , 1 – х 0 , где достигаются максимумы. Решая уравнение численно, находим приближенно x 0 ≈ 0,07; 1 – x 0 ≈ 0,93.

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

При нашей стратегии и стратегии противника у средний выигрыш равен

Найдем минимум a 1 (y) при 0 < у < 1. Функция a 1 (y) симметрична относительно y = 1/2 и может иметь только один или два максимума; ее минимум, во всяком случае, достигается либо в середине отрезка (0, 1), либо на его концах. Полагая у = 0 (или у = 1), найдем

Полагая у = 1/2, получаем

что больше, чем a 1 (0); следовательно, цена игры не меньше, чем а 1 (0):

Теперь допустим, что противник применяет стратегию S B *, а мы-стратегию х. Тогда средний выигрыш будет

Но мы выбрали х 0 именно так, чтобы при х = х 0 достигался максимум выражения (7.2); следовательно,

т.е. противник применением стратегии S B * может не допустить проигрыша, большего 0,530; следовательно, ν = 0,530 и есть цена игры, а стратегии S A * и S B * дают решение. Это значит, что мы должны с одинаковой частотой пользоваться прицелами с х = 0,07 и x = 0,93, а противник с одинаковой частотой не маневрировать и маневрировать с максимальной перегрузкой.

Заметим, что выигрыш ν = 0,530 заметно больше, чем нижняя цена игры , которую мы могли бы обеспечить себе, применяя свою максиминную стратегию х 0 = 1/2.

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

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

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

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

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

"Теория игр изучает то, каким образом двое или более игроков выбирают отдельные действия или целые стратегии. Название этой теории настраивает на несколько отвлеченный лад, поскольку оно ассоциируется с игрой в шахматы и бридж или с ведением войн. На самом деле выводы этой дисциплины весьма глубоки. Теория игр была разработана выходцем из Венгрии, гениальным математиком Джоном фон Нейманом (1903-1957). Эта теория сравнительно молодая математическая дисциплина.

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

Равновесие совершенно конкурентного рынка также является равновесием по Нэшу, или некооперативным равновесием, при котором каждая фирма и каждый потребитель принимают решения исходя из уже существующих цен как не зависящих от его воли. Мы уже знаем, что в условиях, когда каждая фирма стремится максимизировать прибыль, а каждый потребитель - полезность, равновесие возникает, когда цены равны предельным издержкам, а прибыль - нулю. " Мамаева Л.Н. Институциональная экономика: Курс лекций - М.: Издательско-торговая корпорация «Дашков и К», 2012. - 200 с.

Вспомним концепцию "невидимой руки" Адама Смита: "Преследуя собственные интересы, он (индивид) часто в большей степени способствует процветанию общества, чем если бы он к этому сознательно стремился" Смит А. Исследование о природе и причинах богатства народов // Антология экономической классики. - М.: Эконов-ключ, 19931. Парадокс "невидимой руки" заключается в том, что, хотя каждый и действует как самостоятельная сила, в конечном итоге общество остается в выигрыше. При этом конкурентное равновесие является равновесием по Нэшу еще и в том смысле, что ни у кого нет повода изменять свою стратегию, если и все остальные придерживаются своей. В условиях совершенно конкурентной экономики некооперативное поведение является экономически эффективным с точки зрения интересов общества.

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

Однако во многих случаях некооперативное поведение приводит к экономической неэффективности или даже представляет угрозу для общества (например, гонка вооружений). Некооперативное поведение как со стороны США, так и со стороны СССР заставляло обе стороны вкладывать огромные средства в военную область и привело к созданию арсенала, состоящего из почти 100000 ядерных боеголовок. Существует также опасение, что чрезмерная доступность оружия в Америке может стать причиной своего рода внутренней гонки вооружений. Одни люди вооружают себя против других - и этот "бег наперегонки" может продолжаться до бесконечности. Здесь в действие вступает вполне "видимая рука", направляющая это разрушительное состязание и не имеющая ничего общего с "невидимой рукой" Адама Смита. Еще один важный экономический пример - "игры в загрязнения" (окружающей среды). Здесь объектом нашего внимания станет такой вид побочных эффектов, как загрязнение. Если бы фирмы никогда и никого не спрашивали о том, как им поступить, любая из них скорее предпочла бы создавать загрязнения, чем устанавливать дорогостоящие очистители. Если же какая-нибудь фирма из благородных побуждений решилась бы уменьшить вредные выбросы, то издержки, а следовательно, и цены на ее продукцию, возросли бы, а спрос упал. Вполне возможно, эта фирма просто обанкротилась бы. Живущие в жестоком мире естественного отбора, фирмы скорее предпочтут оставаться в условиях равновесия по Нэшу Ни одной фирме не удастся повысить прибыль, уменьшая загрязнение.

Вступив в смертоносную экономическую игру, каждая неконтролируемая государством и максимизирующая прибыль сталелитейная фирма будет производить загрязнения воды и воздуха. Если какая-либо фирма попытается очищать свои выбросы, то тем самым она будет вынуждена повысить цены и потерпеть убытки. Некооперативное поведение установит равновесие по Нэшу в условиях высоких выбросов. Правительство может предпринять меры, с тем чтобы равновесие переместилось. В этом положении загрязнение будет незначительным, прибыли же останутся теми же. Мамаева Л.Н. Институциональная экономика: Курс лекций - М.: Издательско-торговая корпорация «Дашков и К», 2012. - 203 с.

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

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

Можно попытаться объяснить этот синдром с точки зрения теории игр. Стало привычным в современной экономике разделять данные разновидности политики. Центральный банк Америки - Федеральная резервная система - определяет независимо от правительства денежно-кредитную политику, назначая процентные ставки. Налогово-бюджетной политикой, налогами и расходами - заведуют законодательные и исполнительные власти. Однако каждый из этих видов политики имеет разные цели. Центральный банк стремится ограничить рост предложения денег и обеспечить низкие темпы инфляции.

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

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

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

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

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

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

Нормальная форма игры двух участников состоит из двух платежных матриц, показывающих, какую сумму получит каждый из игроков при любой из возможных пар стратегий. Обычно эти матрицы выражают в форме единой матрицы, которую называют биматрицей. Элементами биматрицы являются пары чисел, первое из которых определяет величину выигрыша первого игрока, а второе - величину выигрыша второго. Первый игрок (государство) выбирает одну из m стратегий, при этом каждой стратегии соответствует строка матрицы I (i= 1,…,m). Второй игрок (бизнес) выбирает одну из n стратегий, при этом каждой стратегии соответствует столбец матрицы j (j= 1,…,n). Пара чисел на пересечении строки и столбца, которые соответствуют стратегиям, выбранным игроками, показывает величину выигрыша каждого из них. В общем случае, если игрок I выбирает стратегию i а игрок II - стратегию j, то выигрыши первого и второго игроков соответственно равны и (i= 1,…,m; j= 1,…,n), где m,n - число конечных стратегий соответственно игроков I и II. Предполагается, что каждому из игроков известны все элементы биматрицы выигрышей. В этом случае их стратегия называется определенной и имеет конечное число вариантов.

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

Существуют и другие классы игр, где игроки выигрывают и проигрывают одновременно.

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

В качестве примера рассмотрим игру, в которой участвуют два игрока, каждый из них имеет по две стратегии. Выигрыши каждого из игроков определяются такими правилами: если оба игрока выбирают стратегии с одинаковыми номерами (игрок I - , игрок II -), то первый игрок выигрывает, а второй проигрывает (государство повышает налоги - бизнес платит их, т.е. выигрыш государства определяет проигрыш бизнеса); если оба игрока выбирают разные стратегии (игрок I - і 1 игрок II - j 2 то первый проигрывает, а второй выигрывает (государство повышает налоги на бизнес - бизнес уклоняется от них; проигрыш государства - выигрыш бизнеса).

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

Можно выделить несколько способов (путей) наложения ограничений.

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

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

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

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

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

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

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

Конечные антагонистические игры в нормальной форме называются матричными. Это название объясняется возможностью следующей интерпретации игр такого типа. Будем понимать стратегии первого игрока (игрок I - государство) как строки некоторой матрицы, а стратегии второго игрока (игрок II - бизнес) - как ее столбцы. Для краткости стратегиями игроков называют не сами строки или столбцы матрицы, а их номера. Тогда ситуациями игры оказываются клетки этой матрицы, стоящие на пересечениях каждой строки с каждым из столбцов. Заполнив эти клетки-ситуации числами, описывающими выигрыши игрока I в этих ситуациях, мы завершим задание игры. Полученная матрица называется матрицей выигрыша игры, или матрицей игры. Ввиду антагонистичности матричной игры выигрыш игрока II в каждой ситуации вполне определяется выигрышем игрока I в этой ситуации, отличаясь от него только знаком. Поэтому дополнительных указаний о функции выигрыша игрока II в матричной игре не требуется.

Матрицу, имеющую m строк и n столбцов, называют (m*n) - матрицей, а игру с этой матрицей - (m*n) - игрой.

Процесс (m*n) - игры с матрицей можно представить следующим образом:

Игрок I фиксирует номер строки i, а игрок II - номер столбца j, после чего первый игрок получает от своего противника сумму

Целью игрока I в матричной игре является получение максимального выигрыша, цель игрока II состоит в том, чтобы дать игроку I минимальный выигрыш.

Пусть игрок I (государство) выбирает некоторую свою стратегию i. Тогда в наихудшем случае он получит выигрыш min . В теории игр игроки предполагаются осторожными, рассчитывающими на наименее благоприятный для себя поворот событий.

Такое наименее благоприятное для игрока I положение дел может наступить, например, в том случае, когда стратегия i станет известной игроку II (бизнес). Предвидя такую возможность, игрок I должен выбирать свою стратегию так, чтобы максимизировать этот минимальный выигрыш:

min = max min (I)

Значение, стоящее в правой части равенства, является гарантированным выигрышем игрока I. Игрок II (бизнес) должен выбрать такую стратегию, что

max = min max (II)

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

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

У игроков могут быть дополнительные возможности - выбор своих стратегий случайно и независимо друг от друга (стратегии соответствуют строкам и столбцам матрицы). Случайный выбор игроком своих стратегий называется смешанной стра тегии этого игрока. В (m*n) - игрё смешанные стратегии игрока I определяются наборами вероятностей: X = (,…), с которыми этот игрок выбирает свои первоначальные, чистые стратегии.

В основе теории матричных игр лежит теорема Неймана активных стратегиях: "Если один из игроков придерживается своей оптимальной стратегии, то выигрыш остается неизменным и равным цене игры независимо от того, что делает другой игрок, если он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях" Neumann J. Contributions to the theory of games. 1995.. - 155 с.). Отметим, что активной называется чистая стратегия игрока, входящая в его оптимальную смешанную стратегию с отличной от нуля вероятностью.

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

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

Для играющего в матричную игру субъекта характерны следующие качества:

элементы матрицы интерпретируются как денежные платежи и соответственно их выигрыш и проигрыш оцениваются в денежной форме;

каждый из игроков применяет к этим элементам функцию полезности;

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

Эти предположения приводят к играм с нулевой суммой, в которых возникают отношения кооперирования, торгов и другого типа взаимодействий между игроками как до начала игры, так и в ее процессе. Мамаева Л.Н. Институциональная экономика: Курс лекций - М.: Издательско-торговая корпорация «Дашков и К», 2012. - 210 - 211с.

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

Рассмотрим это на следующем примере. Пусть первый игрок к моменту начала игры G обладает капиталом в x долларов. Тогда его капитал в конце игры будет равен + x, где - получаемый им от игры фактический выигрыш. Полезность, которую он приписывает такому исходу, равна f (+ х), где f - функция полезности.

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