0

Lets say my friends and I ($n$ people in total) are moving together to an $n$-room house and each one uf us has a precise ordering of the rooms we'd like to live in. That is, if $\{R_j\}_{j=1}^n$ is the set of rooms and $\{A_i\}_{i=1}^n$ the set of people then, for every $1\le i\le n$ there exists a total ordering $\le_i$ of $\{R_j\}_{j=1}^n$. For example, $R_3\le_4 R_5\le_4 R_{n-1}\le_4\dots\le_4 R_2$ means that person number four thinks room 2 is the best and room 3 the worst.

How should the rooms be distributed so as to make everyone the happiest? There are a lot of discussions here and there about what constitutes a "fair" or "envy-free" allocation and some algorithms. I for once am interested in the practical side of the matter. Is there a pen and paper procedure or a matlab function?

Why is this different to fair cake-cutting? And why is it harder than a simple optimization problem?

augustoperez
  • 3,216
  • I would think that "envy-free" is impossible in general. For instance if everyone agrees that the palatial master bedroom with large closets and massive bath is best, and the windowless converted utility closet in the subbasement is worst, someone is going to end up extremely envious of someone else, no matter how you distribute the rooms. – Paul Sinclair Aug 14 '20 at 00:17
  • If the only difference between the results is who gets which room, then by most definitions of the word, fairness may be impossible for the same reason. However, if there is a second variable, it can be used to balance the unfairness. Maybe Miss palatial bedroom has to pay a much bigger share of the rent than Mr subbasement. – Paul Sinclair Aug 14 '20 at 00:26

0 Answers0