• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • Computational complexity of manipulation: A survey
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
November 17, 2026
Physicists Show How a Solvent Shapes the Response of Drug Molecules
Many drug molecules can switch between different three-dimensional shapes. Using a mathematical model of ibuprofen dissolved in supercritical CO₂, researchers from HSE University and the Institute of Solution Chemistry of the Russian Academy of Sciences have shown that the solvent can make these molecules appear to respond unusually slowly. The molecules themselves continue to change shape rapidly, but their surroundings rearrange much more slowly, and this lag shows up in the measurements. The study has been published in The Journal of Chemical Physics. 
November 10, 2026
Physicists Train AI to Optimise Particle Beams in Accelerators
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science and the Budker Institute of Nuclear Physics at the Siberian Branch of the Russian Academy of Sciences have developed RLABC (Reinforcement Learning for Accelerator Beamline Control), a framework that uses reinforcement learning to identify optimal settings for a particle accelerator. In a computer simulation, RLABC optimised the accelerator's parameters to achieve a particle transmission rate of 70%. The study has been published in Computer Physics Communications.
November 9, 2026
'Organ-on-a-Chip Technology Could Eliminate the Need for Animal Testing'
The Laboratory of Molecular Physiology at the HSE Faculty of Biology and Biotechnology investigates how molecular regulators known as microRNAs control gene expression and contribute to the development of diseases, including cancer, viral and inflammatory conditions, and pregnancy complications. At HSE University, researchers develop organ-on-a-chip models: miniature devices containing living cells that mimic the functions of human organs, such as the placenta and intestines. These models help researchers understand how diseases develop and how drugs affect them. HSE News Service spoke with Evgeny Knyazev, Head of the Laboratory.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Computational complexity of manipulation: A survey

Automation and Remote Control. 2016. Vol. 77. No. 3. P. 369–388.
Veselova Y. A.

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.

Priority areas: economics IT and mathematics
Language: English
Full text
DOI
Text on another site
Keywords: коллективный выборsocial choiceвычислительная сложностьманипулированиеmanipulationComputational Complexity
Similar publications
Discount programs as a price discrimination tool for firms operating in markets with shared customer bases
Tabashnikova D., Tikhonova K., / NRU Higher School of Economics. Series EC "Economics". 2026.
Added: November 14, 2026
How Innovation Takes Shape: Organizations, Ecosystems, and Technological Futures
Meissner D., Dong F., Marcondes de Moraes G. et al., / Series WP BRP "Basic research program". 2026. No. WP BRP 131/STI/2026.
The last decades witnessed a never-ending debate about the generation of innovations under different circumstances and, to a lesser extent, on adoption. With a dedicated focus on technologies, the topic of adoption and diffusion emerged only a little. However, this focus is on technologies, expressed in Technology Acceptance Models and Technology Diffusion Models, which cover ...
Added: November 6, 2026
The Social Life of Innovation: Trust, Resistance, and the Unequal Costs of Change
Meissner D., Marcondes de Moraes G., Brandão Fischer B. et al., / Series WP BRP "Basic research program". 2026. No. WP BRP 130/STI/2026.
Innovation has been discussed in political, academic, management and public debates for many years. It’s usually understood as a driver of change and economic development in different contexts depending on the nature of the debate. What is often neglected is society and people’s perceptions. In each debate, a handful of representatives of social groups claim ...
Added: November 6, 2026
Влияние санкционных шоков на техническую эффективность сельскохозяйственных предприятий: опыт молочного животноводства региона
Nikulina Y., / Высшая школа экономики. Серия EC "Economics". 2026. № 1.
This paper estimates the impact of the international sanctions of 2014 and 2022, as well as the food embargo, on the technical efficiency of agricultural enterprises. The assessment was carried out using panel data from agricultural enterprises specializing in dairy production in the Leningrad Region for the period 2010–2023, employing stochastic frontier analysis. It is ...
Added: October 11, 2026
Subsidy Effects on Productivity and Technical Efficiency of Corporate Dairy Farms in the Russian Federation
Nikulina Y., Jamali Jaghdani T., Götz L. et al., / Series "Working Papers". 2026.
The impact of state subsidies on Russia's post-Soviet dairy output remains controversial; this study provides an empirical analysis of that relationship. Using an unbalanced panel dataset of 123 dairy enterprises in the Leningrad Region spanning the period from 2010 to 2023, we employ stochastic frontier analysis to assess these relationships. The results indicate that subsidies ...
Added: September 30, 2026
Отдача от платформенной занятости на российском рынке труда: «премия» или «штраф»?
Kapeliushnikov R., / Высшая школа экономики. Серия WP3 "Проблемы рынка труда". 2026. № WP3/2026/02.
The paper is the first attempt in the Russian literature to assess returns to platform employment in the Russian labor market. The theory offers no clear predictions regarding its impact on workers’ earnings: there might be both a premium and a penalty. We distinguish three groups of workers: employees; self-employed using internet-platforms; self-employed not using ...
Added: September 28, 2026
A Three-Party W-State Quantum Secret Sharing Protocol with X-Gate Encoding and Forbidden-Outcome Detection
Timur Teregulov, Elena R. Loubenets, / Series Quantum Physics "arXiv". 2026. No. 2609.31472.
We develop a new three-party quantum secret-sharing (QSS) protocol based on a three-qubit W state. This protocol encodes the secret-sequence bits using X gates and employs randomly selected Hadamard operations and measurement bases to generate information and security-test rounds. We evaluate the efficiency of the proposed protocol and analyze its security against an internal adversary ...
Added: September 28, 2026
The Effect of AMMs on Price Bubble Formation in Cryptocurrency Markets under Proof-of-Work and Proof-of-Stake
Usvitskiy A., Mizyakov V., / Series "SSRN Working Paper Series". 2026.
Added: September 24, 2026
On calibration of remote sensing retrievals of ecosystem respiration (Reco) with tower measurements over,Russian forests and wetlands
Shabanov N., Kuricheva O., Kurbatova J. et al., / Series Working Papers SSRN "Department of Economics Ca’ Foscari University of Venice". 2026.
The carbon balance of an ecosystem is the difference between Gross Primary Productivity (GPP) and Ecosystem Respiration (Reco) as expressed by Net Ecosystem Exchange (NEE). While remote sensing retrievals of GPP have reached maturity, Reco estimation remains underexplored and ultimately cast bias on NEE. Here we present an end-to-end multi-scale analysis of the mechanism of ...
Added: August 21, 2026
Three Algorithms for Merging Hierarchical Navigable Small World Graphs
Ponomarenko A., / Series Computer Science "arxiv.org". 2025.
This paper addresses the challenge of merging hierarchical navigable small world (HNSW) graphs, a critical operation for distributed systems, incremental indexing, and database compaction. We propose three algorithms for this task: Naive Graph Merge (NGM), Intra Graph Traversal Merge (IGTM), and Cross Graph Traversal Merge (CGTM). These algorithms differ in their approach to vertex selection ...
Added: July 30, 2026
Institutions, Normative Expectations, and Harassment Bribery: Evidence from a Three-country Experiment
Zhuravleva T., Afanasev K., Engelmann J. et al., / Series "SSRN Working Paper Series". 2026.
Extortionary ("harassment") bribery can persist even when widely condemned, consistent with a coordination problem sustained by beliefs about what others do and what others consider acceptable. We study whether a minimal institutional featurethe presence of a third-party monitor empowered to punish-shifts (i) normative expectations about extortion and compliance and (ii) empirical expectations about their prevalence. ...
Added: July 22, 2026
Cyclical Fluctuations, Financial Frictions, and Productivity Differences across Firms
Mishin A., Guerrieri L., Kim J., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Within narrowly defined industries, the most productive firms produce far more than the least productive from the same inputs, and this dispersion widens in downturns. We build a tractable representative-agent model in which financial frictions—adverse selection and moral hazard—make firms sort endogenously into lenders, strategic defaulters, and producers. As credit conditions vary, the resulting misallocation ...
Added: June 28, 2026
Устойчивость на текучей основе: долгосрочная устойчивая цена на нефть
Власов С. А., Nevalennyi M., Сафиулин Р. Р. et al., / Банк России. Серия Аналитическая записка "Материалы Банка России". 2026.
В аналитической записке обсуждается долгосрочно устойчивый уровень цены на российскую нефть. Это тот уровень, к которому цена нефти, вероятнее всего, будет тяготеть в долгосрочной перспективе. Потребность в его определении возникает по нескольким причинам. Во-первых, цена на нефть остается одним из ключевых экономических показателей российской экономики, определяющих экспорт, обменный курс рубля, прибыль, доходы и расходы бюджета, ...
Added: June 27, 2026
Учебная модель малой открытой экономики для анализа денежно-кредитной политики (с примерами из практики Банка России
Глазова А. М., Nevalennyi M., Синяков А. А., / Банк России. Серия Препринты Банка России "Серия докладов об экономических исследованиях". 2025. № 154.
The paper proposes a graphical model of a small open economy. The dynamics of the graphical model is then illustrated using impulse responses from the corresponding formal semi-structural model (QPM model). The authors have several goals in preparing this description of the graphical macroeconomic model. The first goal of the paper is to present an adapted ...
Added: June 27, 2026
A Static Capital Buffer is Hard To Beat
Mishin A., Guerrieri L., Canzoneri M. et al., / Series 2026-042 "Finance and Economics Discussion Series (FEDS)". 2026.
Added: June 27, 2026
Growth in noncommutative algebras and entropy in derived categories
Piontkovski D., / Series arXiv "math". 2026.
A noncommutative projective variety is defined, following Artin and Zhang, by a graded coherent algebra 𝐴. The category of coherent sheaves is then the quotient qgr(𝐴) of the category of finitely presented graded modules by the subcategory of torsion modules. We consider the categorical and polynomial entropies of the Serre twist, that is, of the ...
Added: June 23, 2026
Universal Comparison Methodology for Hough Transform Approaches
Kazimirov D., Vitalii Gulevskii, Kroshnin A. et al., Mathematics 2026 Article 1136
The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations, or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper ...
Added: May 28, 2026
О СЛОЖНОСТИ ПРОБЛЕМЫ ТОТАЛЬНОЙ ВЫВОДИМОСТИ В НЕУКОРАЧИВАЮЩИХ И КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИКАХ
Dudakov S., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
In this paper we study the problem of total derivability in context-free, noncontracting, and context-sensitive grammars. Given a grammar and a terminal word, one has to determine whether there exists a derivation of this word which uses each production no less than a given number of times. It is proved that the problem of total ...
Added: March 18, 2026
О схлопывании вероятностных иерархий. I
Speranski S. O., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Added: December 27, 2025
Некоторые классификации сложности задачи о вершинной 3-раскраске
Дахно Г. С., Malyshev D., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Added: November 26, 2025
NP-полнота игры “Ханаби” при минимальных параметрах
Onoprienko A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters ofthe game ...
Added: November 23, 2025
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке
Rybakov M., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Added: June 21, 2025
Сложность константных фрагментов ненормальных модальных логик
Kudinov A., Rybakov M., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Added: June 21, 2025
Optimal Approximation of Average Reward Markov Decision Processes
Sapronov Y., Yudin N., 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 ...
Added: June 10, 2025
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit