Применение дизайна механизмов в задачах распределения

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

В целом, задачи распределения можно описать следующим образом.

Есть множество агентов {1, …, N}, а также множество объектов распределения {1, …, M}, которые надлежит распределить. У агентов есть предпочтения относительно предметов, но и у объектов распределения могут быть предпочтения относительно агентов. У каждого объекта распределения m есть свой объем q_m, который отвечает за количество агентов, которым может достаться данный объект распределения. Задача планировщика состоит в том, чтобы эффективно распределить объекты распределения агентам в связи с их заявленными предпочтениями, не превышая объемы объектов распределения.

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

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