Теоретико-игровые модели интернета (А.В. Савватеев)

1) С.Меликов, Д.В. Мусатов, А.В. Савватеев
Теоретико-игровые модели интернета.

Аннотация:

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

Для сложных сетей известно множество локальных и глобальных числовых
характеристик: распределение степеней вершин, коэффициент
кластеризации, коэффициент ассортативности и др. В первой части
доклада мы дадим обзор этих характеристик и представим результаты их
измерения для различных интернет-графов. Выяснится, что для
интернет-сетей характерен ряд особенностей: Парето-распределение
степеней, высокий коэффициент кластеризации, положительная
ассортативность, маленький диаметр и т.д. Конечной целью моделирования
интернет-сетей является построение модели с теми же особенностями.

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

2) Равновесия Нэша (миграционно-устойчивые структуры)
в задачах многомерного размещения

А.В. Савватеев

Аннотация

Рассмотрим следующую задачу, в последнее время ставшую почти
классической. Имеется континуальный (безатомный) спрос на клубное
благо, расселённый каким-то образом в многомерном ``пространстве
разногласия''. Допустимым способом удовлетворения спроса назовём
любое разбиение потребителей на группы, состоящие из игроков,
приписанных к одной и той же вариации блага.

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

Разбиение называется миграционно услойчивым, если никто не хочет
``втихую'' сменить группу. При этом подразумевается, что в каждой
из групп принят свой способ деления издержек на поставку блага,
и смена группы означает выбор новых правил игры. В докладе будет
рассказано о новых достижениях в различных вариациях этой задачи,
ведущей свою историю как минимум от Тьебу (1956).