Single peaked preferences

Single-peaked preferences are a class of preference relations. A group has single-peaked preferences over a set of outcomes if the outcomes can be ordered along a line such that:

Each agent has a "best outcome" in the set, and
For each agent, outcomes that are further from his or her best outcome are preferred less.

Single-peaked preferences are typical of one-dimensional domains. A typical example is when several consumers have to decide on the amount of public good to purchase. The amount is a one-dimensional variable. Usually, each consumer decides on a certain quantity which is best for him or her, and if the actual quantity is more/less than that ideal quantity, the agent is then less satisfied.

With single-peaked preferences, there is a simple truthful mechanism for selecting an outcome, which is to select the median quantity; this results in the median voter theorem.^{[citation needed]} It is truthful because the median function satisfies the strong monotonicity property.

The notion was first presented by Duncan Black^[1] and later by Kenneth Arrow.^[2]

Definitions

Let $X=\{x_{1},\ldots ,x_{m}\}$ be the set of possible outcomes. Let $N=\{1,\ldots ,n\}$ be the set of agents. The preference-relation of agent i is denoted by $\succ _{i}$ . The maximum element of $\succ _{i}$ in X is denoted by $x_{i}^{*}$ _.

Definition using a common order

The group N is said to have single-peaked preferences over X, if there exists an ordering > of the outcomes such that, for every agent i in N:

$x_{k}<x_{j}\leq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}$
$x_{k}>x_{j}\geq x_{i}^{*}\Rightarrow x_{j}\succ _{i}x_{k}$

In words, $x_{i}^{*}$ is the ideal point for agent i. When the agent compares between two outcomes that are both to the right or to the left of his ideal point, he strictly prefers whichever option is closest to $x_{i}^{*}$ .

Note that the preference-relations $\succ _{i}$ are different, but the ordering > of the outcomes must be the same for all agents.

Necessary condition

Ballester and Haeringer^[3] proved the following necessary condition for single-peaked preferences.

If the group N has single-peaked preferences over X, then for every triplet of outcomes in X, there exists an outcome that is not ranked last by any agent in N.

Some examples

Single-peaked preferences

The following graph shows a set of three preferences that are single-peaked over outcomes {A,B,C,D,E}. On the vertical axis, the number represents the preference ranking of the outcome, with 1 being most preferred. Two outcomes that are equally preferred have the same ranking.

The ordering over the outcomes is A < B < C < D < E. The ideal outcome for the green agent is A, for the red it is B, for the blue it is C. For each agent, when we move away from his ideal outcome, the ranking decreases.

It can also be verified that, for each triplet of outcomes, one of them is never ranked last - the one in the middle. E.g., in {A,B,C}, B is never ranked last; in {C,D,E}, D is never ranked last; etc.

Non single-peaked preferences

If each of the two preferences represented by the following two graphs is added to the three preferences above, then the resulting group of four preferences is not single-peaked:

For the blue preferences, it can be seen that the preference ranking spikes down for "D" and then spikes up for "E". This proves that the blue preferences are not single-peaked with respect to the ordering A<B<C<D<E, but it still does not prove that there is no other ordering with which all four preferences are single-peaked. To formally prove this, consider the set of three outcomes {A, D, E}. Each of these outcomes is a worst outcome of some agent: A is worst for the red agent, D is worst for the blue agent, and E is worst for the green agent above. Therefore, no ordering on X can make the set of preferences single-peaked.

The green preferences are not formally single-peaked because they have two outcomes that are the most preferred: "B" and "C". Such preferences are sometimes called single-plateaued.

Interpretations

Single-peaked preferences have a number of interpretations for different applications.

A simple application of ideological preferences is to think of the outcome space $\{x_{1},x_{2},\ldots ,x_{n}\}$ as locations on a street and each $x_{i}$ as the address of an individual. Suppose a single bus stop has to be located on the street and every individual wishes to walk as little as possible to the stop. Individuals then have single-peaked preferences: individual $i$ 's ideal point is $x_{i}$ and she dislikes other locations the farther they are to the west or the farther they are to the east.

The outcome space can also be thought as different policies in an ideological spectrum: policies from the Left vs policies from the Right; policies that are more liberal vs policies that are more conservative; policies that are pro free markets vs policies that are pro state intervention. Voters have single-peaked preferences if they have an ideal balance between the two directions of the ideological spectrum and if they dislike policies the farther away they are from their ideal point.

Related preference domains

A group of agents is said to have single-dipped preferences over a set of possible outcomes if the outcomes can be ordered along a line such that:

Each agent has a "worst outcome" in the set, and -
For each agent, outcomes that are further from his worst outcome are preferred more.

Lackner and Peters^[4] study a class of preferences that are single-peaked on a circle.

Recognition

The single-peaked recognition problem is the following decision problem: given a set of preferences on a set of outcomes, decide if there is a common order of the outcomes for which the preferences are single-peaked. Usually, it is required to also find this common order, if it exists.

Trick^[5] presents a polynomial-time algorithm for recognizing preferences that are single-peaked on a tree.

Escoffier, Spanjaard and Tydrichova^[6] study the problem of recognizing preferences that are single-peaked on a general graph.

References

^ Black, Duncan (1948-02-01). "On the Rationale of Group Decision-making". Journal of Political Economy. 56 (1): 23–34. doi:10.1086/256633. ISSN 0022-3808. S2CID 153953456.
^ Baumol, William J.; Arrow, Kenneth J. (1952-01-01). "Social Choice and Individual Values". Econometrica. 20 (1): 110. doi:10.2307/1907815. hdl:2027/inu.30000082056718. ISSN 0012-9682. JSTOR 1907815.
^ Ballester, Miguel A.; Haeringer, Guillaume (2010-07-15). "A characterization of the single-peaked domain". Social Choice and Welfare. 36 (2): 305–322. doi:10.1007/s00355-010-0476-3. ISSN 0176-1714. S2CID 14975233.
^ Peters, Dominik; Lackner, Martin (2020-06-24). "Preferences Single-Peaked on a Circle". Journal of Artificial Intelligence Research. 68: 463–502. doi:10.1613/jair.1.11732. ISSN 1076-9757.
^ Trick, Michael A. (1989-06-01). "Recognizing single-peaked preferences on a tree". Mathematical Social Sciences. 17 (3): 329–334. doi:10.1016/0165-4896(89)90060-7. ISSN 0165-4896.
^ Escoffier, Bruno; Spanjaard, Olivier; Tydrichová, Magdaléna (2020). "Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms". In Harks, Tobias; Klimm, Max (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 12283. Cham: Springer International Publishing. pp. 291–306. arXiv:2004.13602. doi:10.1007/978-3-030-57980-7_19. ISBN 978-3-030-57980-7. S2CID 216562247.

Austen-Smith, David & Jeffrey Banks (2000). Positive Political Theory I: Collective Preferences. University of Michigan Press. ISBN 978-0-472-08721-1.
Mas-Colell, Andreu, Michael D. Whinston, and Jerry R. Green (1995). Microeconomic Theory. Oxford University Press. ISBN 978-0-19-507340-9.{{cite book}}: CS1 maint: multiple names: authors list (link)
Moulin, Hervé (1991). Axioms of Cooperative Decision Making. Cambridge University Press. ISBN 978-0-521-42458-5.

[1] Black, Duncan (1948-02-01). "On the Rationale of Group Decision-making". Journal of Political Economy. 56 (1): 23–34. doi:10.1086/256633. ISSN 0022-3808. S2CID 153953456.

[2] Baumol, William J.; Arrow, Kenneth J. (1952-01-01). "Social Choice and Individual Values". Econometrica. 20 (1): 110. doi:10.2307/1907815. hdl:2027/inu.30000082056718. ISSN 0012-9682. JSTOR 1907815.

[3] Ballester, Miguel A.; Haeringer, Guillaume (2010-07-15). "A characterization of the single-peaked domain". Social Choice and Welfare. 36 (2): 305–322. doi:10.1007/s00355-010-0476-3. ISSN 0176-1714. S2CID 14975233.

[4] Peters, Dominik; Lackner, Martin (2020-06-24). "Preferences Single-Peaked on a Circle". Journal of Artificial Intelligence Research. 68: 463–502. doi:10.1613/jair.1.11732. ISSN 1076-9757.

[5] Trick, Michael A. (1989-06-01). "Recognizing single-peaked preferences on a tree". Mathematical Social Sciences. 17 (3): 329–334. doi:10.1016/0165-4896(89)90060-7. ISSN 0165-4896.

[6] Escoffier, Bruno; Spanjaard, Olivier; Tydrichová, Magdaléna (2020). "Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms". In Harks, Tobias; Klimm, Max (eds.). Algorithmic Game Theory. Lecture Notes in Computer Science. Vol. 12283. Cham: Springer International Publishing. pp. 291–306. arXiv:2004.13602. doi:10.1007/978-3-030-57980-7_19. ISBN 978-3-030-57980-7. S2CID 216562247.

[1]

[2]

[3]

[4]

[5]

[6]