Gibbard's theorem: Difference between revisions
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: | Line 1: | ||
{{wikipedia}} |
|||
#REDIRECT [[Gibbard-Satterthwaite theorem]] |
|||
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/> |
|||
Revision as of 21:49, 25 November 2021
From w:Gibbard's theorem: [1]
In the fields of mechanism design and social choice theory, Gibbard's theorem is a result proven by philosopher Allan Gibbard in 1973.[2] It states that for any deterministic process of collective decision, at least one of the following three properties must hold:
- The process is 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 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 (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[3] 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.
References
- ↑ https://en.wikipedia.org/w/index.php?title=Gibbard%27s_theorem&oldid=1033066316
- ↑ Gibbard, Allan (1973). "Manipulation of voting schemes: A general result" (PDF). Econometrica. 41 (4): 587–601. doi:10.2307/1914083. JSTOR 1914083.
- ↑ Gibbard, Allan (1978). "Straightforwardness of Game Forms with Lotteries as Outcomes" (PDF). Econometrica. 46 (3): 595–614. doi:10.2307/1914235.