Global InformationRental harmony information
Rental harmony[1][2] is a kind of a fair division problem in which indivisible items and a fixed monetary cost have to be divided simultaneously. The housemates problem[3][4] and room-assignment-rent-division[5][6] are alternative names to the same problem.[7][8]: 305–328
In the typical setting, there are partners who rent together an -room house for cost fixed by the homeowner. Each housemate may have different preferences — one may prefer a large room, another may prefer a room with a view to the main road, etc. The following two problems should be solved simultaneously:
- (a) Assign a room to each partner,
- (b) Determine the amount each partner should pay, such that the sum of payments equals the fixed cost.
There are several properties that we would like the assignment to satisfy.
- Non-negativity (NN): all prices must be 0 or more: no partner should be paid to get a room.
- Envy-freeness (EF): Given a pricing scheme (an assignment of rent to rooms), we say that a partner prefers a given room if he believes that the parcel of room+rent is weakly better than all other parcels. EF means that every partner prefers his allotted room. I.e, no partner would like to take another room at the rent assigned to that room.
- Pareto-efficiency (PE): No other assignment of partners to rooms is weakly better for all partners and strictly better for at least one partner (given the price-vector).
Envy-freeness implies Pareto-efficiency. Proof: Suppose by contradiction that there exists an alternative assignment, with the same price-vector, that is strictly better for at least one partner. Then, in the current allocation, that partner is envious.
The rental-harmony problem has been studied under two different assumptions on the partners' preferences:
- In the ordinal utility version, each partner has a preference relation on bundles [room, price]. Given a price-vector, the partner should only be able to say which room (or rooms) he prefers to rent at that price.
- In the cardinal utility version, each partner has a vector of monetary valuations. The partner should say, for each room, exactly how much money he is willing to pay for that room. The partner is assumed to have quasilinear utility, i.e., if he values the room as and pays , his net utility is .
The cardinal assumption implies the ordinal assumption, since given a valuation vector it is always possible to construct a preference relation. The ordinal assumption is more general and puts less mental burden on the partners.
- ^ Su, F. E. (1999). "Rental Harmony: Sperner's Lemma in Fair Division". The American Mathematical Monthly. 106 (10): 930–942. doi:10.2307/2589747. JSTOR 2589747.
- ^ Azrieli, Yaron; Shmaya, Eran (2014). "Rental harmony with roommates". Journal of Economic Theory. 153: 128. arXiv:1406.6672. doi:10.1016/j.jet.2014.06.006. S2CID 12129179.
- ^ Potthoff, Richard F. (2002). "Use of Linear Programming to Find an Envy-Free Solution Closest to the Brams–Kilgour Gap Solution for the Housemates Problem". Group Decision and Negotiation. 11 (5): 405. doi:10.1023/A:1020485018300. S2CID 122452727.
- ^ Sung, Shao Chin; Vlach, Milan (2004). "Competitive envy-free division". Social Choice and Welfare. 23. doi:10.1007/s00355-003-0240-z. S2CID 11638306.
- ^ Abdulkadiroğlu, Atila; Sönmez, Tayfun; Utku Ünver, M. (2004). "Room assignment-rent division: A market approach". Social Choice and Welfare. 22 (3): 515. CiteSeerX 10.1.1.198.186. doi:10.1007/s00355-003-0231-0.
- ^ Lachlan Dufton and Kate Larson (2011). "Randomised Room Assignment-Rent Division" (PDF). Proceedings of the IJCAI-2011 Workshop on Social Choice and Artificial Intelligence. IJCAI. pp. 34–39. Retrieved 5 March 2016.
- ^ Haake, Claus-Jochen; Raith, Matthias G.; Su, Francis Edward (2002). "Bidding for envy-freeness: A procedural approach to n-player fair-division problems". Social Choice and Welfare. 19 (4): 723. CiteSeerX 10.1.1.26.8883. doi:10.1007/s003550100149. S2CID 2784141.
- ^ Steven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218.