Introduction

---

Suppose students need to choose a day for their project presentations. Each student has a preference ranking over the available presentation slots. The professor wants to prioritize students based on their seniority. How do we match the students to presentation slots such that 1) the allocation is optimal and 2) all agents reveal their preferences truthfully?

Properties

---

Our solution guarantees the following properties:

1. Efficiency (Pareto efficient): Our algorithm allocates the items to participants such that it is impossible to find another allocation that benefits a participant without making another participant worse off.
2. Truthfulness: None of the participants would ever benefit from misreporting her ranking, or picking a less desired item.

Algorithm Overview

---

Our algorithm simply follows by letting each participant pick her best item among the remaining items. Participants get to pick according to a predefined order such as seniority. In our algorithm, participants’ priority ordering is top to bottom.

The algorithm is guaranteed an allocation that is optimal, that is no other allocation can make all participants weakly better off while making some agents strictly better off.

The algorithm also guarantees truthfulness, meaning that no participant can get a better allocation by not picking her best available item.

Strategy-proof allocation of indivisible goods
By: Lars-Gunnar Svensson