?
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.
Kravtsova M., Musaev A. U., Welzel C., / Series "SSRN Working Paper Series". 2026.
Elaborating on Welzel et al.'s "Cool Water Theory," our study zooms into the more limited (albeit still varied) framework conditions of Russia's huge territory. Within Russia's confines, we examine how the combination of moderately cool seasons with steady rain (i.e., Cool Water) affects sub-national areas' contemporary societal progress in two modernization indicators: material prosperity in ...
Added: June 3, 2026
Синяков А. А., Зверева В., Шелованова Т. И., / Центральный банк Российской Федерации. Серия 132 / 2024 "Серия докладов об экономических исследованиях". 2024. № 132.
At the end of 2023, Russia updated its Strategy for Improving Financial Literacy and Developing Financial Culture Until 2030. Unlike the previous strategy, the current strategic goals include not only financial literacy but also financial culture. ‘Culture’ is normative and socially preferred behaviour. The updated strategy brings into focus the relationship between financial literacy and responsible financial behaviour. To explore this relationship, the authors rely on data from the All-Russian Survey of Consumer Finance (2020 and 2022). Socially ...
Added: June 1, 2026
Vorchik A., / SSRN. Серия Social Science Research Network "Social Science Research Network". 2026.
This work is devoted to a theoretical explanation of the Easterlin paradox, according to which long-term economic growth does not make average level of people's happiness increasing. By happiness, we mean the intensity of emotions people experience while comparing their new income with its expected value, or the target income with its original value. In the first case, ...
Added: May 31, 2026
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
Shipilov F., Barnyakov A., Ivanov A. et al., / Series Physics "arxiv.org". 2026.
A fast simulation of the detector response is a vital task in high-energy physics (HEP). Traditional Monte-Carlo methods form the backbone of modern particle physics simulation software but are computationally expensive. We present a machine-learning-based approach to fast simulation of the Focusing Aerogel Ring Imaging Cherenkov (FARICH) detector response. Given a particle track and momentum, ...
Added: May 19, 2026
Derkacheva A., Sakirkina M., Kraev G. et al., /. 2026.
Comprehensive data on natural hazards and their consequences are crucial for effective for risk assessment, adaptation planning, and emergency response. However, many countries face challenges with fragmented, inconsistent, and inaccessible data, particularly regarding local-scale events. To address this data gap in Russia, we developed an end-to-end processing pipeline that scrapes news from various online sources, ...
Added: April 28, 2026
Pilé I., Deng Y., Shchur L., / Series arXiv "math". 2026. No. 2604.10254.
We investigate the spatial overlap of successive spin configurations in Markov chain Monte Carlo simulations using the local Metropolis algorithm and the Svendsen-Wang and Wolff cluster algorithms. We examine the dynamics of these algorithms for two models in different universality classes: the Ising model and the Potts model with three components. The overlap of two ...
Added: April 20, 2026
Ustyuzhanin V., / Series Econometrics "arxiv". 2026.
This paper proposes Covariate-Balanced Weighted Stacked Difference-in-Differences (CBWSDID), a design-based extension of weighted stacked DID for settings in which untreated trends may be conditionally rather than unconditionally parallel. The estimator separates within-subexperiment design adjustment from across-subexperiment aggregation: matching or weighting improves treated-control comparability within each stacked subexperiment, while the corrective stacked weights of Wing et ...
Added: April 3, 2026
Gabdullin N., Androsov I., / Series Computer Science "arxiv.org". 2026.
Label prediction in neural networks (NNs) has O(n) complexity proportional to the number of classes. This holds true for classification using fully connected layers and cosine similarity with some set of class prototypes. In this paper we show that if NN latent space (LS) geometry is known and possesses specific properties, label prediction complexity can ...
Added: April 2, 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
Vorchik A., / Social Science Research Network. Серия SSRN Working Paper Series "SSRN Working Paper Series". 2026.
This article is devoted to the phenomenon of intrinsic motivation, to understand which two models are proposed. We study how positive/negative intrinsic motivation to work (experienced utility) affects worker's individual labour supply (model I) and the amount of effort they exert (model II). In model I, we use intrinsic motivation to explain the positive/negative slope ...
Added: March 15, 2026
Vorchik A., Мамышев М. А., / Series Social Science Research Network "Social Science Research Network". 2025.
In this paper, we develop a formal mathematical model aimed to explain the Dunning-Kruger effect that beginners systematically overestimate their own competence in various fields of knowledge and activity. We argue that the Dunning-Kruger effect arises from the emotional nature of confidence combined with unknown unknowns that it simply can not take into account due ...
Added: February 11, 2026
Musaev A. U., Vorchik A., / Series Social Science Research Network "Social Science Research Network". 2026.
This paper attempts to model the evolutionary theory of modernization and democratization. The model reflects the key provisions of R. Inglehart and C. Welzel's theory and provides a microfoundation for the adaptation of subjective values to the objective importances of the survival factors and the structure of the labour markets from the perspective of evolutionary ...
Added: February 10, 2026
Antsygina A., Teteryatnikova M., Tremewan J. C. et al., / Series "SSRN Working Paper Series". 2025.
Many competitive environments allow for a third party to be indirectly involved by supporting one or both sides in the conflict. Such support can come from trade partners, colleagues, or allies, who can in turn benefit from a supported party's success. We use theory and an experiment to investigate how support relationships develop endogenously in ...
Added: January 31, 2026
Akhmedova A., / Series "SSRN Working Paper Series". 2026.
The study explores a psychological phenomenon of inaction inertia-avoiding action after missing a more favourable opportunity. Unlike action inertia (e.g.,sunk costs effect), inaction inertia has been less studied, particularly in economic contexts. Considering the reference dependent nature of the phenomenon, I build on the work of Kőszegi and Rabin (2006) to examine how past experiences ...
Added: January 23, 2026
Speranski S. O., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Added: December 27, 2025
Дахно Г. С., Malyshev D., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Added: November 26, 2025
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
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
Veselova Y. A., Maastricht: Maastricht University, 2023.
Collective decision-making is a part of everyday life in modern society. People invented a variety of voting procedures for aggregating individual preferences into a collective choice. However, the problem is that people can misrepresent their preferences in order to achieve a more preferable voting result. This phenomenon is called manipulation and is considered negative since ...
Added: February 26, 2025
Дахно Г. С., Malyshev D., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Added: December 3, 2024
Kryukov G. M., Sandomirskaia M., Automation and Remote Control 2024 Vol. 85 P. 696–710
In this paper, the disclosure of information about the scoring model is investigated. Some of the company’s customers find out their internal rating in the company. Such customers can change their behavior to increase their internal rating. The customers who are aware of the leakage are represented as players who can choose a strategy: whether ...
Added: November 19, 2024