Introduction

Suppose you want to distribute tasks among the members of a team. Members have preferences over tasks and these preferences may be conflicting (e.g. two members may want to do the same task). How should we distribute the tasks through a lottery such that no member is envious of another one?

Properties

Our solution guarantees the following properties:

1. Efficiency: PS guarantees the prescribed probabilistic matching (lottery) is efficient, meaning that no other lottery exists that can strictly improve the outcome for some participants without making other participants worse off.
2. Fairness: The lottery prescribed by PS is envy-free. This means that no participant will prefer the chances (lottery) that is assigned to another agent to her own. Envy-freeness is stronger than fairness notion of equal treatment of equals provided by RP

Algorithm Overview

Probabilistic serial rule (PS) provides a probabilistic fair solution, similar to RP. However it achieves stronger efficiency and fairness guarantees (see here for a detailed comparison). It works as follows: suppose items are different types of pizzas. Each agent starts "eating" her top choice pizza at the same rate as every other agent. Once a pizza is consumed, agents move to their next preferred pizza; until all pizzas are eaten.

PS guarantees that the probabilistic matching (lottery) is efficient and envy-free. We illustrate the probabilistic matching (lottery) assigned to each participant. To ensure that the sampled assignment is fair ex post (EF1), a combination of PS and Birkhoff's decomposition algorithm is used.

A new solution to the random assignment problem
By: Anna Bogomolnaia and Hervé Moulin
Investigating the characteristics of one-sided matching mechanisms under various preferences and risk attitudes
By: Hadi Hosseini, Kate Larson, and Robin Cohen
Simultaneously achieving ex-ante and ex-post fairness
By: Haris Aziz