ELEMENTARNOE REShENIE ZADAChI SPRAVEDLIVOGO DELENIYa

Мұқаба
  • Авторлар: Blank M.L1,2,3, Polyakov M.O4,5
  • Мекемелер:
    1. Институт проблем передачи информацииим. А.А. Харкевича РАН
    2. Национальный исследовательский университет“Высшая школа экономики”
    3. Высшая школа современной математики МФТИ
    4. Институт проблем передачи информации им. А.А. Харкевича РАН
    5. Национальный исследовательский университет “Высшая школа экономики”
  • Шығарылым: Том 60, № 1 (2024)
  • Беттер: 41-59
  • Бөлім: Large Systems
  • URL: https://rjsocmed.com/0555-2923/article/view/667559
  • DOI: https://doi.org/10.31857/S0555292324010066
  • EDN: https://elibrary.ru/KJGZYI
  • ID: 667559

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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

Авторлар туралы

M. Blank

Институт проблем передачи информацииим. А.А. Харкевича РАН; Национальный исследовательский университет“Высшая школа экономики”; Высшая школа современной математики МФТИ

Email: blank@iitp.ru
Москва, Россия

M. Polyakov

Институт проблем передачи информации им. А.А. Харкевича РАН; Национальный исследовательский университет “Высшая школа экономики”

Email: pmaxol73@gmail.com
Москва, Россия

Әдебиет тізімі

  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

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу

© Russian Academy of Sciences, 2024