Курсы по теории игр. «Теория систем и системный анализ. Лекции по теории игр

Метод Гаусса-Зейделя

Метод заключается в поочерёдном нахождении частных экстремумов целевой функции по каждому фактору. При этом на каждом этапе стабилизируют (k-1) факторов и варьируют только один i-ый фактор

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

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

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

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

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

Метод градиента (обычный) осуществляется по следующей схеме:

а) выбирают базовую точку;

б) выбирают шаги движения по каждому фактору;

в) определяют координаты пробных точек;

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

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

где H i -шаг движения по X i .

X i – координаты предыдущей рабочей точки.

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

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

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

а) Метод крутого восхождения (Бокса - Уилсона).

б) Принятие решений после крутого восхождения.

в) Симплексный метод оптимизации.

г) Достоинства и недостатки методов.

5.7.3 Метод крутого восхождения (Бокса- Уилсона)

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

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

Где i,j,k-единичные векторы в направлении соответствующих координатных осей.

Порядок расчёта .

Исходными данными является математическая модель процесса, полученная любым способом (ПФЭ, ДФЭ и т.д.).

Расчеты проводят в следующем порядке:

а) уравнение регрессии лучше перевести в натуральный вид по формулам кодирования переменных:

где x i -кодированное значение переменной x i ;

X i - натуральное значение переменной x i ;

X i Ц -центральный уровень фактора в натуральном виде;

l i -интервал варьирования фактора x i в натуральном виде.

б) вычисляют шаги движения к оптимуму по каждому фактору.

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

B i *.l I ,

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

Знак шага движения l a ’ должен совпадать со знаком коэффициента уравнения регрессии, соответствующего базовому фактору (B a). Величина шагов для других факторов вычисляется пропорционально базовому по формуле:

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

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

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

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

Если Y® max X i =X i ц +gl i ` ’

если Y® min .X i =X i ц -gl i ` . (5.36)

Возникшая в сороковых годах XX века математическая теория игр чаще всего применяется именно в экономике. Но как с помощью концепции игр смоделировать поведение людей в обществе? Зачем экономисты изучают, в какой угол чаще бьют пенальти футболисты, и как выиграть в «Камень, ножницы, бумагу» в своей лекции рассказал старший преподаватель кафедры микроэкономического анализа ВШЭ Данил Федоровых.

Джон Нэш и блондинка в баре

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

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

Стратегия - описание действий игрока во всех возможных ситуациях.

Исход - комбинация выбранных стратегий.

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

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

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

«Камень, ножницы, бумага»

Рассмотрим другие игры на предмет равновесия. Например, в «Камне, ножницах, бумаге» нет равновесия по Нэшу: во всех ее вероятных исходах нет варианта, в котором оба участника были бы довольны своим выбором. Тем не менее, существует Чемпионат мира и World Rock Paper Scissors Society, собирающее игровую статистику. Очевидно, что вы можете повысить свои шансы на победу, если будете что-то знать об обычном поведении людей в этой игре.

Чистая стратегия в игре - это такая стратегия, при которой человек всегда играет одинаково, выбирая одни и те же ходы.

По данным World RPS Society, камень является самым часто выбираемым ходом (37,8%). Бумагу ставят 32,6%, ножницы - 29,6%. Теперь вы знаете, что нужно выбирать бумагу. Однако, если вы играете с тем, кто тоже это знает, вам уже не надо выбирать бумагу, потому что от вас ожидается то же самое. Есть знаменитый случай: в 2005 году два аукционных дома Sotheby“s и Christie”s решали, кому достанется очень крупный лот - коллекция Пикассо и Ван Гога со стартовой ценой в 20 миллионов долларов. Собственник предложил им сыграть в «Камень, ножницы, бумагу», и представители домов отправили ему свои варианты по электронной почте. Sotheby“s, как они позже рассказали, особо не задумываясь, выбрали бумагу. Выиграл Christie”s. Принимая решение, они обратились к эксперту - 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым сильным, поэтому большинство людей его выбирают. Но если мы играем не с совсем глупым новичком, он камень не выбросит, будет ожидать, что это сделаем мы, и сам выбросит бумагу. Но мы будем думать на ход вперед, и выбросим ножницы».

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

Смешанные стратегии и спорт

Более серьезных примеров смешанных стратегий очень много. Например, куда подавать в теннисе или бить/принимать пенальти в футболе. Если вы ничего не знаете о вашем сопернике или просто постоянно играете против разных, лучшей стратегией будет поступать более-менее случайно. Профессор Лондонской школы экономики Игнасио Паласиос-Уэрта в 2003 году опубликовал в American Economic Review работу, суть которой заключалась в поиске равновесия по Нэшу в смешанных стратегиях. Предметом исследования Паласиос-Уэрта выбрал футбол и в связи с этим просмотрел более 1400 ударов пенальти. Разумеется, в спорте все устроено хитрее, чем в «Камне, ножницах, бумаге»: там учитывается сильная нога спортсмена, попадания в разные углы при ударе со всей силы и тому подобное. Равновесие по Нэшу здесь заключается в расчете вариантов, то есть, к примеру, определении углов ворот, в которые надо бить, чтобы выиграть с большей вероятностью, зная свои слабые и сильные стороны. Статистика по каждому футболисту и найденное в ней равновесие в смешанных стратегиях, показало, что футболисты поступают примерно так, как предсказывают экономисты. Вряд ли стоит утверждать, что люди, которые бьют пенальти, читали учебники по теории игр и занимались довольно непростой математикой. Скорее всего, есть разные способы научиться оптимально себя вести: можно быть гениальным футболистом, и чувствовать, что делать, а можно - экономистом, и искать равновесие в смешанных стратегиях.

В 2008 году профессор Игнасио Паласиос-Уэрта познакомился с Авраамом Грантом, тренером «Челси», который играл тогда в финале Лиги чемпионов в Москве. Ученый написал записку тренеру с рекомендациями по серии пенальти, которые касались поведения вратаря соперника - Эдвина ван дер Сара из «Манчестер Юнайтед». Например, по статистике, он почти всегда отбивал удары на среднем уровне и чаще бросался в естественную для пробивающего пенальти сторону. Как мы определили выше, правильнее все-таки рандомизировать свое поведение с учетом знаний о сопернике. Когда счет по пенальти был уже 6:5, Николя Анелька, нападающий «Челси», должен был забивать. Показывая перед ударом в правый угол, ван дер Сар будто спросил у Анелька, не собирается ли он бить туда.

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

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

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

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

Улучшение по Парето

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

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

Трагедия общины

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

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

Когда вас призывают прийти на субботник, ни от кого в отдельности не будет зависеть, станет двор чистым или нет: если я выйду один, я не смогу убрать все, или, если выйдут все, то не выйду я, потому что все и без меня уберут. Другой пример - перевозка грузов в Китае, о котором я узнал в замечательной книге Стивена Ландсбурга «Экономист на диване». 100-150 лет назад в Китае был распространен способ перевозки грузов: все складывалось в большой кузов, который тащили семь человек. Заказчики платили, если груз доставлялся вовремя. Представьте, что вы - один из этих шести. Вы можете прилагать усилия, и тянуть изо всех сил, и если все будут так делать, груз доедет вовремя. Если кто-нибудь один так делать не будет, все тоже доедут вовремя. Каждый думает: «Если все остальные тянут как следует, зачем это делать мне, а если все остальные тянут не со всей силы, то я ничего не смогу изменить». В итоге, со временем доставки все было очень плохо, и сами грузчики нашли выход: они стали нанимать седьмого и платить ему деньги за то, чтобы он стегал лентяев плетью. Само наличие такого человека заставляло всех работать изо всех сил, потому что иначе все попадали в плохое равновесие, из которого никому в отдельности с выгодой не выйти.

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

Сommitment device

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

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

Другие примеры игр:

Модель Бертрана

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

Разъезд на узкой дороге

Рассмотрим примеры выбора между двумя возможными равновесиями. Представьте, что Петя и Маша едут навстречу друг другу по узкой дороге. Дорога настолько узкая, что им обоим нужно съехать на обочину. Если они решат повернуть налево или направо от себя, они просто разъедутся. Если же один повернет направо, а другой налево от себя, или наоборот, случится авария. Как выбрать, куда съехать? Чтобы помогать искать равновесие в подобных играх, существуют, например, правила дорожного движения. В России каждому нужно повернуть направо.

В забаве Chiken, когда два человека едут на большой скорости навстречу друг другу, тоже есть два равновесия. Если оба сворачивают на обочину, возникает ситуация, которая называется Chiken out, если оба не сворачивают, то погибают в страшной аварии. Если я знаю, что мой соперник едет прямо, мне выгодно съехать, чтобы выжить. Если я знаю, что мой соперник съедет, то мне выгодно ехать прямо, чтобы после получить 100 долларов. Сложно предсказать, что случится на самом деле, однако, у каждого из игроков есть свой метод выиграть. Представьте, что я закрепил руль так, что его нельзя повернуть, и показал это своему сопернику. Зная, что у меня нет выбора, соперник отскочит.

QWERTY-эффект

Иногда бывает очень сложно перейти из одного равновесия в другое, даже если оно означает пользу для всех. Раскладка QWERTY была создана, чтобы замедлить скорость печати. Поскольку если бы все печатали слишком быстро, головки печатной машинки, которые бьют по бумаге, цеплялись бы друг за друга. Поэтому Кристофер Шоулз разместил часто стоящие рядом буквы на максимально далеком расстоянии. Если вы зайдете в настройки клавиатуры на своем компьютере, вы сможете выбрать там раскладку Dvorak и печатать гораздо быстрее, так как сейчас нет проблемы аналоговых печатных машин. Дворак рассчитывал, что мир перейдет на его клавиатуру, но мы по-прежнему живем с QWERTY. Конечно, если бы мы перешли на раскладку Дворака, будущее поколение было бы нам благодарно. Все мы приложили бы усилия и переучились, в результате вышло бы равновесие, в котором все печатают быстро. Сейчас мы тоже в равновесии - в плохом. Но никому не выгодно быть единственным, кто переучится, потому что за любым компьютером, кроме личного, работать будет неудобно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение 1.1 .Стратегическая игра - это тройка

где обозначения расшифровываются следующим образом:

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

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

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

Пример 1.1 . Первый пример возьмем совсем уж из детства - рассмотрим классическую игру "камень-ножницы-бумага" 2Хотя насчет детства еще можно поспорить: в США вот недавно появилась аж целая ассоциация, посвященная игре в " Rock , Paper , Scissors " под логичным названием USARPS. Призы неплохие - можете попробовать свои силы на сайте http://www.usarps.com/ . . Камень побеждает ножницы, ножницы побеждают бумагу, бумага - камень. У игры получается вот какая матрица (где означает победу того игрока, чьи стратегии выписаны слева, а - победу игрока, стратегии которого стоят в первой строке):

Конец примера 1.1 .

Пример 1.2 . В качестве второго примера рассмотрим классическую игру полковника Блотто [ , ]. Полковник Блотто должен распределить свои силы ( солдат) между несколькими участками поля боя ( участков). Его противник должен сделать то же самое (количество его солдат может отличаться). Выигрывает тот, кто победит на большем количестве участков боя.

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

(3,0,0), (2,1,0), (2,0,1), (1,2,0), (1,1,1), (1,0,2), (0,3,0), (0,2,1), (0,1,2), (0,0,3).

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

Конец примера 1.2 .

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

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

Пример 1.3 . Рассмотрим рынок некоего продукта, на котором находятся ровно две фирмы: . Стратегия каждого из участников - количество продукта, которое он производит: .