Random Priority (Random Serial Dictatorship)

Interact Learn

Problem Statement

Suppose your professor wants to assign reading topics to students in class. Each student is then required to present a topic to the whole class. Clearly, each student may prefer some topics to another but some students may prefer the same topic. How should the professor ensure fair treatment of students while taking their preferences into account?



Try it out

Input is not a number!
Input is not a number!

Introduction

Suppose your professor wants to assign reading topics to students in class. Each student is then required to present a topic to the whole class. Clearly, each student may prefer some topics to another but some students may prefer the same topic. How should the professor ensure fair treatment of students while taking their preferences into account?



Properties

Our solution guarantees the following properties:

  1. Efficiency: The algorithm guarantees that the outcome of the lottery is Pareto efficient, meaning that no subgroups of participants would be willing to exchange items after the fact.
  2. Fairness: RP prescribes a lottery that guarantees probabilistic fairness of equal treatment of equals. This means the lottery gives all agents the same chance of picking first, second, third, and so on.
  3. Truthfulness: None of the participants would ever benefit from misreporting her ranking order over items.


Algorithm Overview

Random Priority (aka Random Serial Dictatorship) is a fair extension of SD when there is no predefined ordering of agents. RP achieves fairness by permuting over all possible ordering of agents and then selecting one uniformly at random.

RP prescribes a lottery that satisfies Pareto efficiency, equal treatment of equals, and truthfulness.

Random serial dictatorship and the core from random endowments in house allocation problems
By: Atila Abdulkadi̇roğlu and Tayfun Sönmez
An exact analysis of stable allocation
By: Donald Knuth