Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userParadoxes in Sequential Voting
79
0
0.0
(
0
)
Added by
Oren Dean
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We analyse strategic, complete information, sequential voting with ordinal preferences over the alternatives. We consider several voting mechanisms: plurality voting and approval voting with deterministic or uniform tie-breaking rules. We show that strategic voting in these voting procedures may lead to a very undesirable outcome: Condorcet winning alternative might be rejected, Condorcet losing alternative might be elected, and Pareto dominated alternative might be elected. These undesirable phenomena occur already with four alternatives and a small number of voters. For the case of three alternatives we present positive and negative results.
rate research
Read More
We discuss voting scenarios in which the set of voters (agents) and the set of alternatives are the same; that is, voters select a single representative from among themselves. Such a scenario happens, for instance, when a committee selects a chairperson, or when peer researchers select a prize winner. Our model assumes that each voter either renders worthy (confirms) or unworthy any other agent. We further assume that the prime goal of each agent is to be selected himself. Only if that is not feasible, will he try to get one of those that he confirms selected. In this paper, we investigate the open-sequential voting system in the above model. We consider both plurality (where each voter has one vote) and approval (where a voter may vote for any subset). Our results show that it is possible to find scenarios in which the selected agent is much less popular than the optimal (most popular) agent. We prove, however, that in the case of approval voting, the ratio between their popularity is always bounded from above by 2. In the case of plurality voting, we show that there are cases in which some of the equilibria give an unbounded ratio, but there always exists at least one equilibrium with ratio 2 at most.
Recently, we introduced in arXiv:1105.2434 a model for product adoption in social networks with multiple products, where the agents, influenced by their neighbours, can adopt one out of several alternatives. We identify and analyze here four types of paradoxes that can arise in these networks. To this end, we use social network games that we recently introduced in arxiv:1202.2209. These paradoxes shed light on possible inefficiencies arising when one modifies the sets of products available to the agents forming a social network. One of the paradoxes corresponds to the well-known Braess paradox in congestion games and shows that by adding more choices to a node, the network may end up in a situation that is worse for everybody. We exhibit a dual version of this, where removing available choices from someone can eventually make everybody better off. The other paradoxes that we identify show that by adding or removing a product from the choice set of some node may lead to permanent instability. Finally, we also identify conditions under which some of these paradoxes cannot arise.
Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than $k$ candidates. In this paper, we study such groups -- known as $n/k$-justifying groups -- both theoretically and empirically. First, we show that under the impartial culture model, $n/k$-justifying groups of size less than $k/2$ are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small $n/k$-justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small $n/k$-justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.
In the context of computational social choice, we study voting methods that assign a set of winners to each profile of voter preferences. A voting method satisfies the property of positive involvement (PI) if for any election in which a candidate x would be among the winners, adding another voter to the election who ranks x first does not cause x to lose. Surprisingly, a number of standard voting methods violate this natural property. In this paper, we investigate different ways of measuring the extent to which a voting method violates PI, using computer simulations. We consider the probability (under different probability models for preferences) of PI violations in randomly drawn profiles vs. profile-coalition pairs (involving coalitions of different sizes). We argue that in order to choose between a voting method that satisfies PI and one that does not, we should consider the probability of PI violation conditional on the voting methods choosing different winners. We should also relativize the probability of PI violation to what we call voter potency, the probability that a voter causes a candidate to lose. Although absolute frequencies of PI violations may be low, after this conditioning and relativization, we see that under certain voting methods that violate PI, much of a voters potency is turned against them - in particular, against their desire to see their favorite candidate elected.
We propose a new single-winner election method (Schulze method) and prove that it satisfies many academic criteria (e.g. monotonicity, reversal symmetry, resolvability, independence of clones, Condorcet criterion, k-consistency, polynomial runtime). We then generalize this method to proportional representation by the single transferable vote (Schulze STV) and to methods to calculate a proportional ranking (Schulze proportional ranking). Furthermore, we propose a generalization of the Condorcet criterion to multi-winner elections. This paper contains a large number of examples to illustrate the proposed methods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
