N people share a house with N rooms and a fixed total rent; how can the rooms be allocated and priced at...

decision/rent.division New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

N people share a house with N rooms and a fixed total rent; how can
the rooms be allocated and priced at the same time so that the result
is fair?

I was wondering whether anyone out there has a good algorithm for the
following problem.  There are N people in a house with N rooms.  The
rent is fixed.  How do you allocate the rooms and price the rooms at
the same time?  I would like to do this in a way that takes into
account how much each room is "worth" -- that is, the pricing will be
"fair" but those who are willing and able can pay more for a better
room.

-- <yee@garnet.berkeley.edu>, June 1995

[ Editor: the first paragraph is the editor's summary.  See also
decision/division for fair division of a cake. ]

Show solution

[ Editor: only references were given in the collected postings; no
algorithm was worked out. ]

In <3qjefb$11ik@rover.ucs.ualberta.ca> eerkut@gpu.srv.ualberta.ca
(Erhan Erkut) writes:

[Good suggestion to use assignment approach deleted -- DMR.]

>Another alternative is to use a market approach where people are free to
>bid on rooms, and buy and sell after the initial assignments.

Something like this is done in L. S. Shapley & H. E. Scarf, "On cores
and indivisibility", _Journal_of_Mathematical_Economics_ 1 (1974),
pp. 23-28.  If I remember their article, they analyze a market for
housing where there are N houses and N people who can trade among
houses.

There has also been some research considering the sequencing of
jobs in job shops as such a trading game.  See Imma Curiel, Jos
Potters, & Rajendra Prasad, "Sequencing and Cooperation",
_Operations_Research_ Vol. 42, No. 3 (May 1994), and the articles
referenced therein and the articles referenced by those articles
(I think that that'll also lead you to the Shapley-Scarf article
that I mentioned above).  This is a little different because of
the externalities (a long job near the front of the queue is more
costly to everyone behind than a short job near the front of the
queue), but it may still be relevant.

-- Daniel M. Rosenblum <dmr@andromeda.rutgers.edu>