Unidimensional unfolding is a classical problem in mathematical psychology (Coombs, 1950, Coombs, 1964). It is a problem of converting the qualitative scale to a numerical one. There is a set of individuals. Each agent has a preference order (a qualitative scale) represented by a linear order. Representing dissimilarities as distances we locate both agents’ ideal points and alternatives on a numerical scale. This numerical scale represents agents’ preferences if each agent always prefers an alternative that is nearer to his/her ideal point according to the numerical scale. A necessary and sufficient condition for unidimensional unfolding was obtained by Michell (1994). Doignon and Falmagne (1994) proposed an algorithm for testing unidimensionality and for constructing a numerical scale representing given preferences when it exists.

If we weaken the requirement of the existence of a numerical scale to the existence of a qualitative scale, we get the single-peaked consistency problem (Escoffier et al., 2008). The qualitative scale is represented by a linear order of alternatives, commonly called axis. Each agent has an ideal point on this axis. The axis represents agents’ preferences if, for each agent and for each pair of alternatives that lay on the same side of the axis concerning the agent’s ideal point, the agent always prefers an alternative that is nearer to his/her ideal point. Preferences over alternatives from the different sides from the ideal point are not derived from the axis. Agents with the same ideal point may have different preferences over pairs of alternatives from different sides from the ideal point. This preference model is called the single-peaked preferences. All upper contour sets of single-peaked preference orders are connected concerning the given axis. This fact is utilized in the solution of the single-peaked consistency problem (Escoffier et al., 2008). Kraiczy and Elkind (2022a) contributed to the sampling approach to the single-peaked consistency problem.

The structured preferences approach is based on a similarity assumption. All agents share a common representation of alternatives space. The idea that similarity among agents is the basis for constructing a solution to aggregation problems comes from Arrow (see Barberà et al. (2020)).

Structured alternatives space leads to structured preferences. We analyze several structures of alternatives space and connect them with the structures of preference profiles. A preference profile is a tuple of preference orders. We are interested in counting and characterizing some classes of structured preference profiles. Finding the number of structured preference profiles is aimed at estimating the relative frequency of different structures. By finding the number of single-peaked preference profiles we find the probability that there exists a solution for the single-peaked consistency problem.

By forbidden subprofiles characterization, we get a detection algorithm. By detecting structured preference profiles one can exploit the properties of a structured set of alternatives. Structured preferences have wide applications in computational social choice (Elkind et al., 2022, Karpov, 2022).

Single-peaked preferences imply the median voter theorem (Black, 1958), have vast computational applications (Brandt et al., 2015, Cornaz et al., 2012, Faliszewski et al., 2011), axiomatic justification (Puppe, 2018), and forbidden subprofiles characterization (Ballester & Haeringer, 2011). Single-peaked preferences are consistent with attribute-based choice rules (Aschenbrenner, 1981, Coombs and Avrunin, 1977). Due to Fishburn’s book (Fishburn, 1973) single-peaked preferences are sometimes called in computer science literature “preferences derived from a psychological model” (Bartholdi & Trick, 1986). Simplicity and clear properties predetermine wide applications of single-peaked preferences in economics, political science, psychology, and computer science.

There were several attempts to find the number of single-peaked preference profiles. Durand (2003) found them for three and four alternatives. Lackner and Lackner (2017) found the number of single-peaked preference profiles with two agents. Karpov (2020) solved the problem for five alternatives. The problem of finding the precise number of single-peaked preference profiles faces a high combinatorial complexity, because of the exponential number of different axes (there are m!/2 different axes). Many combinatorial problems are computationally intractable (see Valiant, 1979a, Valiant, 1979b for the definition of #P-complete problems and corresponding examples). Up to now no computationally efficient method was known for counting single-peaked preference profiles.

This paper solves the general problem of counting single-peaked preference profiles by finding a recursive formula.

Single-peaked on a circle preferences were introduced by Peters and Lackner (2020) and by Nehring and Puppe (2007) as a particular case of the generalized single-peaked domain. This preference model has several computational applications. Utilizing our result for the single-peaked preference profiles, we obtain a recursive formula for the number of preference profiles that are single-peaked on a circle.

Arrow’s single-peaked preferences are single-peaked on each triple of alternatives. The number of Arrow’s single-peaked preference profiles is found for three, four, and five alternatives.

Narcissistic preference profiles consist of m preference orders over m alternatives such that all agents have different top choice alternatives. Narcissistic single-peaked preferences are applied to some matching problems (Bartholdi and Trick, 1986, Bredereck et al., 2020). We obtained some results about the number of single-peaked narcissistic preference profiles and single-peaked on a circle narcissistic preference profiles.

We consider the restricted tier domain and Fishburn’s domain because of their combinatorial properties. These domains are subsets of single-peaked domain and single-peaked on a circle domain.

Restricted tier preferences share a common relation over groups of alternatives, each of them contains one or two alternatives. Liu and Zeng (2019) applied this preference model to the probabilistic assignment problem. We prove, that the restricted tier preference profiles are single-peaked, and provide a forbidden subprofiles characterization.

Condorcet domains are sets of linear orders with the property that, whenever the preferences of all agents belong to this set, the majority relation, induced by the preference profile with an odd number of agents, has no cycles. Fishburn’s domain (Fishburn, 1996) is a nicely structured Condorcet domain in which some triples of alternatives are single-peaked and some are single-dipped. Galambos and Reiner (2008) showed that it is the largest Condorcet domain up to seven alternatives, Leedham-Green et al. (2023) showed that for eight alternatives there is a larger domain. Fishburn’s domain is a basis for constructing large Condorcet domains (Karpov et al., 2023, Karpov and Slinko, 2023a). We proved that Fishburn’s domain is a subset of single-peaked on a circle domain.

The related literature consists of counting results for the number of single-peaked for a given axis narcissistic and single-crossing narcissistic preference profiles (Chen & Finnendahl, 2018), group-separable and group-separable narcissistic preference profiles (Karpov, 2019), and enriched group-separable preference profiles (Ferrari, 2022). Forbidden configurations characterization is known for single-peaked preference profiles (Ballester & Haeringer, 2011), group-separable preference profiles (Ballester & Haeringer, 2011), single-crossing preference profiles (Bredereck et al., 2013), single-peaked single-crossing preference profiles (Elkind et al., 2020), small one–dimensional Euclidean preference profiles (Chen & Grottke, 2021), and structured dichotomous preference profiles (Terzopoulou et al., 2021). There are polynomial time recognition algorithms for top-monotonic preference profiles (Magiera & Faliszewski, 2019), 2-axes single-peaked preference profiles (Yang, 2020), caterpillar group-separable preference profiles (Kraiczy & Elkind, 2022b).

The structure of the paper is as follows. Section 2 contains the main result concerning the number of single-peaked preference profiles. Section 3 counts single-peaked on a circle preference profiles. Section 4 presents the calculation of the number of Arrow’s single-peaked preference profiles. Section 5 contains the enumeration and characterization results for the restricted tier preference profiles. Section 6 introduces Fishburn’s domain and proves that it is a subset of single-peaked on a circle domain. Section 7 concludes and discusses an application of combinatorial results to random sampling algorithms.