ЭЛЕМЕНТАРНОЕ РЕШЕНИЕ ЗАДАЧИ СПРАВЕДЛИВОГО ДЕЛЕНИЯ

Обложка
  • Авторы: Бланк М.Л1,2,3, Поляков М.О4,5
  • Учреждения:
    1. Институт проблем передачи информацииим. А.А. Харкевича РАН
    2. Национальный исследовательский университет“Высшая школа экономики”
    3. Высшая школа современной математики МФТИ
    4. Институт проблем передачи информации им. А.А. Харкевича РАН
    5. Национальный исследовательский университет “Высшая школа экономики”
  • Выпуск: Том 60, № 1 (2024)
  • Страницы: 41-59
  • Раздел: Большие системы
  • URL: https://journals.rcsi.science/0555-2923/article/view/260299
  • DOI: https://doi.org/10.31857/S0555292324010066
  • EDN: https://elibrary.ru/KJGZYI
  • ID: 260299

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

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

Об авторах

М. Л Бланк

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

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

М. О Поляков

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

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

© Российская академия наук, 2024

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах