Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ ZENODOarrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
ZENODO
Other literature type . 2026
License: CC BY
Data sources: ZENODO
ZENODO
Research . 2026
License: CC BY
Data sources: Datacite
addClaim

Two New Proofs of the Gibbard--Satterthwaite Theorem

Authors: Fathi, Kevin;

Two New Proofs of the Gibbard--Satterthwaite Theorem

Abstract

We present two new proofs of the Gibbard–Satterthwaite theorem, the foundational result in social choice theory establishing that every surjective, strategy-proof social choice function on three or more alternatives is dictatorial. Both proofs share a common engine—the Mutual Exclusion of Influence (a six-line theorem showing that two voters cannot both control the same alternative pair at a shared profile while ranking the pair differently)—but diverge in how they derive dictatorship from this principle. The first proof is purely combinatorial: mutual exclusion combined with a transition sequence identifies a uniquely decisive voter without constructing a classical pivotal voter. The second proof is information-theoretic: under the uniform distribution on preference profiles, strategy-proofness yields an exact identity relating conditional outcome entropy to option-set size. The zero-overlap theorem—a measure-theoretic consequence of mutual exclusion—forces influence entropy to concentrate entirely in a single voter, characterizing dictatorship as the unique entropy profile (log |X|, 0, …, 0) compatible with strategy-proofness and surjectivity. To our knowledge, the second proof is the first to establish the Gibbard–Satterthwaite theorem via Shannon-type information-theoretic quantities. The Mutual Exclusion Theorem itself is new and replaces the pivotal-voter construction across all four established proof routes with a single structural principle. Both proofs connect to the Adversarial Aggregation Channel (AAC) framework, in which the influence entropy corresponds to adversarial sub-channel capacity and the mutual exclusion principle instantiates a channel-capacity conservation law.

Keywords

mutual exclusion of influence, option sets, adversarial aggregation channel, impossibility theorems, Shannon entropy, Gibbard–Satterthwaite theorem, influence concentration, social choice theory, information theory

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green