Разделения без зависти с учетом социальных сетей с помощью скрытия информации

Задача о справедливом дележе является одной из основных задач теории социального выбора. В последнее время все больше работ начали так или иначе вводить социальные сети в классические критерии, такие как отсутствие зависти или пропорциональность, что позволило создать более эффективные алгоритмы для нахождения таких разделений. Другие работы рассматривают приближения, использующие скрытие предметов, так как в общем случае такие разделения могут не существовать. В данной работе вводятся новые критерии, которые объединяют идею со скрытием фиксированного числа предметов и социальные сети. Таким образом, появляется возможность лучше моделировать реальные ситуации и создавать более эффективные алгоритмы для некоторых классов графов, сохраняя при этом достижимость. Более того, благодаря структуре социальной сети требуется меньшее число скрытий, чем в стандартном случае. В данной работе также изучается параметризованная сложность задач, связанный с данными критериями. Были рассмотрены некоторые хорошо изученные структурные параметры, такие как древесная ширина и кликовая ширина, а также другие параметры, такие как число типов предметов и число типов агентов. Были определены случаи, при которых задачи становятся FPT, и случаи, при которых они W[1]-трудные или еще сложнее. Ключевые слова: Справедливый дележ, параметризованная алгоритмы, W[1]-трудность, древесная ширина, кликовая ширина, точные алгоритмы.