2023/08/05 by Alexander Karpov, Klas Markström, Karpov, Alexander +5 · 1 citation
Decision Sciences · Mathematics · Medicine · #Advanced Optimization Algorithms Research #Antiplatelet Therapy and Cardiovascular Diseases #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Economics and business #Scheduling and Timetabling Solutions #Theoretical Economics (econ.TH)
paper · pdf · doi:10.48550/arxiv.2308.02817
openalex publication_date 2023/08/05 · openalex created_date 2023/08/09 · openalex updated_date 2026/07/28
In this paper, we introduce the class of bipartite peak-pit domains. This is a class of Condorcet domains which include both the classical single-peaked and single-dipped domains. Our class of domains can be used to model situations where some alternatives are ranked based on a most preferred location on a societal axis, and some are ranked based on a least preferred location. This makes it possible to model situations where agents have different rationales for their ranking depending on which of two subclasses of the alternatives one is considering belong to. The class of bipartite peak-pit domains includes most peak-pit domains for n≤ 7 alternatives, and the largest Condorcet domains for each n≤ 8. In order to study the maximum possible size of a bipartite peak-pit domain we introduce set-alternating schemes. This is a method for constructing well-structured peak-pit domains which are copious and connected. We show that domains based on these schemes always have size at least 2n-1 and some of them have sizes larger than the domains of Fishburn's alternating scheme. We show that the maximum domain size for sufficiently high n exceeds 2.1973n. This improves the previous lower bound for peak-pit domains 2.1890n from \citekarpov2023constructing, which was also the highest asymptotic lower bound for the size of the largest Condorcet domains.