Computing Voting Rules with Elicited Incomplete Votes
- URL: http://arxiv.org/abs/2402.11104v2
- Date: Thu, 26 Sep 2024 18:55:01 GMT
- Title: Computing Voting Rules with Elicited Incomplete Votes
- Authors: Daniel Halpern, Safwan Hossain, Jamie Tucker-Foltz,
- Abstract summary: We study voting rules that are computable by querying voters about $t m$ candidates.
For scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries.
- Score: 11.550634521005968
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the difficulty of specifying complete ordinal preferences over a large set of $m$ candidates, we study voting rules that are computable by querying voters about $t < m$ candidates. Generalizing prior works that focused on specific instances of this problem, our paper fully characterizes the set of positional scoring rules that can be computed for any $1 \leq t < m$, which, notably, does not include plurality. We then extend this to show a similar impossibility result for single transferable vote (elimination voting). These negative results are information-theoretic and agnostic to the number of queries. Finally, for scoring rules that are computable with limited-sized queries, we give parameterized upper and lower bounds on the number of such queries a deterministic or randomized algorithm must make to determine the score-maximizing candidate. While there is no gap between our bounds for deterministic algorithms, identifying the exact query complexity for randomized algorithms is a challenging open problem, of which we solve one special case.
Related papers
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - On the Complexity of Winner Determination and Strategic Control in
Conditional Approval Voting [13.207754600697138]
Conditional Minisum (CMS) is a voting rule for multi-issue elections with preferential dependencies.
We show that CMS can be viewed as a solution that achieves a satisfactory tradeoff between expressiveness and computational efficiency.
arXiv Detail & Related papers (2022-02-03T16:15:54Z) - Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms.
For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime.
In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem.
We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
arXiv Detail & Related papers (2021-09-13T18:10:52Z) - Towards Meta-Algorithm Selection [78.13985819417974]
Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates.
We show that meta-algorithm-selection can indeed prove beneficial in some cases.
arXiv Detail & Related papers (2020-11-17T17:27:33Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
We revisit one of the most basic and widely applicable techniques in the literature of differential privacy.
This simple algorithm privately tests whether the value of a given query on a database is close to what we expect it to be.
We suggest an alternative, equally simple, algorithm that can continue testing queries as long as any single individual does not contribute to the answer of too many queries.
arXiv Detail & Related papers (2020-10-02T10:50:52Z) - Discriminative Learning via Adaptive Questioning [6.378513792050356]
We consider the problem of designing an adaptive sequence of questions that optimally classify a candidate's ability into one of several categories or discriminative grades.
A candidate's ability is modeled as an unknown parameter, which, together with the difficulty of the question asked, determines the likelihood with which s/he is able to answer a question correctly.
arXiv Detail & Related papers (2020-04-11T16:50:00Z) - Binary Classification with XOR Queries: Fundamental Limits and An
Efficient Algorithm [15.127728811011245]
We consider a query-based data acquisition problem for binary classification of unknown labels.
We consider an effective query type that asks "group attribute" of a chosen subset of objects.
We propose an efficient inference algorithm that achieves this limit even when the noise parameters are unknown.
arXiv Detail & Related papers (2020-01-31T11:23:02Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms.
We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
arXiv Detail & Related papers (2020-01-29T09:40:58Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
We study the problem of clustering a set of items from binary user feedback.
We devise an algorithm with a minimal cluster recovery error rate.
For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
arXiv Detail & Related papers (2019-10-14T09:18:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.