Laboratory of Mathematical Logic at PDMI

Пятница, 18 сентября, комната 106. Начало в 18:00.

Докладчик: Н. Гравин.

Тема: Экономные механизмы для аукционов на покупку путей в графе.

Abstract

В докладе будут рассматриваться аукционы, в которых покупатель хочет нанять группу агентов для выполнения одной сложной задачи, например для покупки пути в графе между двумя заданными вершинами. Как обычно для построения механизма проведения аукциона предполагается, что агенты действуют эгоистично и хотят максимизировать свою прибыль. Это в частности приводит к тому, что агенты, возможно, будут указывать неправильную стоимость выполнения своей работы. В связи с этим нас будут интересовать только те механизмы, в которых каждому агенту выгодно сообщать свою истинную цену выполнения работы.
Отношение экономности, введенное Карлин, Кэмпе, Тамиром на FOCS'05, показывает, на сколько механизм переплачивает агентам по сравнению с равновесием Нэша.

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