### Article

## Computational complexity of manipulation: A survey

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.

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for the 3-colouring problem is infinite.

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 notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and Vertex k-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k > 3 there is a continuum of boundary classes for Vertex k-colorability.

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.

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.

This book constitutes the refereed proceedings of the 23rd Annual Symposium on Combinatorial Pattern Matching, CPM 2012, held in Helsinki, Finalnd, in July 2012. The 33 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 60 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees, regular expressions, graphs, point sets, and arrays. The goal is to derive non-trivial combinatorial properties of such structures and to exploit these properties in order to either achieve superior performance for the corresponding computational problems or pinpoint conditions under which searches cannot be performed efficiently. The meeting also deals with problems in computational biology, data compression and data mining, coding, information retrieval, natural language processing, and pattern recognition.

The notion of a boundary class is a useful notion in the investigation of the complexity of extremal problems on graphs. One boundary class is known for the independent set problem and three boundary classes are known for the dominating set problem. In this paper it is proved that the set of boundary classes for the 3-colouring problem is infinite.