Core-Stable Committees under Restricted Domains

• URL: http://arxiv.org/abs/2108.01987v1
• Date: Wed, 4 Aug 2021 12:04:29 GMT
• Title: Core-Stable Committees under Restricted Domains
• Abstract summary: We study the setting of committee elections, where a group of individuals needs to collectively select a given size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location.
• Score: 27.621521330479208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the setting of committee elections, where a group of individuals needs to collectively select a given size subset of available objects. This model is relevant for a number of real-life scenarios including political elections, participatory budgeting, and facility-location. We focus on the core -- the classic notion of proportionality, stability and fairness. We show that for a number of restricted domains including voter-interval, candidate-interval, single-peaked, and single-crossing preferences the core is non-empty and can be found in polynomial time. We show that the core might be empty for strict top-monotonic preferences, yet we introduce a relaxation of this class, which guarantees non-emptiness of the core. Our algorithms work both in the randomized and discrete models. We also show that the classic known proportional rules do not return committees from the core even for the most restrictive domains among those we consider (in particular for 1D-Euclidean preferences). We additionally prove a number of structural results that give better insights into the nature of some of the restricted domains, and which in particular give a better intuitive understanding of the class of top-monotonic preferences.

Related papers

• Selective Ensemble Based on Preference-Directed Multi-Objective Bandits [90.75513823660775]
  We formalize a sequential decision problem under partially specified linear preferences.<n>We then propose a preference-directed upper confidence bound (PrefUCB) algorithm.<n> Experiments on large pre-trained model selective ensemble tasks and online asset allocation under institutional mandates validate our method.
  arXiv  Detail & Related papers  (2026-06-20T07:52:46Z)
• How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings? [58.740078141879984]
  Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on.<n>Recent work in causality-based domain generalization has shown how shared causal structure can induce invariant predictors.<n>In this paper, we study when full or partial causal knowledge can provably improve supervised domain adaptation.
  arXiv  Detail & Related papers  (2026-06-10T21:07:49Z)
• Computing Thiele Rules on Interval Elections and their Generalizations [46.93587966131188]
  We show that computing a Thiele outcome is NP-hard in general.<n>On the candidate interval (CI) domain, they are computable in time via a linear program (LP) that has a totally unimodular constraint matrix.<n>We also provide an alternative definition of LC that is closer in spirit to VCI and has a natural interpretation in approval elections.
  arXiv  Detail & Related papers  (2026-05-04T18:39:48Z)
• Outer Diversity of Structured Domains [13.671577050006421]
  An ordinal preference domain is a subset of preference orders that the voters are allowed to cast in an election.<n>We introduce and study the notion of outer diversity of a domain and evaluate its value for a number of well-known structured domains.
  arXiv  Detail & Related papers  (2026-02-17T16:42:05Z)
• A Bayesian Approach to Low-Discrepancy Subset Selection [0.0]
  Low-discrepancy designs play a central role in quasi-Monte Carlo methods and are increasingly influential in other domains such as machine learning, robotics and computer graphics.<n>In recent years, one such low-discrepancy construction method called subset selection has received a lot of attention.<n>We establish, for the first time, that the subset selection problem with respect to kernel discrepancies is also NP-hard.
  arXiv  Detail & Related papers  (2026-02-16T10:11:07Z)
• Snowveil: A Framework for Decentralised Preference Discovery [0.0]
  This paper introduces Decentralised Preference Discovery (DPD), the problem of determining the collective will of an electorate under constraints of censorship resistance, partial information, and asynchronous communication.<n>We propose Snowveil, a novel framework for this task. Snowveil uses an iterative, gossip-based protocol where voters repeatedly sample the preferences of a small, random subset of the electorate to progressively converge on a collective outcome.<n>We develop a multi-level analytical method to show that the system almost surely converges to a stable, single-winner in finite time, a process that can then be iterated to construct a set of winning
  arXiv  Detail & Related papers  (2025-12-20T17:31:55Z)
• Guidance Not Obstruction: A Conjugate Consistent Enhanced Strategy for Domain Generalization [50.04665252665413]
  We argue that acquiring discriminative generalization between classes within domains is crucial. In contrast to seeking distribution alignment, we endeavor to safeguard domain-related between-class discrimination. We employ a novel distribution-level Universum strategy to generate supplementary diverse domain-related class-conditional distributions.
  arXiv  Detail & Related papers  (2024-12-13T12:25:16Z)
• DeepVoting: Learning Voting Rules with Tailored Embeddings [13.037431161285971]
  We recast the problem of designing a good voting rule into one of learning probabilistic versions of voting rules. We show that embeddings of preference profiles derived from the social choice literature allows us to learn existing voting rules more efficiently. We also show that rules learned using embeddings can be tweaked to create novel voting rules with improved axiomatic properties.
  arXiv  Detail & Related papers  (2024-08-24T17:15:20Z)
• MOKD: Cross-domain Finetuning for Few-shot Classification via Maximizing Optimized Kernel Dependence [97.93517982908007]
  In cross-domain few-shot classification, NCC aims to learn representations to construct a metric space where few-shot classification can be performed. In this paper, we find that there exist high similarities between NCC-learned representations of two samples from different classes. We propose a bi-level optimization framework, emphmaximizing optimized kernel dependence (MOKD) to learn a set of class-specific representations that match the cluster structures indicated by labeled data.
  arXiv  Detail & Related papers  (2024-05-29T05:59:52Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Most Equitable Voting Rules [30.930621357547487]
  ANR impossibility -- there is no voting rule that satisfies anonymity, neutrality, and resolvability -- holds even in the simple setting of two alternatives and two agents. We propose a novel and strong notion of most equitable refinements that optimally preserves anonymity and neutrality for any irresolute rule that satisfies the two axioms.
  arXiv  Detail & Related papers  (2022-05-30T03:56:54Z)
• Maximizing Conditional Independence for Unsupervised Domain Adaptation [9.533515002375545]
  We study how to transfer a learner from a labeled source domain to an unlabeled target domain with different distributions. In addition to unsupervised domain adaptation, we extend our method to the multi-source scenario in a natural and elegant way.
  arXiv  Detail & Related papers  (2022-03-07T08:59:21Z)
• 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)
• Robust Voting Rules from Algorithmic Robust Statistics [25.313563663123354]
  We give an algorithm that can accurately estimate the central ranking even when a constant fraction of its samples are arbitrarily corrupted. Our work can be thought of as a natural infusion of perspectives from algorithmic robust statistics into one of the central inference problems in voting and information-aggregation.
  arXiv  Detail & Related papers  (2021-12-13T02:30:26Z)
• Rethinking Counting and Localization in Crowds:A Purely Point-Based Framework [59.578339075658995]
  We propose a purely point-based framework for joint crowd counting and individual localization. We design an intuitive solution under this framework, which is called Point to Point Network (P2PNet)
  arXiv  Detail & Related papers  (2021-07-27T11:41:50Z)
• Preference learning along multiple criteria: A game-theoretic perspective [97.94912276610002]
  We generalize the notion of a von Neumann winner to the multi-criteria setting by taking inspiration from Blackwell's approachability. Our framework allows for non-linear aggregation of preferences across criteria, and generalizes the linearization-based approach from multi-objective optimization. We show that the Blackwell winner of a multi-criteria problem instance can be computed as the solution to a convex optimization problem.
  arXiv  Detail & Related papers  (2021-05-05T03:23:11Z)
• Universal Domain Adaptation through Self Supervision [75.04598763659969]
  Unsupervised domain adaptation methods assume that all source categories are present in the target domain. We propose Domain Adaptative Neighborhood Clustering via Entropy optimization (DANCE) to handle arbitrary category shift. We show through extensive experiments that DANCE outperforms baselines across open-set, open-partial and partial domain adaptation settings.
  arXiv  Detail & Related papers  (2020-02-19T01:26:11Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

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.