Fair rent division: Maximin and Lexislack

Built by Dominik Peters. First published: October 2022. Last updated: August 2024.

This page allows you to compute the results of two algorithms for fairly assigning rooms to roommates. The input consists of each person specifying a valuation for each room. The algorithms then compute an assignment of rooms to people and the corresponding rent to be paid by each person. Both algorithm divide the rent in an envy-free way: no person would prefer another person's room over their own, measuring a room's attractiveness as the valuation for the room minus its rent.

The first algorithm used on this page is maximin which maximizes the utility (valuation minus rent) of the least happy person, and which has been studied in several papers (for example, Gal, Mash, Procaccia, Zick (2017)). The second algorithm is the lexislack algorithm which aims to find an outcome that is robustly fair so that the rent allocation is likely to remain fair even if the valuations change slightly. It maximizes how much happier roommates are with their room compared to other rooms, maximizing this difference (the slack) lexicographically. It was proposed by Peters, Procaccia, Zhu (2022) and is similar to an earlier proposal of Critch (2015).

Both algorithms are based on computing linear programs, which is done locally in your browser using the HiGHS solver run via WebAssembly (highs.js). Check out my lp-model javascript package for building similar apps. The algorithms also solve a weighted bipartite matching problem using the lap-jv library.

Loading page...