A simple characterization of single-peaked domains

1. Problem Statement

The paper addresses a fundamental problem in social choice theory: characterizing the single-peaked domain on a tree structure.

• Context: While single-peaked preferences are classically defined over a linear order (a line), many real-world economic and political environments are better modeled by networks. Trees (connected graphs with no cycles) serve as a canonical generalization of linear orders.
• The Challenge: Identifying the specific conditions under which a domain of preferences is "single-peaked" with respect to a given tree.
• The Gap: Previous literature has characterized single-peaked domains using restrictions on triples/quadruples of alternatives (Ballester & Haeringer, 2011), Condorcet properties (Puppe, 2018), or the existence of specific random social choice functions (Chatterji et al., 2016). This paper seeks a characterization based on the strategy-proofness of a specific, simple class of deterministic rules.

2. Methodology and Model

The authors employ a standard social choice framework combined with graph-theoretic concepts.

• Setting:
  • Alternatives ($X$): A finite set of nodes in a graph.
  • Agents ($N$): A set of $n$ agents.
  • Preferences ($P$): Strict orderings over $X$. A domain $D$ is a subset of all possible strict orderings.
  • Structure: The alternatives form a Tree ($G$), meaning there is a unique path between any two nodes.
• Key Concepts:
  • Path Hull ($H(S)$): For a set of alternatives $S$, $H(S)$ is the minimal connected subgraph containing $S$ (the union of all paths between elements of $S$).
  • Distance Minimizer ($\pi(x, S)$): For a leaf node $\ell$ and a set $S$, $\pi(\ell, S)$ is the unique node in $H(S)$ closest to $\ell$.
• The Class of Rules (Extreme Rules):
  • An Extreme Rule ($f^\ell$) is defined by a specific leaf $\ell$ of the tree.
  • Mechanism: Given a profile of preferences, the rule identifies the set of top-ranked alternatives (peaks), $\tau(P)$. It then selects the alternative in the path hull $H(\tau(P))$ that is closest to the designated leaf $\ell$.
  • Properties: These rules are inherently unanimous (if everyone agrees on a peak, that peak is chosen) and anonymous (agents are treated symmetrically) regardless of the domain.

3. Key Contributions

The paper's primary contribution is a necessary and sufficient condition for a domain to be single-peaked on a tree, based entirely on the incentive properties of extreme rules.

• Characterization via Strategy-Proofness: The authors prove that a domain is single-peaked on a tree if and only if every extreme rule defined on that tree is strategy-proof.
• Simplicity of Representation: Unlike previous characterizations that rely on complex consistency conditions or randomization, this approach uses a deterministic, explicit rule: "Select the peak closest to a fixed leaf."
• Direction of Logic: While much literature fixes a rule and asks "on which domains is it strategy-proof?", this paper fixes the class of rules (extreme rules) and asks "what is the domain where all of them are strategy-proof?"

4. Main Results

The central theorem (Theorem 1) establishes the equivalence between the structural property of the domain and the incentive property of the rules.

Theorem 1: Let $G$ be a tree and $D$ be a minimally rich domain (every alternative is a top choice for some preference). The following are equivalent:

1. Strategy-Proofness: Every extreme rule $f \in F(G)$ is strategy-proof on $D$.
2. Single-Peakedness: The domain $D$ is single-peaked on $G$.

Definition of Single-Peakedness on a Tree:
A preference $P_i$ is single-peaked on $G$ if for any distinct $a, b$, if $b$ lies on the unique path between the peak $\tau(P_i)$ and $a$, then $b$ is preferred to $a$ ($b P_i a$).

Proof Sketch:

• ($\Rightarrow$) Necessity: If the domain is not single-peaked, there exists a preference where an agent prefers an alternative $a$ over their peak $t$, but $a$ is "behind" $t$ relative to some leaf. The authors construct a profile where an agent can manipulate an extreme rule (associated with a leaf on the "wrong" side of the path) by misreporting their peak to shift the outcome from $t$ to $a$.
• ($\Leftarrow$) Sufficiency: If the domain is single-peaked, the authors show that for any agent, the outcome of an extreme rule is either their true peak or lies on the path between their peak and the outcome of the other agents' peaks. Due to the single-peaked property, the agent cannot benefit by moving their reported peak away from their true peak.

5. Significance and Implications

• Theoretical Unification: The result bridges the gap between the geometric structure of the alternative space (trees) and the incentive compatibility of social choice functions. It confirms that the "extreme" nature of these rules (anchoring to a leaf) perfectly captures the geometry of single-peakedness.
• Efficiency: The paper notes that if a domain is single-peaked on a tree, extreme rules are not only strategy-proof but also Pareto efficient.
• Relation to Median Voter Schemes: The authors situate extreme rules within the broader class of Extended Median Voter Schemes (e.m.v.s.) characterized by Schummer and Vohra (2002). They argue that while e.m.v.s. are powerful, their representation is often implicit. Extreme rules provide a simple, explicit, and direct representation of a subclass of strategy-proof rules, making them easier to analyze and implement.
• Robustness: The characterization holds for any tree structure, generalizing the classic result that single-peakedness on a line is equivalent to the strategy-proofness of the median voter rule.

Conclusion

Bhattacharya and Pramanik provide a clean, elegant characterization of single-peaked domains on trees. By demonstrating that the strategy-proofness of all extreme rules (rules anchored to leaves) is equivalent to the domain being single-peaked, they offer a powerful tool for identifying valid preference domains in network-based social choice problems without relying on complex algebraic restrictions.