Вычислительная сложность манипулирования в задаче голосования
When a society needs to take a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is manipulation. We say a voting rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by misrepresenting his or her preferences. The popular approach to comparing manipulability of voting rules is defining complexity class of the corresponding manipulation problem. This paper provides a survey into manipulation complexity literature considering variety of problems with different assumptions and restrictions.
Procedures aggregating individual preferences into a collective choice differ in their vulnerability to manipulations. To measure it, one may consider the share of preference profiles where manipulation is possible in the total number of profiles, which is called Nitzan-Kelly's index of manipulability. The problem of manipulability can be considered in different probability models. There are three models based on anonymity and neutrality: impartial culture model (IC), impartial anonymous culture model (IAC), and impartial anonymous and neutral culture model (IANC). In contrast to the first two models, the IANC model, which is based on anonymity and neutrality axioms, has not been widely studied. In addition, there were no attempts to derive the difference of probabilities (such as Nitzan-Kelly's index) in IC and IANC analytically. We solve this problem and show in which cases the upper bound of this difference is high enough, and in which cases it is almost zero. These results enable us to simplify the computation of indices.
The author believes that today propaganda is a two way mechanism of communication. In addition to imposing and informational pressure, it involves the formation of public opinion on the basis of awareness of the benefits of the proposed policy for the society. Propaganda is not only a tool of ideology, but also an independent element in the overall structure of the ideological system, especially in conditions of Soviet "idiocracy". Therefore all attempts of Western political science and sociology to separate propaganda and education do not work on the example of Soviet reality.
This article describesseveral impossibility results in social choice theory and demonstrates their importance for democratic theory. Since 1950s social scientists paid a great attention to the investigation of collective decision-making. This interest led to the formation of a new field of study within economics and political science, social choice theory. The main resultsof this strand of research are various impossibilitytheorems which illustrateinconsistencies indifferentvoting rules. Arrow`s impossibility theorem is usually considered to bethe most important result of this kind: however, many other impossibility theorems were proved during the last fifty years, among them the Gibbard-Satterthwaite theorem, Amartya Sen's liberal paradox and discursive dilemma. These paradoxical findingsreveal serious inner defects of democratic decision-making and therefore challenge the democratic idea itself, which is presumably the central project of modern political thought. Therefore, they are of great interest for democratic theorists.
Originally published in 1951, Social Choice and Individual Valuesintroduced “Arrow’s Impossibility Theorem” and founded the field of social choice theory in economics and political science. This new edition, including a new foreword by Nobel laureate Eric Maskin, reintroduces Arrow’s seminal book to a new generation of students and researchers.
"Far beyond a classic, this small book unleashed the ongoing explosion of interest in social choice and voting theory. A half-century later, the book remains full of profound insight: its central message, ‘Arrow’s Theorem,’ has changed the way we think.”—Donald G. Saari, author of Decisions and Elections: Explaining the Unexpected
Kenneth J. Arrow is professor of economics emeritus, Stanford University, and a Nobel laureate. Eric S. Maskin is Albert O. Hirschman Professor, School of Social Science, Institute of Advanced Study, Princeton, NJ, and a Nobel laureate.
Aleskerov et al.  and  estimated the degree of manipulability for the case of multi-valued choice (without using any tie-breaking rule) and for Impartial Culture (IC). In our paper, we address the similar question for the multi-valued choice and for Impartial Anonymous Culture (IAC). We use Nitzan-Kelly's (NK) index to estimate the degree of manipulability, which is calculated as the share of all manipulable voting situations, and calculate indices for 3 alternatives and up to 10000 voters. We have found that for the case of 3 alternatives Nanson's procedure shows the best results. Hare's procedure shows close, but a bit higher results. The worst aggregation procedure in terms of manipulability is Plurality rule. Additionally, it turned out that NK indices for IAC are smaller than NK indices for IC.
The article is devoted to the development of the principles of communicative strategies typology construction which is considered to be a method of scientific research of individuals' communicative interaction.
Conference Proceedings report findings presented at the 20th Annual Conference of the National Association of Teachers of English in Russia held in Voronezh in April, 2014. The proceedings might be useful for English language teachersworking at different levels - from University to kindergarten. linguists, interpreters and translators, as well as students and postgraduates majoring in EFL, linguistics and cultural studies.