Conjunto de Smith

Em sistemas de votação, o conjunto de Smith, em homenagem a John H. Smith, mas também conhecido como o ciclo superior, é o menor conjunto não vazio de candidatos em uma eleição especial de tal forma que cada membro derrota todos os candidatos fora do set em uma eleição aos pares. O conjunto de Smith fornece um padrão de escolha ideal para um resultado eleitoral. Os sistemas de votação que sempre elegem um candidato do conjunto Smith passam no critério Smith e são considerados "Smith-eficientes".

Um conjunto de candidatos em que todos os membros do conjunto derrotam todos os membros fora do conjunto é conhecido como um conjunto dominante .

Propriedades

O conjunto Smith sempre existe e está bem definido. Existe apenas um menor conjunto dominante, pois os conjuntos dominantes são aninhados e não vazios e o conjunto de candidatos é finito.
O conjunto de Smith pode ter mais de um candidato, seja por empates aos pares ou por ciclos, como no paradoxo de Condorcet .
O vencedor do Condorcet, se houver, é o único membro do conjunto Smith.
O conjunto de Smith é sempre um subconjunto do conjunto de candidatos preferido por maioria mútua, se houver.

Comparação com o conjunto de Schwartz

O conjunto de Schwartz está intimamente relacionado e é sempre um subconjunto do conjunto de Smith. O conjunto de Smith é maior se e somente se um candidato no conjunto de Schwartz tiver um empate em pares com um candidato que não esteja no conjunto de Schwartz.

Algoritmos

O conjunto de Smith pode ser calculado com o algoritmo de Floyd – Warshall no tempo Θ $(n^{3})$ . Também pode ser calculado usando uma versão do algoritmo de Kosaraju ou do algoritmo de Tarjan no tempo Θ $(n^{2})$ .

Também pode ser encontrado por criar uma matriz de comparação aos pares com os candidatos classificados por seu número de vitórias aos pares menos derrotas aos pares (um ranking do método de Copeland ) e, em seguida, procurando o menor quadrado de células ao superior esquerdo que possa ser coberto assim que todas as células à direita dessas células mostram vitórias aos pares. Todos os candidatos nomeados à esquerda dessas células estão no conjunto Smith.

Exemplo: suponha que os candidatos A, B e C estejam no conjunto Smith, cada um batendo em pares um dos outros, mas todos os três pares em pares D e E. A, B e C seriam colocados nas 3 primeiras linhas (suponha que eles são colocados nessa ordem para este exemplo) da tabela de comparação em pares e, em seguida, verificamos que, ao cobrir todas as células de "A bate A" (a célula que compara A a si mesma) a "C bate C", todas as células à direita (as células que comparam A, B e C com D e E) mostrariam vitórias aos pares, enquanto que nenhum conjunto menor de células poderia fazê-lo, então A, B e C estariam no conjunto Smith.

Exemplo com a clasificação de Copeland:

As pérdidas e empates são escritas em negritas
	A	B	C	D	E	F	G
A	---	Gana	Pierde	Gana	Gana	Gana	Gana
B	Pierde	---	Gana	Gana	Gana	Gana	Gana
C	Gana	Pierde	---	Pierde	Gana	Gana	Win
D	Pierde	Pierde	Gana	---	Empate	Gana	Gana
E	Pierde	Pierde	Pierde	Empate	---	Gana	Gana
F	Pierde	Pierde	Pierde	Pierde	Pierde	---	Gana
G	Pierde	Pierde	Pierde	Pierde	Pierde	Pierde	---

A perde a C, assim que já sabemos que todos os candidatos de A a C (A, B, y C) estão no conjunto de Smith. Existe uma comparação entre um desses candidatos e um candidato que não é um deles: C perde a D, assim que D tambem está no conjunto. Agora existe otra tal comparação: D empate con E, assim que E tambem está no conjunto. Agora todos os candidatos que seguramente estão no conjunto ganam a todos os candidatos que já não estão no conjunto, así que sómente esses cinco candidatos estão no conjunto de Smith.

Ver também

Referências

Ward, Benjamin (1961). «Majority Rule and Allocation». Journal of Conflict Resolution. 5: 379–389. doi:10.1177/002200276100500405
Smith, J.H. (1973). «Aggregation of Preferences with Variable Electorates». Econometrica. 41: 1027–1041. JSTOR 1914033. doi:10.2307/1914033 Apresenta uma versão de um Critério Condorcet generalizado que é satisfeito quando as eleições aos pares se baseiam na escolha da maioria simples e, para qualquer conjunto dominante, qualquer candidato no conjunto é coletivamente preferido a qualquer candidato que não esteja no conjunto. Mas Smith não discute a ideia de um menor conjunto dominante.
Fishburn, Peter C. (1977). «Condorcet Social Choice Functions». SIAM Journal on Applied Mathematics. 33: 469–489. doi:10.1137/0133030 Reduz o critério generalizado de Condorcet de Smith ao menor conjunto dominante e o chama de Princípio de Condorcet de Smith.
Schwartz, Thomas (1986). The Logic of Collective Choice. Columbia University Press. New York: [s.n.] Discute o conjunto de Smith (chamado GETCHA) e o conjunto de Schwartz (chamado GOTCHA) como possíveis padrões para a escolha coletiva ideal.