Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра в нормальной форме, доминирующие стратегии
Loading...
From the course by Moscow Institute of Physics and Technology
Теория игр
31 ratings
From the lesson
Равновесия Нэша
В первой неделе вы познакомитесь с основными концепциями теории игр: игры в нормальной форме, (доминируемыми) стратегиями, равновесиями по Нэшу.
Meet the Instructors
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Итак, что же такое классическая игра в нормальной форме?
Это, прежде всего, указание списка играющих.
Перенумеруем игроков.
Этот список может быть конечный, как во всех предыдущих случаях — более того,
в предыдущих случаях он вообще состоял из двух человек — либо бесконечный.
И в случае, если этот список бесконечный, возникает вопрос,
есть ли какая-то дополнительная структура, то есть, например,
может быть, что игроки — это жители какой-то территории.
В этом случае разумно считать, что эта территория снабжена какой-то метрикой,
тогда, как бы, у игроков возникает, на множестве игроков,
возникает метрическая структура: близкие и далекие игроки.
Ну и, как правило, их функции выигрыша, их платежные,
грубо говоря, матрицы, платежные функции, они будут похожи.
Но это сложные случаи; очень хорошо, достаточно хорошо развита теория
таких метрических игр, об этом мы поговорим в самом конце курса.
А пока будем считать, что у нас просто конечное число игроков.
Далее, каждому игроку ставится соответствие стратегическое множество.
То есть, просто произвольного вида множество, абстрактное множество.
И считается, что человек, когда происходит акт игры,
разыгрывания игры, он просто выбирает из этого множества какой-то элемент, говорит,
вот у меня будет вот такая стратегия, я буду играть вот такую вот стратегию.
Соответственно, если игра, как во всех предыдущих сюжетах,
одновременная и одноразовая, одношаговая, то просто одновременно,
не глядя друг на друга, не подсматривая друг к другу в стратегические списки,
каждый выбирает какую-то из своих стратегий.
Следовательно, исход — это просто некоторая точка декартова произведения.
[БЕЗ_ЗВУКА]
Вот.
Теория игр занимается вопросом предсказания исхода.
То есть, мы имеем дело с ситуацией, когда, грубо говоря,
каждый сидит за своим отдельным столиком, столики разделены ширмой,
у каждого на столике находится прибор с рычагом.
Этот рычаг может быть в разных положениях.
И, в каких именно положениях, задается соответствующим множеством положений.
Кстати сказать, эти множества вполне могут быть непрерывными, то есть,
игроков может быть конечное число, а множества могут быть, скажем, отрезками,
квадратами, либо каким-то просто конечными множествами, то есть, зависит от того,
какая специфика данной конкретной игры.
И каждый человек должен поставить рычаг в нужное себе положение, в то,
которое он выбрал, не глядя на других.
Вот одновременно выбирают положения рычагов и складывается некоторый исход,
то есть, элемент вот такого прямого произведения.
Иногда специфицируется прямо множество исходов само по себе,
то есть говорится, что есть некоторое отображение,
скажем, Ψ, из прямого произведения в некое
абстрактно сразу же изначально заданное множество всех исходов A.
А иногда считается,
что просто множество исходов — это прямое произведение всех стратегических множеств.
Далее, чтобы понять, что происходит,
нам нужно знать, как игроки оценивают те или иные исходы.
Надо понимать следующее: что игроки оценивают не свои стратегии,
то есть, что вот одна стратегия лучше другой или хуже другой,
а именно целиком весь исход, потому что на них влияют остальные.
Я выбираю стратегию из множества S1, если я первый игрок.
Но проблема в том, что выбор второго,
третьего и так далее игрока влияет на мой выигрыш.
Я не могу повлиять на их выбор, но их выбор влияет на мой выигрыш.
В этом и состоит игра.
Игра состоит в том, что весь исход целиком влияет на выигрыш людей,
поэтому функции выигрыша нужно задавать
непосредственно на вот таком вот множестве.
На множестве всех исходов.
Вот такие вот функции, которые вводят ранжирование,
какие исходы лучше, а какие хуже.
В некоторых случаях непосредственно вводится прямо ранжирование,
то есть отношение, некоторое бинарное отношение на множестве,
на прямом произведении, которое указывает, как сравниваются любые два исхода.
Мы для простоты введем вот такую функцию и все, то есть, эта функция будет задавать.
Если значение функции на данном исходе больше, чем на каком-то другом,
то мы говорим, что данный исход для человека предпочтительнее.
Если же здесь изначально введено множество A,
то можно задавать функции выигрыша непосредственно на множестве A,
и тогда у нас получается композиция отображений.
Ψ отображает исходы в A,
а потом функции эти у υ отображают исход, множество исходов в вещественные числа.
То есть, оценивают, какие исходы лучше, какие хуже.
И в этих условиях, в дилемме заключенного,
которую мы рассмотрели, и во всех её реинкарнациях,
наблюдалось, что один из исходов был лучше, чем другой.
Давайте введём формальное определение.
Определение.
Стратегия, извините — одна из стратегий игрока.
Не исход, а одна из стратегий игрока была лучше, чем все остальные.
Стратегия — Si*,
из множества всех стратегий i игрока,
называется слабо- или
сильно- доминирующей,
если для
любой другой стратегий,
Si из Si, для любой другой,
не совпадающей с данной, а также, внимание,
для любого набора стратегий всех остальных игроков.
То есть, для любого набора S1, S2, ..., Si- 1,
Si + 1,..., Sn выполнено следующее
неравенство: υi(S1,...,
Si- 1, ..., Si*,
Si + 1,..., Больше или равно,
в случае слабо доминирующей,
или строго больше в случае сильно доминирующей,
чем у Ui(S1,..., Si,..., Sn),
то есть при подстановке сюда вот этой вот произвольной другой стратегии.
Итак, стратегия доминирует все остальные — иногда говорят доминантная, кстати,
тут есть некоторая терминологическая множественность терминов, иногда говорят
доминантная стратегия, слабо доминантная или сильно доминантная — в том случае,
если любая другая стратегия хуже не зависимо от того, как играют остальные.
Если не строго хуже, то это говорит о слабом доминировании, если строго хуже,
то о сильном доминировании.
Вот. Это первое определение, и, понятно,
что в дилемме заключенного у нас одна из стратегий всегда оказывалась доминантной.
И, соответственно, второе определение, связанное с дилеммой заключенного,
определение два.
Исход (S1*,...,
Sn*) доминирует
исход (Š1,...,
Šn) по Парето,
если для любого игрока
верно неравенство,
что υi(S1*,..., Sn*) строго больше,
чем υi(Š1,..., Šn).
Есть еще понятие слабого доминирования по Парето,
но я сейчас не буду на нем останавливаться.
Итак, сильно доминирующая стратегия — это которая
лучше всех остальных при любом поведении остальных игроков,
а исход доминирует по Парето, если с точки
зрения любого игрока он лучше какого-то другого исхода, вот который он доминирует.
То есть, один исход доминирует другой по Парето, вот, и что,
в чем пафос дилеммы заключенного?
Пафос такой, что если вы возьмете набор сильно доминирующих стратегий,
доминантных стратегий, то совершенно необязательно,
что такой набор будет доминировать по Парето любой другой исход.
Напротив, в нашей ситуации набор стратегий,
которые были доминантные, составляет исход, который, наоборот,
проигрывает по Парето какому-то другому исходу.
И в этом, как бы, состоит главный пафос дилеммы заключенного.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
