ELEMENTARNOE REShENIE ZADAChI SPRAVEDLIVOGO DELENIYa

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Предлагается новый и сравнительно элементарный подход для решения за дачи справедливого деления непрерывного ресурса (измеримого пространства, пирога и т.п.) между несколькими участниками, критерии выбора которых опи сываются зарядами (мерами со знаком). Постановка задачи с зарядами рассмат ривается впервые. Задача сводится к анализу свойств траекторий специально построенной динамической системы, действующей на пространстве конечных измеримых разбиений. Доказана экспоненциально быстрая сходимость к пре дельному решению как для случая мер, так и для случая зарядов.

About the authors

M. L Blank

Email: blank@iitp.ru

M. O Polyakov

Email: pmaxol73@gmail.com

References

  1. Brams S.J., Jones M.A., Klamler C. Better Ways to Cut a Cake // Notices Amer. Math. Soc. 2006. V. 53. № 11. P. 1314–1321.
  2. Moulin H. Fair Division and Collective Welfare. Cambridge: MIT Press, 2003.
  3. Brams S.J. Mathematics and Democracy: Designing Better Voting and Fair Division Pro- cedures. Princeton, NJ: Princeton Univ. Press, 2008.
  4. Barbanel J.B., Brams S.J., Stromquist W. Cutting a Pie Is Not a Piece of Cake // Amer. Math. Monthly. 2009. V. 116. № 6. P. 496–514. https://doi.org/10.1080/00029890.2009.11920966
  5. Dubins L.E., Spanier E.H. How to Cut a Cake Fairly // Amer. Math. Monthly. 1961. V. 68. № 1. Part 1. P. 1–17. https://doi.org/10.1080/00029890.1961.11989615
  6. Ляпунов А.А. О вполне аддитивных вектор-функциях // Изв. АН СССР. Сер. матем. 1940. Т. 4. № 6. С. 465–478. https://www.mathnet.ru/rus/im3907
  7. Halmos P.R. The Range of a Vector Measure // Bull. Amer. Math. Soc. 1948. V. 54. № 4. P. 416–421. https://doi.org/10.1090/S0002-9904-1948-09020-6
  8. Stromquist W. How to Cut a Cake Fairly // Amer. Math. Monthly. 1980. V. 87. № 8. P. 640–644. https://doi.org/10.1080/00029890.1980.11995109
  9. Su F.E. Rental Harmony: Sperner’s Lemma in Fair Division // Amer. Math. Monthly. 1999. V. 106. № 10. P. 930–942. https://doi.org/10.2307/2589747
  10. Stromquist W. Envy-free Cake Divisions Cannot Be Found by Finite Protocols // Electron. J. Combin. 2008. V. 15. № 1. Research Paper R11 (10 pp.). https://doi.org/10.37236/735
  11. Aziz H., Mackenzie S. A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents // Proc. 2016 IEEE 57th Annu. Symp. on Foundations of Computer Science (FOCS’2016). New Brunswick, NJ, USA. Oct. 9–11, 2016. Los Alamitos, CA: IEEE Comp. Soc., 2016. P. 416–427. https://doi.org/10.1109/FOCS.2016.52
  12. Dehghani S., Farhadi A., HajiAghayi M.T., Yami H. Envy-free Chore Division for an Ar- bitrary Number of Agents // Proc. 29th Annu. ACM–SIAM Symp. on Discrete Algorithms (SODA’2018). New Orleans, LA, USA. Jan. 7–10, 2018. Philadelphia, PA: SIAM, 2018. P. 2564–2583. https://doi.org/10.1137/1.9781611975031.164
  13. Segal-Halevi E. Fairly Dividing a Cake after Some Parts Were Burnt in the Oven. https://arxiv.org/abs/1704.00726v5 [math.CO], 2018.
  14. Бланк М.Л. Как делить неделимое // Докл. Акад. наук. 2016. Т. 471. № 6. С. 635–639. https://doi.org/10.7868/S0869565216360044
  15. Segal-Halevi E., Hassidim A., Aumann Y. Waste Makes Haste: Bounded Time Algorithms for Envy-free Cake Cutting with Free Disposal // ACM Trans. Algorithms. 2016. V. 13. № 1. Art. 12 (32 pp.). https://doi.org/10.1145/2988232

Copyright (c) 2024 Russian Academy of Sciences

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies