4 ms·

Does this still work if one person has an upper limit on how much they can spend that is less than an equal split?

• cowsandmilk 12y ago
  yes... unless the conclusion from the process is that the apartment is too expensive for the roommates to split; or your preferences are not compatible with each other.
• ronaldx 12y ago
  The algorithm is likely to ask anyone to choose a favoured room from an equal split, so in theory the algorithm won't work if someone has a smaller-than-equality budget. The algorithm depends on everyone having a personal way of splitting the cost of the house so that they would be equally happy with any room. If you are only willing to spend less-than-equality on a particular room, you should be prepared to spend more-than-equality on another room to compensate. Someone without that possibility might get a result incompatible with their needs or might be taken advantage of by a knowledgeable enemy player, I would think. So in theory, no, this method won't work perfectly. But in practice, yes, you might still get a decent result. This algorithm is good for cake-cutting, since everyone likes to receive cake, but less good for rent-splitting, since not everyone likes to pay rent.
• sesqu 12y ago
  It might. The associated paper makes the assumption that for every division of rent, some room is acceptable. However, the lemma itself makes no such demand, but only guarantees the existence of an approximate rent division. The algorithm given refines the rent division iteratively, so an upper spend limit only means you might end up with rooms assigned and a portion of the rent unpaid. You could then fix the underfunded tenant's room and iterate on the others, but there's no longer a guarantee that the others wouldn't envy the bum's rent.