Diversity of Structured Domains via k-Kemeny Scores

• URL: http://arxiv.org/abs/2509.15812v1
• Date: Fri, 19 Sep 2025 09:40:39 GMT
• Title: Diversity of Structured Domains via k-Kemeny Scores
• Abstract summary: We study the k-Kemeny problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones.<n>We show that k-Kemeny remains intractable under most of these domains, even for k=2, and we use k-Kemeny to rank these domains in terms of their diversity.
• Score: 13.671577050006421
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the k-Kemeny problem, we are given an ordinal election, i.e., a collection of votes ranking the candidates from best to worst, and we seek the smallest number of swaps of adjacent candidates that ensure that the election has at most k different rankings. We study this problem for a number of structured domains, including the single-peaked, single-crossing, group-separable, and Euclidean ones. We obtain two kinds of results: (1) We show that k-Kemeny remains intractable under most of these domains, even for k=2, and (2) we use k-Kemeny to rank these domains in terms of their diversity.

Related papers

• 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)
• Speeding up Local Search for the Indicator-based Subset Selection Problem by a Candidate List Strategy [0.0]
  In evolutionary multi-objective optimization, the indicator-based subset selection problem involves finding a subset of points that maximizes a given quality indicator.<n>Local search is an effective approach for obtaining a high-quality subset in this problem.<n>This paper proposes a candidate list strategy for local search in the indicator-based subset selection problem.
  arXiv  Detail & Related papers  (2025-03-06T09:06:49Z)
• Determining Winners in Elections with Absent Votes [26.675597212113658]
  We study the determining winner with the absent votes problem when the votes are top-truncated. We show that the WAV problem is NP-complete for the single transferable vote. We propose a special case of positional scoring rule such that the problem can be computed in time.
  arXiv  Detail & Related papers  (2023-10-11T02:52:16Z)
• Core-Stable Committees under Restricted Domains [27.621521330479208]
  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.
  arXiv  Detail & Related papers  (2021-08-04T12:04:29Z)
• 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)
• Curriculum Graph Co-Teaching for Multi-Target Domain Adaptation [78.28390172958643]
  We identify two key aspects that can help to alleviate multiple domain-shifts in the multi-target domain adaptation (MTDA) We propose Curriculum Graph Co-Teaching (CGCT) that uses a dual classifier head, with one of them being a graph convolutional network (GCN) which aggregates features from similar samples across the domains. When the domain labels are available, we propose Domain-aware Curriculum Learning (DCL), a sequential adaptation strategy that first adapts on the easier target domains, followed by the harder ones.
  arXiv  Detail & Related papers  (2021-04-01T23:41:41Z)
• Cross-Domain Grouping and Alignment for Domain Adaptive Semantic Segmentation [74.3349233035632]
  Existing techniques to adapt semantic segmentation networks across the source and target domains within deep convolutional neural networks (CNNs) do not consider an inter-class variation within the target domain itself or estimated category. We introduce a learnable clustering module, and a novel domain adaptation framework called cross-domain grouping and alignment. Our method consistently boosts the adaptation performance in semantic segmentation, outperforming the state-of-the-arts on various domain adaptation settings.
  arXiv  Detail & Related papers  (2020-12-15T11:36:21Z)
• Cross-Domain Generalization Through Memorization: A Study of Nearest Neighbors in Neural Duplicate Question Detection [72.01292864036087]
  Duplicate question detection (DQD) is important to increase efficiency of community and automatic question answering systems. We leverage neural representations and study nearest neighbors for cross-domain generalization in DQD. We observe robust performance of this method in different cross-domain scenarios of StackExchange, Spring and Quora datasets.
  arXiv  Detail & Related papers  (2020-11-22T19:19:33Z)
• Domain2Vec: Domain Embedding for Unsupervised Domain Adaptation [56.94873619509414]
  Conventional unsupervised domain adaptation studies the knowledge transfer between a limited number of domains. We propose a novel Domain2Vec model to provide vectorial representations of visual domains based on joint learning of feature disentanglement and Gram matrix. We demonstrate that our embedding is capable of predicting domain similarities that match our intuition about visual relations between different domains.
  arXiv  Detail & Related papers  (2020-07-17T22:05:09Z)
• Mind the Gap: Enlarging the Domain Gap in Open Set Domain Adaptation [65.38975706997088]
  Open set domain adaptation (OSDA) assumes the presence of unknown classes in the target domain. We show that existing state-of-the-art methods suffer a considerable performance drop in the presence of larger domain gaps. We propose a novel framework to specifically address the larger domain gaps.
  arXiv  Detail & Related papers  (2020-03-08T14:20:24Z)

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.