Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Complexity of the Possible Winner Problem over Partitioned Preferences
126
0
0.0
(
0
)
Added by
Batya Kenig
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Batya Kenig
Ask ChatGPT about the research
No Arabic abstract
The Possible-Winner problem asks, given an election where the voters preferences over the set of candidates is partially specified, whether a distinguished candidate can become a winner. In this work, we consider the computational complexity of Possible-Winner under the assumption that the voter preferences are $partitioned$. That is, we assume that every voter provides a complete order over sets of incomparable candidates (e.g., candidates are ranked by their level of education). We consider elections with partitioned profiles over positional scoring rules, with an unbounded number of candidates, and unweighted voters. Our first result is a polynomial time algorithm for voting rules with $2$ distinct values, which include the well-known $k$-approval voting rule. We then go on to prove NP-hardness for a class of rules that contain all voting rules that produce scoring vectors with at least $4$ distinct values.
rate research
Read More
It remains an open question how to determine the winner of an election given incomplete or uncertain voter preferences. One solution is to assume some probability space for the voting profile and declare the candidates having the best chance of winning to be the (co-)winners. We refer to this as the Most Probable Winner (MPW). In this paper, we propose an alternative winner interpretation for positional scoring rules - the Most Expected Winner (MEW), based on the expected performance of the candidates. This winner interpretation enjoys some desirable properties that the MPW does not. We establish the theoretical hardness of MEW over incomplete voter preferences, then identify a collection of tractable cases for a variety of voting profiles. An important contribution of this work is to separate the voter preferences into the generation step and the observation step, which gives rise to a unified voting profile combining both incomplete and probabilistic voting profiles.
We study the following communication variant of local search. There is some fixed, commonly known graph $G$. Alice holds $f_A$ and Bob holds $f_B$, both are functions that specify a value for each vertex. The goal is to find a local maximum of $f_A+f_B$ with respect to $G$, i.e., a vertex $v$ for which $(f_A+f_B)(v)geq (f_A+f_B)(u)$ for every neighbor $u$ of $v$. Our main result is that finding a local maximum requires polynomial (in the number of vertices) bits of communication. The result holds for the following families of graphs: three dimensional grids, hypercubes, odd graphs, and degree 4 graphs. Moreover, we provide an emph{optimal} communication bound of $Omega(sqrt{N})$ for the hypercube, and for a constant dimensional greed, where $N$ is the number of vertices in the graph. We provide applications of our main result in two domains, exact potential games and combinatorial auctions. First, we show that finding a pure Nash equilibrium in $2$-player $N$-action exact potential games requires polynomial (in $N$) communication. We also show that finding a pure Nash equilibrium in $n$-player $2$-action exact potential games requires exponential (in $n$) communication. The second domain that we consider is combinatorial auctions, in which we prove that finding a local maximum in combinatorial auctions requires exponential (in the number of items) communication even when the valuations are submodular. Each one of the results demonstrates an exponential separation between the non-deterministic communication complexity and the randomized communication complexity of a total search problem.
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.
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 framework, 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.
Prior work on the complexity of bribery assumes that the bribery happens simultaneously, and that the briber has full knowledge of all voters votes. But neither of those assumptions always holds. In many real-world settings, votes come in sequentially, and the briber may have a use-it-or-lose-it moment to decide whether to bribe/alter a given vote, and at the time of making that decision, the briber may not know what votes remaining voters are planning on casting. In this paper, we introduce a model for, and initiate the study of, bribery in such an online, sequential setting. We show that even for election systems whose winner-determination problem is polynomial-time computable, an online, sequential setting may vastly increase the complexity of bribery, in fact jumping the problem up to completeness for high levels of the polynomial hierarchy or even PSPACE. On the other hand, we show that for some natural, important election systems, such a dramatic complexity increase does not occur, and we pinpoint the complexity of their bribery problems in the online, sequential setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
