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

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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

作者简介

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