Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userElection Control by Manipulating Issue Significance
137
0
0.0
(
0
)
Added by
Andrew Estornell
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Integrity of elections is vital to democratic systems, but it is frequently threatened by malicious actors. The study of algorithmic complexity of the problem of manipulating election outcomes by changing its structural features is known as election control. One means of election control that has been proposed is to select a subset of issues that determine voter preferences over candidates. We study a variation of this model in which voters have judgments about relative importance of issues, and a malicious actor can manipulate these judgments. We show that computing effective manipulations in this model is NP-hard even with two candidates or binary issues. However, we demonstrate that the problem is tractable with a constant number of voters or issues. Additionally, while it remains intractable when voters can vote stochastically, we exhibit an important special case in which stochastic voting enables tractable manipulation.
rate research
Read More
Constructive election control considers the problem of an adversary who seeks to sway the outcome of an electoral process in order to ensure that their favored candidate wins. We consider the computational problem of constructive election control via issue selection. In this problem, a party decides which political issues to focus on to ensure victory for the favored candidate. We also consider a variation in which the goal is to maximize the number of voters supporting the favored candidate. We present strong negative results, showing, for example, that the latter problem is inapproximable for any constant factor. On the positive side, we show that when issues are binary, the problem becomes tractable in several cases, and admits a 2-approximation in the two-candidate case. Finally, we develop integer programming and heuristic methods for these problems.
In 1998 a long-lost proposal for an election law by Gottlob Frege (1848--1925) was rediscovered in the Thuringer Universitats- und Landesbibliothek in Jena, Germany. The method that Frege proposed for the election of representatives of a constituency features a remarkable concern for the representation of minorities. Its core idea is that votes cast for unelected candidates are carried over to the next election, while elected candidates incur a cost of winning. We prove that this sensitivity to past elections guarantees a proportional representation of political opinions in the long run. We find that through a slight modification of Freges original method even stronger proportionality guarantees can be achieved. This modified version of Freges method also provides a novel solution to the apportionment problem, which is distinct from all of the best-known apportionment methods, while still possessing noteworthy proportionality properties.
In recent years, the optical control of exchange interactions has emerged as an exciting new direction in the study of the ultrafast optical control of magnetic order. Here we review recent theoretical works on antiferromagnetic systems, devoted to i) simulating the ultrafast control of exchange interactions, ii) modeling the strongly nonequilibrium response of the magnetic order and iii) the relation with relevant experimental works developed in parallel. In addition to the excitation of spin precession, we discuss examples of rapid cooling and the control of ultrafast coherent longitudinal spin dynamics in response to femtosecond optically induced perturbations of exchange interactions. These elucidate the potential for exploiting the control of exchange interactions to find new scenarios for both faster and more energy-efficient manipulation of magnetism.
The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not incentive-compatible, thereby these desirable properties only hold for the agents declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is $frac{3}{2}$. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agents utility gain on average by experiments. The experiments show that an agent incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.
In an election, we are given a set of voters, each having a preference list over a set of candidates, that are distributed on a social network. We consider a scenario where voters may change their preference lists as a consequence of the messages received by their neighbors in a social network. Specifically, we consider a political campaign that spreads messages in a social network in support or against a given candidate and the spreading follows a dynamic model for information diffusion. When a message reaches a voter, this latter changes its preference list according to an update rule. The election control problem asks to find a bounded set of nodes to be the starter of a political campaign in support (constructive problem) or against (destructive problem) a given target candidate $c$, in such a way that the margin of victory of $c$ w.r.t. its most voted opponents is maximized. It has been shown that several variants of the problem can be solved within a constant factor approximation of the optimum, which shows that controlling elections by means of social networks is doable and constitutes a real problem for modern democracies. Most of the literature, however, focuses on the case of single-winner elections. In this paper, we define the election control problem in social networks for multi-winner elections with the aim of modeling parliamentarian elections. Differently from the single-winner case, we show that the multi-winner election control problem is NP-hard to approximate within any factor in both constructive and destructive cases. We then study a relaxation of the problem where votes are aggregated on the basis of parties (instead of single candidates), which is a variation of the so-called straight-party voting used in some real parliamentarian elections. We show that the latter problem remains NP-hard but can be approximated within a constant factor.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
