Как находить вектор шепли (3 видео) | Курс школьной геометрии

Вектор Шепли

В этом параграфе мы отдельно рассмотрим еще один подход к поиску оптимальных решений кооперативных игр, предложенный Л. Шепли и ставший на сегодняшний день наиболее распространенным на практике. Этот подход основан на принципе «справедливого дележа» исходя из вклада каждого игрока в выигрыш коалиции.

Вкладом /-го игрока называется величина v(K,) — v <K/i),где v — характеристическая функция кооперативной игры. То есть вклад игро- [1]

ка — это приращение выигрыша коалиции при его участии по сравнению с выигрышем коалиции без этого игрока.

Вектор Шепли, или значение Шепли (Shapley value) Ф(г) =(Фь Ф„), представляет собой распределение, в котором выигрыш каждого игрока Ф, равен его среднему вкладу в соответствующие коалиции К. В форме, практически реализуемой для расчетов, значение Шепли для каждого игрока имеет вид

где п — число игроков;

к — число участников коалиции К.

Вектор Шепли удовлетворяет следующим свойствам (аксиомы Шепли).

1. Линейность (аксиома агрегации). Ф(г) представляет собой линейный оператор, т.е. для любых двух игр с характеристическими функциями и и со:

для любой игры с характеристической функцией v и для любого а

Это свойство показывает, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.

2. Симметричность (аксиома симметрии). Получаемый игроком выигрыш не зависит от его номера. Это означает, что если игра со получена из игры v перестановкой игроков, то ее вектор Шепли Ф(со) есть вектор Ф(и) с соответствующим образом переставленными элементами. То есть игроки, одинаково входящие в игру, должны получать одинаковые выигрыши.
3. Аксиома эффективности. При распределении общего выигрыша не должно выделяться ничего «бесполезному игроку», не вносящему вклада ни в какую коалицию. В теории кооперативных игр такой игрок называется болваном, т.е. для такого игрока i для любой коалиции К, содержащей /, выполняется v(K) — v( К/i) = 0 и соответственно Ф,=0. Благодаря этому свойству вектор Шепли позволяет полностью распределить имеющийся в распоряжении тотальной коалиции выигрыш, т.е. сумма компонент вектора Ф(и) равна v(N). Иными словами, при разделении общего выигрыша коалиции ничего не выделяется на долю «посторонних» игроков, не принадлежащих этой коалиции, но и ничего не взимается с них.

Приведем пример игры с «болваном». В игре трех лиц характеристические функции определяются следующим образом: г(1) = 0;

г(2)=г>(3) = 1;г>(12)=г(13) = 1; г(23) = 3; ь'(123) = 3. Вэтой игре игрок 1 — «болван».

Доказано (теорема Шепли), что для любой кооперативной игры существует единственное распределение выигрыша, удовлетворяющее аксиомам 1—3, и это распределение — вектор Шепли. Если вектор Шепли принадлежит с-ядру, то этот дележ одновременно справедлив и устойчив, но вектор Шепли может и не принадлежать непустому с-ядру.

Пример 4.2. Четыре акционера имеют следующее количество акций: 10, 20, 30 и 40 соответственно. Любое решение утверждается акционерами, имеющими в сумме большинство акций (> 50). Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырех игроков, в которой выигрывающими коалициями являются следующие: , , , , , , . Необходимо найти оптимальный дележ выигрыша между акционерами.

Найдем вектор Шепли для этой игры. Вначале рассмотрим все коалиции, выигрывающие с игроком 1, но не выигрывающие без него. Имеется только одна такая коалиция: , поэтому вектор Шепли для этого игрока содержит всего одно слагаемое. В данной коалиции три игрока, и вектор Шепли для игрока 1 определяется как

Далее определяем все выигрывающие коалиции, но не выигрывающие без игрока 2: , , . Поэтому

В результате получаем вектор Шепли

Отметим, что если считать распределение выигрыша среди акционеров традиционно, т.е. пропорционально количеству имеющихся у них акций, то получим следующее распределение: , отличающееся от вектора Шепли, в котором выигрыши игроков 2 и 3 равны, хотя игрок 3 имеет больше акций. Это получается из-за того, что возможности образования коалиций у игроков 2 и 3 одинаковы. Для игроков 1 и 2 выигрыши соответствуют их различию в количестве имеющихся акций.

Содержание

Как всем пережениться (одно-, дву- и трёхполые браки) с точки зрения математики и почему мужики всегда в выигрыше
Об устойчивом бракосочетании
Процедура Гейла-Шепли
Однополые браки
Вектор Шепли
Кооперативные игры
💥 Видео

Видео:Теория Игр. Решения коалиционных игр вектор Шепли 73Скачать

Как всем пережениться (одно-, дву- и трёхполые браки) с точки зрения математики и почему мужики всегда в выигрыше

В 2012 году Нобелевскую премия по экономике выдали Ллойду Шепли и Элвину Роту. «За теорию стабильного распределения и практики устройства рынков». Алексей Савватеев в 2012 году попытался просто и понятно рассказать в чем суть заслуг математиков. Предлагаю вашему вниманию конспект видеолекции.

Сегодня будет теоретическая лекция. Про эксперименты Эла Рота, в частности с донорством, я не буду рассказывать.

Когда объявили, что Ллойд Шепли (1923-2016) получил нобелевку, был стандартный вопрос: «Как!? Он ещё жив. » Самый знаменитый его результат был получен в 1953 году.

Формально, премию дали за другое. За работу 1962 года за «теорему об устойчивом бракосочетании»: «Приём в колледжи и стабильность брака» (College Admission and the Stability of Marriage).

Об устойчивом бракосочетании

Matching (мэтчинг) — задача о нахождении соответствия.

Есть некая изолированная деревня. Там «m» молодых людей и «w» девушек. Нужно их друг на друге переженить. (Не обязательно одинаковое количество, может в итоге кто-то останется один.)

Какие нужно сделать предпосылки в модели? Что не просто наугад переженить. Делается некий шаг в сторону свободного выбора. Допустим есть мудрый аксакал, который хочет так переженить, чтоб после его смерти не начались разводы. (Развод, это ситуация, когда муж хочет в жены стороннюю женщину больше, чем жену.)

Эта теорема в духе современной экономики. Она исключительно бесчеловечна. Экономика традиционно бесчеловечна. В экономике человек заменен на машину по максимизации прибыли. То что я буду рассказывать — совершенно безумные вещи с точки зрения морали. Не принимайте близко к сердцу.

Экономисты смотрят на брак так.
m₁, m₂,… m_k — мужчины.
w₁, w₂,… w_L — женщины.

Мужчина отождествляется с тем, как он «упорядочивает» девушек. Есть ещё и «нулевой уровень», находясь ниже которого, женщинам вообще нельзя предлагаться в жены, даже если других нет.

Всё происходит в обе стороны, у девушек то же самое.

Начальные данные произвольные. Единственное предположение/ограничение — мы не меняем своих предпочтений.

Теорема: Независимо от распределения и уровня нуля, всегда существует способ установить взаимно однозначное соответствие между частью мужчин и частью женщин, так, что оно будет устойчиво по отношению к любым видам расколов (не только разводов).

Какие могут быть угрозы?

Есть пара (m,w), которая не находится в браке. Но для w текущий муж хуже чем m, а для m текущая жена хуже, чем w. Это неустойчивая ситуация.

Есть еще вариант, что кого-то женили на том, кто «ниже нуля», в этой ситуации тоже брак распадется.

Если женщина в браке, но ей больше нравится неженатый, для которого она выше нуля.

Если два человека, оба не в браке, и оба друг для друга «выше нуля».

Утверждается, что для любых начальных данных такая система браков существует, устойчивая ко всем видам угроз. Во-вторых, алгоритм нахождения такого равновесия очень прост. Соизмерим с M*N.

Эту модель обобщили и расширили до «многоженства» и применили во многих областях.

Процедура Гейла-Шепли

Если все мужчины и все женщины будут выполнять «предписания», то результирующая система бракосочетания окажется устойчивой.

Предписания.
Берем несколько дней, сколько понадобится. Каждый день разбиваем на две части (утро и вечер).

В первое утро каждый мужчина отправляется к своей самой лучшей женщине и стучится в окошко, предлагая ей выйти за него замуж.

Вечером того же дня ход переходит к женщинам.Что может обнаружить женщина? Что под окном у неё толпа, либо один, либо ни одного мужчины. Те, у кого никого не оказалось сегодня, пропускают ход, ждут. Остальные, у кого есть хотя бы один, проверяют пришедших мужчин на то, что они «выше уровня нуля». Чтобы был хотя бы один. Если совсем не повезло и все ниже нуля, тогда всех надо послать. Женщина выбирает максимального из пришедших, говорит ему подождать, а остальных посылает.

Перед вторым днем ситуация такая — у некоторых женщин сидит один мужчина, у некоторых ни одного.

Во второй день всем «свободным» (посланным) мужчинам нужно идти ко второй по приоритету женщине. Если такой нет, то мужчина объявляется холостым. Тем мужчинам, которые уже сидят у женщин, пока ничего не делают.

Вечером женщины смотрят на ситуацию. Если к тому кто уже сидел присоединился более приоритетный, то менее приоритетного отправляют прочь. Если пришедшие ниже, чем уже имеющийся — все отсылаются. Женщины каждый раз выбирают максимальный элемент.

В итоге, каждый мужчина перебрал весь список своих женщин и либо остался один, либо заангажирован у какой-то женщины. Тогда мы всех женим.

Можно ли прогнать весь этот процесс, но чтоб женщины бегали к мужчинам? Процедура симметричная, но решение может быть другим. Но вот вопрос, кому от этого лучше?

Теорема. Рассмотрим не только эти два симметричных решения, но множество всех устойчивых систем бракосочетания. Исходный предложенный механизм (мужчины бегают, а женщины соглашаются/отказываются) приводит к системе бракосочетаний, которая лучше для любого мужчины, чем любая другая и хуже, чем любая другая для любой женщины.

Однополые браки

Рассмотрим ситуацию с «однополыми браками». Рассмотрим математический результат, который ставит под сомнение необходимость их легализовать. Идеологически некорректный пример.

Рассмотрим четырёх гомосексуалистов a, b, c, d.

приоритеты для a: bcd
приоритеты для b: cad
приоритеты для c: abd
для d не имеет значение как он ранжирует оставшихся трёх.

Утверждение: в этой системе нет устойчивой системы бракосочетаний.

Сколько есть систем для четырёх людей? Три. ab cd, ac bd, ad bc. Пары будут разваливаться и процесс зациклится.

«Трёхполые» системы.
Это важнейший вопрос, который открывает целую область математики. Этим занимался мой коллега в Москве — Владимир Иванович Данилов. «Брак» он рассматривал как распитие водки и роли были такие: «разливающий», «говорящий тост» и «тот, кто нарезает колбасу». В ситуации, когда представителя каждой роли 4 и больше — невозможно решить перебором. Вопрос об устойчивой системе — открытый.

Вектор Шепли

В коттеджном поселке решили заасфальтировать дорогу. Нужно скинуться. Как?

Шепли в 1953 году предложил решение этой задачи. Предположим ситуацию конфликта с группой лиц N=. Нужно разделить издержки/выигрыши. Допустим люди сообща сделали что-то полезное, продадут и как разделить прибыль?

Шепли предложил при дележе руководствоваться тем, сколько могли бы получить те или иные подмножества этих людей. Сколько денег смогли бы заработать все 2 N непустых подмножества. И на основе этой информации Шепли написал универсальную формулу.

Пример. Солист, гитарист и барабанщик играют в подземном переходе в Москве. Втроем они зарабатывают 1000 рублей в час. Как её делить? Можно поровну.
V(1,2,3)=1000

Предположим, что
V(1,2)=600
V(1,3)=450
V(2,3)=400
V(1)=300
V(2)=200
V(3)=100

Справедливый дележ невозможно определить до тех пор, пока мы не знаем, какие выигрыши ждут ту или иную компанию, если она отсоединится и будет действовать самостоятельно. А когда мы определили числа (задали кооперативную игру в характеристической форме).

Супераддитивность — это когда вместе зарабатывают больше, чем по отдельности, когда выгоднее объединиться, но непонятно как разделить выигрыш. По этому поводу сломано много копий.

Есть игра. Три бизнесмена одновременно нашли месторождение на 1 млн долларов. Если они втроем договорятся, то миллион их. Любая пара может замочить (отстранить от дела) и весь миллион получить себе. А в одиночку никто ничего не может. Эта страшная кооперативная игра, в которой нет решения. Всегда найдутся такие двое, что они смогут устранить третьего… Кооперативная теория игр начинается с примера, который не имеет решения.

Мы же хотим такое решение, что никакая коалиция не захочет блокировать общее решение. Множество всех дележей, которые нельзя блокировать — это ядро. Бывает что ядро — пустое. Но даже если не пустое, как же делить?

Шепли предлагает делить так. Киньте монету с n! гранями. В этом порядке выписываем всех игроков. Допустим, первый барабанщик. Он заходит и берет свои 100. Дальше заходит «второй», допустим, солист. (Вместе с барабанщиком они могут заработать 450, барабанщик уже взял 100) Солист берет 350. Входит гитарист (вместе 1000, -450), берет 550. Последний вошедший довольно часто бывает в выигрыше. (Супермодулярность)

Если мы для всех порядков выпишем:
ГСБ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
СГБ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
СБГ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
БСГ — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
БГС — (выигрыш С) — (выигрыш Г) — (выигрыш Б)
ГБС — (выигрыш С) — (выигрыш Г) — (выигрыш Б)

И по каждому столбцу сложим и поделим на 6 — усреднение по всем порядкам — это вектор Шепли.

Шепли доказал теорему (примерно): Есть такой класс игр (супермодулярные), в которых следующий вошедший в большую команду — он привнёс в неё больший выигрыш. Ядро всегда не пусто и является выпуклой комбинацией точек (в нашем случае 6 точек). Вектор Шепли лежит в самом центре ядра. Его всегда можно предложить в качестве решения, никто не будет против.

В 1973 году было доказано, что задача с коттеджами — супермодулярна.

Дорогу до первого коттеджа делят все n человек. До второго — n-1 человек. И тд.

В аэропорту есть взлетная полоса. Разным компаниям нужна разная длина. Возникает та же самая задача.

Думаю что те кто выдавал Нобелевскую премию имели ввиду и эту заслугу, а не только задачу марьяжа.

Видео:Теория Игр. Вектор Шепли 74Скачать

Кооперативные игры

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N =<1, 2, . n>, а через S – любое его подмножество. Пусть игроки из S договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r , то есть , а число всевозможных коалиций равно

= 2n – 1.

Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множество игроков S действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.

Функция u, ставящая в соответствие каждой коалиции S наибольший, уверенно получаемый его выигрыш u(S), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков u(S) может получиться, когда игроки из множества S оптимально действуют как один игрок против остальных NS игроков, образующих другую коалицию (второй игрок).

Характеристическая функция u называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция u простая, то коалиции S, для которых u(S)=1, называются выигрывающими, а коалиции S, для которых u(S) = 0, – проигрывающими.

Если в простой характеристической функции u выигрывающими являются те и только те коалиции, которые содержат фиксированную непустую коалицию R, то характеристическая функция u, обозначаемая в этом случае через uR, называется простейшей.

Содержательно простые характеристические функции возникают, например, в условиях голосования, когда коалиция является выигрывающей, если она собирает более половины голосов (простое большинство) или не менее двух третей голосов (квалифицированное большинство).

Более сложным является пример оценки результатов голосования в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член, и только они.

Простейшая характеристическая функция появляется, когда в голосующем коллективе имеется некоторое “ядро”, голосующее с соблюдением правила “вето”, а голоса остальных участников оказываются несущественными.

Пусть коалиции как-то образованы. Тогда возникает вопрос: как делить общий выигрыш с учетом веса каждой коалиции между ее членами?

Естественно положить в основу анализа кооперативной игры принцип оптимального распределения максимального выигрыша u(S) между сторонами .

Реализация этого принципа приводит к рассмотрению С-ядра − множество недоминируемых «вполне устойчивых» дележей кооперативной игры.

Вектор x = (x1, . xn), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции u.

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi выигрыш i—го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

т. е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности

= u(N) (2)

т. е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем u(N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

Система <N, u>, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Делёж x доминирует y, если существует такая коалиция S, для которой делёж x доминирует y. Это доминирование обозначается так: x > y.

Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y. Соотношение доминирования возможно не для всякой коалиции. Так невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

Любой дележ из С-ядра устойчив, в том смысле, что ни одна из коалиций не имеет ни желания, ни возможности изменить исход игры.

Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции S выполнялось неравенство .

С-ядро может оказаться пустым, например, когда есть слишком сильные коалиции. Если С-ядро пусто, то требования всех коалиций одновременно не могут быть удовлетворены.

Пример. Найти С-ядро в кооперативной игре 3-х сторон, если максимальные гарантированные выигрыши всевозможных в данном случае семи коалиций () следующие:

u(1, 2, 3)=9, u(2, 3)=7, u(1, 3)=4, u(1, 2)=4, u(1) =u(2) =u(3) =0.

Воспользуемся утверждением, раскрывающим метод построения С-ядра как множества недоминируемых дележей, т. е. для того, чтобы дележ x(S) принадлежал С-ядру необходимо и достаточно выполнения неравенств:

, S N,

где xi − доля i-ой стороны;

i Î S, такая, что должно выполняться требование xi ³ u(i), i=1, 2, 3.

Составим соотношения (4 уравнения для 3 неизвестных):

Для нахождения x1, x2, x3 получаем следующие системы из 3-х неизвестных: