Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Игра "Аэропорт" и похожие: вычисление вектора Шепли
Loading...
Del curso dictado por Moscow Institute of Physics and Technology
Теория игр
44 calificaciones
De la lección
Кооперативная теория игр. Ядро. Вектор Шепли
На этой неделе мы переходим к изучению кооперативной теории игр, понятию ядра и вектора Шепли.
Conoce a los instructores
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
Итак, давайте вычислим вектор Шепли.
Я выпишу формулу и дам задание на дом её доказать.
Давайте введём некоторые дополнительные обозначения.
Прежде всего, никто нам не мешает упорядочить требования...
и тогда можно выписать
набор чисел где Ci — это стоимость обслуживания полосы li.
И, на самом деле, можно вообще требования переписать в терминах издержек просто,
то есть, издержки на использование соответствующей длины полос.
Разницы никакой нет, просто длину будем измерять в издержках на её обеспечение.
Вот. В силу свойств монотонности,
это совершенно эквивалентная замена.
Итак, есть игра, в которой есть n участников, и список издержек,
который не убывает.
Как выписать вектор Шепли для вот этой вот игры?
Ответ: C1
/ n + (C2
− C1) / (n
− 1) + (C3
− C2) / n − 2 +...
+ C(n − 1) − C(n − 2) / 2 + (Cn
− C(n − 1) / 1) Что это за формула и как её понимать?
А понимать её вот как: Шепли первого перевозчика
равен вот этой компоненте, то есть, эту формулу надо обрубить по сюда.
Шепли, значение Шепли второго перевозчика равен вот этой сумме,
то есть, нужно обрубить формулу по второму члену.
Шепли третьей компоненты — третьего перевозчика,
извините — равна вот этой сумме из трех, и так далее.
Шепли n равно полной сумме, которую я выписал.
Это чрезвычайно наглядно.
Смотрите, что это означает.
Это значит, что вот эту часть используют все перевозчики вообще.
Ну так они поровну делят расходы на неё.
Дальше, для Ан-24 всё заканчивается на этом, и всё.
Следующую часть все, кроме Ан-24, используют.
Ну так они вот эту следующую часть делят поровну между собой на n − 1.
Потом идет следующая часть, делится на n − 2 и самый последний,
вот этот вот Аэробус 380, вот этот последний участок,
который он один использует, он один и обслуживает, то есть,
платит издержки дополнительные за этот последний участок.
Всё, проще некуда вообще.
С этой формулой связано несколько удивительных историй в моей жизни.
Я сейчас их расскажу.
История номер один, это 20 лет назад занимались там...
Ой, 20, Господи, что я говорю, какие 20 лет назад...
7—8 лет назад занимались квартирным вопросом.
Меняли квартиру, был довольно сложный обмен.
В результате, нужно было оформлять документы.
Их можно было бы оформлять либо быстро, и тогда это одна стоимость на всех
вовлеченных сторон, или долго, и тогда это гораздо меньшая стоимость.
Мы никогда не торопились, те стороны торопились.
Маклер, который вел наше дело, сказал: «ну, нормально, как бы,
для этого мы давно уже вывели соответствующие формулы.
Вот вам формула».
И выдаёт вектор Шепли в чистом виде,
говорит: «вы платите половину вот за этот период, который, как бы,
никто не торопится, а они половину эту плюс целиком за разницу двух периодов».
Я очень удивился и говорю: «слушайте, это вот прям по теории.
А можно спросить, говорю, тебя, что будет, если будет три вовлеченных группы,
вот, и что тогда у нас будет?» Вот у нас три вовлеченных группы, допустим,
и вот там какие-нибудь модельные данные ему предожил.
Он говорит: «да, это мы тоже думали об этом, и тоже решили,
что будем делить так», и снова выписывает эту формулу.
То есть эта формула, теоретически оправданная с помощью Ллойда Шепли,
на самом деле приходит в голову, если долго думать о проблеме,
то есть, здесь математика привнесла лишь то, что этот вектор лежит в ядре,
и, соответственно, его ни одна коалиция не оспорит.
А его внешний вид, в общем-то, понятен, то есть он вполне честный.
Вот этот участок делить поровну, следующий поровну между использующими, и так далее.
Надо сказать,
что к подобной же формулировке, к подобной же математической модели,
сводится еще несколько чисто жизненных игр.
Я приведу сейчас ряд примеров таких игр.
Первая игра называется «Коттеджный посёлок».
Есть некоторая трасса,
скоростная трасса там типа М-1, М-2 и так далее.
Вдоль неё в какой-то момент выстраивают...
перпендикулярно к ней выстраивается в некоторый момент какой-то коттеджный
посёлок, вот эти коттеджики стоят.
И вот здесь всё разбито ремонтом.
Встаёт вопрос о том, чтобы построить дорогу.
Асфальтировать вот эту дорогу.
Как распределить ресурсы между этими коттеджами?
Ну, вроде как этот коттедж скажет, наверное, что, ну, то есть, как бы
конфликт здесь можно усмотреть — вот этот коттедж будет говорить: «да ладно,
я вообще не буду ничего делать, вы сами всё сделаете».
А вот этот скажет: «да давайте просто поровну разобьём между всеми».
То есть, здесь возникнет конфликт, а, если бы — да, и на моих глазах, на самом деле,
такой конфликт возникал в некоторой, значит, ситуации.
Но если бы, если знать теорию игр кооперативную, то конфликта не возникнет,
потому что вот эту часть дороги поделят поровну между всеми,
следующую часть поровну между оставшимися,
и так далее вплоть до последнего участка, который уже оплатит вот этот один.
Это чисто полностью эквивалентная вот этой задача.
Подобная же задача — это задача про лифты.
Открывается новый дом и нужно обслуживать лифты.
В принципе, можно было бы с тех, кто живет на первом этаже, брать значительно меньше,
чем с тех, кто живет на десятом, потому что тоже, чем выше, да, тем больше,
больше лифт проезжает до тебя, то есть, вот это вот обслуживание, можно считать,
оставшегося вот этого вот участка, тоже требует дополнительных ресурсов,
но здесь я никогда не видел, чтобы так было, дело обстояло,
то есть, никогда не видел, чтоб к лифтам применялась эта формула.
Ну, скажем, в доме, в котором я живу, она так не применяется.
Делится стоимость обслуживания лифтов на метраж квартиры,
а не на этаж, в частности, вот те, кто на втором этаже,
они вообще могут этим лифтом не пользоваться, но они платят столько же.
Ну, а самая великолепная история на тему вектора Шепли вот в этой
ситуации случилась в Улан-Удэ с одним моим знакомым.
Речь шла о том, чтобы провести
водопровод в гору.
Вдоль горы стояли, опять же, домики.
Были известны стоимости проведения водопровода до каждой вот из этой точки.
До каждой вот этой точки.
Друг жил здесь.
Друг этой формулы в этот момент не знал.
И он каким-то образом смог сделать так, что
вся стоимость подъема воды до самого конца была распределена поровну между всеми.
В частности, конкретные цифры, внимание, 1 700
000 рублей было потрачено на этот водопровод,
и каждый из этих домиков — их было десять — заплатил 170 000.
В частности, 170 000 заплатил вот этот домик, до которого
провести воду стоило 69 000 рублей.
То есть, вот этот человек, даже если бы он просто себе провел воду,
заплатил бы на 100 000 меньше,
чем оказалась его доля по расчетам математическим моего друга.
Ну вот, так сказать, что называется, добро пожаловать в Бурятию!
Бывают очень интересные истории там такие.
Ну, а по сути, видимо, на самом деле, как это объяснимо: ну, наверное,
эти люди друг друга хорошо знали, и всем было, как бы, ну, в падлу, да,
тут торговаться о чем-то, то есть, вот.
Такие забавные приложения теории игр к практике.
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.
© 2019 Coursera Inc. Todos los derechos reservados.
