📈 economics

Local Strategy-proofness and Dictatorship

This paper investigates preference domains where every unanimous and locally strategy-proof social choice function is dictatorial, identifying a necessary condition called "connected with distinct neighbours" and proving its sufficiency within domains satisfying tops-onlyness, while also establishing that this condition implies dictatorship under the stronger requirement of global strategy-proofness.

Original authors: Abinash Panda, Anup Pramanik, Ragini Saxena

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Abinash Panda, Anup Pramanik, Ragini Saxena

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are organizing a party and need to pick a movie to watch. You have a group of friends (voters), and everyone has a different list of movies they like (preferences). You need a rule (a Social Choice Function) to decide which movie gets played based on everyone's lists.

The big question in this paper is: Can we design a fair rule that prevents people from lying about their preferences, without giving total control to just one person?

The Core Conflict: Truth vs. Power

In the world of voting theory, there's a famous rule called the Gibbard-Satterthwaite Theorem. It says: "If you want a rule that is Unanimous (if everyone agrees on a movie, that movie wins) and Strategy-Proof (no one can lie to get a better result), then the only way to do it is to let one person be the Dictator."

In other words, to stop people from cheating, you have to give one person total power. That sounds terrible for democracy!

The Loophole: "Local" Truthfulness

The authors of this paper ask a clever question: What if we relax the rules? What if we only care if people lie about things that are very similar to their true taste?

Global Strategy-Proofness: You can't lie about anything. (e.g., You can't pretend to love a horror movie if you hate them).
Local Strategy-Proofness: You can't lie about things that are neighbors on your list. (e.g., If you rank "Action" #1 and "Comedy" #2, you can't swap them to get a better result. But maybe you could swap "Action" with "Documentary" if they are far apart on your list).

The authors call this Local Strategy-Proofness. It's like saying, "I won't let you lie about your immediate neighbors, but maybe you can lie about the stuff way down your list."

The hope is that by relaxing the rules, we can find a fair, non-dictatorial way to pick a movie.

The Discovery: The "Connected with Distinct Neighbors" Rule

The paper investigates: On which types of preference lists does this "Local" relaxation still force us to have a Dictator?

They introduce a concept called "Connected with Distinct Neighbors." Let's break this down with an analogy.

The Analogy: The Neighborhood Map

Imagine every possible way to rank movies is a house on a giant map.

Connected: You can walk from any house to any other house by stepping only to "neighbor" houses (houses that differ by just one swap).
Distinct Neighbors: This is the tricky part. Imagine you are standing in a house where you love "Action" movies the most. You look at all the houses you can walk to without changing your favorite movie (you still love "Action" #1).
- The rule says: The "neighborhood" of houses that share your favorite movie must have at least two different neighbors outside that group, and those neighbors must have different favorite movies.

If your map of preferences looks like this, you are stuck with a Dictator. Even if you only care about "local" lies, the structure of the map forces one person to have total control.

What Happens on "Bad" Maps?

The authors show that famous, "nice" voting systems (like Single-Peaked preferences, where people have a left-right political spectrum) do not satisfy this "Distinct Neighbors" rule.

Why this matters: On these "nice" maps, you can have a fair, non-dictatorial system that is locally strategy-proof. People can lie a little bit (about distant options) to get a better result, but they can't lie about their immediate neighbors. This is good news for democracy!

However, on "messy" maps (like the Unrestricted Domain where people can rank anything in any order, or the Union of Single-Peaked and Single-Dipped domains), the "Connected with Distinct Neighbors" rule kicks in.

The Result: On these messy maps, even the relaxed "Local" rule forces a Dictator. You cannot escape the tyranny of one person if the preferences are too chaotic.

The Big Takeaway

The "Local" Loophole is Real but Limited: Relaxing the rules to only care about "local" lies does allow for some fair, non-dictatorial systems, but only on specific, well-structured maps of preferences.
The "Connected with Distinct Neighbors" Test: If a group's preferences form a map that is "Connected with Distinct Neighbors," then no matter how you try, you cannot design a fair system that stops even small lies without appointing a Dictator.
Stronger Rules Still Work: Interestingly, if you go back to the strict "Global" rule (no lying at all), these same "messy" maps still force a Dictator. The paper proves that if a map forces a Dictator under the strict rules, it also forces a Dictator under the relaxed "local" rules.

In Simple Terms

Think of the preference domain as a maze.

Some mazes are simple and straight (like a political spectrum). In these mazes, you can build a fair voting machine that stops people from cheating, even if they try to cheat a little bit.
Other mazes are complex and twisty (like the unrestricted domain). In these mazes, the authors prove that any machine that stops even the smallest cheats will inevitably break and hand the keys to a single Dictator.

The paper gives us a precise map (the "Connected with Distinct Neighbors" condition) to tell us exactly which mazes are safe for democracy and which ones are doomed to dictatorship.

1. Problem Statement

The paper investigates the conditions under which local strategy-proofness and unanimity imply dictatorship in social choice theory.

Context: The classic Gibbard-Satterthwaite Theorem states that on unrestricted domains, any strategy-proof (globally) and unanimous social choice function (SCF) must be dictatorial.
Refinement: The authors focus on local strategy-proofness, a weaker condition where agents cannot benefit by misreporting only to adjacent preferences (preferences differing by a single swap of consecutively ranked alternatives).
The Gap: While global strategy-proofness often implies dictatorship, local strategy-proofness does not always do so (e.g., on circular domains). The central research question is: On which preference domains does the combination of unanimity and local strategy-proofness force an SCF to be dictatorial?
Goal: To characterize the class of "dictatorial domains" under the weaker local incentive constraint.

2. Methodology and Framework

The authors employ a structural approach using graph theory and preference domain topology.

Definitions:
- Adjacency ( $P_i \sim P'_i$ ): Two linear orders are adjacent if one can be obtained from the other by swapping two consecutively ranked alternatives.
- Local Strategy-proofness: No agent can manipulate by switching to an adjacent preference.
- Minimally Rich Domain: Every alternative is top-ranked in at least one preference within the domain.
- Top-Connected Closure ( $DTCC(P_i)$ ): The set of all preferences in the domain that are connected to $P_i$ via a path where the top-ranked alternative remains constant throughout the path.
Key Structural Concept: "Connected with Distinct Neighbours" (CDN)
The authors introduce a novel domain property called Connected with Distinct Neighbours. A domain $D$ satisfies CDN if:
1. Connectedness: The domain is connected (any two preferences are linked by a path of adjacent preferences).
2. Distinct Neighbours: For any preference $P_i$ , its top-connected closure $DTCC(P_i)$ has at least two neighboring preferences (preferences adjacent to the set but not in it) whose top-ranked alternatives are distinct.
Graph-Theoretic Tools:
The authors define an undirected graph $G(D)$ induced by the domain where:
- Nodes: The set of alternatives $A$ .
- Edges: An edge exists between alternatives $a$ and $b$ if there exist adjacent preferences in $D$ where $a$ and $b$ are the top-ranked alternatives (swapped).
- They utilize properties of this graph (connectivity, cycles, vertex degrees) to prove their results.

3. Key Contributions and Results

A. Necessary Condition (Theorem 1)

The paper establishes that the Connected with Distinct Neighbours (CDN) property is a necessary condition for dictatorship under unanimity and local strategy-proofness.

Result: If every unanimous and locally strategy-proof SCF on a minimally rich domain $D$ is dictatorial, then $D$ must be connected with distinct neighbours.
Proof Logic: The authors use a contrapositive argument. If a domain fails the CDN property (either disconnected or lacking distinct neighbours for some top-connected closure), they construct a specific non-dictatorial SCF that satisfies both unanimity and local strategy-proofness.

B. Sufficient Condition (Theorem 2)

The authors show that CDN is also a sufficient condition for a specific subclass of domains.

L-tops-only Domains: They define a class of domains where any unanimous and locally strategy-proof SCF automatically satisfies the tops-only property (the outcome depends only on the top-ranked alternatives of voters).
Result: If a domain $D$ is minimally rich, L-tops-only, and satisfies the CDN property, then every unanimous and locally strategy-proof SCF on $D$ is dictatorial.
Significance: This provides a precise characterization for this subclass: $D_{LDICT} = D_{CDN} \cap D_{L-TOPS-ONLY}$ .

C. Strengthening to Global Strategy-proofness (Theorem 3)

The paper addresses whether the "L-tops-only" restriction is necessary for the CDN property to imply dictatorship.

Result: If the requirement is strengthened from local strategy-proofness to global strategy-proofness, then the CDN property alone is sufficient to imply dictatorship.
Implication: $D_{CDN} \subset D_{DICT}$ (The set of CDN domains is a strict subset of dictatorial domains under global strategy-proofness). This implies that even if a CDN domain is not L-tops-only, it cannot support a non-dictatorial, globally strategy-proof, and unanimous SCF.

4. Comparison with Existing Literature

The paper situates its findings against recent work, particularly Hong and Kim (2023) and Kumar et al. (2021a).

vs. Hong and Kim (2023):
- Hong and Kim characterize domains within the class of Sparsely Connected Domains without Restoration (SCD) using the "disagreement property."
- The authors show that their CDN condition is strictly stronger than the combination of connectedness and the disagreement property.
- They provide a counterexample (Example 6) of a domain that satisfies connectedness and disagreement but fails CDN, proving CDN is a tighter necessary condition.
- Their sufficient condition (Theorem 2) applies to a broader class of domains than the SCD restriction used by Hong and Kim.
vs. Local-Global Equivalence (uLGE):
- The paper contributes to the literature on when local strategy-proofness implies global strategy-proofness.
- They show that domains in $D_{LDICT}$ satisfy the uLGE property.
- They demonstrate that their framework can identify uLGE domains (like the domain in Example 5) that do not satisfy the "Property P" (no-restoration) conditions required by previous literature (Kumar et al., 2021a).

5. Significance and Conclusion

Theoretical Advancement: The paper provides the first necessary and sufficient conditions for dictatorship under local strategy-proofness, moving beyond the specific constraints of "sparsely connected" domains.
Structural Insight: By introducing the Connected with Distinct Neighbours property, the authors highlight that the local diversity of preferences around a top-ranked alternative is crucial for preventing non-dictatorial mechanisms.
Practical Implication: The results clarify the limits of relaxing incentive constraints. While local strategy-proofness allows for non-dictatorial rules on some domains (like circular domains), on domains with the CDN structure, even this relaxed constraint forces dictatorship.
Future Directions: The authors conjecture that all CDN domains are L-tops-only, which would provide a complete characterization ( $D_{LDICT} = D_{CDN}$ ). They also suggest extending these results to randomized mechanisms and more general network-based notions of localness.

In summary, the paper rigorously defines the topological requirements of preference domains that make dictatorship inevitable, even when agents are only constrained to be locally honest, thereby refining our understanding of the Gibbard-Satterthwaite theorem in restricted domains.