Автор(ы): Карпов А. В. (ИПУ РАН, Лаборатория 25)Образцова С. (Наньянский Технологический Университет)Faliszewski P. (AGH University)Автор(ов): 3 Параметры публикацииТип публикации: Статья в журнале/сборникеНазвание: The complexity of election problems with group-separable preferencesISBN/ISSN: 1387-2532DOI: 10.1007/s10458-022-09549-7Наименование источника: Autonomous Agents and Multi-Agent SystemsОбозначение и номер тома: Т. 36, вып.1Город: ГейдельбергИздательство: SpringerГод издания: 2022Страницы: 18 (1-28) АннотацияWe analyze the complexity of several NP-hard election-related problems under the assumptions that the voters have group-separable preferences. We show that under this assumption our problems typically remain NP-hard, but we provide more efcient algorithms if additionally the clone decomposition tree is of moderate height. We also show a polynomial time algorithm for sampling group-separable elections uniformly at random. Библиографическая ссылка: Карпов А.В., Образцова С., Faliszewski P. The complexity of election problems with group-separable preferences // Autonomous Agents and Multi-Agent Systems. 2022. Т. 36, вып.1. С. 18 (1-28).