ELEMENTARNOE REShENIE ZADAChI SPRAVEDLIVOGO DELENIYa

Capa
  • Autores: Blank M.L1,2,3, Polyakov M.O4,5
  • Afiliações:
    1. Институт проблем передачи информацииим. А.А. Харкевича РАН
    2. Национальный исследовательский университет“Высшая школа экономики”
    3. Высшая школа современной математики МФТИ
    4. Институт проблем передачи информации им. А.А. Харкевича РАН
    5. Национальный исследовательский университет “Высшая школа экономики”
  • Edição: Volume 60, Nº 1 (2024)
  • Páginas: 41-59
  • Seção: Large Systems
  • URL: https://freezetech.ru/0555-2923/article/view/667559
  • DOI: https://doi.org/10.31857/S0555292324010066
  • EDN: https://elibrary.ru/KJGZYI
  • ID: 667559

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

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

Sobre autores

M. Blank

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

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

M. Polyakov

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

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

Bibliografia

  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

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © Russian Academy of Sciences, 2024