Determining possible and necessary winners given partial orders

DOI10.1613/JAIR.3186MaRDI QIDQ3007558zbMATH OpenOpenAlexWikidataFDO

Authors Lirong Xia, Vincent Conitzer

Publication date 16 June 2011

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.3876

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12) Other applications of logic (03B80)

Abstract: Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.

Recommendations

• Towards a dichotomy for the possible winner problem in elections based on scoring rules
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Possible and necessary winners of partial tournaments
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• The possible winner problem with uncertain weights

Cited in

(48)

• Robust winner determination in positional scoring rules with uncertain weights
• The possible winner with uncertain weights problem
• On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard
• Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules
• Studies in Computational Aspects of Voting
• Weighted partial order oriented three-way decisions under score-based common voting rules
• Kernelization complexity of possible winner and coalitional manipulation problems in voting
• Computing possible and certain answers over order-incomplete data
• Manipulative elicitation -- a new attack on elections with incomplete preferences
• Complexity of manipulation with partial information in voting
• Voting procedures, complexity of
• Possible and necessary winners of partial tournaments
• Manipulation of k-approval under de re knowledge
• The computational impact of partial votes on strategic voting
• Ranking chain sum orders
• Bribery in elections with randomly selected voters: hardness and algorithm
• Approximation and hardness of shift-bribery
• The possible winner problem with uncertain weights revisited
• Complexity of shift bribery for iterative voting rules
• Prices matter for the parameterized complexity of shift bribery
• A Borda count for partially ordered ballots
• New candidates welcome! Possible winners with respect to the addition of new candidates
• Campaign management under approval-driven voting rules
• A distributed social choice protocol for combinatorial domains
• Jérôme Lang's contributions at the interface of economic theory with artificial intelligence
• Representation with incomplete votes
• Incompleteness and incomparability in preference aggregation: complexity results
• Local distance constrained bribery in voting
• A parameterized perspective on protecting elections
• Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules
• On the complexity of bribery and manipulation in tournaments with uncertain information
• Possible and necessary winner problems in iterative elections with multiple rules
• Taking the final step to a full dichotomy of the possible winner problem in pure scoring rules
• Preference elicitation and robust winner determination for single- and multi-winner social choice
• On the evaluation of election outcomes under uncertainty
• Distributed monitoring of election winners
• Multivariate complexity analysis of Swap Bribery
• Optimizing positional scoring rules for rank aggregation
• The possible winner problem with uncertain weights
• Barriers to manipulation in voting
• Reaching a joint decision with minimal elicitation of voter preferences
• On the exact amount of missing information that makes finding possible winners hard
• Verification in incomplete argumentation frameworks
• Fixing balanced knockout and double elimination tournaments
• Bribery in voting with CP-nets
• Approval-based committee voting under incomplete information
• Stability, optimality and manipulation in matching problems with weighted preferences
• Democratix: a declarative approach to winner determination

This page was built for publication: Determining possible and necessary winners given partial orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007558)