Fair Division, Rental Harmony, and Sperner’s Lemma

A guided research project in Algorithms & Discrete Mathematics.

← Algorithms & Discrete Mathematics projects

Experience Research Algorithms & Discrete Mathematics

Question

Can rooms and rent be divided so that every person prefers their own choice?

A fully labelled region points to prices where all rooms can be assigned without envy.
A fully labelled region points to prices where all rooms can be assigned without envy.

Goals

  • Model an envy-free rental division.
  • Use Sperner's lemma to find or approximate a fair solution.

Method

Represent possible rent divisions as points in a simplex and label them by preferences.

  • Collect or define each person's room preferences at different prices.
  • Triangulate the price simplex and assign preference labels to its vertices.
  • Search for a fully labelled small simplex and interpret it as a rental division.