Теория игр в повседневной жизни. С полной или неполной информацией. Список использованной литературы стр.24

Забавный пример применения теории игр есть в фэнтезийной книжке Энтони Пирса «Бравый голем»

Много текста

– Смысл того, что я сейчас вам всем продемонстрирую, – начал Гранди, – заключается в наборе необходимого количества баллов. Баллы могут быть самыми различными – все зависит от комбинации решений, которые принимаются участниками игры. К примеру, предположим, что каждый участник свидетельствует против своего товарища по игре. В этом случае каждому участнику можно присудить по одному очку!
– Одно очко! – сказала Морская Ведьма, проявляя к игре неожиданный интерес. Очевидно, колдунья хотела удостовериться в том, что у голема нет никаких шансов, чтобы демон Ксант остался им доволен.
– А теперь давайте предположим, что каждый из участников игры не свидетельствует против своего товарища! – продолжал Гранди. – В этом случае каждому можно присудить по три балла. Я хочу особенно отметить, что покуда все участники действуют одинаково, то им присуждается одинаковое количество баллов. Ни у кого нет никаких преимуществ перед другим.
– Три очка! – сказала вторая ведьма.
– Но вот теперь мы вправе предложить, что один из игроков начал давать показания против второго, а второй все равно молчит! – сказал Гранди. – В таком случае тот, кто эти показания дает, получает сразу пять очков, а тот, который молчит, не получает ни одного очка!
– Ага! – в один голос воскликнули обе ведьмы, хищно облизывая губы. Было видно, что обе они явно собирались получить по пять очков.
– Я все время терял очки! – воскликнул демон. – Но ведь ты пока только обрисовал ситуацию, а способа ее разрешения еще не представил! Так в чем заключается твоя стратегия? Не надо тянуть время!
– Погоди, сейчас я все объясню! – воскликнул Гранди. – Каждый из нас четверых – нас тут двое големов и две ведьмы – будет сражаться против своих противников. Конечно же, ведьмы постараются никому ни в чем не уступить…
– Конечно! – воскликнули снова обе ведьмы в унисон. Они отлично понимали голема с полуслова!
– А второй голем будет следовать моей тактике, – продолжал Гранди невозмутимо. Он посмотрел на своего двойника. – Ты, конечно, в курсе?
– Да, конечно! Я ведь твоя копия! Я прекрасно все понимаю, что ты думаешь!
– Вот и отлично! В таком случае, давайте-ка сделаем первый ход, чтобы демон смог сам все увидеть. В каждом поединке будет несколько раундов, чтобы вся стратегия смогла проявиться до конца и произвела впечатление целостной системы. Пожалуй, мне следует начать.

– Теперь каждый из нас должен наносить отметки на своих листках бумаги! – обратился голем к ведьме. – Сначала следует нарисовать улыбающееся лицо. Это будет означать, что мы не будем давать показания на товарища по заключению. Можно также нарисовать насупленное лицо, которое означает, что мы думаем только о себе и нужные показания на своего товарища даем. Мы оба сознаем, что лучше было бы, если бы никто не оказался тем самым насупленным лицом, но ведь, с другой стороны, насупленное лицо получает определенные преимущества перед улыбающимся! Но суть заключается в том, что каждый из нас не знает, что выберет другой! Не будем знать до тех пор, покуда партнер по игре не откроет своего рисунка!
– Начинай ты, сволочь! – выругалась ведьма. Она, как всегда, не могла обойтись без бранных эпитетов!
– Готово! – воскликнул Гранди, нарисовав большое улыбающееся лицо на своем листочке бумаги таким образом, чтобы ведьма не смогла увидеть, что он изобразил там. Ведьма сделала свой ход, тоже изобразив лицо. Надо думать, она непременно изобразила недобрую физиономию!
– Ну, а теперь нам остается только показать друг другу наши рисунки, – объявил Гранди. Обернувшись назад, он открыл рисунок публике и показал его во все стороны, чтобы рисунок смогли увидеть все. Что-то недовольно ворча, то же самое сделала и Морская Ведьма.
Как Гранди и рассчитывал, с рисунка колдуньи смотрело злое, недовольное лицо.
– Теперь вы, уважаемые зрители, – сказал Гранди торжественно, – видите, что ведьма предпочла давать на меня показания. Я не собираюсь этого делать. Таким образом, Морская Ведьма набирает пять очков. А я, соответственно, не получаю ни одного балла. И тут…
По рядам зрителей снова прокатился легкий шумок. Все явно сочувствовали голему и страстно желали, чтобы Морская Ведьма проиграла.
Но ведь игра только-только началась! Если только его стратегия была верной…
– Теперь мы можем перейти ко второму раунду! – объявил Гранди торжественно. – Мы снова должны повторить ходы. Каждый рисует лицо, которое ему ближе!
Так и сделали. Гранди изображал теперь хмурое, недовольное лицо.
Как только игроки показали свои рисунки, публика увидела, что теперь оба они изобразили злые лица.
– По два очка каждому! – сказал Гранди.
– Семь два в мою пользу! – заорала ведьма радостно. – Ты никуда отсюда не выберешься, мерзавец!
– Начинаем снова! – воскликнул Гранди. Они сделали по очередному рисунку и показали их публике. Снова те же самые злые лица.
– Каждый из нас повторил предыдущий ход, повел себя эгоистично, а потому, как мне кажется, лучше никому не присуждать очков! – заявил голем.
– Но я все равно веду в игре! – сказала ведьма, радостно потирая руки.
– Ладно, не шуми! – сказал Гранди. – Игра ведь не закончилась. Посмотрим, что будет! Итак, уважаемая публика, мы начинаем четвертый по счету раунд!
Игроки снова сделали рисунки, показав публике то, что они изобразили на своих листках. Оба листка снова явили зрителям те же злые физиономии.
– Восемь – три! – закричала ведьма, заливаясь злобным смехом. – Своей дурацкой стратегией ты выкопал себе могилу, голем!
– Пятый раунд! – закричал Гранди. Повторилось то же самое, что и в прежние раунды, – снова злые лица, только счет изменился – он стал девять – четыре в пользу колдуньи.
– Теперь последний, шестой раунд! – возвестил Гранди. Его предварительные расчеты показывали, что именно этот раунд должен стать судьбоносным. Теперь теория должна была подтвердиться либо быть опровергнута практикой.
Несколько быстрых и нервных движений карандаша по бумаге – и оба рисунка предстали перед глазами публики. Снова два лица, теперь даже с оскаленными зубами!
– Десять – пять в мою пользу! Моя игра! Я победила! – загоготала Морская Ведьма.

– Ты действительно выиграла, – согласился Гранди мрачно. Аудитория зловеще молчала.
Демон шевельнул было губами, чтобы что-то сказать.

– Но наше состязание еще не закончено! – крикнул звонко Гранди. – Это ведь была только первая часть игры.
– Да вам целую вечность подавай! – заворчал демон Ксант недовольно.
– Это верно! – сказал Гранди спокойно. – Но ведь один тур ничего не решает, только методичность указывает на лучший результат.
Теперь голем подошел к другой ведьме.
– Я хотел бы сыграть этот тур с другим противником! – объявил он. – Каждый из нас будет изображать лица, как это было в предыдущий раз, потом будет демонстрировать нарисованное публике!
Так они и сделали. Результат был таким же, как и в прошлый раз – Гранди нарисовал улыбающуюся рожицу, а ведьма – так вообще череп. Она сразу набрала преимущество в целых пять баллов, оставив Гранди позади.
Оставшиеся пять раундов окончились с теми результатами, которых и можно было ожидать. Снова счет стал десять – пять в пользу Морской Ведьмы.
– Голем, мне очень нравится твоя стратегия! – хохотала колдунья.
– Итак, вы просмотрели два тура игры, уважаемые зрители! – воскликнул Гранди. – Я, таким образом, набрал десять очков, а мои соперницы – двадцать!
Публика, которая тоже вела подсчет очков, скорбно закивала головами. Их подсчет совпал с подсчетами голема. Только облако по имени Фракто казалось весьма довольным, хотя, конечно, ведьме оно тоже не симпатизировало.
Но Рапунцелия одобряюще улыбнулась голему – она продолжала верить в него. Она, возможно, осталась единственной, кто верил ему теперь. Гранди надеялся, что он оправдает это безграничное доверие.
Теперь Гранди подошел к своему третьему сопернику – своему двойнику. Он должен был стать его последним противником. Быстро чиркнув карандашами по бумаге, големы показали листочки публике. Все увидели две смеющихся рожицы.
– Заметьте, дорогие зрители, каждый из нас предпочел быть добрым сокамерником! – воскликнул Гранди. – А посему никто из нас не получил в этой игре необходимого преимущества перед соперником. Таким образом, мы оба получаем по три балла и приступаем к следующему раунду!
Второй раунд начался. Результат был тот же, что и в предыдущий раз. Затем оставшиеся раунды. И в каждый раунд оба противника набирали опять по три балла! Это было просто невероятно, но публика была готова подтвердить все происходящее.

Наконец и этот тур подошел к концу, и Гранди, быстро водя своим карандашиком по бумаге, стал подсчитывать результат. Наконец он объявил торжественно:
– Восемнадцать на восемнадцать! В общей сложности я набрал двадцать восемь очков, а мои соперники набрали тридцать восемь!
– Значит, ты проиграл, – возвестила Морская Ведьма радостно. – Победителем станет, таким образом, кто-то из нас!
– Возможно! – спокойно отозвался Гранди. Теперь наступал еще один важный момент. Если все пройдет так, как им и было задумано…
– Нужно довести дело до конца! – воскликнул второй голем. – Мне ведь тоже еще нужно сразиться с двумя Морскими Ведьмами! Игра еще не закончена!
– Да, конечно, давай! – сказал Гранди. – Но только руководствуйся стратегией!
– Да, конечно! – заверил его двойник.
Этот голем подошел к одной из ведьм, и тур начался. Завершился он с тем же результатом, с которым из подобного раунда вышел сам Гранди – счет был десять-пять в пользу колдуньи. Ведьма прямо-таки сияла от невыразимой радости, а публика угрюмо замолчала. Демон Ксант выглядел несколько уставшим, что было не слишком добрым предзнаменованием.
Теперь пришло время заключительного раунда – одна ведьма должна была сражаться против второй. Каждая имела в активе по двадцать очков, которые она смогла получить, сражаясь с големами.
– А теперь, если ты позволишь набрать мне хотя бы несколько лишних очков… – заговорщицки прошептала Морская Ведьма своему двойнику.
Гранди старался сохранить спокойствие хотя бы внешне, хотя в душе его бушевал ураган противоречивых чувств. Его удача сейчас зависела от того, насколько верно он предугадал возможное поведение обеих ведьм – ведь характер их был, в сущности, одним и тем же!
Сейчас наступал самый, пожалуй, критический момент. Но если он ошибся!
– С какой это стати я должна тебе уступать! – прокаркала вторая ведьма первой. – Я сама хочу набрать больше очков и выбраться отсюда!
– Ну, если ты так нахально ведешь себя, – завопила претендентка, – то я тебя сейчас отделаю так, что ты больше не будешь похожа на меня!
Ведьмы, одарив друг друга ненавидящими взглядами, начертили свои рисунки и показали их публике. Конечно же, ничего другого, кроме двух черепов, там оказаться просто не могло! Каждая набрала по одному очку.
Ведьмы, осыпая друг друга проклятьями, приступили ко второму раунду. Результат опять тот же самый – снова два коряво нарисованных черепа. Ведьмы, таким образом, набрали еще по одному очку. Публика старательно все фиксировала.
Так продолжалось и в дальнейшем. Когда тур закончился, усталые ведьмы обнаружили, что каждая из них набрала по шесть очков. Снова ничья!
– Теперь давайте подсчитаем получившиеся результаты и все сравним! – торжествующе сказал Гранди. – Каждая из ведьм набрала по двадцать шесть очков, а големы набрали по двадцать восемь баллов. Итак, что мы имеем? А имеем мы тот результат, что големы имеют большее количество очков!
По рядам зрителей прокатился вздох удивления. Взволнованные зрители стали писать на своих листочках столбики цифр, проверяя правильность подсчета. Многие за это время просто не считали количество набранных баллов, считая, что результат игры им уже известен. Обе ведьмы стали рычать от негодования, непонятно, кого именно обвиняя в происшедшем. Глаза демона Ксанта вновь загорелись настороженным огнем. Его доверие оправдалось!
– Я прошу вас, уважаемая публика, обратить внимание на тот факт, – поднял руку Гранди, требуя от зрителей успокоиться, – что ни один из големов не выиграл ни единого раунда. Но окончательная победа все-таки будет за одним из нас, из големов. Результаты будут более красноречивыми, если состязание продолжится и дальше! Я хочу сказать, дорогие мои зрители, что в вечном поединке моя стратегия будет неизменно оказываться выигрышной!
Демон Ксант с интересом прислушивался к тому, что говорил Гранди. Наконец он, испуская клубы пара, открыл рот:
– А в чем конкретно заключается твоя стратегия?
– Я называю ее «Быть твердым, но честным»! – пояснил Гранди. – Я начинаю игру честно, но затем начинаю проигрывать, потому что мне попадаются очень специфические партнеры. Поэтому в первом раунде, когда оказывается, что Морская Ведьма начинает давать против меня показания, я автоматически остаюсь проигравшим и во втором раунде – и так продолжается до конца. Результат может быть другим, ежели ведьма переменит свою тактику ведения игры. Но поскольку ей такое даже в голову прийти не может, мы продолжали играть по предыдущему шаблону. Когда я начал играть со своим двойником, то он хорошо отнесся ко мне, а я хорошо относился к нему в следующем раунде игры. Поэтому игра у нас пошла тоже по-другому и несколько однообразно, поскольку мы не хотели изменять тактику…
– Но ведь вы не выиграли ни единого тура! – удивленно возразил демон.
– Да, а эти ведьмы не проиграли ни одного тура! – подтвердил Гранди. – Но ведь победа не автоматически достается тому, за кем остались туры. Победа достается тому, кто набрал большее количество баллов, а это совсем другое дело! Мне удалось набрать больше очков, когда мы играли вместе с моим двойником, чем когда я играл с ведьмами. Их эгоистическое отношение принесло им сиюминутную победу, но в плане более долгосрочном оказалось, что именно из-за этого обе они проиграли игру целиком. Часто случается и такое!

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

Елена Вентцель. Элементы теории игр. – М.: Физматгиз, 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 рубль. Если оба назвали одно и то же число, игра заканчивается вничью. Игра, очевидно, не может иметь решения. Однако существуют классы бесконечных игр, для которых решение заведомо существует.

экспериментальной экономики

И других методов анализа

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

Теория игр . Теория игр – аналитический метод, получивший развитие после второй мировой войны и используемый для анализа ситуаций, в которых индивидуумы стратегически взаимодействуют. Шахматы – это прототип стратегической игры, так как результат зависит от поведения противника, так же как и от поведения собственно игрока. Из-за аналогий, найденных между стратегическими играми и формами политического и экономического взаимодействия, теории игр уделяется повышенное внимание в общественных науках. Современная теория игр начинается с работы Д. Неймана и О. Моргенштерна «Теория игр и экономическое поведение» (1944, русский вариант – 1970). Теория исследует взаимодействие индивидуальных решений при некоторых допущениях, касающихся принятия решения в условиях риска, общего состояния окружающей среды, кооперативного или некооперативного поведения других индивидов. Очевидно, что рациональному индивиду приходится принимать решения в условиях неопределенности и взаимодействия. Если выигрыш одного индивида является проигрышем другого, то это игра с нулевой суммой. Когда каждый из индивидов может выиграть от решения одного из них, то имеет место игра с ненулевой суммой. Игра может быть кооперативной, когда возможен сговор, и некооперативной, когда преобладает антагонизм. Одним из известных примеров игры с ненулевой суммой является дилемма заключенного (ДЗ). Этот пример показывает, что, вопреки утверждениям либерализма, преследование индивидом собственного интереса ведет к решению менее удовлетворительному, чем возможные альтернативы.

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

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

В данном контексте достаточно рассмотреть это понятие применительно к теоретико-игровой модели двух лиц 25 . В этой модели каждый из участников располагает некоторым непустым множеством стратегий S i , i = 1, 2. При этом выбор конкретных стратегий из числа доступных игроку осуществляется таким образом, чтобы максимизировать значение собственной функции выигрыша (полезности) u i , i = 1, 2. Значения функции выигрыша заданы на множестве упорядоченных пар стратегий игроков S 1 ´ S 2 , элементами которого выступают всевозможные сочетания стратегий игроков (s 1 , s 2) (упорядоченность пар стратегий заключается в том, что в каждом из сочетаний на первом месте стоит стратегия первого игрока, на втором – второго), т.е. u i = u i (s 1 , s 2), i = 1, 2. Иными словами, выигрыш каждого игрока зависит не только от выбираемой им самим стратегии, но и от стратегии, принятой его противником.

Оптимальным по Нэшу решением признается пара стратегий (s 1 *, s 2 *), s i *Î S i , i = 1, 2, обладающая следующим свойством: стратегия s 1 * обеспечивает игроку 1 максимальный выигрыш, когда игрок 2 выбирает стратегию s 2 *, и симметрично s 2 * доставляет максимальное значение функции выигрыша игрока 2 , когда игроком 1 принимается стратегия s 1 *. Пара стратегий приводит к равновесию по Нэшу, если выбор, сделанный игроком 1 , оптимален при данном выборе игрока 2 , а выбор, сделанный игроком 2, оптимален при данном выборе игрока 1 . Понятие оптимальности по Нэшу очевидным образом обобщается на случай игры n лиц. Следует заметить, что существование равновесия по Нэшу не означает его Парето-оптимальности, а Парето-оптимальный набор стратегий не обязательно должен удовлетворять равновесию по Нэшу. В 1994 г. Дж. Ф. Нэшу, Р. Зельтену и Дж. Ч. Харшани была присуждена Премия памяти А. Нобеля по экономике за их вклад в разработку теории игр и ее приложение к экономике.

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

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

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

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

Обобщенная проблема координации существует, если матрица выигрышей такова, что в любой точке равновесия никто из игроков не имеет стимула изменить свое поведение при данном поведении других игроков, но и никто из игроков не желает, чтобы какой-либо другой игрок изменил его. В этом случае каждый предпочел бы скоординированный результат не скоординированному, но, возможно, каждый захочет предпочесть особый скоординированный результат (рис. 2.2). Например, два производителяА и Б используют различную технологию X и Y , но хотят ввести национальный стандарт изделия, который вызовет сетевые внешние эффекты. Производитель А больше выиграет, если стандартом станет технология Х , а производитель Б – технология Y . Выигрыш оказывается распределенным асимметрично. Итак, производитель А (Б ) предпочтет, чтобы стандартом стала X (Y )-технология, но оба предпочтут любой из скоординированных результатов не скоординированному. Трансакционные издержки в этой модели будут выше, чем в предыдущей (особенно при участии большого количества сторон), так как налицо столкновение интересов. Замена частных попыток координации государственным вмешательством позволила бы уменьшить трансакционные издержки в экономике. Примерами являются государственное введение технологических стандартов, стандартов измерения и качества и т.д. Обобщенная координационная модель иллюстрирует важность не только координационной функции институтов, но и распределительной, от которой зависит способ, ограничивающий возможные альтернативы игроков, и в конечном счете результативность взаимодействия.

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

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

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

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

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

Рассмотрим матрицу выигрышей в ДЗ, анализируемую Р. Аксельродом 27 (рис. 2.3). Независимо от того, что делает другой игрок, предательство дает более высокое вознаграждение, чем кооперация. Если первый игрок думает, что другой игрок будет молчать, то ему выгоднее предать ($5>$3). С другой стороны, если первый игрок думает, что другой предаст, ему все равно выгоднее предать самому ($1 лучше, чем ничего). Следовательно, искушение склоняет к предательству. Но если оба предают, то оба получают меньше, чем в ситуации кооперации ($1+$1<$3+$3).

Рис. 2.3 . Матрица выигрышей в дилемме заключенного

Дилемма заключенного – знаменитая проблема в экономике – показывает: то, что рационально или оптимально для одного агента, может не быть рациональным или оптимальным для группы индивидов, рассматриваемых совместно. Эгоистичное поведение индивида может быть вредным или разрушительным для группы. В повторяющихся играх ДЗ соответствующая стратегия неочевидна. Чтобы найти хорошую стратегию, и были организованы турниры. Если выигрыш был бы получен строго на основе победа–проигрыш, то каждый участник турнира должен был предложить непрерывное отступничество. Однако правила выигрыша дали понять, что организация некоторой кооперации могла бы привести к более высоким общим результатам. К удивлению многих, победила простая стратегия «зуб за зуб», предложенная А. Рапопортом: игрок кооперируется на первом шаге и затем делает тот ход, который другой игрок делал на предыдущем шаге.

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

Анализ результатов турниров выявил четыре свойства, приводящие к успешной стратегии: 1) стремление избежать ненужного конфликта и кооперироваться так долго, как это делает другой; 2) способность к вызову перед лицом ничем не вызванного предательства другого; 3) прощение после ответа на вызов; 4) ясность поведения, чтобы другой игрок мог распознать и адаптироваться к образу действия первого.

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

Теория игр может быть важным инструментом для изучения человеческого взаимодействия в ограниченных правилами обстоятельствах. Благодаря своим возможностям изучать последствия разных институциональных соглашений она также может быть полезна с точки зрения государственной политики при проектировании новых институциональных соглашений. Теория игр использовалась в анализе общественных благ, олигополии, картеля и сговоров на рынках товаров и труда. При всех своих достоинствах теория игр обладает и относительными слабостями. Некоторые авторы высказали сомнения относительно применения модели дилеммы заключенного в социальной науке. Например, М. Тейлор в 1987 г. предположил, что такие игры соответствуют обстоятельствам обеспечения общественными благами. В 1985 г. Н. Шофилд утверждал, что агенты должны формировать согласованные понятия об убеждениях и желаниях других агентов, включая проблемы познания и интерпретации, которые не просты для моделирования 28 . Многие экономисты отмечали, что использование теории игр без оговорок может свести экономическую деятельность к слишком статичной схеме. В частности, нобелевский лауреат Р. Стоун в 1948 г. писал: «Главная черта, благодаря которой теория игр впадает в противоречие с живой действительностью, заключается в том, что объект исследования ограничен во времени – игра имеет начало и конец. Об экономической действительности этого не скажешь. Именно в возможности обособить партию от игры и заключается глубокое расхождение теории с реальностью, а это расхождение ограничивает ее применение» 29 . Однако с тех пор неоценимо много сделано для сглаживания этого расхождения и расширения применения теории игр в экономике.

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

Вообще экономический эксперимент – это воспроизведение экономического явления или процесса с целью изучения в наиболее благоприятных условиях и дальнейшего практического изменения. Эксперименты, которые осуществляются в реальных условиях, называются естественными, или полевыми, а эксперименты, проводимые в искусственных условиях, – лабораторными. Последние зачастую требуют использования экономико-математических методов и моделей. Естественные эксперименты могут проводиться на микроуровне (эксперименты Р. Оуэна, Ф. Тейлора, по внедрению хозрасчета на предприятии и т.п.) и на макроуровне (варианты экономической политики, свободные экономические зоны и пр.). Лабораторные эксперименты – это искусственно воспроизведенные экономические ситуации, некие экономические модели, чья среда (условия протекания эксперимента) контролируется исследователем в лаборатории.

Американский экономист Эл. Рот, с конца 70-х гг. работающий в области экспериментальной экономики, отмечает ряд преимуществ лабораторных экспериментов перед «полевыми» 30 . В лабораторных условиях возможен полный контроль экспериментатора над средой и поведением субъектов, в то время как при «полевых» экспериментах можно контролировать лишь ограниченное число факторов среды и почти невозможно – поведение экономических субъектов. Именно благодаря этому лабораторные эксперименты позволяют более точно определять условия, при которых можно ожидать повторения отдельных явлений. Кроме того, естественные эксперименты дорогостоящи, и в случае неудачи затрагивают судьбы многих людей.

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

Для примера остановимся на результатах исследования сравнительной эффективности институтов рынка, которые опубликованы Ч.А. Холтом и представлены А.Е. Шаститко 31 . В исследовании сопоставляются выводы теоретической и экспериментальной моделей рынка, полученные с помощью контролируемых экспериментов. Результаты поведения агентов измеряются с помощью коэффициента исчерпания суммы потенциальных рент покупателя и продавца, что соответствует эффективности обмена. Коэффициент исчерпания – отношение фактически (экспериментально) полученной ренты к максимально возможной величине – изменяется от 0 до 1. Сравнение проводилось по следующим формам рынка: двусторонний аукцион, торговля на основе ценовых заявок одной из сторон, расчетная палата, децентрализованные переговоры о цене, торговля на основе заявок с последующими переговорами. Наиболее интересные результаты экспериментов получены разными группами исследователей по двум первым формам рынка (табл. 2.1).

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

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

Эта отрасль математики получила определенное отражение в массовой культуре. В 1998 году американская писательница и журналисткаСильвия Назар опубликовала книгу о жизни Джона Нэша, нобелевского лауреата по экономике за достижения в теории игр, а в 2001 по мотивам книги снят фильм «Игры разума». (Таким образом, теория игр - одна из немногих отраслей математики в которой можно получить Нобелевскую премию). Некоторые американские телевизионные шоу, например, Friend or Foe , Alias или NUMBERS периодически используют в своих выпусках теорию игр.

Джон Нэш - математик,нобелевский лауреат известен широкой общественности благодаря фильму Игры разума.

Понятие теории игр

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

• Конфликт,
• Принятие решения в конфликте,
• Оптимальность принятого решения.

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

Если назвать участников конфликта коалициями действия (обозначив их множество как D, возможные действия каждой из коалиции действия - ее стратегиями (множество всех стратегий коалиции действия K обозначается как S ), результаты конфликта - ситуациями (множество всех ситуаций обозначается как S ; считается, что каждая ситуация складывается вследствие выбора каждой из коалиций действия некоторой своей стратегии, так, что ), заинтересованные стороны - коалициями интересов (их множество - I) и, наконец, говорить о возможных преимуществах для каждой коалиции интересов K одной ситуации s " перед другим s "(этот факт обозначается как ), то конфликт в целом может быть описан как система

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

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

Отдельными классами бескоалиционный игр есть:

• антагонистические игры, включая матричные игры и игры на единичном квадрате.
• динамичные игры, в том числе дифференциальные игры,
• рекурсивные игры,
• игры на выживание

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

Математический аппарат

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

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

Оптимальность и развязки

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

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

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

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

История

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

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

В результате изучения данной главы студент должен:

знать

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

уметь

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

владеть

Методами определения исходов игры.

Игры: основные понятия и принципы

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

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

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

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

Теория игр – это математическая теория конфликтных ситуаций.

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

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

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

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

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

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

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

В литературе встречаются следующие определения элементов, составляющих игру.

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

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

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

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

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

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

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

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

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

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

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

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

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

Повторим, что задача теории игр – нахождение оптимальных стратегий.

Классификация игр представлена на рис. 8.1.

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

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

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

Рис. 8.1.

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

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

• 4. По количеству стратегий каждого игрока игры подразделяются на конечные (число стратегий каждого игрока конечно) и бесконечные (множество стратегий каждого игрока бесконечно).
• 5. По количеству информации, имеющейся у игроков относительно прошлых ходов, игры подразделяются на игры с полной информацией (имеется вся информация о предыдущих ходах) и неполной информацией. Примерами игр с полной информацией могут быть шахматы, шашки и т.п.
• 6. По виду описания игры подразделяются на позиционные игры (или игры в развернутой форме) и игры в нормальной форме. Позиционные игры задаются в виде дерева игры. Но любая позиционная игра может быть сведена к нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. В позиционных играх ходы делаются в дискретные моменты времени. Существуют дифференциальные игры, в которых ходы делаются непрерывно. Эти игры изучают задачи преследования управляемого объекта другим управляемым объектом с учетом динамики их поведения, которая описывается дифференциальными уравнениями.

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

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

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

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

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

Приведем следующий пример. Игра "Зачет". Пусть игрок 1 – студент, готовящийся к зачету, а игрок 2 – преподаватель, принимающий зачет. Будем считать, что у студента две стратегии: A1 – хорошо подготовиться к зачету; A 2 – не подготовиться. У преподавателя имеется тоже две стратегии: B1 – поставить зачет; B 2 – не поставить зачет. В основу оценки значений выигрышей игроков можно положить, например, следующие соображения, отраженные в матрицах выигрышей:

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

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

Еще один пример хорошо известной биматричной игры "Дилемма заключенного".

Каждый из двух игроков располагает двумя стратегиями: A 2 и B 2 – стратегии агрессивного поведения, a A i и B i – миролюбивое поведение. Предположим, что "мир" (оба игрока миролюбивы) лучше для обоих игроков, чем "война". Случай, когда один игрок агрессивный, а другой миролюбивый, выгоднее агрессору. Пусть матрицы выигрышей игроков 1 и 2 в данной биматричной игре имеют вид

Для обоих игроков агрессивные стратегии A2 и B2 доминируют мирные стратегии Ах и B v Таким образом, единственное равновесие в доминирующих стратегиях имеет вид (А2, B 2), т.е. постулируется, что результатом некооперативного поведения является война. В то же время исход (A1, B1) (мир) дает больший выигрыш для обоих игроков. Таким образом, некооперативное эгоистическое поведение вступает в противоречие с коллективными интересами. Коллективные интересы диктуют выбор мирных стратегий. В то же время, если игроки не обмениваются информацией, война является наиболее вероятным исходом.

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

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

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

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

На рис. 8.2 представлена экстенсивная форма игры, а в табл. 8.1 – стратегическая форма.

Рис. 8.2.

Таблица 8.1. Игра с одновременным принятием решений в стратегической форме

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

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

• Воробьев Η. Н. Теория игр для экоиомистов-кибериетиков. М.: Наука, 1985.
• Вентцель Е. С. Исследование операций. М.: Наука, 1980.