В течение жизни мы постоянно взаимодействуем с другими людьми. Маленькие дети, пытаясь добиться того, чтобы родители купили понравившуюся конфетку, часто шантажируют родителей своими слезами. Принимая решение заплакать, ребенок рискует — он не знает, как поведут себя папа с мамой. В чуть более взрослом возрасте абитуриенты, выбирающие вуз, принимают сложное решение о том, в какие университеты подать документы. Ошибка может стоить дорого: при неправильной стратегии можно оказаться в слабом университете или вообще остаться без заветного студенческого билета. Окончив вуз, юноши и девушки начинают искать работу. Перед интервью с работодателем они штудируют статьи в интернете о том, что можно и чего нельзя говорить на интервью, — они пытаются найти наилучшую стратегию своего поведения, исходя из ожиданий компании, в которую они устраиваются. Все эти ситуации объединяет то, что решения, которые принимают одни люди, оказывают влияние на других людей. Такие взаимодействия называются стратегическими. Именно их изучает теория игр. Чтобы проанализировать ту или иную реальную жизненную ситуацию стратегического взаимодействия и найти оптимальный вариант поведения в ней, необходимо сделать две вещи. Во-первых, необходимо формально записать ситуацию на языке теории игр, то есть создать модель (игру). Во-вторых, после того как модель (игра) составлена, ее необходимо решить. Этому мы будем учиться в течение курса. Мы разберем основные виды игр (одновременные и последовательные, с совершенной и несовершенной информацией, коалиционные и некоалиционные), приведем способы их решения и обсудим их на многочисленных примерах. Курс будет интересен желающим разобраться в том, как конкурируют друг с другом несколько компаний и можно ли гарантированно выиграть в шашки, есть ли смысл угрожать на переговорах и с кем стоит объединяться в коалиции в парламенте. FAQ В: Требуется ли предварительная подготовка для прохождения курса? О: Курс является базовым, поэтому он не требует специальной подготовки. Для его успешного освоения достаточно уверенных знаний курса математики в объеме школьной программы. В одном-двух примерах могут пригодиться знания начал математического анализа (дифференцирование функций одной переменной, необходимое условие экстремума) и знания начал теории вероятностей (понятие математического ожидания случайной величины). В: Что требуется для успешного окончания курса? О: Итоговая оценка за курс складывается из результатов 10 оцениваемых тестов. Для успешного окончания курса необходимо дать не менее 80 % правильных ответов на каждый из этих тестов.
Игры в нормальной форме
Loading...
Из курса от партнера National Research University Higher School of Economics
Теория игр (Game Theory)
611 оценки
Из урока
Стратегические взаимодействия
Добро пожаловать на первую неделю нашего курса! На этой неделе мы поговорим о предмете изучения теории игр; определим, какие ситуации можно называть стратегическими взаимодействиями, а какие — нельзя; обсудим примеры таких взаимодействий и узнаем о том, как описывать реальные жизненные ситуации на формальном теоретико-игровом языке.
Познакомьтесь с преподавателями
Dmitry DagaevAssociate Professor, Deputy Vice Rector
Department of Higher Mathematics
Мы рассмотрели достаточно
подробно несколько примеров стратегического взаимодействия.
Теперь давайте научимся формально описывать эти
стратегические взаимодействия на языке теории игр.
Сначала, начнем с игр в нормальной форме.
Для того чтобы задать игру в нормальной форме, нужно сделать три вещи.
Нужно, во-первых, указать множество всех игроков в этой игре.
Во-вторых, указать множество возможных стратегий каждого игрока.
И, в-третьих, указать платеж, который получает каждый игрок.
Итак, мы задаем множество игроков.
Будем обозначать это множество I.
И оно состоит из имен этих игроков.
Для простоты будем обозначать их один, два, три и так далее… n.
Будем считать, что игроков по крайней мере двое.
Иначе нет никакого взаимодействия между несколькими игроками.
Теперь, у каждого игрока есть множество его возможных стратегий.
Будем обозначать через S большое
с индексом i множество возможных стратегий игрока номер i.
После того как каждый игрок посмотрел на множество своих возможных стратегий,
он должен сделать выбор: какую из этих своих стратегий сыграть.
Он вытаскивает из этого мешка со множеством всех
своих возможных стратегий одну единственную стратегию.
Будем обозначать ее s с индексом i маленькая.
После того как каждый игрок выбрал,
какую стратегию он сыграет, формируется набор этих стратегий.
Его мы будем называть профилем стратегий.
(s1, …, sn) — это профиль стратегий игроков.
Теперь, когда зафиксирован профиль стратегий, мы должны определить платежи,
которые получат игроки, если будет сыгран этот профиль стратегий.
Таким образом, у каждого из игроков должна быть задана функция платежей.
Обозначим ее через u с индексом i.
Она определена на множестве всех возможных профилей стратегий.
Что бы ни сыграли игроки, мы должны знать,
сколько получит каждый из игроков в этом случае.
Давайте рассмотрим в качестве примера одну из самых известных в теории игр
игр, которая называется «Битва полов».
Муж и жена одновременно и независимо друг от друга решают,
где им провести выходной день.
Муж больше хочет на футбол, а жена предпочитает балет.
При этом они хотят провести этот вечер вместе.
Они принимают это решение независимо:
у них нет возможности обменяться информацией.
Мобильных телефонов еще нет.
Множество игроков в этой игре — это муж и жена.
У каждого из игроков есть две возможные стратегии.
У мужа есть стратегия «пойти на футбол» и стратегия «пойти на балет».
У жены есть стратегия «пойти на футбол» и «пойти на балет».
Таким образом, в этой игре есть четыре возможных профиля стратегий:
(Футбол, Футбол), (Футбол, Балет), (Балет, Футбол) и (Балет, Балет).
Здесь первая стратегия — это стратегия мужа.
Вторая стратегия — стратегия жены.
Теперь, когда мы описали множество возможных стратегий игроков,
нам нужно определить платежи, которые они получат в каждом возможном профиле игры.
Давайте представим, что оба игрока выбрали пойти на футбол.
Тогда они проведут вечер вместе.
Но при этом муж будет смотреть футбол,
ему это нравится, а жена будет смотреть футбол, и это ей не очень нравится.
Тогда муж получит платеж, равный пяти, а жена чуть меньший платеж —
платеж, равный четырем.
Если муж пойдет на футбол, а жена пойдет на балет,
то они будут смотреть то, что им интересно, но будут делать это поодиночке.
И тогда их платежи будут равны единице.
Если муж пойдет на балет, а жена пойдет на футбол,
то они и проведут выходной день по отдельности друг от друга,
и будут смотреть не очень интересующее их мероприятие.
Их платеж в этом случае будет равен нулю.
Наконец, если и муж, и жена пойдут на балет,
то тогда они снова проведут вечер вместе, но жене будет
чуть лучше: она будет смотреть балет, а муж наслаждаться им не будет.
Платеж мужа будет равен четырем, а платеж жены будет равен пяти.
«Битву полов», как и другие конечные игры в нормальной форме двух лиц,
можно представить в виде матрицы.
Давайте представим, что мы выписали по горизонтали все стратегии мужа,
по вертикали — все возможные стратегии жены,
и на пересечении строчки и столбца поставили
платежи игроков в том случае, если они играют соответствующие стратегии.
Муж играет ту стратегию, которая записана в указанной строчке,
а жена играет ту стратегию, которая записана в указанном столбце.
Будем первым платежом записывать платеж первого игрока,
а вторым платежом — платеж второго игрока.
Таким образом, матрица «Битвы полов» представлена на ваших экранах.
Например, в профиле (Футбол, Футбол) платежи игроков равны соответственно
пять — у мужа и четыре — у жены.
Это левая верхняя ячейка в этой матрице.
А, например, если муж пойдет на балет, а жена пойдет на футбол,
то платежи игроков будут равны нулю: как платеж мужа, так и платеж жены.
Еще один пример одновременного стратегического взаимодействия —
это аукцион Викри.
Давайте представим, что на аукцион выставлена очень редкая почтовая марка.
Ее хотели бы приобрести многие коллекционеры.
Все коллекционеры по-разному оценивают стоимость этой марки.
Марка продается по правилам закрытого аукциона второй цены.
То есть участники аукциона одновременно подают свои ставки в закрытых конвертах.
После этого конверты вскрываются, и победителем становится участник,
который предложил максимальную ставку.
Покупка этой марки осуществляется по второй максимальной цене.
То есть не по самой максимальной, а по той, которая следует за ней.
Давайте формализуем этот аукцион в виде игры в нормальной форме.
В этой игре есть n игроков — участников аукциона.
И ценность марки будем обозначать через v с индексом i.
Она больше нуля для каждого из игроков, но может различаться для каждого из них.
Давайте пронумеруем этих игроков таким образом,
что оценочная стоимость марки для первого игрока — самая высокая.
Ее обозначаем через v1.
Для второго игрока — чуть ниже.
Ее обозначаем через v2. И так далее.
У каждого из игроков есть множество возможных стратегий,
состоящие из различных ставок, которые он может сделать.
Будем обозначать ставку игрока i через b с индексом i.
Каждый игрок может выбрать абсолютно любое значение b с индексом i:
от нуля до плюс бесконечности.
Теперь, чем закончится аукцион?
Давайте обозначим через b с чертой с индексом i
максимальную из всех ставок игроков, за исключением i-го игрока.
В каких случаях i-й игрок выигрывает аукцион?
Он выигрывает его, во-первых, в случае, если он поставил больше,
чем все остальные участники аукциона, а, во-вторых, в случае,
если он поставил столько же, сколько и кто-то еще,
но при этом номер игрока i —
минимальный среди всех номеров участников, которые поставили такую же цену.
Будем считать, что первый игрок имеет небольшое преимущество перед
всеми остальными, а именно: если все поставили одинаковую ставку,
то первый игрок выиграет эту марку.
То есть игрок с меньшим номером будет выигрывать в случае,
если игроки поставили одинаковые ставки.
Теперь нужно формально определить платежи игроков.
Платеж i-го игрока определяется следующим образом.
Если участники аукциона сделали ставки (b1, …, bn),
то платеж, который получает i-й игрок, соответственно равен либо
v с индексом i минус b с чертой с индексом i в случае, если i выиграл аукцион,
и 0 в случае, если участник i проиграл этот аукцион.
То есть если i-й игрок выиграл аукцион,
то он получает разницу между ценностью марки со своей точки зрения
и ценой, которую ему пришлось заплатить за эту марку.
Если участник проиграл аукцион, то он не получает ничего.
Это были игры в нормальной форме, с помощью которых мы будем
моделировать одновременные стратегические взаимодействия.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
