Undecidability of the existence of dictator for strongly candidate stable voting procedures in an infinite society and Cantor's diagonal argument
The strong candidate stability theorem by Dutta et al. [ 4], one of the major theoremsof social choice theory, states that, with a finite number of voters, there exists a dictator for any voting procedure which satisfies strong candidate stability, strong unanimity and independence of irrelevant alternatives (IIA). This paper investigates a decidability problem of voting procedures in a society with an infinite number of individuals (infinite society) using Cantor's diagonal argument presented by Yanofsky [ 19] which is based on Lawvere [ 10]. We will show the following result. The problem whether a strongly candidate stable voting procedure has a dictator or has no dictator in an infinite society is undecidable. It is proved using the arguments similar to those used to prove an extended version of Cantor's theorem that there cannot be an onto function from <img src="/img/revistas/cam/v27n3/n_bastao.gif" align=absmiddle>(the set of natural numbers) to its power set <img src="/img/revistas/cam/v27n3/p1_curs.gif" align=absmiddle>(<img src="/img/revistas/cam/v27n3/n_bastao.gif" align=absmiddle>). This undecidability means that for any strongly candidate stable voting procedure we can not decide whether or not it has a dictator in finite steps by some program. A dictator of a voting procedure is a voter such that if he strictly prefers a candidate (denoted by x) to another candidate (denoted by y), then the voting procedure does not choose y. Strong candidate stability requires that there be no change in the outcome of an election if a candidate withdraws who would lose ifevery candidate stood for office.
| Main Author: | |
|---|---|
| Format: | Digital revista |
| Language: | English |
| Published: |
Sociedade Brasileira de Matemática Aplicada e Computacional
2008
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S1807-03022008000300002 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The strong candidate stability theorem by Dutta et al. [ 4], one of the major theoremsof social choice theory, states that, with a finite number of voters, there exists a dictator for any voting procedure which satisfies strong candidate stability, strong unanimity and independence of irrelevant alternatives (IIA). This paper investigates a decidability problem of voting procedures in a society with an infinite number of individuals (infinite society) using Cantor's diagonal argument presented by Yanofsky [ 19] which is based on Lawvere [ 10]. We will show the following result. The problem whether a strongly candidate stable voting procedure has a dictator or has no dictator in an infinite society is undecidable. It is proved using the arguments similar to those used to prove an extended version of Cantor's theorem that there cannot be an onto function from <img src="/img/revistas/cam/v27n3/n_bastao.gif" align=absmiddle>(the set of natural numbers) to its power set <img src="/img/revistas/cam/v27n3/p1_curs.gif" align=absmiddle>(<img src="/img/revistas/cam/v27n3/n_bastao.gif" align=absmiddle>). This undecidability means that for any strongly candidate stable voting procedure we can not decide whether or not it has a dictator in finite steps by some program. A dictator of a voting procedure is a voter such that if he strictly prefers a candidate (denoted by x) to another candidate (denoted by y), then the voting procedure does not choose y. Strong candidate stability requires that there be no change in the outcome of an election if a candidate withdraws who would lose ifevery candidate stood for office. |
|---|