2014/02/18 by Christian Geist, Geist, Christian
Computer Science · Economics, Econometrics and Finance · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic in Computer Science (cs.LO) #Multiagent Systems (cs.MA)
paper · pdf · doi:10.48550/arxiv.1402.4303
openalex publication_date 2014/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.