Anonymity and Strategy-Proofness on a Domain of Single-Peaked and Single-Dipped Preferences

Basic Information

• Paper ID: 2410.03387
• Title: Anonymity and strategy-proofness on a domain of single-peaked and single-dipped preferences
• Author: Oihane Gallo (University of Barcelona)
• Classification: econ.TH (Economic Theory)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2410.03387

Abstract

This paper analyzes the problem of locating public facilities in a society where agents have single-peaked or single-dipped preferences. The research considers the domain analyzed by Alcalde-Unzu et al. (2024), where each agent's preference type is public information, but the location of their peak/valley and the remainder of their preferences are unknown. The paper characterizes all strategy-proof and type-anonymous rules on this domain. Building on existing results, a two-step characterization is provided: first, compute the median between peaks and a fixed set of locations (Moulin, 1980), yielding either a single alternative or a pair of adjacent alternatives. If the median result is a pair, a "double-quota majority method" is applied in the second step to select an alternative from that pair (Moulin, 1983).

Research Background and Motivation

Problem Definition

The core problem addressed by this research is: how to design social choice rules that satisfy both strategy-proofness and anonymity for public facility location in a mixed preference domain containing both single-peaked and single-dipped preferences.

Research Significance

1. Practical Relevance: Public facility location is an important problem in urban planning, where different types of facilities lead to different preference structures among residents
2. Theoretical Value: Extends classical single-peaked preference theory and provides theoretical foundations for mixed preference domains
3. Fairness Considerations: Anonymity ensures all agents have equal influence in the decision-making process

Limitations of Existing Approaches

1. Gibbard-Satterthwaite Theorem: In unrestricted preference domains, no social choice rule simultaneously satisfies strategy-proofness and non-dictatorship
2. Single Preference Type Restriction: Existing research primarily focuses on purely single-peaked or purely single-dipped preference domains
3. Absence of Anonymity: While Alcalde-Unzu et al. (2024) characterize strategy-proof rules, they do not consider anonymity requirements

Research Motivation

The paper aims to introduce type-anonymity constraints while maintaining strategy-proofness, providing a complete theoretical characterization for mixed preference domains.

Core Contributions

1. Introduction of Type-Anonymity Concept: Proposes a new definition of type-anonymity for mixed preference domains, allowing agent permutations within the same preference type
2. Two-Step Characterization Theorem: Proves that strategy-proof and type-anonymous rules can be completely characterized through a two-step procedure combining mixed median functions and double-quota majority methods
3. Alternative Characterization Method: Based on results from Alcalde-Unzu et al. (2024), provides an alternative characterization method and proves the equivalence of both approaches
4. Theoretical Extension: Extends classical results from Moulin (1980, 1983) to mixed preference domains

Methodology Details

Task Definition

Input:

• Set of agents N = {1, ..., n}, partitioned into set A (single-peaked preferences) and D (single-dipped preferences)
• Set of feasible alternatives X ⊆ ℝ
• Preference profile R = (Ri)i∈N

Output:

• Social choice rule f: R → X

Constraints:

• Strategy-proofness: No agent benefits from misreporting preferences
• Type-anonymity: Permutations of agents of the same type do not affect outcomes

Model Architecture

Step One: Mixed Median Function

Define mixed median function med: Ω^a_f → Ωf ∪ Ω^C2_f, where:

• Compute the median of a peaks and (a+1) fixed locations
• Fixed locations γ^1_f, ..., γ^(a+1)_f ∈ Ωf ∪ Ω^C2_f satisfy:
  1. γ^1_f ≤* ... ≤* γ^(a+1)_f
  2. γ^1_f = minΩf or minΩ^C2_f
  3. γ^(a+1)_f = maxΩf or maxΩ^C2_f

Step Two: Double-Quota Majority Method

For each pair of adjacent alternatives (x,y) ∈ Ωmed ∩ Ω^C2_f:

• Define double-quota set {q(x,y) = (q^A_(x,y), q^D_(x,y))}
• Select left alternative x if and only if:
  • |L^A_(x,y)(R)| ≥ q^A_(x,y) and |L^D_(x,y)(R)| ≥ q^D_(x,y)

Technical Innovations

1. Double-Quota Mechanism: Unlike classical single-quota approaches, sets separate quota thresholds for each preference type
2. Mixed Median: Allows fixed locations to take values as either single alternatives or pairs of adjacent alternatives
3. Type-Anonymous Left Coalition System: In step one, considers only coalition size rather than specific composition
4. Type-Anonymous Left Decisive Set: In step two, makes decisions based on the number of supporters of each type

Theoretical Results

Main Theorems

Theorem 1 (First Characterization): The following statements are equivalent:

1. f: R → Ωf is strategy-proof and type-anonymous
2. f: R → Ωf is group strategy-proof and type-anonymous
3. There exist a mixed median function med and a set of double-quota majority methods such that for each R ∈ R:
   • If med(p(R)) ∈ Ωf, then f(R) = med(p(R))
   • If med(p(R)) ∈ Ω^C2_f, then f(R) = t_med(p(R))(R)

Theorem 2 (Second Characterization): Based on the framework of Alcalde-Unzu et al. (2024), through characterization via type-anonymous left coalition systems and type-anonymous left decisive sets.

Equivalence Proof

Section 5 of the paper provides detailed proof of the equivalence between the two characterization methods, demonstrating how to convert between fixed location sets and type-anonymous left coalition systems.

Related Work

Classical Theoretical Foundations

1. Black (1948): First discusses single-peaked preferences, proving strategy-proofness of median voting rule
2. Moulin (1980): Characterizes all strategy-proof anonymous rules on single-peaked preference domain
3. Moulin (1983): Characterizes strategy-proof anonymous rules for binary choice problems
4. Barberà et al. (2012), Manjunath (2014): Strategy-proof rules on single-dipped preference domain

Mixed Domain Research

1. Berga and Serizawa (2000), Achuthankutty and Roy (2018): Prove that Gibbard-Satterthwaite results still hold in mixed domains containing all single-peaked and single-dipped preferences
2. Alcalde-Unzu and Vorsatz (2018): Characterize strategy-proof rules when peaks/valleys are public information
3. Alcalde-Unzu et al. (2024): Direct foundation of this paper, characterizes strategy-proof rules when preference types are public information

Conclusions and Discussion

Main Conclusions

1. In mixed single-peaked and single-dipped preference domains, strategy-proof and type-anonymous rules have a clear two-step structure
2. Type-anonymity imposes additional constraints on strategy-proof rules, requiring decisions to be based only on the number of supporters rather than their identities
3. The two different characterization methods are mathematically completely equivalent

Limitations

1. Preference Restrictions: The model does not allow indifference relations in preferences
2. Information Assumptions: Requires preference types to be public information
3. One-Dimensional Space: Only considers facility location problems in linear spaces

Future Directions

1. Extension to Indifference Preferences: Extend single-peaked/single-dipped preferences to single-plateau/single-basin preferences
2. Multidimensional Spaces: Consider facility location problems in multidimensional spaces
3. Incomplete Information: Study cases where preference types are private information

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Provides complete theoretical characterization for mixed preference domains
2. Methodological Innovation: The design of double-quota mechanisms and mixed median functions is innovative
3. Rigor: Mathematical proofs are rigorous and logic is clear
4. Practical Value: Provides theoretical guidance for public facility location

Weaknesses

1. Application Limitations: In practice, preference types may be difficult to identify accurately
2. Computational Complexity: The paper does not discuss computational complexity of the rules
3. Empirical Validation: Lacks empirical or experimental verification

Impact

1. Theoretical Contribution: Provides new theoretical tools for social choice theory
2. Methodological Value: The two-step characterization method may apply to other mixed preference problems
3. Policy Significance: Provides theoretical foundation for public decision-making mechanism design

Applicable Scenarios

1. Urban Planning: Location selection for train stations, sports facilities, shopping centers
2. Public Policy: Collective decision-making considering different preference types
3. Mechanism Design: Allocation mechanisms requiring both efficiency and fairness

Technical Details Supplement

Key Definitions

• Type-Anonymity: For any preference profile R and permutation σ preserving type structure, f(R) = f(R^σ)
• Mixed Median Function: Combines median computation for both single alternatives and pairs of adjacent alternatives
• Double-Quota Majority Method: Sets different support thresholds for each of the two preference types

Mathematical Formulation

The paper employs rigorous mathematical language, including:

• Definition of partial order relation ≤*
• Concepts of restricted peak p(Ri) and restricted valley d(Ri)
• Formal definitions of winning coalitions and decisive sets

This research makes important contributions to social choice theory in mixed preference domains, laying a solid theoretical foundation for future related research.