A simple characterization of single-peaked domains
Mihir Bhattacharya, Anup Pramanik · 2026
Read A simple characterization of single-peaked domains by Mihir Bhattacharya, Anup Pramanik (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26563.txt.
Introduction
Bhattacharya and Pramanik characterized the single-peaked domain on a tree through extreme-rule strategy-proofness. For every tree, the rules follow unanimous verdicts and treat voters symmetrically, on any preference domain. They proved the rules stay strategy-proof solely on the single-peaked domain tied to that tree. The result gives a clean test for single-peakedness via extreme-rule behavior.
Catalog record
| CREATOR | Mihir Bhattacharya, Anup Pramanik |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 18473 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26563
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A simple characterization of single-peaked domains Mihir Bhattacharya, Anup Pramanik Abstract This paper characterizes the single-peaked domain on a tree via the strategy-proofness of extreme rules defined on that tree. For any tree, these rules are unanimous and anonymous on any preference domain. In particular, we show that they are strategy-proof only on the single-peaked domain associated with that tree. Keywords . social choice function; strategy-proofness; extreme rules on a tree; single-peaked domain JEL Classification . D71, D72, D82 1 Introduction Single-peaked preferences occupy a central place in political economy and social choice. First formalized by 6 , they can be informally described as follows. Alternatives are arranged along an underlying order. A preference ordering is single-peaked with respect to this order if for any triple of alternatives a,b and c such that b is between a and c , either b is preferred to a or b is preferred to c . A collection of preference orderings constitutes a single-peaked domain when all preferences are single-peaked with respect to a common underlying order. This restriction emerges naturally in many economic and political contexts. More importantly, it has powerful implications for aggregation. In particular, single-peakedness ensures the existence of well-behaved social choice functions, both in the sense of Arrow’s framework and under strategic considerations (see 1 and 11 ). While the classical definition of single-peaked preference is based on an exogenous order over alternatives, many economic environments are more naturally represented by networks, with tree structures providing a canonical generalization (see, for example, 9 , 8 and 15 ). In this paper, our objective is to provide a characterization of the single-peaked domain on a tree. We characterize the domain via the strategy-proofness of a class of rules, called extreme rules, defined with respect to a fixed tree whose nodes coincide with the set of alternatives. Each extreme rule is associated with a designated leaf of the tree. Given any preference profile, consider the set of top-ranked alternatives and the minimal connected subgraph that contains them. The rule selects the alternative in this subgraph that is closest to the designated leaf. These rules are well-defined for any domain of strict preferences and satisfy unanimity and anonymity. However, whether they are strategy-proof depends on the domain under consideration. Our main result is as follows. Fix a tree and consider the set of all extreme rules on that tree. A domain is single-peaked with respect to this tree if and only if every extreme rule is strategy-proof. A strand of the literature provides characterizations of the single-peaked domain. 2 show that a preference profile is single-peaked if and only if it satisfies a collection of restrictions on all triples and quadruples of alternatives. 12 characterizes single-peaked domains as Condorcet domains that are minimally rich, connected, and contain a pair of completely reversed preference orders. 7 show that a domain is single-peaked on a tree if and only if it admits a strategy-proof, unanimous, tops-only random social choice function satisfying a compromise property. Our result complements this literature by providing a characterization of single-peaked domains on trees via the strategy-proofness of a simple class of rules defined with respect to the underlying tree. Another strand of the literature seeks to overcome the 10 - 14 impossibility by fixing a rule with desirable properties and characterizing the domains on which it is strategy-proof; see, for instance, 4 , 5 , 13 , and 3 . In contrast, our approach proceeds in the opposite direction. We characterize the single-peaked domain on a tree via the strategy-proofness of the class of extreme rules defined on that tree. The remainder of the paper is organized as follows. Section 2 introduces the model. Section 3 introduces the class of extreme rules on a tree and studies their basic properties. Section 4 presents and proves the main characterization result. 2 Model Let X be a finite set of alternatives with |X|\geq 3 . The set of agents is N=\{1,\ldots,n\} . For each agent i\in N , let P_{i} denote agent i ’s preference, which is a strict ordering over the elements of X . 1 1 1 A strict ordering over A is a complete , transitive and antisymmetric binary relation over X . For any a,b\in X , we write a\;P_{i}\;b if agent i strictly prefers alternative a to b under P_{i} . Let \mathbb{P} denote the set of all strict orderings over X , referred to as the unrestricted domain . An arbitrary subset \mathbb{D}\subseteq\mathbb{P} is called a domain . Throughout this paper, we assume that all agents share the same preference domain. A preference profile P=(P_{1},\ldots,P_{n})\in\mathbb{D}^{n} specifies one preference for each agent. For any subset S\subseteq N , let P_{S}=(P_{i})_{i\in S} denote the sub-profile of agents in S , and write P=(P_{S},P_{-S}) . In particular, for a single agent i , we write P=(P_{i},P_{-i}) . For any P_{i}\in\mathbb{D} , let \tau(P_{i}) denote agent i ’s top-ranked alternative. For any subset S\subseteq N , let \tau(P_{S})=\{\tau(P_{i})\mid i\in S\} denote the set of top-ranked alternatives of agents in S . In particular, for a profile P\in\mathbb{D}^{n} , we write \tau(P)=\tau(P_{N}) . Definition 1 A social choice function (scf), or a rule , is a mapping f:\mathbb{D}^{n}\rightarrow X . The following incentive property of a scf is central in the mechanism design literature and will play a key role in our paper. Definition 2 A scf f is manipulable by agent i at a profile P\in\mathbb{D}^{n} via P^{\prime}_{i}\in\mathbb{D} if f(P^{\prime}_{i},P_{-i})\;P_{i}\;f(P). A scf f is strategy-proof if it is not manipulable by any agent at any profile. We assume that an agent’s preference is her private information. Strategy-proofness, therefore, states that each agent has a weakly dominant strategy to report her preferences truthfully: no agent can benefit from misreporting, regardless of her beliefs about the reports of others. We also consider the following standard properties of scfs. Definition 3 A scf f satisfies efficiency if for every profile P\in\mathbb{D}^{n} , there is no alternative a\in X such that a\;P_{i}\;f(P)\quad\text{for all }i\in N. Efficiency requires that the rule never selects a Pareto dominated alternative. Definition 4 A scf f satisfies unanimity if for every profile P\in\mathbb{D}^{n} and every alternative a\in X , whenever \tau(P)=\{a\} , we have f(P)=a. Note that efficiency implies unanimity. A permutation of N is a bijection \sigma:N\to N . For a profile P=(P_{1},\ldots,P_{n})\in\mathbb{D}^{n} , define P^{\sigma}=(P_{\sigma(1)},\ldots,P_{\sigma(n)}) . Definition 5 A scf f satisfies anonymity if for every P\in\mathbb{D}^{n} and every permutation \sigma of N , f(P^{\sigma})=f(P). Anonymity requires that the rule treat all agents symmetrically: the outcome depends only on the profile of preferences and not on the identities of the agents. 3 Extreme Rules on a Tree We introduce a class of scfs that will be central to our analysis. To do so, we first introduce some graph-theoretic notation. Let G=(X,E) be a graph on X , where the node set is X and E consists of unordered pairs of elements of X . A path from x to y in G is a sequence of distinct nodes (x_{0},x_{1},\dots,x_{k}) such that x_{0}=x , x_{k}=y , and \{x_{j-1},x_{j}\}\in E for all j=1,\dots,k . The graph G is connected if for every x,y\in X there exists a path