Which Is the Fairest (Rent Division) of Them All?
What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee...
| Publicado en: | Communications of the ACM Vol. 61; no. 2; pp. 93 - 101 |
|---|---|
| Autores principales: | , , , |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Feb2018
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=127712860&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 127712860 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Feb2018 vid: 61 iid: 2 pid: 68 pub: Association for Computing Machinery artinfo: ui: 127712860 10.1145/3166068 ppf: 93 ppct: 8 formats: tig: atl: Which Is the Fairest (Rent Division) of Them All? aug: au: Gal, Kobi Procaccia, Ariel D. Mash, Moshe Zick, Yair affil: Dept. of Software and Information Systems Engineering, Ben-Gurion University, Beer-Sheva, Israel Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA School of Computing, National University of Singapore su: Rent Algorithms Fairness Program transformation Computer programming Computer software sug: subj: Rent Algorithms Fairness Program transformation Computer programming Computer software ab: What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the "fairest" solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2018 holdings: @attributes: islocal: N |
|---|