nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Rent Division Among Groups

verfasst von : Mohammad Ghodsi, Mohamad Latifian, Arman Mohammadi, Sadra Moradian, Masoud Seddighin

Erschienen in: Combinatorial Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we extend the Rent Sharing problem to the case that every room must be allocated to a group of agents. In the classic Rent Sharing problem, there are n agents and a house with n rooms. The goal is to allocate one room to each agent and assign a rent to each room in a way that no agent envies any other option. Our setting deviates from the classic Rent Sharing problem in a sense that the rent charged to each room must be divided among the members of the resident group.

We define three notions to evaluate fairness, namely, weak envy-freeness, aggregate envy-freeness and strong envy-freeness. We also define three different policies to divide the cost among the group members, namely, equal, proportional, and free cost-sharing policies.

We present several positive and negative results for different combinations of the fairness criteria and rent-division policies. Specifically, when the groups are pre-determined, we propose a strong envy-free solution that allocates the rooms to the agents, with free cost-sharing policy. In addition, for the case that the groups are not pre-determined, we propose a strong envy-free allocation algorithm with equal cost-sharing policy. We leverage our results to obtain an algorithm that determines the maximum total rent along with the proper allocation and rent-division method.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Competitiveness of Memoryless Strategies for the k-Canadian Traveller Problem

Nächstes Kapitel Sequence Sentential Decision Diagrams

[n] refers to the set \(\{1,2,\ldots ,n\}\).

\(\mathcal N=\bigcup _{i,j} a_{i,j}\).

Note that if \(V_{i,k}=0\), by individual rationality, \(\mathcal{R}(k)=0\) and no agent has to pay any cost.

We refer the reader to the full version of the paper for this proof.

Foley, D.K.: Resource allocation and the public sector (1967)

Gamov, G., Stern, M.: Puzzle math. Viking, New York (1958)MATH

Procaccia, A.D.: Cake cutting: not just child’s play. Commun. ACM 56(7), 78–87 (2013)CrossRef

Robertson, J., Webb, W.: Cake-Cutting Algorithms: Be Fair If You Can (1998)

Segal-Halevi, E., Hassidim, A., Aumann, Y.: Envy-free cake-cutting in two dimensions. In: AAAI, vol. 15, pp. 1021–1028 (2015)

Gal, Y.K., Mash, M., Procaccia, A.D., Zick, Y.: Which is the fairest (rent division) of them all? In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 67–84. ACM (2016)

Cohler, Y.J., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Optimal envy-free cake cutting. In: AAAI (2011)

Su, F.E.: Rental harmony: Sperner’s lemma in fair division. Am. Math. Mon. 106(10), 930–942 (1999)MathSciNetCrossRef

Aragones, E.: A derivation of the money Rawlsian solution. Soc. Choice Welf. 12(3), 267–276 (1995)CrossRef

10.

Chan, P.H., Huang, X., Liu, Z., Zhang, C., Zhang, S.: Assignment and pricing in roommate market. In: AAAI, pp. 446–452 (2016)

11.

Segal-Halevi, E., Nitzan, S.: Proportional cake-cutting among families. arXiv preprint arXiv:1510.03903 (2015)

12.

Robert, C., Carnevale, P.J.: Group choice in ultimatum bargaining. Organ. Behav. Hum. Decis. Process. 72(2), 256–279 (1997)CrossRef

13.

Bornstein, G., Yaniv, I.: Individual and group behavior in the ultimatum game: are groups more “rational" players? Exp. Econ. 1(1), 101–108 (1998)CrossRef

14.

Messick, D.M., Moore, D.A., Bazerman, M.H.: Ultimatum bargaining with a group: underestimating the importance of the decision rule. Organ. Behav. Hum. Decis. Process. 69(2), 87–101 (1997)CrossRef

15.

Santos, F.P., Santos, F.C., Paiva, A., Pacheco, J.M.: Evolutionary dynamics of group fairness. J. Theor. Biol. 378, 96–102 (2015)CrossRef

16.

Manurangsi, P., Suksompong, W.: Asymptotic existence of fair divisions for groups. Math. Soc. Sci. 89, 100–108 (2017)MathSciNetCrossRef

17.

Suksompong, W.: Approximate maximin shares for groups of agents. Math. Soc. Sci. 92, 40–47 (2018)MathSciNetCrossRef

18.

Chen, Y., Lai, J.K., Parkes, D.C., Procaccia, A.D.: Truth, justice, and cake cutting. Games Econ. Behav. 77(1), 284–297 (2013)MathSciNetCrossRef

19.

Alijani, R., Farhadi, M., Ghodsi, M., Seddighin, M., Tajik, A.S.: Envy-free mechanisms with minimum number of cuts. In: AAAI, pp. 312–318 (2017)

20.

Stromquist, W.: Envy-free cake divisions cannot be found by finite protocols. Electron. J. Comb. 15(1), 11 (2008)MathSciNetMATH

21.

Dehghani, S., Farhadi, A., HajiAghayi, M., Yami, H.: Envy-free chore division for an arbitrary number of agents. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2564–2583. SIAM (2018)CrossRef

22.

Alkan, A., Demange, G., Gale, D.: Fair allocation of indivisible goods and criteria of justice. Econ.: J. Econ. Soc. 1023–1039 (1991)MathSciNetCrossRef

23.

Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., Yami, H.: Fair allocation of indivisible goods: improvements and generalizations. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 539–556. ACM (2018)

24.

Farhadi, A., et al.: Fair allocation of indivisible goods to asymmetric agents. In: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pp. 1535–1537. International Foundation for Autonomous Agents and Multiagent Systems (2017)

25.

Procaccia, A.D., Wang, J.: Fair enough: guaranteeing approximate maximin shares. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, pp. 675–692. ACM (2014)

26.

Amanatidis, G., Markakis, E., Nikzad, A., Saberi, A.: Approximation algorithms for computing maximin share allocations. ACM Trans. Algorithms (TALG) 13(4), 52 (2017)MathSciNetMATH

27.

Cole, R., Gkatzelis, V.: Approximating the nash social welfare with indivisible items. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pp. 371–380. ACM (2015)CrossRef

28.

Ghodsi, M., Saleh, H., Seddighin, M.: Fair allocation of indivisible items with externalities. arXiv preprint arXiv:1805.06191 (2018)

29.

Procaccia, A.D., Velez, R.A., Yu, D.: Fair rent division on a budget. In: AAAI (2018)

30.

Azrieli, Y., Shmaya, E.: Rental harmony with roommates. J. Econ. Theory 153, 128–137 (2014)MathSciNetCrossRef

Titel: Rent Division Among Groups
verfasst von: Mohammad Ghodsi
Mohamad Latifian
Arman Mohammadi
Sadra Moradian
Masoud Seddighin
Verlag: Springer International Publishing
Buch: Combinatorial Optimization and Applications
Print ISBN: 978-3-030-04650-7

Electronic ISBN: 978-3-030-04651-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-04651-4_39

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"