A central theme in computational social choice is to study the extent to which voting systems computationally resist manipulative attacks seeking to influence the outcome of elections, such as manipulation (i.e., strategic voting), control, and bribe
ry. Bucklin and fallback voting are among the voting systems with the broadest resistance (i.e., NP-hardness) to control attacks. However, only little is known about their behavior regarding manipulation and bribery attacks. We comprehensively investigate the computational resistance of Bucklin and fallback voting for many of the common manipulation and bribery scenarios; we also complement our discussion by considering several campaign management problems for Bucklin and fallback.
Previous work on voter control, which refers to situations where a chair seeks to change the outcome of an election by deleting, adding, or partitioning voters, takes for granted that the chair knows all the voters preferences and that all votes are
cast simultaneously. However, elections are often held sequentially and the chair thus knows only the previously cast votes and not the future ones, yet needs to decide instantaneously which control action to take. We introduce a framework that models online voter control in sequential elections. We show that the related problems can be much harder than in the standard (non-online) case: For certain election systems, even with efficient winner problems, online control by deleting, adding, or partitioning voters is PSPACE-complete, even if there are only two candidates. In addition, we obtain (by a new characterization of coNP in terms of weight-bounded alternating Turing machines) completeness for coNP in the deleting/adding cases with a bounded deletion/addition limit, and we obtain completeness for NP in the partition cases with an additional restriction. We also show that for plurality, online control by deleting or adding voters is in P, and for partitioning voters is coNP-hard.
Most work on manipulation assumes that all preferences are known to the manipulators. However, in many settings elections are open and sequential, and manipulators may know the already cast votes but may not know the future votes. We introduce a fram
ework, in which manipulators can see the past votes but not the future ones, to model online coalitional manipulation of sequential elections, and we show that in this setting manipulation can be extremely complex even for election systems with simple winner problems. Yet we also show that for some of the most important election systems such manipulation is simple in certain settings. This suggests that when using sequential voting, one should pay great attention to the details of the setting in choosing ones voting rule. Among the highlights of our classifications are: We show that, depending on the size of the manipulative coalition, the online manipulation problem can be complete for each level of the polynomial hierarchy or even for PSPACE. We obtain the most dramatic contrast to date between the nonunique-winner and unique-winner models: Online weighted manipulation for plurality is in P in the nonunique-winner model, yet is coNP-hard (constructive case) and NP-hard (destructive case) in the unique-winner model. And we obtain what to the best of our knowledge are the first P^NP[1]-completeness and P^NP-completeness results in the field of computational social choice, in particular proving such completeness for, respectively, the complexity of 3-candidate and 4-candidate (and unlimited-candidate) online weighted coalition manipulation of veto elections.
Candidate control of elections is the study of how adding or removing candidates can affect the outcome. However, the traditional study of the complexity of candidate control is in the model in which all candidates and votes are known up front. This
paper develops a model for studying online control for elections where the structure is sequential with respect to the candidates, and in which the decision regarding adding and deleting must be irrevocably made at the moment the candidate is presented. We show that great complexity---PSPACE-completeness---can occur in this setting, but we also provide within this setting polynomial-time algorithms for the most important of election systems, plurality.
Electoral control models ways of changing the outcome of an election via such actions as adding/deleting/partitioning either candidates or voters. To protect elections from such control attempts, computational complexity has been investigated and the
corresponding NP-hardness results are termed resistance. It has been a long-running project of research in this area to classify the major voting systems in terms of their resistance properties. We show that fallback voting, an election system proposed by Brams and Sanver (2009) to combine Bucklin with approval voting, is resistant to each of the common types of control except to destructive control by either adding or deleting voters. Thus fallback voting displays the broadest control resistance currently known to hold among natural election systems with a polynomial-time winner problem. We also study the control complexity of Bucklin voting and show that it performs at least almost as well as fallback voting in terms of control resistance. As Bucklin voting is a special case of fallback voting, each resistance shown for Bucklin voting strengthens the corresponding resistance for fallback voting. Such worst-case complexity analysis is at best an indication of security against control attempts, rather than a proof. In practice, the difficulty of control will depend on the structure of typical instances. We investigate the parameterized control complexity of Bucklin and fallback voting, according to several parameters that are often likely to be small for typical instances. Our results, though still in the worst-case complexity model, can be interpreted as significant strengthenings of the resistance demonstrations based on NP-hardness.
A key question in cooperative game theory is that of coalitional stability, usually captured by the notion of the emph{core}--the set of outcomes such that no subgroup of players has an incentive to deviate. However, some coalitional games have empty
cores, and any outcome in such a game is unstable. In this paper, we investigate the possibility of stabilizing a coalitional game by using external payments. We consider a scenario where an external party, which is interested in having the players work together, offers a supplemental payment to the grand coalition (or, more generally, a particular coalition structure). This payment is conditional on players not deviating from their coalition(s). The sum of this payment plus the actual gains of the coalition(s) may then be divided among the agents so as to promote stability. We define the emph{cost of stability (CoS)} as the minimal external payment that stabilizes the game. We provide general bounds on the cost of stability in several classes of games, and explore its algorithmic properties. To develop a better intuition for the concepts we introduce, we provide a detailed algorithmic study of the cost of stability in weighted voting games, a simple but expressive class of games which can model decision-making in political bodies, and cooperation in multiagent settings. Finally, we extend our model and results to games with coalition structures.
We propose models for lobbying in a probabilistic environment, in which an actor (called The Lobby) seeks to influence voters preferences of voting for or against multiple issues when the voters preferences are represented in terms of probabilities.
In particular, we provide two evaluation criteria and two bribery methods to formally describe these models, and we consider the resulting forms of lobbying with and without issue weighting. We provide a formal analysis for these problems of lobbying in a stochastic environment, and determine their classical and parameterized complexity depending on the given bribery/evaluation criteria and on various natural parameterizations. Specifically, we show that some of these problems can be solved in polynomial time, some are NP-complete but fixed-parameter tractable, and some are W[2]-complete. Finally, we provide approximability and inapproximability results for these problems and several variants.
We study sincere-strategy preference-based approval voting (SP-AV), a system proposed by Brams and Sanver [Electoral Studies, 25(2):287-305, 2006], and here adjusted so as to coerce admissibility of the votes (rather than excluding inadmissible votes
a priori), with respect to procedural control. In such control scenarios, an external agent seeks to change the outcome of an election via actions such as adding/deleting/partitioning either candidates or voters. SP-AV combines the voters preference rankings with their approvals of candidates, where in elections with at least two candidates the voters approval strategies are adjusted--if needed--to approve of their most-preferred candidate and to disapprove of their least-preferred candidate. This rule coerces admissibility of the votes even in the presence of control actions, and hybridizes, in effect, approval with pluralitiy voting. We prove that this system is computationally resistant (i.e., the corresponding control problems are NP-hard) to 19 out of 22 types of constructive and destructive control. Thus, SP-AV has more resistances to control than is currently known for any other natural voting system with a polynomial-time winner problem. In particular, SP-AV is (after Copeland voting, see Faliszewski et al. [AAIM-2008, Springer LNCS 5034, pp. 165-176, 2008]) the second natural voting system with an easy winner-determination procedure that is known to have full resistance to constructive control, and unlike Copeland voting it in addition displays broad resistance to destructive control.
Cake-cutting protocols aim at dividing a ``cake (i.e., a divisible resource) and assigning the resulting portions to several players in a way that each of the players feels to have received a ``fair amount of the cake. An important notion of fairness
is envy-freeness: No player wishes to switch the portion of the cake received with another players portion. Despite intense efforts in the past, it is still an open question whether there is a emph{finite bounded} envy-free cake-cutting protocol for an arbitrary number of players, and even for four players. We introduce the notion of degree of guaranteed envy-freeness (DGEF) as a measure of how good a cake-cutting protocol can approximate the ideal of envy-freeness while keeping the protocol finite bounded (trading being disregarded). We propose a new finite bounded proportional protocol for any number n geq 3 of players, and show that this protocol has a DGEF of 1 + lceil (n^2)/2 rceil. This is the currently best DGEF among known finite bounded cake-cutting protocols for an arbitrary number of players. We will make the case that improving the DGEF even further is a tough challenge, and determine, for comparison, the DGEF of selected known finite bounded cake-cutting protocols.
Holzer and Holzer (Discrete Applied Mathematics 144(3):345--358, 2004) proved that the Tantrix(TM) rotation puzzle problem with four colors is NP-complete, and they showed that the infinite variant of this problem is undecidable. In this paper, we st
udy the three-color and two-color Tantrix(TM) rotation puzzle problems (3-TRP and 2-TRP) and their variants. Restricting the number of allowed colors to three (respectively, to two) reduces the set of available Tantrix(TM) tiles from 56 to 14 (respectively, to 8). We prove that 3-TRP and 2-TRP are NP-complete, which answers a question raised by Holzer and Holzer in the affirmative. Since our reductions are parsimonious, it follows that the problems Unique-3-TRP and Unique-2-TRP are DP-complete under randomized reductions. We also show that the another-solution problems associated with 4-TRP, 3-TRP, and 2-TRP are NP-complete. Finally, we prove that the infinite variants of 3-TRP and 2-TRP are undecidable.
