Разработанный МФТИ курс отличается тем, что все основные конструкции и принципы теории вводятся непосредственно на основе разбираемых "с нуля" конкретных этюдов. Каждый этюд начинается с понятной непрофессионалу проблемы. В одних случаях это просто "детская игра", в других - формализованное жизненное наблюдение, в третьих - обобщённая социальная закономерность. Сюжет затем разворачивается, исходя из логики содержащегося в нём конфликта, и сам порождает тот или иной принцип разрешения конфликта, который окончательно строго формализуется в виде решения игры. Этюдов всего рассмотрено чуть более десяти, и они в совокупности покрывают основные формальные конструкции базовой теории игр. В нескольких отступлениях приведены формулировки теорем существования игровых решений с набросками доказательств.
Супермодулярные кооперативные игры
Loading...
來自 Moscow Institute of Physics and Technology 的課程
Теория игр
32 個評分
從本節課中
Кооперативная теория игр. Ядро. Вектор Шепли
На этой неделе мы переходим к изучению кооперативной теории игр, понятию ядра и вектора Шепли.
與講師見面
Дмитрий Ильинскийпреподаватель
кафедра дискретной математики МФТИ
В свете всего сказанного до этого особый интерес представляют игры,
в которых концепции вектора Шепли и концепции ядра согласованы друг с другом.
То есть в которых, грубо говоря, есть гарантия того, что вектор Шепли всегда
попадает в ядро, потому что тогда можно взять этот вектор Шепли,
предложить всем раздать его и сказать: «Ну смотрите, как естественно он получается,
а кроме того, посмотрите, никто из вас не хочет протестовать против него».
Значит, есть такой класс один игр, наиболее известный,
называется «супермодулярные игры».
Супермодулярные кооперативные игры.
Я тут подчеркиваю «кооперативные», потому что есть еще
супермодулярные игры стратегические, которые совершенно
другую смысловую нагрузку несут, и их ни в коем случае нельзя путать с этими.
Это два совершенно разных класса из разных, так сказать, областей знания.
Итак, определение,
определение-теорема, определение,
черточка, теорема.
Следующие 2
свойства игры эквивалентны.
Игры v из IR в степени 2 в степени N, то есть вектора длины 2 в степени N,
который предписывает каждой коалиции, каждому подмножеству,
некоторый выигрыш, который этим подмножеством может быть достигнут.
Так вот, следующие 2 свойства такого вектора кооперативной
игры эквивалентны друг другу,
эквивалентны, двоеточие.
Первое свойство: для
любого игрока
i и также,
а также для любой пары вот
таких вот подмножеств,
то есть для любой пары вложенных друг в друга коалиций, одна шире другой,
причем i не принадлежит даже большей из них, тем более — меньшей тоже.
Так вот, для любой вот такой вот тройки i, T, S,
где T вложено в S и i не принадлежит S,
v от [S ∪ i],
то есть если я присоединил к S i,
вот этот вот значок (∪) часто используется в кооперативной теории игр,
он обозначает дизъюнктное объединение, то есть когда к
множеству прибавляется какое-то множество, которое с ним никак не пересекается.
Так вот, выигрыш вот такой новой коалиции за
вычетом выигрыша старой не меньше,
то есть разница, то, что привнес i-тый игрок в
коалицию S не меньше, чем то, что он привнес в коалицию T.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] Итак,
игроки привносят больший выигрыш в большие по включению коалиции.
А второе свойство, эквивалентное вот этому, состоит в том,
что для любых произвольно взятых коалиций
S и T, выигрыш,
который достигается объединением, тут я уже не пишу дизъюнктное,
потому что оно совершенно произвольное — эти могут пересекаться, и более того,
тут как раз записано: сумма
выигрышей объединенных коалиций и пересеченных друг с другом.
То есть выигрыш, которого могут добиться объединенные коалиции плюс выигрыш,
которого могут добиться члены обоих коалиций одновременно, не меньше,
чем выигрыш S плюс выигрыш T.
Упражнение.
Доказать эквивалентность эти двух свойств.
Так вот, определение-теорема.
Игра, обладающая этими свойствами, ну любым из них, а соответственно,
и вторым тоже, обладающая
свойствами 1, 2,
называется супермодулярной.
[БЕЗ СЛОВ] На самом деле, я немножко приоткрою завесу,
я не буду углубляться в это, в эту область знания: есть такая теория решеток,
упорядоченных множеств с некоторыми добавочными аксиомами.
И множество всех подмножеств любого множества — это решетка.
Даже так называемая полная решетка, это я так просто для тех,
кто сильно интересуется разными смежными областями.
И есть понятие супермодулярной функции на решетке.
Так вот, любая игра — это функция на решетке,
потому что она каждому подмножеству сопоставляет число.
И супермодулярная игра — это просто супермодулярная функция относительно,
соответственно, свойства решетки,
решетчатых свойств множества всех подмножеств, множества коалиций.
Вот. То есть мы,
мы не будем дальше разрабатывать эту тему,
но просто на самом деле понятие супермодулярности здесь согласовано с
понятием супермодулярности в теории решеток полностью.
Ну вот.
Значит, что же можно сказать про супермодулярные кооперативные игры?
А вот что можно сказать.
Основная теорема [БЕЗ
СЛОВ] о супермодулярных играх.
Кстати, иногда вот так вот
записывают: SMD-игра, супермодулярная.
Звучит она так.
Доказывать я ее не буду, но тем не менее, ее очень полезно знать,
она входит в необходимый минимум теоретика-игровика.
Пусть v — SMD-игра,
супермодулярная игра.
Тогда для любого упорядочения
игроков σ из группы
всех перестановок на n символах,
для любого упорядочения игроков дележ Шепли,
дележ Шепли для этого упорядочения σ,
то есть тот дележ, который входит в сумму Шепли, сумма Шепли — это сумма по всем n!
дележам, деленная на n!.
Так вот, дележ Шепли для σ принадлежит ядру игры.
Ну и понятно, в частности, это означает, что ядро не пусто,
потому что дележ Шепли для любого упорядочения можно построить.
И более того,
эти дележи,
эти дележи
порождают ядро.
Ядро в смысле выпуклого анализа,
то есть ядро игры является
выпуклой оболочкой, выпуклой
оболочкой n!
этих дележей.
Итак, если у нас есть супермодулярная игра, тогда,
как бы вы ни выстроили игроков в некоторый линейный порядок и запустили их,
выдали каждому причитающееся ему: первый зашел — получил свое,
второй зашел — получил разность между их парой и предыдущим, и так далее.
Любой такой дележ принадлежит ядру.
В частности, ядро уже не пусто.
Это первое утверждение.
Второе утверждение заключается в том, что, грубо говоря, больше в ядре ничего нет.
Ну то есть ядро как выпуклое множество, естественно,
должно содержать все их комбинации, так вот только их оно и содержит.
Ну и в этом можно сказать тогда,
что вектор Шепли лежит в центре ядра в том смысле,
что он является комбинацией вот этих вершин с равными коэффициентами: 1 / n!
сумма всех дележей.
Но тут надо быть осторожным.
Дело в том, что никто не застрахован от того,
когда некоторые дележи попадают уже в выпуклую комбинацию некоторых других.
Скажем, ядро не обязано быть шестиугольником,
ну может быть четырехугольником.
Например, если игроков 3, то ядро, самое большое,
будет шестиугольником, потому что у нас шесть дележей максимум.
Но иногда оно будет вырождаться в четырехугольник, в треугольник,
и тогда какие-то дележи будут либо повторять какие-то старые,
либо лежать внутри выпуклой оболочки, и тогда уже нельзя будет сказать, что,
грубо говоря, что вектор Шепли лежит в самом центре ядра,
потому что это не очень определенное понятие.
Вектор Шепли — это просто комбинация с равными весами всех дележей,
но некоторые дележи попадают внутрь, некоторые — на границы.
Но в любом случае понятно, что вектор Шепли,
будучи выпуклой комбинацией, попадает внутрь ядра выпуклого множества.
Так что особый интерес представляют супермодулярные игры.
Среди игр, которые мы рассматривали до этого,
супермодулярной является первая игра.
Самая первая — подземные музыканты с теми выигрышами,
которые мы вначале им приписали.
