Mecanismo de ditadura - Dictatorship mechanism

Na teoria da escolha social , um mecanismo de ditadura é uma regra pela qual, entre todas as alternativas possíveis, os resultados da votação refletem as preferências de uma única pessoa pré-determinada, sem consideração dos demais eleitores. Ditadura por si só não é considerado um bom mecanismo na prática, mas é teoricamente importante: por teorema impossibilidade de Arrow , quando há pelo menos três alternativas, a ditadura é a única classificou votando sistema eleitoral que satisfaça domínio irrestrito , eficiência de Pareto , e independência do alternativas irrelevantes . Da mesma forma, pelo teorema de Gibbard , quando há pelo menos três alternativas, a ditadura é a única regra à prova de estratégia .

A não ditadura é uma propriedade das regras de votação mais comuns , nas quais os resultados são influenciados pelas preferências de todos os indivíduos. Essa propriedade é satisfeita se não houver um único eleitor i com a ordem de preferência individual P, de modo que P é sempre a ordem de preferência social ("vencedora"). Em outras palavras, as preferências do indivíduo i nem sempre devem prevalecer. Os sistemas de votação anônima (com pelo menos dois eleitores) satisfazem automaticamente a propriedade de não ditadura.

A regra da ditadura tem variantes que são úteis na prática: ditadura serial , ditadura aleatória e ditadura serial aleatória (veja abaixo).

Definição formal

A não ditadura é uma das condições necessárias no teorema da impossibilidade de Arrow . Em Social Choice and Individual Values , Kenneth Arrow define não-ditadura como:

Não há eleitor i in { 1 , ..., n } tal que, para cada conjunto de ordenamentos no domínio da constituição, e cada par de estados sociais x e y , x y implica x P y .

Naturalmente, a ditadura é uma regra que não satisfaz a não-ditadura.

Ditadura em série

Um mecanismo de ditadura é bem definido apenas quando o ditador tem uma única opção preferida. Quando o ditador é indiferente entre duas ou mais opções preferidas, é possível escolher uma delas de forma arbitrária / aleatória, mas isso não será Pareto eficiente . Uma solução mais eficiente é nomear um segundo ditador, que tem o direito de escolher, entre todas as melhores opções do primeiro ditador, aquela que mais preferir. Se o segundo ditador também é indiferente entre duas ou mais opções, então um terceiro ditador escolhe entre elas, e assim por diante. Essa regra é chamada de ditadura serial . Outro nome para isso é mecanismo de prioridade .

O mecanismo de prioridade é freqüentemente usado em problemas de alocação de casas . Por exemplo, ao alocar dormitórios para os alunos, é comum ordenar os alunos por uma ordem de prioridade pré-especificada (por exemplo, por idade, notas, distância, etc.) e deixar que cada um deles, por sua vez, escolha seus quartos preferidos os disponíveis.

Ditadura aleatória e ditadura em série aleatória

A regra da ditadura é obviamente injusta, mas tem uma variante que é justa na expectativa. Na regra da ditadura aleatória (RD) , um dos eleitores é escolhido uniformemente ao acaso, e a alternativa mais preferida por esse eleitor é escolhida. Esta é uma das regras comuns para a escolha social aleatória . Quando usado em corpos multi-consistentes, às vezes é chamado de cédula aleatória .

Da mesma forma que a ditadura, a ditadura aleatória também deve lidar com a possibilidade de indiferenças; a solução comum é estendê-lo para a ditadura serial aleatória (RSD), também chamada de prioridade aleatória . Nesse mecanismo, uma permutação aleatória dos eleitores é selecionada, e cada eleitor, por sua vez, restringe as alternativas existentes às que mais preferem, dentre as que ainda estão disponíveis. É um mecanismo comum na alocação de objetos indivisíveis entre os agentes; veja a alocação aleatória de itens prioritários .

Propriedades

Allan Gibbard provou o teorema da ditadura aleatória . Diz que, quando as preferências são estritas, RD é a única regra que satisfaz as três propriedades a seguir:

  • Anonimato: a loteria não discrimina antecipadamente entre os diferentes eleitores.
  • Forte resistência à estratégia de SD: todo relatório falso de um agente resulta em um resultado que é fracamente dominado estocasticamente .
  • Eficiência de Pareto ex-post: o resultado final é eficiente de Pareto.
    • Na verdade, com preferências estritas, RD satisfaz uma propriedade de eficiência mais forte chamada eficiência SD : a loteria resultante não é dominada estocasticamente. Com preferências fracas, RSD satisfaz a eficiência ex-post, mas viola a eficiência SD.
    • Mesmo com preferências estritas, RD viola a propriedade mais forte chamada de eficiência de PC: a loteria resultante pode ser dominada no sentido de comparações de pares (para cada agente, a probabilidade de que outra loteria produza uma alternativa melhor do que a loteria RD é maior do que o ao contrário).

O RD também satisfaz uma propriedade chamada consistência da agenda. É a única regra que satisfaz as seguintes propriedades:

  • Consistência de contração forte ("regularidade"): as probabilidades não podem diminuir ao remover alternativas arbitrárias.
  • Eficiência ex-post.
  • Uma versão probabilística de Independência de alternativas irrelevantes .

Pesquisas subsequentes forneceram provas alternativas, bem como várias extensões. Um resultado de impossibilidade relaciona-se a estender o teorema para preferências fracas. Ele diz que, com preferências fracas, as propriedades de anonimato, eficiência de SD e segurança de estratégia de SD são incompatíveis quando há pelo menos 4 agentes e 4 alternativas. A prova foi derivada usando um solucionador SMT e verificada por um provador interativo de teoremas Isabelle / HOL .

RD satisfaz um axioma chamado consistência da população e um axioma chamado consistência da clonagem , mas viola a consistência da composição .

Computação

É fácil implementar os mecanismos RD e RSD na prática: basta escolher um eleitor aleatório, ou uma permutação aleatória, e deixar que cada ditador, por sua vez, escolha a melhor opção. No entanto, às vezes se deseja calcular com antecedência qual é a probabilidade de uma determinada alternativa ser escolhida. Com RD (quando as preferências são estritas), isso também é fácil: a probabilidade de que a alternativa x seja escolhida é igual ao número de eleitores que classificam x primeiro, dividido pelo número total de eleitores. Mas a situação é diferente com RSD (quando há indiferenças):

  • Calcular as probabilidades é #P -difícil;
  • Existe um algoritmo eficiente para calcular o suporte (as alternativas escolhidas com probabilidade positiva);
  • Existem algoritmos com complexidade parametrizada tratável , onde os parâmetros são: número de objetos, número de alternativas e número de tipos de eleitores.
  • Existe um algoritmo de tempo exponencial para calcular as probabilidades no contexto da votação de aprovação fracionária .

Referências

  1. ^ Game Theory Second Edition Guillermo Owen Ch 6 pp124-5 Axiom 5 Academic Press, 1982 ISBN  0-12-531150-8
  2. ^ a b c Felix Brandt (2017-10-26). "Escolha Social Probabilística". Em Endriss, Ulle (ed.). Tendências em escolha social computacional . Lulu.com. ISBN 978-1-326-91209-3.
  3. ^ Gibbard, Allan (1977). "Manipulação de esquemas que misturam votação com acaso" . Econometrica . 45 (3): 665–681. doi : 10.2307 / 1911681 . ISSN  0012-9682 .
  4. ^ Pattanaik, Prasanta K .; Peleg, Bezalel (1986). "Distribuição de poder sob regras de escolha social estocástica" . Econometrica . 54 (4): 909–921. doi : 10.2307 / 1912843 . ISSN  0012-9682 .
  5. ^ Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian (31/01/2018). "Provando a incompatibilidade de eficiência e segurança da estratégia por meio de solução SMT" . Jornal do ACM . 65 (2): 6: 1-6: 28. arXiv : 1604.05692 . doi : 10.1145 / 3125642 . ISSN  0004-5411 .
  6. ^ a b "A complexidade computacional da ditadura serial aleatória" . Cartas de Economia . 121 (3): 341–345. 01-12-2013. arXiv : 1304.3169 . doi : 10.1016 / j.econlet.2013.09.006 . ISSN  0165-1765 .
  7. ^ "Algoritmos parametrizados para a ditadura serial aleatória" . Ciências Sociais Matemáticas . 72 : 1–6. 01-11-2014. doi : 10.1016 / j.mathsocsci.2014.07.002 . ISSN  0165-4896 .
  8. ^ Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (01/06/2005). “Escolha coletiva sob preferências dicotômicas” . Journal of Economic Theory . 122 (2): 165–184. doi : 10.1016 / j.jet.2004.05.005 . ISSN  0022-0531 .