We investigate the manipulation of power indices in TU-cooperative games by stimulating (subject to a budget constraint) changes in the propensity of other players to participate to the game. We display several algorithms that show that the problem is often tractable for so-called network centrality games and influence attribution games, as well as an example when optimal manipulation is intractable, even though computing power indices is feasible.
Results on the reliability extension of a cooperative game @cite_17 @cite_43 @cite_4 @cite_41 @cite_5 are naturally related. So is the rich literature on , both in non-cooperative and coalitional settings @cite_6 @cite_9 @cite_10 @cite_0 @cite_35 @cite_20 @cite_45 and @cite_42 in voting. Our framework covers both scenarios, that in which an external perpetrator bribes agents to change their reliabilities, and that in which this is done by a coalition of agents.
@cite_35 @cite_4 @cite_41 @cite_9 @cite_42 @cite_6 @cite_0 @cite_43 @cite_45 @cite_5 @cite_10 @cite_20 @cite_17
1852468282 1540727845 2100229481 2163422411
Weighted voting games are a popular model of collaboration in multiagent systems. In such games, each agent has a weight (intuitively corresponding to resources he can contribute), and a coalition of agents wins if its total weight meets or exceeds a given threshold. Even though coalitional stability in such games is important, existing research has nonetheless only considered the stability of the grand coalition. In this paper, we introduce a model for weighted voting games with coalition structures. This is a natural extension in the context of multiagent systems, as several groups of agents may be simultaneously at work, each serving a different task. We then proceed to study stability in this context. First, we define the CS-core, a notion of the core for such settings, discuss its non-emptiness, and relate it to the traditional notion of the core in weighted voting games. We then investigate its computational properties. We show that, in contrast with the traditional setting, it is computationally hard to decide whether a game has a non-empty CS-core, or whether a given outcome is in the CS-core. However, we then provide an efficient algorithm that verifies whether an outcome is in the CS-core if all weights are small (polynomially bounded). Finally, we also suggest heuristic algorithms for checking the non-emptiness of the CS-core. One key question in cooperative game theory is that of coalitional stability. A coalition in such games is stable when no subset of the agents in it has a rational incentive to leave the coalition. Finding a division of the gains of the coalition (an imputation) lies at the heart of many cooperative game theory solution concepts, the most prominent of which is the core. However, some coalitional games have empty cores, and any imputation in such a game is unstable. We investigate the possibility of stabilizing the coalitional structure using external payments. In this case, a supplemental payment is offered to the grand coalition by an external party which is interested in having the members of the coalition work together. The sum of this payment plus the gains of the coalition, called the coalition's "adjusted gains", may be divided among the members of the coalition in a stable manner. We call a division of the adjusted gains a super-imputation, and define the cost of stability (CoS) as the minimal sum of payments that stabilizes the coalition. We examine the cost of stability in weighted voting games, where each agent has a weight, and a coalition is successful if the sum of its weights exceeds a given threshold. Such games offer a simple model of decision making in political bodies, and of cooperation in multiagent settings. We show that it is coNP-complete to test whether a super-imputation is stable, but show that if either the weights or payments of agents are bounded then there exists a polynomial algorithm for this problem. We provide a polynomial approximation algorithm for computing the cost of stability. We study the complexity of influencing elections through bribery: How computationally complex is it for an external actor to determine whether by paying certain voters to change their preferences a specified candidate can be made the election's winner? We study this problem for election systems as varied as scoring protocols and Dodgson voting, and in a variety of settings regarding homogeneous-vs.-nonhomogeneous electorate bribability, bounded-size-vs.-arbitrary-sized candidate sets, weighted-vs.-unweighted voters, and succinct-vs.-nonsuccinct input specification. We obtain both polynomial-time bribery algorithms and proofs of the intractability of bribery, and indeed our results show that the complexity of bribery is extremely sensitive to the setting. For example, we find settings in which bribery is NP-complete but manipulation (by voters) is in P, and we find settings in which bribing weighted voters is NP-complete but bribing voters with individual bribe thresholds is in P. For the broad class of elections (including plurality, Borda, k- approval,and veto) known as scoring protocols, we prove a dichotomy result for bribery of weighted voters: We find a simple-to-evaluate condition that classifies every case as either NP-complete or in P. We examine agent failures in weighted voting games. In our cooperative game model, R-WVG, each agent has a weight and a survival probability, and the value of an agent coalition is the probability that its surviving members would have a total weight exceeding a threshold. We propose algorithms for computing the value of a coalition, finding stable payoff allocations, and estimating the power of agents. We provide simulation results showing that on average the stability level of a game increases as the failure probabilities of the agents increase. This conforms to several recent results showing that failures increase stability in cooperative games.