Bipartite peak-pit domains
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915649430749184 |
|---|---|
| author | Karpov, Alexander Markström, Klas Riis, Søren Zhou, Bei |
| author_facet | Karpov, Alexander Markström, Klas Riis, Søren Zhou, Bei |
| contents | 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\leq 7$ alternatives, and the largest Condorcet domains for each $n\leq 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 $2^{n-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.1973^n$. This improves the previous lower bound for peak-pit domains $2.1890^n$ from \cite{karpov2023constructing}, which was also the highest asymptotic lower bound for the size of the largest Condorcet domains. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_02817 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Bipartite peak-pit domains Karpov, Alexander Markström, Klas Riis, Søren Zhou, Bei Discrete Mathematics Theoretical Economics 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\leq 7$ alternatives, and the largest Condorcet domains for each $n\leq 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 $2^{n-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.1973^n$. This improves the previous lower bound for peak-pit domains $2.1890^n$ from \cite{karpov2023constructing}, which was also the highest asymptotic lower bound for the size of the largest Condorcet domains. |
| title | Bipartite peak-pit domains |
| topic | Discrete Mathematics Theoretical Economics |
| url | https://arxiv.org/abs/2308.02817 |