Справедливое случайное назначение

Справедливое случайное назначение является своего рода проблема справедливого разделения.

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

В общем, честное задание может оказаться невозможным. Например, если Алиса и Батья оба предпочтут восточную комнату западной, только один из них получит ее, а другой будет завидовать. В настройке случайное назначение справедливость достигается с помощью лотереи. Итак, в приведенном выше простом примере Алиса и Батья подбрасывают честную монету, и победитель получает восточную комнату.

Есть несколько способов распространить метод «подбрасывания монеты» на ситуации, в которых есть более двух агентов, и у них могут быть разные отношения предпочтений для объектов:

• Случайный Приоритет (RP) - это правдивый механизм. Это ex-ante без зависти и ex-ante , эффективное по Парето, но не ex-ante, эффективное по Парето. Это очень простой механизм, требующий от агентов только порядкового ранжирования по отдельным позициям.
• Конкурентное равновесие на основе равных доходов (CEEI) - это рыночный механизм: каждый элемент рассматривается как делимый товар. Каждому агенту дается $1\; /\; n\; \{\backslash \; displaystyle\; 1\; /\; n\}$-доля каждого товара, затем агентам разрешается торговать до тех пор, пока не будет достигнуто равновесие. Это ex-ante и ex-post эффективно по Парето и ex-ante без зависти, но не правдиво. Это более сложный механизм, который требует от агентов наличия полных функций кардинальной полезности (или, альтернативно, порядкового ранжирования в лотереях).
• Вероятностный последовательный (PS) - это алгоритм, который гарантирует ex -ante свобода от зависти, ex-ante и ex-post эффективность по Парето, но не соответствует действительности. Для этого требуется только порядковое ранжирование предметов.

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