4,193
edits
Gibbard's theorem: Difference between revisions
Crude adaptation of the intro from w:Gibbard's theorem: (<https://en.wikipedia.org/w/index.php?title=Gibbard%27s_theorem&oldid=1033066316>). More work to be done....
Psephomancy (talk | contribs) (Redirected page to Gibbard-Satterthwaite theorem) Tags: New redirect Visual edit |
(Crude adaptation of the intro from w:Gibbard's theorem: (<https://en.wikipedia.org/w/index.php?title=Gibbard%27s_theorem&oldid=1033066316>). More work to be done....) Tag: Removed redirect |
||
Line 1:
{{wikipedia}}
From [[w:Gibbard's theorem]]: <ref>https://en.wikipedia.org/w/index.php?title=Gibbard%27s_theorem&oldid=1033066316</ref>
<blockquote>
In the fields of [[mechanism design]] and [[social choice theory]], '''Gibbard's theorem''' is a result proven by philosopher [[Allan Gibbard]] in 1973.<ref>{{cite journal|last=Gibbard|first=Allan|author-link=Allan Gibbard|year=1973|title=Manipulation of voting schemes: A general result|url=http://www.eecs.harvard.edu/cs286r/courses/fall11/papers/Gibbard73.pdf|journal=Econometrica|volume=41|issue=4|pages=587–601|doi=10.2307/1914083|jstor=1914083}}</ref> It states that for any deterministic process of collective decision, at least one of the following three properties must hold:
# The process is [[Dictatorship mechanism|dictatorial]], i.e. there exists a distinguished agent who can impose the outcome;
# The process limits the possible outcomes to two options only;
# The process is open to [[Tactical voting|strategic voting]]: once an agent has identified their preferences, it is possible that they have no action at their disposal that best defends these preferences irrespective of the other agents' actions.
A corollary of this theorem is [[Gibbard–Satterthwaite theorem]] about voting rules. The main difference between the two is that Gibbard–Satterthwaite theorem is limited to [[Ranked voting|ranked (ordinal) voting rules]]: a voter's action consists in giving a preference ranking over the available options. Gibbard's theorem is more general and considers processes of collective decision that may not be ordinal: for example, voting systems where voters assign grades to candidates. Gibbard's theorem can be proven using [[Arrow's impossibility theorem]].
Gibbard's theorem is itself generalized by [[Gibbard's 1978 theorem]]<ref>{{Cite journal|last=Gibbard|first=Allan|date=1978|title=Straightforwardness of Game Forms with Lotteries as Outcomes|url=https://cms.kellogg.northwestern.edu/research/math/papers/203.pdf|journal=Econometrica|volume=46|issue=3|pages=595–614|doi=10.2307/1914235}}</ref> and [[Hylland's theorem]], which extend these results to non-deterministic processes, i.e. where the outcome may not only depend on the agents' actions but may also involve an element of chance.
</blockquote>
== References ==
<references/>
| |||