?
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.
Язык:
английский
Мишин А. О., 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 г.
Добавлено: 3 июня 2026 г.
Синяков А. А., Зверева В., Шелованова Т. И., / Центральный банк Российской Федерации. Серия 132 / 2024 "Серия докладов об экономических исследованиях". 2024. № 132.
В конце 2023 года в России была принята обновленная Стратегия повышения финансовой грамотности и формирования финансовой культуры до 2030 года. В отличие от предыдущей стратегии, в новом документе целью признается не только финансовая грамотность, но и финансовая культура. Культура — это нормативное, ответственное с точки зрения общества поведение. Обновленная стратегия делает актуальным вопрос о связи финансовой грамотности и ответственного финансового поведения. Данные «Всероссийского обследования населения по потребительским финансам» за 2020 и 2022 годы используются ...
Добавлено: 1 июня 2026 г.
Ворчик А. Д., / SSRN. Серия Social Science Research Network "Social Science Research Network". 2026.
Эта работа посвящена теоретическому объяснению парадокса Истерлина, согласно которому долгосрочный экономический рост не приводит к росту среднего уровня счастья людей. Под счастьем мы понимаем интенсивность эмоций, которые люди испытывают, когда сравнивают свой новый доход с ожидаемым либо целевой - с изначальным. В первом случае мы имеем дело с реактивным подходом к росту, тогда как во втором ...
Добавлено: 31 мая 2026 г.
Добавлено: 28 мая 2026 г.
Добавлено: 19 мая 2026 г.
Добавлено: 28 апреля 2026 г.
Добавлено: 20 апреля 2026 г.
Gabdullin N., Андросов И. А., / Series Computer Science "arxiv.org". 2026.
Добавлено: 2 апреля 2026 г.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Ворчик А. Д., / Social Science Research Network. Серия SSRN Working Paper Series "SSRN Working Paper Series". 2026.
Эта статья посвящена феномену внутренней мотивации, для понимания которого предлагаются две модели. Исследуется, как положительная/отрицательная внутренняя мотивация к работе (испытываемая полезность) влияет на предложение труда работника (модель I) и количество прикладываемых им усилий (модель II). В модели I внутренняя мотивация позволяет объяснить положительный/отрицательный наклон и возможное загибание кривой индивидуального предложения труда (backward-bending labour supply curve). ...
Добавлено: 15 марта 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 г.