№ | Слайд | Текст |
1 |
 |
Маршрутизация и парадокс заключенногоДмитрий Трофимов, Владимир Полевиков 26 октября 2006г. |
2 |
 |
План докладаВведение Примеры Формальные определения Границы цены анархии Уменьшение цены анархии 2 / 57 |
3 |
 |
ВведениеЧто происходит, когда каждый участник некоторого процесса в системе действует «сам за себя»? Оптимально ли это для системы, и выгодно ли это самим участникам при большом их количестве? 3 / 57 |
4 |
 |
ВведениеСамостоятельная (или «эгоистичная») маршрутизация (selfish routing) – режим распределения нагрузки в многопользовательских сетях. Каждый пользователь организует свой маршрут, руководствуясь собственными интересами, независимо от других. 4 / 57 |
5 |
 |
Области примененияУказанная модель поведения на практике встречается в таких областях, как: Компьютерные сети Дорожные сети Экономические процессы 5 / 57 |
6 |
 |
Цена анархииРезультат «эгоистичной» маршрутизации зачастую бывает значительно неэффективным. «Цена анархии» (The Price of Anarchy) - количественная мера такой неэффективности. 6 / 57 |
7 |
 |
План докладаВведение Примеры Формальные определения Границы цены анархии Уменьшение цены анархии 7 / 57 |
8 |
 |
Парадокс заключенногоИграют два игрока и банк У каждого игрока на руках по две карты: «кооперируюсь» и «отказываюсь» Каждый игрок выбирает одну карту так, чтобы не видел другой игрок Выигрыш каждого игрока зависит от выбора карт обоими игроками 8 / 57 |
9 |
 |
Парадокс заключенногоВозможные исходы Оба сыграли «кооперируюсь»: каждый получает 300 долларов от банка. Оба сыграли «отказываюсь»: каждый штрафуется на 10 долларов Один сыграл «кооперируюсь», второй – «отказываюсь»: первый штрафуется на 100 долларов, второй получает 500. Как бы сыграли вы в этой ситуации? 9 / 57 |
10 |
 |
Парадокс заключенногоНезависимо от выбора другого игрока, всегда выгодно играть «отказываюсь»! (потеря 10 долларов при отказе второго игрока и выигрыш 500 при его кооперации, против потери 100 или выигрыша 300 в случае вашей кооперации) Если играют два незнакомых между собой «рационально мыслящих» игрока, оба всегда останутся в минусе (при том, что оба могли получить по 300 долларов каждый) 10 / 57 |
11 |
 |
Другие примерыПарадокс заключенного наглядно показывает, что действующие несогласованно участники могут делать свой выбор не лучшим образом. Далее мы рассмотрим два важных примера неэффективных сетей, и на основе этих примеров – получим оценку неэффективости. 11 / 57 |
12 |
 |
Пример Пигу (Pigou)Задана сеть из двух вершин – источника и стока, и двух параллельных ребер между ними. По сети необходимо пропустить единицу нагрузки (трафика), распределенную между большим количеством независимых пользователей. Цена ребра зависит от нагрузки на него. 12 / 57 |
13 |
 |
Пример Пигу (Pigou)Пример Пигу с линейной стоимостью (слева), и с полиномиальной стоимостью (справа) c(x) – функция стоимости ребра от нагрузки на него 13 / 57 |
14 |
 |
Линейный пример ПигуОчевидно, что нижний путь никогда не бывает дороже верхнего (и строго дешевле, если хоть кто-то выберет верхний путь) Следовательно, все пользователи выберут нижний путь. Итого, стоимость пути каждого пользователя – 1. Существует ли лучшее решение? 14 / 57 |
15 |
 |
Линейный пример ПигуПредположим, что мы можем централизованно управлять маршрутами пользователей. Направим половину пользователей по верхнему пути, остальных – по нижнему. Наихудшая стоимость пути для отдельного пользователя – 1 (то есть, никому хуже не стало) Средняя стоимость – (1/2)·1 + (1/2)·(1/2) = 3/4 15 / 57 |
16 |
 |
Нелинейный пример ПигуВ нелинейном случае все гораздо хуже… В самостоятельном режиме все вновь выберут нижний путь, средняя стоимость – 1. Направим ? пользователей по верхнему пути, остальных (1-?) – по нижнему. Средняя стоимость - ?+(1-?)p+1 – с ростом p стремится к нулю при ??0. 16 / 57 |
17 |
 |
Цена анархии в примере ПигуОпределим «цену анархии» как отношение стоимости, полученной в самостоятельном режиме, к минимальной возможной стоимости. Цена анархии примера Пигу – 4/3 в линейном случае, и неограниченно растет с увеличением p – в нелинейном. 17 / 57 |
18 |
 |
Цена анархии в примере ПигуВозникает ряд важных вопросов: Может ли цена анархии быть высока при линейных стоимостях? Растет ли цена анархии с увеличением сложности сети? Выше ли цена анархии в сетях с несколькими парами «источник-сток»? Ответ на все три вопроса – «нет», это будет показано далее. 18 / 57 |
19 |
 |
Парадокс Браеса (Braess)«Парадокс Браеса» – еще один неожиданный пример возможной неоптимальности нагрузки. Задана сеть из двух вершин – источника и стока, и двух промежуточных вершин между ними. Пытаясь как-то улучшить ситуацию, мы добавляем «бесплатное» ребро между промежуточными вершинами. 19 / 57 |
20 |
 |
Парадокс БраесаПример Браеса: пытаясь улучшить обстановку в сети (слева), мы добавляем ребро нулевой стоимости (справа). Как изменится средняя стоимость в результате? 20 / 57 |
21 |
 |
Парадокс БраесаДо добавления ребра оба пути равноценны, пользователи делятся поровну между ними со средней стоимостью 3/2. Что изменилось после добавления ребра? Посмотрим на маршрут s?v?w?t. Его стоимость – 2·x, что не хуже любого из первоначальных (1+x) при любой степени нагрузки (и строго лучше, если хоть кто-то выбрал один из первоначальных) Следовательно, теперь всем пользователям выгодно выбрать именно этот маршрут! Средняя стоимость в этом случае стала равной 2. 21 / 57 |
22 |
 |
Парадокс БраесаДобавление ребра (постройка дороги) нулевой стоимости лишь ухудшило результат... Получается, что улучшить транспортную ситуацию в некоторых сетях можно, не только не прокладывая новых ребер, но и просто удалив часть имеющихся! Можно ли удалением ребер в более сложных сетях, или в сетях с нелинейными функциями на ребрах снизить стоимость в большее число раз, чем это возможно для простых сетей? 22 / 57 |
23 |
 |
План докладаВведение Примеры Формальные определения Границы цены анархии Уменьшение цены анархии 23 / 57 |
24 |
 |
Сети и потокиВспомним понятие потоков в сетях Сеть задается графом G=(V,E) и множеством из k пар «источников» и «стоков» – вершин s1..k и t1..k Pi – множество вершинно простых путей из si в ti P – объединение всех Pi Предполагаем, что Pi непусто 24 / 57 |
25 |
 |
Сети и потокиПоток в сети G – вектор fp Для потока f и пути p из Pi – fp есть доля нагрузки из si в ti , использующая путь p. Поток на путях fp порождает поток на ребрах fe: fe = ?fp, по всем путям p из P, проходящим через ребро e. Общая величина нагрузки на каждой паре (si,ti) – вектор ri Поток называется допустимым, если он распределяет всю нагрузку r: для каждого i=1…k ?fp=ri, p из Pi 25 / 57 |
26 |
 |
Функции стоимостиДля моделирования негативного влияния повышенной нагрузки на сеть введем на ребрах функцию стоимости от нагрузки ce(x) ce(x) – неотрицательна, непрерывна, неубывающая. Сеть с самостоятельной маршрутизацией задается тройкой (G,r,c) – графом, величиной нагрузки и функциями стоимости. 26 / 57 |
27 |
 |
Равновесие Вардропа (Wardrop)При самостоятельной маршрутизации каждый участник стремится минимизировать стоимость своего собственного пути Допустимый поток f называется равновесием Вардропа, если для любой пары путей p и q, где fp > 0 (то есть путь p кем-либо используется), выполнено неравенство: cp(f) ? cq(f) где cp(f) определяется, как сумма стоимостей по всем ребрам из p. 27 / 57 |
28 |
 |
Равновесие Вардропа (Wardrop)Очевидно, что стоимости всех путей, которые используются уравновешенным потоком, равны. В любой сети (G,r,c) такое равновесие существует, и оно единственно. Стоимость С(f) допустимого потока f: C(f) = ?cp(f)fp, по всем путям p из P. Допустимый поток является оптимальным, если его стоимость минимальна среди всех допустимых потоков. 28 / 57 |
29 |
 |
Цена анархииЦена анархии сети (G,r,c): ?(G,r,c) = C(f) ? C(f*) где f – уравновешенный поток, а f* - оптимальный поток. В случае существования уравновешенного потока нулевой стоимости определяем цену анархии как 1. Цена анархии на множестве сетей X: ?(?) = sup ?(G,r,c) по всем сетям (G,r,c) из ? 29 / 57 |
30 |
 |
План докладаВведение Примеры Формальные определения Границы цены анархии Уменьшение цены анархии 30 / 57 |
31 |
 |
Границы цены анархииНасколько неоптимальным получается поток в сети с самостоятельной маршрутизацией? Пример Пигу и его нелинейный вариант показывают зависимость цены анархии от класса используемых функций стоимости. Далее мы попробуем получить верхнюю и нижнюю оценки цены анархии на разных классах функций. 31 / 57 |
32 |
 |
Граница ПигуДля любого множества C функций стоимости получим нижнюю оценку на основе примеров Пигу. Напомним, в чем заключается пример Пигу: 32 / 57 |
33 |
 |
Граница ПигуПусть C содержит все постоянные функции вида c(x) = a Выберем функцию стоимости нижнего ребра c2 из C и величину r ? 0 Подберем функцию стоимости верхнего ребра c1, равную везде c2(r) Цена анархии для такой сети: max (c2(r)r ? (c2(x)x + (r-x)c2(r))) Требование x?r не является обязательным из-за неубывания c2 0?x?r 33 / 57 |
34 |
 |
Граница ПигуВыбрав функцию c2 и величину r наихудшим возможным образом, получим нижнюю оценку цены анархии, известную как граница Пигу: ?(C) = sup (sup (c(r)r ? (c(x)x + (r-x)c(r))), x,r?0), по всем c из C при этом выражение 0/0 приравнивается по определению цены анархии к 1. Примеры оценок Для класса линейных функций: ?(C) = 4/3 Для класса полиномов с неотрицательными коэффициентами степени p: ?(C) = (1?p(p+1)?(p+1)/p)?1 34 / 57 |
35 |
 |
Граница ПигуТребование наличия всех константных функций в C можно заменить менее жестким требованием наличия в C хотя бы одной функции c, для которой c(0) > 0. В этом случае мы заменяем константную функцию с помощью добавления в сеть произвольного количества параллельных путей: В иных случаях нижняя оценка точно неизвестна 35 / 57 |
36 |
 |
Верхняя оценкаПолучим верхнюю оценку цены анархии Из определения границы Пигу: c(x)x ? c(r)r ? ?(C) + (x?r)c(r) для всех x, r ? 0, и для всех функций из C. Теорема. Для любой сети (G,r,c) с функциями из C: ?(G,r,c) ? ?(C) то есть, граница Пигу является также и верхней границей. 36 / 57 |
37 |
 |
Верхняя оценкаДля доказательства теоремы получим такой факт: Допустимый поток f в сети (G,r,c) является равновесием Вардропа в том и только в том случае, если выполнено: ?ce(fe)fe ? ? ce(fe)f*e для всех допустимых потоков f* в сети (G,r,c) Для доказательства утверждения запишем очевидное следствие из определения равновесия Вардропа: ?cp(f)fp ? ? cp(f)f*p для всех допустимых потоков f*. Раскрывая cp(f) по определению как ?ce(fe), и изменяя порядок суммирования, получаем требуемое. 37 / 57 |
38 |
 |
Верхняя оценкаДоказательство: Пусть f* - оптимальный поток, f - равновесие Вардропа. Тогда: c(f*) = ?ce(f*e)f*e ? (1??(C))?ce(fe)fe + ?(f*e?fe)ce(fe) ? c(f) ? ?(C) что и требовалось доказать. 38 / 57 |
39 |
 |
ИтогоМы получили точную оценку цены анархии для многих классов функций стоимости, в частности, для линейных функций цена анархии равна 4/3 Так как эта оценка достигается уже на простейших примерах, цена анархии никак не зависит от сложности сети, а зависит лишь от используемых функций стоимости. 39 / 57 |
40 |
 |
План докладаВведение Примеры Формальные определения Границы цены анархии Уменьшение цены анархии 40 / 57 |
41 |
 |
Оценка парадокса БраесаПриведенный в начале пример Браеса с сетью из 4 узлов – лишь «вершина айсберга»… Для более сложных сетей негативное влияние парадокса может быть сколь угодно велико 41 / 57 |
42 |
 |
Коэффициент БраесаВо сколько раз можно улучшить стоимость потока, удалив некоторые ребра из сети? Эта величина – коэффициент Браеса: ?(G,r,c) = max (C(f) ? C(fH)) где H – произвольный подграф G, содержащий путь из s в t, f и fH – уравновешенные потоки в сетях G и H соответственно. 42 / 57 |
43 |
 |
Коэффициент БраесаКоэффициент Браеса может расти с увеличением размера сети Теорема. Для любого n?2 существует сеть (G,r,c) из n вершин, такая что: ?(G,r,c) ? [n/2] Доказательство. Интерес представляют только случаи n = 2k+2 для натуральных k. Введем понятие графов Браеса. 43 / 57 |
44 |
 |
Графы БраесаГраф Браеса Bk=(Vk,Ek): Vk = {s,v1..k,w1..k,t} Ek = A U B U C A = {(vi,wi), i=1..k} B = {(vi,wi-1), i=2..k} U {(s,wk)} U {(v1,t)} C = {(s,vi),i=1..k} U {(wi,t), i=1..k} Граф Браеса B1 – исходный пример Браеса. 44 / 57 |
45 |
 |
Графы Браеса B2 и B3Примеры графов Браеса степеней 2 (слева) и 3 (справа) 45 / 57 |
46 |
 |
Графы БраесаОпределим функции стоимостей на ребрах разных типов: A: c(x) = 0 B: c(x) = 1 C: для ребер (wi,t) и (s,vk-i+1) c(k ? (k+1)) = 0, c(1) = i Построенная сеть (Bk,k,c) – худший случай для эффекта Браеса. (этот факт оставим без доказательства) 46 / 57 |
47 |
 |
Оценка коэффициента БраесаУравновешенный в сети (Bk,k,c) поток получается путем направления единицы нагрузки на каждый из k путей вида s?vi?wi?t Стоимость каждого такого пути – k+1 Если выбросить все ребра типа A, то по всем оставшимся k+1 путям пойдет доля нагрузки, равная k/(k+1) Стоимость каждого такого пути – 1 Коэффициент Браеса этой сети: ?(G,r,c) ? k+1 = n/2 что и требовалось доказать. 47 / 57 |
48 |
 |
Борьба с парадоксом БраесаМожно ли для данной сети с линейными функциями стоимости определить за полиномиальное время: надо ли в ней удалить какие-либо ребра, и если да, то какие? Если нельзя, то существует хотя бы приближенный алгоритм оценки коэффициента Браеса? Какой алгоритм очевиден, какое приближение он дает, и почему? 48 / 57 |
49 |
 |
Борьба с парадоксом БраесаОчевидный (хоть и бесполезный) алгоритм – отдающий на выход исходную сеть. Ошибется он не более чем в 4/3 раза, поскольку цена анархии не превышает границы Пигу, которая для линейных функций известна. Более точного алгоритма, работающего за полиномиальное время, не существует. 49 / 57 |
50 |
 |
Задача о двух путяхК сформулированной задаче сводится известная NP-полная задача о двух вершинно непересекающихся путях в графе: Пусть задан ориентированный граф G=(V,E) с различными вершинами s1,s2,t1,t2. Существует ли пара вершинно непересекающихся путей P1 и P2, из s1 в t1 и из s2 в t2 соответственно? 50 / 57 |
51 |
 |
Задача о двух путяхАлгоритмом для обнаружения парадокса Браеса можно было бы решить эту задачу: если такой пары путей не существует, то в изображенном графе алгоритм после исключения парадокса получит поток стоимости 3/2, иначе – лишь стоимости 2. 51 / 57 |
52 |
 |
Уменьшение цены анархииПрочие известные методы уменьшения цены анархии включают: Удешевление ребер Централизованное управление частью потока Введение дополнительной платы на ребрах 52 / 57 |
53 |
 |
Удешевление реберВажный результат: стоимость уравновешенного потока величины r не превышает стоимости оптимального потока в той же сети величины 2·r. Если мы заменим функции стоимости ce(x) на c'e(x) = ce(x/2)/2, то уравновешенный поток в новой сети (G,r,c') будет не хуже оптимального потока в исходной сети. Эффект такого удешевления функций тот же, что и от оптимальной «ручной» маршрутизации всех потоков в исходной сети. 53 / 57 |
54 |
 |
Централизованное управлениеНекоторую долю нагрузки мы можем распределять на наше усмотрение Однако, это может увеличить стоимость ребер за счет затрат на централизацию, что может свести на нет весь эффект. Плохой случай такого рода для нелинейного примера Пигу: c(x)=xp/(1-?) где 0 ? ?? 1 - доля управляемой нагрузки. 54 / 57 |
55 |
 |
Введение платы за ребраДаем некоторым ребрам дополнительную стоимость ?e, изменяя функции стоимости: c’e(x)=ce(x) + ?e Этим мы заставляем пользователей выбирать другие маршруты, но вводимая дополнительная плата может перевесить весь выигрыш от этого… 55 / 57 |
56 |
 |
Заключение (основные моменты)Взаимодействие нескольких участников, когда каждый действует в собственных интересах, может быть неэффективно для всех Во многих случаях степень этой неэффективности довольно мала; однако в некоторых случаях она может быть велика Многие вопросы являются открытыми Полученные результаты представляют практическую значимость 56 / 57 |
57 |
 |
Источники[1] Selfish Routing and the Price of Anarchy http://theory.stanford.edu/~tim/papers/optima.ps [2] Добрые парни финишируют первыми http://www.mista.ru/fant/gen/12.htm [3] Введение в теорию, методы и экономические приложения задач о дополнительности http://www.imm.uran.ru/RUS/WIN/PUBLIC/JRN/POPOV/popov1.pdf 57 / 57 |
«Маршрутизация и парадокс заключенного» |
http://900igr.net/prezentacija/literatura/marshrutizatsija-i-paradoks-zakljuchennogo-170800.html