Випадковий пріоритет , також називається Випадковою послідовною диктатурою (RSD) , це процедура справедливого випадкового розподілу - справедливого розподілу неподільних предметів між людьми.

Припустимо, що партнерів повинні розділити між собою (або менше) різних предметів. Оскільки предмети є неподільними, деякі партнери неминуче отримають менш бажані предмети (або взагалі не отримають нічого). RSD намагається забезпечити справедливість у цій ситуації наступним чином. Намалюйте випадкову перестановку агентів з рівномірного розподілу. Потім нехай вони послідовно вибирають об'єкт у цьому порядку (тобто перший агент у порядку отримує перший вибір і так далі).

Властивості RSD є правдивим механізмом, коли кількість предметів не перевищує кількість агентів, оскільки у вас є тільки одна можливість вибрати предмет, і очевидною домінуючою стратегією в цій ситуації є вибір найкращого з доступних предметів.

RSD завжди дає апостеріорно Парето-ефективний (PE) результат. Більше того, в задачі призначення кожне детерміноване парето-ефективне призначення є результатом SD для певного порядку агентів.

RSD не є апріорно Парето-ефективним (PE), коли агенти мають утиліти Фон Неймана-Моргенштерна (VNM) щодо випадкових розподілів, тобто лотерей над об'єктами (зауважте, що апріорна беззаздрісність є "слабшою" за апостеріорну беззаздрісність, але апріорна Парето-ефективність є "сильнішою" за апостеріорну парето-ефективність). Як приклад, припустимо, що є три агенти, три предмети і утиліти VNM такі: Предмет x Предмет y Предмет z Аліса 1 0.8 0 Боб 1 0.2 0 Карл 1 0.2 0 RSD дає кожному агенту ймовірність 1/3 для кожного об'єкта (оскільки їхні уподобання щодо певних об'єктів збігаються), і профіль вектора очікуваної корисності (0.6, 0.4, 0.4). Але призначення предмета y для Аліси напевно і предметів x, z випадково між Бобом і Карлом дає вектор очікуваної корисності (0.8, 0.5, 0.5). Отже, початковий вектор корисності не є Парето-ефективним.

Більше того, коли агенти мають порядкові ранжування, RSD не задовольняє навіть слабшу властивість - SD-ефективність.

Коли ранжування агентів щодо об'єктів вибирається випадково з рівною ймовірністю, ймовірність того, що розподіл, отриманий за допомогою RSD, буде апріорно Парето-ефективним, наближається до нуля з ростом кількості агентів.

Альтернативне правило, Правило ймовірнісного серіалу, є SD-ефективним (що передбачає апостеріорну Парето-ефективність) і SD-беззаздрісним (що передбачає апріорну беззаздрісність), але воно не є правдивим. Неможливо отримати переваги від обох механізмів:

За кардинальних адитивних функцій корисності жоден механізм не є симетричним, правдивим і апріорно Парето-ефективним. За порядковими функціями корисності жоден механізм не є SD-ефективним, стратегієстійким і не ставиться до рівних однаково.

Генералізації

Більше об'єктів, ніж агентів Коли об'єктів більше ніж , деякі агенти можуть отримати більше ніж один об'єкт. Існує кілька способів розширення RSD на цей випадок.

Один зі способів — визначити квоту для кожного агента (так, щоб сума квот дорівнювала кількості об'єктів), і дозволити кожному агенту по черзі вибирати предмети до його/її квоти. Ця процедура залишається стратегієстійкою, але є дуже несправедливою. Інший спосіб — дозволити кожному агенту вибрати один предмет, а потім провести ще один раунд, в якому кожен агент вибирає один предмет, поки всі об'єкти не будуть розподілені; це призводить до процедури розподілу предметів за принципом "по черзі". Ця процедура є справедливішою, але не є стратегієстійкою. Обидві процедури є особливими випадками послідовності вибору.

Загальне прийняття рішень RSD можна визначити для більш загального випадку, в якому група повинна вибрати одну альтернативу з набору альтернатив. У цьому випадку RSD працює наступним чином: спочатку випадковим чином перестановлюються агенти. Починаючи з набору всіх альтернатив, кожному агенту у порядку перестановки пропонується вибрати свою улюблену альтернативу (альтернативи) серед тих, що залишилися. Якщо після врахування переваг усіх агентів залишаються більше ніж одна альтернатива, RSD випадковим чином розподіляє ймовірності серед цих альтернатив. У випадку поділу предметів, згаданому раніше, альтернативи відповідають розподілам предметів між агентами. Кожен агент має великі еквівалентні класи в своїх перевагах, оскільки він байдужий до всіх розподілів, у яких отримує той самий предмет.

У цьому загальному випадку, якщо всі агенти мають строгі переваги щодо альтернатив, то RSD зводиться до випадкового вибору агента та вибору альтернативи, яку цей агент любить найбільше. Цю процедуру називають випадковою диктатурою (RD), і це є єдина процедура, яка є ефективною та стратегієстійкою, коли переваги є строгими. Однак, коли агенти можуть мати слабкі переваги, жодна процедура, яка розширює RD (до якої належить RSD), не задовольняє одночасно ефективність та стратегієстійкість.

Посилання