On a method of obtaining an approximate solution of an exact fair division problem

• Autorzy: Legut J.

Identyfikatory

DOI

10.14708/ma.v46i2.5134

Warianty tytułu

PL

O metodzie wyznaczania przybliżonego rozwiązania problemu ściśle sprawiedliwego podziału

• Języki publikacji: EN

Abstrakty

EN

Let the unit interval [0; 1] represent a cake to be divided among n players estimating the measurable subsets of [0; 1] by non-atomic probability measures μ₁,…, μ_n. An approximate method is presented of obtaining an exact fair division {A₁,…, A_n} of the cake such that μ_i (A_j) ≈ 1/n for all i, j = 1,…, n and U_i A_i = [0, 1].

PL

Niech odcinek jednostkowy [0; 1] reprezentuje tort, który ma być podzielony między n graczy, którzy oceniają mierzalne podzbiory odcinka [0; 1] przy pomocy bezatomowych miar probabilistycznych μ₁,…, μ_n. W pracy pokazano przybliżoną metodę uzyskania ściśle sprawiedliwego podziału {A₁,…, A_n}, takiego że μ_i (A_j) ≈ 1/n dla każdego i, j = 1,…, n oraz U_i A_i = [0, 1].

Słowa kluczowe

EN

cake cutting; exact fair division; algorithm

PL

dokładny podział; sprawiedliwy podział; algorytm

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2018
• Tom: Vol. 46, no. 2
• Strony: 245--256
• Opis fizyczny: Bibliogr. 20 poz., fot.

Twórcy

autor

Legut J.

• Wrocław University of Science and Technology, Faculty of Pure and Applied Mathematics, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] N. Alon. Splitting necklaces. Adv. in Math., 63 (3): 247-253, 1987. ISSN 0001-8708. doi: 10.1016/0001-8708(87)90055-7. URL https://doi.org/10.1016/0001-8708(87)90055-7. Cited on p. 247.
• [2] M. Asada, F. Frick, V. Pisharody, M. Polevy, D. Stoner, L. H. Tsang, and Z. Wellner. Fair division and generalizations of Sperner- and KKM-type results. SIAM J. Discrete Math., 32 (1): 591-610, 2018. ISSN 0895-4801; 1095-7146/e. doi: 10.1137/17M1116210. Zbl 1385.54013. Cited on p. 246.
• [3] M. Bożykowski. Problem podziału zbioru dóbr niepodzielnych w sytuacji nierównych uprawnień. Decyzje, 18: 25-47, 2014. ISSN 2391-761X. URL https://journal.kozminski.edu.pl/index.php/decyzje/article/view/12. Cited on p. 245.
• [4] S. J. Brams and A. D. Taylor. An envy-free cake division protocol. Amer. Math. Monthly, 102 (1): 9-18, 1995. ISSN 0002-9890. doi: 10.2307/2974850. MR 1321451. Cited on p. 246.
• [5] S. J. Brams and A. D. Taylor. On envy-free cake division. J. Combin. Theory Ser. A, 70 (1): 170-173, 1995. ISSN 0097-3165. doi: 10.1016/0097-3165(95)90088-8. MR 1324009. Cited on p. 246.
• [6] S. J. Brams, A. D. Taylor, and W. S. Zwicker. Old and new moving-knife schemes. Math. Intelligencer, 17 (4): 30-35, 1995. ISSN 0343-6993. doi: 10.1007/BF03024785. MR 1365006. Cited on p. 246.
• [7] K. n. Cechlárová and E. Pillárová. On the computability of equitable divisions. Discrete Optim., 9 (4): 249-257, 2012. ISSN 1572-5286. doi: 10.1016/j.disopt.2012.08.001. MR 2969265. Cited on p. 246.
• [8] K. n. Cechlárová and E. Pillárová. A near equitable 2-person cake cutting algorithm. Optimization, 61 (11): 1321-1330, 2012. ISSN 0233-1934. doi: 10.1080/02331934.2011.563306. MR 2995500. Cited on p. 246.
• [9] K. n. Cechlárová, J. Doboš, and E. Pillárová. On the existence of equitable cake divisions. Inform. Sci., 228: 239-245, 2013. ISSN 0020-0255. doi: 10.1016/j.ins.2012.11.024. MR 3018714. Cited on p. 246.
• [10] M. Dall'Aglio, J. Legut, and M. Wilczyński. On finding optimal partitions of a measurable space. Mat. Stosow., 43 (2): 157-172, 2015. ISSN 1730-2668. doi: 10.14708/ma.v43i2.754. MR 3455464. Cited on p. 246.
• [11] L. E. Dubins and E. H. Spanier. How to cut a cake fairly. Amer. Math. Monthly, 68: 1-17, 1961. ISSN 0002-9890. doi: 10.2307/2311357. MR 0129031. Cited on p. 246.
• [12] C. R. Hobby and J. R. Rice. A moment problem in L1 approximation. Proc. Amer. Math. Soc., 16: 665-670, 1965. ISSN 0002-9939. doi: 10.2307/2033900. MR 0178292. Cited on p. 247.
• [13] B. Knaster. Sur le problème du partage pragmatique de h. steinhaus. Annales de la Société Polonaise de Mathématique, 19: 228-230, 1946. ISSN 230-0241. Rocznik Polskiego Towarzystwa Matematycznego. Cited on p. 246.
• [14] J. Legut. Optimal fair division for measures with piecewise linear density functions. Int. Game Theory Rev., 19 (2): 1750009, 12, 2017. ISSN 0219-1989. doi: 10.1142/S0219198917500098. MR 3645742. Cited on p. 246.
• [15] A. Liapounoff. Sur les fonctions-vecteurs complètement additives. Bull. Acad. Sci. URSS. Sér. Math. [Izvestia Akad. Nauk SSSR], 4: 465-478, 1940. Cited on p. 246.
• [16] J. M. Robertson and W. A. Webb. Near exact and envy free cake division. Ars Combin., 45: 97-108, 1997. ISSN 0381-7032. MR 1447762. Cited on p. 246.
• [17] H. Steinhaus. The problem of fair division. Econometrica, 16 (1): 101-104, 1948. ISSN 0012-9682, 1468-0262. doi: 10.2307/1914289. in: Report of the Washington Meeting, September 6-18, 1947, pp. 33-111. Cited on p. 246.
• [18] H. Steinhaus. Sur la division pragmatique. Econometrica, 17 (Supplement): 315-319, 1949. ISSN 0012-9682. doi: 10.2307/1907319. URL https://doi.org/10.2307/1907319. Cited on p. 246.
• [19] W. Stromquist. How to cut a cake fairly. Am. Math. Mon., 87: 640-644, 1980. ISSN 0002-9890. doi: 10.2307/2320951. Zbl 0441.90002. Cited on p. 246.
• [20] F. E. Su. Rental harmony: Sperner's lemma in fair division. Am. Math. Mon., 106 (10): 930-942, 1999. ISSN 0002-9890. doi: 10.2307/2589747. Zbl 1010.05077. Cited on p. 246.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).