Finding the Pareto optimal equitable allocation of homogeneous divisible goods among three players

• Autorzy: Dall'Aglio M. , Di Luca C. , Milone L.

Identyfikatory

DOI

10.5277/ord170303

• Języki publikacji: EN

Abstrakty

EN

We consider the allocation of a finite number of homogeneous divisible items among three players. Under the assumption that each player assigns a positive value to every item, we develop a simple algorithm that returns a Pareto optimal and equitable allocation. This is based on the tight relationship between two geometric objects of fair division: The Individual Pieces Set (IPS) and the Radon–Nykodim Set (RNS). The algorithm can be considered as an extension of the Adjusted Winner procedure by Brams and Taylor to the three-player case, without the guarantee of envy-freeness.

Słowa kluczowe

EN

fair division; Pareto optimality; graph theory; adjusted winner procedure

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2017
• Tom: Vol. 27, No. 3
• Strony: 35--50
• Opis fizyczny: Bibliogr. 16 poz., rys.

Twórcy

autor

Dall'Aglio M.

• LUISS University, Department of Economics and Finance, Viale Romania 32, 00197 Roma, Italy

autor

Di Luca C.

• LUISS University, Department of Economics and Finance, Viale Romania 32, 00197 Roma, Italy

autor

Milone L.

• LUISS University, Department of Economics and Finance, Viale Romania 32, 00197 Roma, Italy

Bibliografia

• [1] BARBANEL J.B., On the structure of Pareto optimal cake partitions, J. Math. Econ., 2000, 33 (4), 401–424.
• [2] BARBANEL J.B., The Geometry of Efficient Fair Division, Cambridge University Press, Cambridge 2005.
• [3] BARBANEL J.B., ZWICKER W.S., Two applications of a theorem of Dvoretzky, Wald, and Wolfovitz to cake division, Theory Dec., 1997, 43 (2), 203–207.
• [4] BOGOMOLNAIA A., MOULIN H., Competitive fair division under linear preferences, Working Papers 2016–07, Business School, Economics, University of Glasgow.
• [5] BOGOMOLNAIA A., MOULIN H., SANDOMIRSKIY F., YANOVSKAYA E., Competitive division of a mixed manna, Econometrica, 2017, accepted for publication.
• [6] BRAMS S.J., JONES M.A., KLAMLER C., N-person cake-cutting: There may be no perfect division, Am. Math. Monthly, 2013, 120 (1), 35–47.
• [7] BRAMS S.J., TAYLOR A.D., Fair Division. From Cake-Cutting to Dispute Resolution, Cambridge University Press, Cambridge 1996.
• [8] BRAMS S.J., TAYLOR A.D., The Win-Win Solution. Guaranteeing Fair Shares to Everybody, W.W. Norton, New York 1999.
• [9] DALL’AGLIO M., The Dubins–Spanier optimization problem in fair division theory, J. Comp. Appl. Math., 2001, 130 (1), 17–40.
• [10] DALL’AGLIO M., DI LUCA C., MILONE L., Characterizing and Finding the Pareto Optimal Equitable Allocation of Homogeneous Divisible Goods Among Three Players, arXiv:1606.01028, 2016.
• [11] DALL’AGLIO M., HILL T.P., Maximin share and minimax envy in fair-division problems, J. Math. Anal. Appl., 2003, 281, 346–361.
• [12] DEMKO S., HILL T.P., Equitable distribution of indivisible objects, Math. Soc. Sci., 1988, 16 (2), 145–158.
• [13] KALAI E., Proportional solutions to bargaining situations. Interpersonal utility comparisons, Econometrica, 1977, 45 (7), 1623–1630.
• [14] KALAI E., SMORODINSKY M., Other solutions to Nash’s bargaining problem, Econometrica, 1975, 43 (3), 513–518.
• [15] OLVERA-LÓPEZ W., SÁNCHEZ- SÁNCHEZ F., An algorithm based on graphs for solving a fair division problem, Oper. Res., 2014, 14 (1), 11–27.
• [16] WELLER D., Fair division of a measurable space, J. Math. Econ., 1985, 14 (1), 5–17.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).