Voting is a simple mechanism to aggregate the preferences of agents. Many voting rules have been shown to be NP-hard to manipulate. However, a number of recent theoretical results suggest that this complexity may only be in the worst-case since manipulation is often easy in practice. In this paper, we show that empirical studies are useful in improving our understanding of this issue. We demonstrate that there is a smooth transition in the probability that a coalition can elect a desired candidate using the veto rule as the size of the manipulating coalition increases. We show that a rescaled probability curve displays a simple and universal form independent of the size of the problem. We argue that manipulation of the veto rule is asymptotically easy for many independent and identically distributed votes even when the coalition of manipulators is critical in size. Based on this argument, we identify a situation in which manipulation is computationally hard. This is when votes are highly correlated and the election is "hung". We show, however, that even a single uncorrelated voter is enough to make manipulation easy again.
Finally, similar phenomena have been observed in the phase transition for the Hamiltonian cycle problem @cite_22 @cite_11 . If the number of edges is small, there is likely to be a node of degree smaller than 2. There cannot therefore be any Hamiltonian cycle. By the time that there are enough edges for all nodes to be of degree 2, there are likely to be many possible Hamiltonian cycles and even a simple heuristic can find one. Thus, the phase transition in the existence of a Hamiltonian cycle is not associated with hard instances of the problem. The behavior seen here is similar. By the time the coalition is large enough to manipulate the result, the variance in scores between the candidates is likely to be so large that computing a successful manipulation or proving none is possible is easy.
@cite_22 @cite_11
2045652154 1938603953
Abstract We continue the study of boundary classes for NP -hard problems and focus on seven NP -hard graph problems involving non-local properties: Hamiltonian Cycle , Hamiltonian Cycle Through Specified Edge , Hamiltonian Path , Feedback Vertex Set , Connected Vertex Cover , Connected Dominating Set and Graph VC CON Dimension . Our main result is the determination of the first boundary class for Feedback Vertex Set . We also determine boundary classes for Hamiltonian Cycle Through Specified Edge and Hamiltonian Path and give some insights on the structure of some boundary classes for the remaining problems. Using an improved backtrack algorithm with sophisticated pruning techniques, we revise previous observations correlating a high frequency of hard to solve Hamiltonian cycle instances with the Gn,m phase transition between Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500 vertices are easily solved. When we artificially restrict the degree sequence with a bounded maximum degree, although there is some increase in difficulty, the frequency of hard graphs is still low. When we consider more regular graphs based on a generalization of knight's tours, we observe frequent instances of really hard graphs, but on these the average degree is bounded by a constant. We design a set of graphs with a feature our algorithm is unable to detect and so are very hard for our algorithm, but in these we can vary the average degree from O(1) to O(n). We have so far found no class of graphs correlated with the Gn,m phase transition which asymptotically produces a high frequency of hard instances.