The Price of Majority Support

• URL: http://arxiv.org/abs/2201.12303v1
• Date: Fri, 28 Jan 2022 18:09:16 GMT
• Title: The Price of Majority Support
• Authors: Robin Fritsch and Roger Wattenhofer
• Abstract summary: We quantify the loss in representativeness that results from requiring the outcome to have majority support. Our results can also be seen as quantifying Anscombes paradox which states that topic-wise majority outcome may not be supported by a majority.
• Score: 25.71206255965502
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of finding a compromise between the opinions of a group of individuals on a number of mutually independent, binary topics. In this paper, we quantify the loss in representativeness that results from requiring the outcome to have majority support, in other words, the "price of majority support". Each individual is assumed to support an outcome if they agree with the outcome on at least as many topics as they disagree on. Our results can also be seen as quantifying Anscombes paradox which states that topic-wise majority outcome may not be supported by a majority. To measure the representativeness of an outcome, we consider two metrics. First, we look for an outcome that agrees with a majority on as many topics as possible. We prove that the maximum number such that there is guaranteed to exist an outcome that agrees with a majority on this number of topics and has majority support, equals $\ceil{(t+1)/2}$ where $t$ is the total number of topics. Second, we count the number of times a voter opinion on a topic matches the outcome on that topic. The goal is to find the outcome with majority support with the largest number of matches. We consider the ratio between this number and the number of matches of the overall best outcome which may not have majority support. We try to find the maximum ratio such that an outcome with majority support and this ratio of matches compared to the overall best is guaranteed to exist. For 3 topics, we show this ratio to be $5/6\approx 0.83$. In general, we prove an upper bound that comes arbitrarily close to $2\sqrt{6}-4\approx 0.90$ as $t$ tends to infinity. Furthermore, we numerically compute a better upper and a non-matching lower bound in the relevant range for $t$.

Related papers

• Selecting the Most Conflicting Pair of Candidates [6.838139628413773]
  We study committee elections from a perspective of finding the most conflicting candidates, that is, candidates that imply the largest amount of conflict, as per voter preferences. By proposing basic axioms to capture this objective, we show that none of the prominent multiwinner voting rules meet them. A subsequent deepened analysis sheds more light on how they operate.
  arXiv  Detail & Related papers  (2024-05-09T16:00:20Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  Learning from human feedback plays an important role in aligning generative models, such as large language models (LLM) We study a model within this problem domain--contextual dueling bandits with adversarial feedback, where the true preference label can be flipped by an adversary. We propose an algorithm namely robust contextual dueling bandit (algo), which is based on uncertainty-weighted maximum likelihood estimation.
  arXiv  Detail & Related papers  (2024-04-16T17:59:55Z)
• Let's Agree to Agree: Targeting Consensus for Incomplete Preferences through Majority Dynamics [13.439086686599891]
  We focus on a process of majority dynamics where issues are addressed one at a time and undecided agents follow the opinion of the majority. We show that in the worst case, myopic adherence to the majority damages existing consensus; yet, simulation experiments indicate that the damage is often mild.
  arXiv  Detail & Related papers  (2022-04-28T10:47:21Z)
• The price of unfairness in linear bandits with biased feedback [62.25313751895011]
  We study the problem of sequential decision making with biased linear bandit feedback. We show that the worst case regret is higher than the dT 1/2 log(T) regret rate obtained under unbiased feedback. Interestingly, the gap-dependent rates reveal the existence of non-trivial instances where the problem is no more difficult than its unbiased counterpart.
  arXiv  Detail & Related papers  (2022-03-18T08:03:20Z)
• The Optimal Size of an Epistemic Congress [11.984912130257795]
  We analyze the optimal size of a congress in a representative democracy. We find that the optimal congress size should be linear in the population size. We conclude by analyzing under what conditions congresses of sub-optimal sizes would still outperform direct democracy.
  arXiv  Detail & Related papers  (2021-07-02T12:51:11Z)
• PAC Best Arm Identification Under a Deadline [101.10352416022559]
  We study $(epsilon, delta)$-PAC best arm identification, where a decision-maker must identify an optimal arm with probability at least $1 - delta$, while minimizing the number of arm pulls (samples) In this work, the decision-maker is given a deadline of $T$ rounds, where, on each round, it can adaptively choose which arms to pull and how many times to pull them. We propose Elastic Batch Racing (EBR), a novel algorithm for this setting and bound its sample complexity, showing that EBR is optimal with respect to both
  arXiv  Detail & Related papers  (2021-06-06T19:48:32Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  We show that the C$2$UCB algorithm has the optimal regret bound $tildeO(dsqrtkT + dk)$ for the partition matroid constraints. For general constraints, we propose an algorithm that modifies the reward estimates of arms in the C$2$UCB algorithm.
  arXiv  Detail & Related papers  (2021-01-20T04:29:18Z)
• Positionality-Weighted Aggregation Methods for Cumulative Voting [0.0]
  We propose aggregation methods that give weighting to the minority's positionality on cardinal cumulative voting. Minority opinions are more likely to be reflected proportionately to the average of the distribution in two of the above three methods. It is possible to visualize the number and positionality of the minority from the analysis of the aggregation results.
  arXiv  Detail & Related papers  (2020-08-20T03:55:49Z)
• Quota-based debiasing can decrease representation of already underrepresented groups [5.1135133995376085]
  We show that quota-based debiasing based on a single attribute can worsen the representation of already underrepresented groups and decrease overall fairness of selection. Our results demonstrate the importance of including all relevant attributes in debiasing procedures and that more efforts need to be put into eliminating the root causes of inequalities.
  arXiv  Detail & Related papers  (2020-06-13T14:26:42Z)

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.