Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Аэропорт"
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория игр
32 calificaciones
De la lección
Кооперативная теория игр. Ядро. Вектор Шепли
На этой неделе мы переходим к изучению кооперативной теории игр, понятию ядра и вектора Шепли.
Conoce a los instructores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Супермодулярные игры это такой очень яркий пример,
когда теория помогла практике.
Один из очень немногих примеров такого рода.
Значит, по теории мы видели, что супермодулярные игры совершенно
замечательные, и у них ядро не пусто, оно допускает совершенно четкое описание и
вектор Шепли попадает в него и, в каком-то смысле, даже в его центр.
Но, как правило, после этого должно было бы выясниться,
что в реальности таких игр не существует, что в некотором приближении можно считать,
что это формализация вот таких вот обстоятельств, но тут же выяснится,
что куча подробностей мелких мешает тому, чтобы это была правильная формализация,
и так далее и тому подобное, стандартный переход от теории к практике.
Но нет, вот в этом конкретном месте огромная удача, а именно: достаточно
широкий и важный класс игр в экономике оказывается супермодулярным.
Давайте я его опишу.
Это первое упоминание соответствующего класса
игр в 1973 году общеизвестно под названием Airport Game.
Но на самом деле я в процессе преподавания теории игр последние
15—17 лет нашел еще четыре примера, как минимум,
в которых возникает игра ровно того же самого класса,
ну просто математической формализации той же самой, что и Airport Game,
то есть это какое-то такое выделенное место, и такие игры всегда супермодулярны.
Значит, что же это за игра?
Игра это вот какая.
Есть взлетная полоса.
[БЕЗ СЛОВ] И есть некоторое количество авиакомпаний,
которые используют самолеты разного, так сказать, калибра.
И разным самолетам требуется разная длина взлетной полосы.
АН-24, допустим.
Airbus 320
или 380 какой-нибудь, там, Airbus, да?
Боинг Боинг-747,
737, ну в общем не знаю,
разные самолеты с разными требованиями на длину взлетной полосы.
Но понятно, что взлетная полоса-то одна и ее надо постоянно
поддерживать в хорошем состоянии.
Есть некие издержки, которые все время надо нести,
постоянно поддерживать эту взлетную полосу.
Или может быть вариация задачи состоит в том,
что нужно построить некоторую взлетную полосу новую,
которую будет использовать некоторое количество различных экипажей.
И мы вот эти вот авиакомпании с соответствующими самолетами считаем
игроками.
Соответственно, множество игроков – это множество авиакомпаний,
которые своими судами используют взлетную полосу.
Понятно, что никто не будет строить отдельную полосу для АН,
отдельную – для Б, отдельную – для А.
Конечно, будут делать общую полосу самой большой длины среди всех
взлетающих по ней самолетов.
Но вопрос вот в чем: как распределить издержки по обслуживанию вот этой
взлетной полосы?
Но давайте поймем, что это на самом деле классическая кооперативная игра.
Потому что, что такое v от коалиции S игроков?
Ну это вот что такое: предположим, что эта коалиция отделяется и сама
занимается обслуживанием своих самолетов или сама строит себе взлетную полосу.
Тогда чему будут равны ее издержки?
Они равны минус, извините,
ее выигрыш равен равен издержкам, поэтому нужно знак «минус» ставить перед ними.
«Минус» издержки поддержке полосы
длины максимум по всем i из S
требований li То есть мы считаем,
что l1, l2, ..., ln – это требования на длину полосы, которые,
ну они фиксированы для нас, мы не можем ничего с ними сделать, изменить их нельзя,
они просто даны и все, такой самолет должен иметь вот такую взлетную полосу,
чтобы взлететь гарантированно, а такой самолет – вот такую.
Значит, это требование это просто экзогенные величины в модели.
И есть также функция С(*), которая совершенно произвольна,
вот что я хочу подчеркнуть: что она- совершенно произвольная неубывающая
функция, то есть необязательно совершенно считать, что она линейна.
Какая угодно: у вас взлетная полоса может быть где-то проходить там по каким-то
скальникам, которые нужно шлифовать, а где-то там по болоту,
а где-то еще как-то, где-то в степи, где она очень дешевая.
То есть она может быть составлена из нескольких кусков совершенно разной
стоимостью поддержки, но ясно, что более длинную поддерживать дороже,
это совершенно очевидно.
Поэтому речь идет о произвольной функции C, ну, единственное,
что она не должна убывать.
То есть вот данные модели, совершенно произвольные числа и утверждение состоит в
том, что игра, заданная вот таким способом, всегда является супермодулярной.
При любых l1, l2, ..., ln,
а также функции C неубывающей.
Ну еще раз: игра определяется так,
что выигрыш каждой коалиции – это на самом деле ее проигрыш,
то есть со знаком «минус» издержки, которые она должна нести.
Теперь мы должны проверить, что эта игра супермодулярна.
Давайте я непосредственно возьму и проверю это прямо перед камерой,
потому что один раз это стоит сделать.
Это очень легкая, совсем несложная проверка.
Значит, я буду проверять утверждение о том,
что присоединение игрока
к большей коалиции,
если игрок i, который не находится в коалиции S, присоединяется к ней,
то выигрыш этой коалиции вырастает не меньше,
чем он вырастает, если i присоединяется к T.
Но выигрыш это минус проигрыш, правильно?
Поэтому надо проверять, что проигрыш увеличивается не больше,
чем во втором случае.
То есть нужно проверить, что v(S ∪ i)
− v(S) ≥
всегда, чем v(T ∪ i − v(T).
Если я вспомню, что это такое, я запишу, соответственно,
со знаком «минус», переворачивается неравенство в другую сторону, написано,
что издержки от (максимальной длины среди
всех j из S ∪ i полосы) −
издержки от (максимума просто по всем
j из S lj-того) вырастает не больше, чем в случае,
когда я то же самое записываю для коалиции тут (T ∪ i).
А тут j из T.
Вот, то есть если здесь максимумы
соответственно взяты по меньшим множествам.
Итак, есть две коалиции авиаперевозчиков: коалиция S и коалиция T.
Есть новый авиаперевозчик.
Коалиция S содержит коалицию T.
Новый авиаперевозчик приходит в коалицию S.
И что вот это такое?
Это необходимое удлинение взлетной полосы, которое благодаря ему возникло.
То есть, например, если требование, связанное с ним,
с этим авиаперевозчиком, li меньше, чем максимальное
требование где-то вот здесь, то эта величина просто равна 0.
То есть он не вносит дополнительного какого-то удлинения
полосы его обслуживания.
По-прежнему максимум тот же самый – издержки не изменились.
Но в этом случае понятно, что 0 ≤ неотрицательной величины.
Здесь написана неотрицательная величина в любом случае.
Поэтому в этом случае проверять ничего не надо.
Проверять надо в том случае, когда требование на коалицию S,
максимальная длина экипажей, которые поднимаются в коалиции S,
все-таки ниже, чем требования у новопришедшего.
Новопришедший там вот этот вот аэробус «Титаник-380».
Он пришел, допустим, вот сюда и вот дополнительная эта самая,
которую он должен обслуживать дополнительная полоса,
и нужно вычислить прирост издержек – это C от вот этого − C от вот этого.
Но T содержится-то внутри вот этого вот участка, то есть коалиции S.
Содержит в себе коалицию T, поэтому требование на коалицию T никак не дальше
этой точки, максимум вот этих l внутри коалиции T не может выходить за пределы
максимума по коалиции S, которая больше, поэтому к T он добавляет либо столько же,
либо еще больше, если эти требования на T, если в T есть элемент, так сказать,
если самые большие требования накладывает тот перевозчик из S, который в T не лежит.
В таком случае, если i приходит в множество T,
он удлиняет еще по сравнению с этим полосу и, соответственно, издержки увеличиваются,
что и требовалось доказать, но уменьшиться они никак не могут.
Вот.
Тем самым, все такие игры являются супермодулярными.
И, соответственно, во всех таких играх является разумным,
оправданным и логичным использование вектора Шепли.
В следующем сюжете мы выпишем для него очень интересную красивую формулу.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
