?
Вычислительная сложность манипулирования в задаче голосования
.
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.
Keywords: коллективный выборsocial choiceвычислительная сложностьманипулированиеsocial choice rulesmanipulationправила коллективного выбораComputational Complexity
Publication based on the results of:
In book
Красноярск : Сибирский федеральный университет, 2014
Veselova Y. A., Автоматика и телемеханика 2016 Т. 77 № 3 С. 7-32
When a society needs to make a collective decision one could apply some aggregation method, particularly, voting. One of the main problems with voting is the manipulability of voting rules. We say a social choice rule is vulnerable to manipulation if there exists at least one voter who can achieve a better voting result by ...
Added: October 25, 2014
Veselova Y. A., 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 ...
Added: June 8, 2016
Veselova Y. A., , in : Clusters, orders, trees: methods and applications. In Honor of Boris Mirkin's 70th Birthday. Vol. 92.: Berlin : Springer, 2014. P. 391-404.
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 ...
Added: October 24, 2013
Subochev A., Журнал Новой экономической ассоциации 2016 № 2(30) С. 181-192
Recently, three ratings of Russian economic journals have been independently proposed by Mura-vyev (2012), Balatsky (2015) and researchers from the Higher School of Economics (2014). In this paper, quantitative estimates of their (in)consistency are obtained. Additionally, these three order-ings are compared to journal rankings based on values of Science Index and 2- and 5-year impact ...
Added: June 26, 2016
Subochev A., В кн. : XVII Апрельская международная научная конференция по проблемам развития экономики и общества: в 4 кн. Кн. 1.: М. : Издательский дом НИУ ВШЭ, 2017. С. 111-120.
A set of related majority rule-based social choice correspondences are considered: the union of minimal Р-dominating sets MPD (Duggan 2011, Subochev 2016) the union of weakly stable sets MWS (Aleskerov & Kurbanov 1999), the union of minimal P-externally stable sets MPES (Wuffl et al. 1989, Subochev 2008) and the union of minimal R-externally stable sets ...
Added: June 26, 2016
Fuad Aleskerov, Karabekyan D., Ivanov A. et al., , in : Evaluating Voting Systems with Probability Models. : Cham : Springer, 2021. P. 231-249.
Added: April 14, 2021
Veselova Y. A., Group Decision and Negotiation 2019
We consider the problem of individual manipulation under incomplete information when voters do not know a full preference profile. Instead, voters know the result of an opinion poll (the outcome of a poll information function pi, e.g. a list of scores or a set of winners). In this case, a voter has an incentive to ...
Added: November 1, 2019
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...
Added: June 6, 2012
Shitov Y., St Petersburg Mathematical Journal 2014 Vol. 26 No. 2 P. 216-228
The tropical arithmetic operations on R are defined as (a,b) -> min{a,b} and (a,b) -> a+b. We are interested in the concept of a semimodule, which is rather ill-behaved in tropical mathematics. In our paper we study the semimodules S in R^n having topological dimension two, and we show that any such S has always ...
Added: May 24, 2014
Aleskerov F. T., Subochev A., Доклады Академии Наук. Информатика 2009 Т. 426 № 3 С. 318-320
A concept of k-stable alternatives is introduced. Relationship of classes of k-stable alternatives with dominant, uncovered and weakly stable sets is established. ...
Added: September 25, 2014
Malyshev D., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
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 ...
Added: November 25, 2012
Sirotkin D., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
The vertex 3-colourability problem is to determine for a given graph whether one can divide its vertex set into three subsets of pairwise non-adjacent vertices. This problem is NP-complete in the class of planar graphs, but it becomes polynomial-time solvable for planar triangulations, i.e. planar graphs, all facets of which (including external) are triangles. Additionally, ...
Added: July 2, 2018
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...
Added: June 23, 2013
Alekseev V., Lozin V. V., Malyshev D. et al., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
We study the computational complexity of finding a maximum independent set of vertices in a planar graph. In general, this problem is known to be NP-hard. However, under certain restrictions it becomes polynomial-time solvable. We identify a graph parameter to which the complexity of the problem is sensible and produce a number of both negative ...
Added: November 7, 2012
Veselova Y. A., В кн. : Управление развитием крупномасштабных систем (MLSD’2019): материалы Двенадцатой международной конференции, 1–3 окт. 2019 г. : Институт проблем управления им. В.А. Трапезникова РАН, 2019. С. 1185-1187.
При манипулировании со стороны коалиций существует опасность получить результат худший,
чем был изначально, если не все члены коалиции решают манипулировать. В этом случае манипулирование
небезопасно. В докладе рассматривается вопрос о том, для каких правил и при каких условиях
манипулирование небезопасно. ...
Added: November 1, 2019
Goldengorin B. I., Malyshev D., Pardalos P. M., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...
Added: June 23, 2013
Karabekyan D., Экономический журнал Высшей школы экономики 2009 Т. 13 № 1 С. 19-34
Рассматриваются предпочтения на множествах альтернатив (расширенные предпочтения). Анализируется ряд известных свойств, которым должны удовлетворять алгоритмы получения расширенных предпочтений из предпочтений на множестве альтернатив. Затем описываются существующие и предлагаются новые методы расширения предпочтений. Выделено три группы методов: лексико-графические, вероятностные и усреднения рангов, которые исследуются на соответствие известным свойствам. Если лексикографические и вероятностные методы для любого числа ...
Added: October 15, 2012
Shitov Y., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Added: February 23, 2016
Sirotkin D., Malyshev D., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766
The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree ...
Added: June 5, 2021
Vassiliev V., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836
The local multiplicities of the caustics, the Maxwell sets, and the complex Stokes' sets in the spaces of versal deformations of Pham singularities (that is, of germs of holomorphic functions C^n --> C^1 which are expressed by the sums of degrees of the coordinate functions) are calculated ...
Added: December 27, 2017
Shvydun S., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...
Added: October 20, 2015
Aleskerov F. T., Karabekyan D., Ivanov A. et al., , in : Procedia Computer Science. Vol. 139: 6th International Conference on Information Technology and Quantitative Management.: Elsevier, 2018. P. 212-220.
The degree of individual manipulability of majoritarian aggregation procedures is evaluated for the case of one-dimensional positioning of alternatives and agents. The calculation of the degree of manipulability is performed for 3-5 alternatives. We find that the group of rules dominates all others in terms of the lowest share of all manipulable profiles, and for ...
Added: October 24, 2018
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Added: November 30, 2012
Aleskerov F. T., Meshcheryakova N., Shvydun S. et al., , in : 6th International Conference on Computers Communications and Control (ICCCC) 2016. : Oradea : Agora University, 2016. P. 118-123.
The problem of quick detection of central nodes in large networks is studied. There are many measures that allow to evaluate a topological importance of nodes of the network. Unfortunately, most of them cannot be applied to large networks due to their high computational complexity. However, if we narrow the initial network and apply these ...
Added: June 8, 2016