?
Computational complexity of manipulation: A survey
Automation and Remote Control. 2016. Vol. 77. No. 3. P. 369–388.
In situations when a group of people has to make a decision based on the set of individual preferences, they use a certain aggregation method, in particular, voting. One of the main problems for any non-dictatorial social choice rule is the possibility for the voters to achieve a more preferable outcome of the voting by misrepresenting their preferences. Such actions on behalf of the voters are called manipulation, or strategic voting. One approach used to compare social choice rules in terms of how hard they are to manipulate is to find the complexity classes of manipulation problems for a given aggregation method. In this work, we present a survey of the studies of complexity classes of manipulation problems under various model assumptions and constraints.
Язык:
английский
Никулина Ю. Н., / Высшая школа экономики. Серия EC "Economics". 2026. № 1.
В работе оценивается влияние международных санкций 2014 г. и 2022 г., а также
продовольственного эмбарго на техническую эффективность сельскохозяйственных
предприятий. Оценка выполнена на панельных данных сельскохозяйственных
организаций молочной специализации Ленинградской области за 2010-2023 гг. с
использованием анализа стохастической границы. Показано, что продовольственное
эмбарго 2014 г. сопровождалось снижением технической эффективности
сельскохозяйственных предприятий, тогда как эффектом санкций стало приближение к
производственной границе, что может ...
Добавлено: 11 октября 2026 г.
Добавлено: 30 сентября 2026 г.
Капелюшников Р. И., / Высшая школа экономики. Серия WP3 "Проблемы рынка труда". 2026. № WP3/2026/02.
В работе впервые в отечественной литературе оценивается отдача от платформенной занятости на российском рынке труда. Теория не дает однозначных предсказаний относительно влияния этой формы занятости на заработки: это может быть как премия, так и штраф. Выделяются три группы занятых: наемные работники; ненаемные работники, использующие интернет-платформы; ненаемные работники, не использующие интернет-платформы. Эмпирическую базу составляют микроданные Проекта ...
Добавлено: 28 сентября 2026 г.
Timur Teregulov, Elena R. Loubenets, / Series Quantum Physics "arXiv". 2026. No. 2609.31472.
Добавлено: 28 сентября 2026 г.
Усвицкий А. В., Мизяков В. С., / Series "SSRN Working Paper Series". 2026.
Добавлено: 24 сентября 2026 г.
Shabanov N., Kuricheva O., Kurbatova J. и др., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
Добавлено: 21 августа 2026 г.
Добавлено: 22 июля 2026 г.
Мишин А. О., Guerrieri L., Kim J., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Добавлено: 28 июня 2026 г.
Власов С. А., Неваленный М. Ю., Сафиулин Р. Р. и др., / Банк России. Серия Аналитическая записка "Материалы Банка России". 2026.
В аналитической записке обсуждается долгосрочно устойчивый уровень цены на российскую нефть. Это тот уровень, к которому цена нефти, вероятнее всего, будет тяготеть в долгосрочной перспективе. Потребность в его определении возникает по нескольким причинам. Во-первых, цена на нефть остается одним из ключевых экономических показателей российской экономики, определяющих экспорт, обменный курс рубля, прибыль, доходы и расходы бюджета, ...
Добавлено: 27 июня 2026 г.
Глазова А. М., Неваленный М. Ю., Синяков А. А., / Банк России. Серия Препринты Банка России "Серия докладов об экономических исследованиях". 2025. № 154.
В статье предлагается учебная графическая модель малой открытой экономики. Динамика наглядной модели затем иллюстрируется посредством импульсных откликов из соответствующей ей формальной полуструктурной модели (КПМ). Принимаясь за подготовку этого описания на основе графической макроэкономической модели, авторы преследуют несколько целей. Первая цель работы: представить адаптированную версию графической модели принятия решений современным центральным банком для читателей, которым может быть сложно сразу разбираться с продвинутыми графическими ...
Добавлено: 27 июня 2026 г.
Мишин А. О., Guerrieri L., Canzoneri M. и др., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Добавлено: 27 июня 2026 г.
Богатырёв Р. А., Сандомирская М. С., / NRU Higher School of Economics. Series EC "Economics". 2026. No. 19(1).
This work develops a tractable model of price competition in fragmented markets where consumers consider both local and distant varieties, with cross-regional purchases subject to stochastic costs. Global competition and full localization emerge as polar cases; hybrid competition is not merely intermediate and exhibits distinctive features such as an endogenous price ceiling and non-monotonic entry ...
Добавлено: 11 июня 2026 г.
Добавлено: 28 мая 2026 г.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Сапронов Ю. Ф., Юдин Н. Е., Computational Mathematics and Mathematical Physics 2025 Vol. 65 No. 3 P. 567–581
We continue to develop the concept of studying the ε-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods ...
Добавлено: 10 июня 2025 г.