Finding Preference Profiles of Condorcet Dimension $k$ via SAT – ScienceOpen
Processing math: 100%
72
views
0
recommends
+1 Recommend
0 collections
    16
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Finding Preference Profiles of Condorcet Dimension k via SAT

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Condorcet winning sets are a set-valued generalization of the well-known concept of a Condorcet winner. As supersets of Condorcet winning sets are always Condorcet winning sets themselves, an interesting property of preference profiles is the size of the smallest Condorcet winning set they admit. This smallest size is called the Condorcet dimension of a preference profile. Since little is known about profiles that have a certain Condorcet dimension, we show in this paper how the problem of finding a preference profile that has a given Condorcet dimension can be encoded as a satisfiability problem and solved by a SAT solver. Initial results include a minimal example of a preference profile of Condorcet dimension 3, improving previously known examples both in terms of the number of agents as well as alternatives. Due to the high complexity of such problems it remains open whether a preference profile of Condorcet dimension 4 exists.

          Related collections

          Author and article information

          Journal
          2014-02-18
          2016-03-02
          Article
          1402.4303
          4db262ec-e92b-409a-bc82-0f4638ad34b0

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Corrected typos, updated references, and added conclusion
          cs.MA cs.AI cs.LO

          Theoretical computer science,Artificial intelligence
          Theoretical computer science, Artificial intelligence

          Comments

          Comment on this article