Preambolo: ritorno sull’elezione presidenziale francese

Il 6 maggio, François Hollande è stato eletto presidente della Repubblica francese. Per i nostri lettori stranieri, richiamiamo per la prima volta come funziona un’elezione presidenziale in Francia. Un piccolo numero di candidati (10 in questo caso) di vari bordi politici è stato precedentemente selezionato da funzionari eletti locali, si procede tra loro a un’elezione a due torre. In tale voto, è organizzato un primo turno di voto in cui ogni elettore deve scegliere uno dei candidati (o astenersi). Se uno dei candidati riceve la maggioranza assoluta dei voti espressi (che è raro nella pratica), allora questo candidato è dichiarato vincitore. Altrimenti, si procede a un secondo turno di voto in cui i due candidati che hanno ricevuto il maggior numero di voti nel primo turno competere in faccia a faccia; Il candidato che riceve il più voto nel secondo round viene quindi dichiarato il vincitore.

Ricordiamo anche quali sono stati i risultati delle elezioni del 2012. Per semplificare la presentazione, manterremo solo i cinque candidati principali ( Quale a volte astrai dalla loro iniziale), vale a dire François Bayrou (B), François Hollande (H), Marine Le Pen (L), Jean-Luc MéLenchon (M) e Nicolas Sarkozy (s). I risultati del primo round erano i seguenti:

  1. Olanda (31%)
  2. sarkozy (28%)
  3. le penna (19%)
  4. mélenchon (13%)
  5. bayrou (9%)

Nessuno dei candidati ha superato il 50% dei voti, c’è così aveva un secondo turno contro l’Olanda a Sarkozy, i cui risultati erano:

  1. holland (52%)
  2. sarkozy (48%)

JPEG - 32,4 KBFrançois Hollande Hollande, il candidato eletto dalla gente.

Alla fine, è stato l’Olanda che è stato eletto presidente.

Siamo un po ‘più curiosi, e chiediamo che cosa avrebbero potuto essere i risultati degli altri viso a facce immaginabili. Oltre al secondo round h-s che è avvenuto effettivamente, ci sarebbero state 9 altre possibilità: B – H, B – L, B – M, B – S, H – L, H – M, L – m, L – S e M – S. Ovviamente non sapremo mai con certezza cosa avrebbero dato queste seconde torri fittizie; Tuttavia, per credere agli istituti di indagine, i risultati sarebbero stati praticamente come segue:

  • bayrou bat holland 51 – 49;
  • bayrou batte la penna 74 – 26;
  • Bayrou Bat MéLenchon 75 – 25;
  • bayrou bat sakarkozy 55 – 45;
  • holland batti le penna 65 – 35;
  • Holland Bat MéLenchon 80 – 20;
  • le penna bat mélenchon 53 – 47;
  • le penna è battuto da sarkozy 32 – 68;
  • méLenchon è Beaten di Sarkozy 36 – 64.

Sintetizziamo tutto questo sotto forma del “diagramma di preferenza binario” di seguito, dove:

  • ogni candidato è rappresentato da una posizione separata;
  • Tra ogni coppia di candidati, c’è una freccia che punta verso quello dei due che si trascurisse sul viso a faccia (trascuriamo la possibilità di un ex ie);
  • Su ogni freccia, indiciamo il punteggio (in percentuale) con cui il vincitore della vincitrice del viso a faccia interessata vince.

Diagramma di preferenze binarie per le elezioni presidenziali

Cosa avrebbero potuto dare le seconde torri immaginabili tra i cinque candidati principali nelle elezioni presidenziali francesi del 2012 ( Le frecce puntano ai vincitori).

jpeg - 28,4 kb françois bayrou bayrou, il candidato voluto da parte del popolo?

A Troding Strikes: François Bayrou avrebbe sconfitto uno dei suoi avversari nel secondo round! Come, nella situazione storica, non è stato qualificato, ovviamente non è stato eletto, ma diversi editori hanno sottolineato che c’era una forma di paradosso … non sarebbe stato logico, in effetti, un candidato generalmente preferito a qualsiasi altro il favorito di tutti?

Filosofia del criterio di Condorcet

Dichiarazione del criterio

jpeg - 42.3 ko nicolas de Condorcet Ritratto di Condomret Nicolas di Jean-Baptiste Greuze.

Si trovava in ogni caso l’opinione di Nicolas de Condorcet, studioso francese del diciottesimo secolo, che era uno dei pionieri dello studio matematico della democrazia. Inserito le seguenti definizioni (che ci adattiamo qui nella lingua moderna):

Definizioni (vincitore di Condomret; Criterio di Condorcet)

Se, tra i candidati per un’elezione, c’è uno che, di fronte a qualsiasi Altro, è preferito dalla maggioranza degli elettori, allora questo candidato è chiamato il vincitore del Condorcet.

Si dice che un metodo elettorale soddisfa il criterio di Concorcet quando, quando c’è un vincitore del Condorcet, è sempre lui che questo metodo dichiara il vincitore (a condizione che gli elettori abbiano votato in base alle loro genuine preferenze ).

Prima di tutto, è necessario un audit: stiamo parlando del vincitore del Condorcet come se fosse unico, ma è così? La risposta è “sì”:

teorema (unicità del vincitore del comando)

non può essere più di un vincitore del condorcetto con un’elezione.

Dimostrazione

Immagina una situazione in cui ci sarebbero stati due vincitori di Condorcet (almeno), chiamato X e Y. Poiché X è un vincitore del Condorcet, supera N ‘import dai suoi concorrenti di fronte -Face-to-Face, così in particolare Y. Ma degli stessi, dal momento che c’è un vincitore del Condorcet, deve sconfiggere X Face-to-Face … o il viso a faccia tra X e Y può ovviamente avere solo Un vincitore: quindi è realmente impossibile che ci sia più di un vincitore del Condomret.

La tesi di condorcet era che, per un metodo elettorale per essere davvero giusto, deve soddisfare il Criterio omonimo. Citare il grande uomo:

Può derivare dal modo di votare nelle elezioni ordinarie una decisione effettivamente contraria alla pluralità. Pertanto, si dovrebbe sostituire in questo modulo quello in cui ogni voto, esprimendo l’ordine secondo cui pone i candidati, pronunciarebbero sia le rispettive preferenze che dà loro. Quando vuoi scegliere il candidato più dignitoso, sarà sufficiente che il sistema non implica la contraddizione per il candidato che merita la preferenza su tutti.

Condorcet si opporrà pertanto al nostro metodo insolitivo con due turni, dall’esempio di Bayrou mostra che non soddisfa il suo criterio! Ma prima di andare oltre, dovrebbe essere spiegato quali sono le giustificazioni teoriche sulla tesi di Condomret.

Giustificazione matematica del criterio di condorcese

Se leggi il mio articolo precedente, probabilmente ricordi che un grande problema della teoria matematica delle elezioni è quanto segue: gli elettori a volte hanno interesse per “voto strategico” esprimendo un falso parere che avrebbe portato il risultato del voto migliore per loro di quello. Cosa avrebbe dato sincero Suffrage! Nel caso del voto disincomanico con due torri che stavamo parlando del preambolo, un tipico esempio è ciò che è chiamato il “voto utile”. Immagina e il giorno prima delle prime sondaggi tondo danno Sarkozy lontano dal piombo, seguito dalla penna e dall’Olanda al gomito a gomito, e molto più lontano MéLenchon. Considera un elettore fittizio che è un grande fan di MéLenchon, è mescolato sull’Olanda, non piace Sarkozy e odia la penna. Questo elettore Dice: “Se voto MéLenchon, non sarà abbastanza per qualificarlo per il secondo round comunque; D’altra parte, corro il rischio di vedere un secondo turno tra i due candidati che mi piacciono i minimi. D’altra parte, votando Holland, riducono le possibilità di un secondo turno Sarkozy – Le Pen e io promuovo l’eliminazione del mio candidato odiato! Quindi ho interesse a votare l’Olanda “.

Ma quando prendiamo in considerazione questo fenomeno strategico di voto, il vincitore del Condorcet (se ce n’è uno) può organizzare per essere eletto di sicuro! (In ogni caso in il metodo insolito con due round).
In effetti, immagina che ci sia un vincitore del Condorcet chiamato X, e supponiamo che i sondaggi prevedono la vittoria di un altro candidato. Come X è un vincitore del Condorcet, c’è la maggioranza degli elettori che preferiscono a Y. Questa maggioranza può quindi consultare e dire “Comprendiamo i voti per X dal primo round; Quindi avrà la maggioranza dei voti sul suo nome e sarà eletto, che più interessante per noi! “. Certo, questo non significa che tutti gli elettori di questa maggioranza abbiano X per il candidato preferito. Si può persino immaginare che un numero considerevole di loro preferisca un terzo candidato Z e potrebbe essere tentato di fare vincere Z con l’aiuto di I vecchi elettori che preferiscono anche z a x … ma è appena perso, perché x è un vincitore del condominio, c’è anche la maggioranza (ma non costituita dagli stessi elettori, ovviamente) che preferisce X a Z; se Z diventa Troppo pericoloso nei sondaggi, è la maggioranza che verrà quindi ligore per votare X per evitare l’elezione di z!

Quindi, un metodo soddisfacente il criterio di condominio ha questo vantaggioso che gli elettori non debbano scavare Cervello per sapere se il loro voto è ben calcolato: con un metodo del genere, se c’è un vincitore del Condorcet, sarà necessariamente eletto!

Un’altra qualità dei metodi che soddisfa il criterio del CondoRcet è il seguente: mentre i metodi convenzionali (compresi i metodi A, B, C, D e E dell’articolo precedente) sono soggetti a un fenomeno di “voci di dispersione” quando il numero di candidati diventa grande, fenomeno che può portare a un risultato irrilevante, il risultato di un metodo che soddisfa il criterio di Condorcet non cambia quando prelevamo o aggiungiamo candidati “piccoli”:

teorema (indifferenza ai piccoli candidati)

  1. se partiamo da una situazione in cui un candidato è conquistato Condorcet, e uno o più degli altri candidati si ritirano dal Elezione, quindi il vincitore del Condomret iniziale rimane il vincitore di Condomret dopo questo prelievo.
  2. Viceversa, se condividiamo una situazione in cui un candidato è conquistatore di Condorcet, e uno o più nuovi candidati sono introdotti a ciascuno di cui il E Il vincitore iniziale è preferito faccia a faccia, quindi il vincitore del Condorcet iniziale rimane il vincitore del Condomret dopo questa aggiunta.

Dimostrazione

Il ritiro o l’aggiunta di un candidato non modifica le preferenze binarie degli elettori tra gli altri candidati. Per punto i, dal momento che il nostro vincitore iniziale del Condorcet ha inizialmente battuto tutti i suoi avversari in faccia a faccia, in modo che rimane il caso se uno o più dei suoi avversari si ritirano. Per il punto II, il nostro vincitore iniziale del Condorcet continua a battere tutti i suoi avversari iniziali, e abbiamo pensato che stava anche picchiando i suoi nuovi avversari, in modo che sia sempre vincitore di Condorcet nella nuova situazione.

Nota D’altra parte che, se il vincitore del Prospect Condomret è in un sensità un vincitore inevitabile, è come non necessariamente colui che è davvero il favorito del popolo (nel senso che avevamo menzionato Nell’articolo precedente, vale a dire misurando la felicità totale che questo candidato porterà al pubblico se eletto). Quindi, se ci sono solo due candidati X e Y, e il 51% degli elettori preferisce leggermente X a Y e il 49% degli elettori preferisce molto in gran parte Y a X, è x che sarà eletto quando vogliamo dire che è piuttosto dove rappresenta la volontà del popolo. Detto questo, questo fenomeno della “dittatura di maggioranza”
non è direttamente correlato al criterio di CondoRcet: è infatti un vizio inerente alla democrazia,
come già incluso Kant.

Per il momento, abbiamo parlato molto sulla filosofia e poche matematiche (e persino meno ricerche!). Ma questa introduzione era necessaria per capire perché il criterio di CondoRcet è un oggetto matematico naturale e importante. Nella seconda parte di questo articolo, parleremo ora di ricerche molto più recenti che ruotano attorno a questo criterio.

Il Paradox del Condorcet esiste davvero?

il paradosso del condominio

Il criterio di Condomret ci porta naturalmente per parlare del Condorcet Paradox, che avevamo già incontrato nell’articolo precedente. Questo paradosso afferma in sostanza che non è necessariamente un vincitore del condominio:

Paradox Condorcet (1785)

Non appena ci sono almeno 3 candidati , ci sono situazioni in cui non c’è vincitore di condomm.

dimostrazione

Supponiamo che ci siano almeno 3 candidati e scegliere tre candidati particolari tra loro, chiamati x, y e z. Immaginiamo che tutti gli elettori preferiscano X, Y e Z a tutti gli altri candidati, in modo che nessuno di questi altri candidati non possa essere conquistatore di Condom. Ora possiamo immaginare inoltre che il 40% degli elettori abbia l’ordine di preferenza “x Allora Y allora Z”, il 35% “y allora z allora x” e 25% “Z e poi x allora Y”. Poi il 65% degli elettori preferisce X a Y (quindi non c’è un vincitore del condorcetto), il 75% preferisce Y a Z (quindi Z non è un vincitore del condorcetto) e il 60% preferisce Z a X (quindi x non è un condorcetto Vincitore): nessun candidato è quindi conquistatore di Condomret.

Tuttavia, abbiamo visto nel preambolo un caso reale Elezione con non meno di 5 candidati in cui vi è davvero un vincitore del condommetto! suggerisce che potrebbe esistere un fenomeno che vierebbe il paradosso della condorcetta in pratica, perché le situazioni politiche realistiche avrebbero verificato alcune particolari assunzioni in cui Il paradosso è impossibile. Nei paragrafi seguenti, presenteremo diversi modelli di preferenze politiche e vedere se consentono o non il verificarsi del paradosso del Condorcet.

Paradox CondoRcet su una scacchiera politica

Introdurremo qui una modellizzazione piuttosto realistica delle preferenze politiche degli elettori chiameremo la modellazione per la scacchiera politica, la cui idea è semplicemente in generale, Stiamo votando per il candidato le cui posizioni cadono per quanto riguarda le nostre opinioni. Si presume che ci sia una “scacchiera politica” astratta (che rende possibile parlare di “distanza politica”) su cui i candidati possono essere collocati così come gli elettori, come le preferenze di ciascun elettore sono il candidato che è il più vicino a quello più lontano.

Si potrebbe sperare che con tale modellazione, non c’è mai un paradosso di condorcet … ma questo non è il caso! Supponiamo che la scacchiera politica corrisponda a una vera scacchiera (le cui scatole misurano, dicono, lato 5 cm), dove si posiziona un candidato x sulla scatola B7, un candidato Y sulla scatola F7, un candidato Z IT E4 e un candidato C2 . Immaginiamo che l’elettorato sia diviso in quattro gruppi di varie dimensioni, ognuna delle quali ha esattamente la stessa posizione di uno dei candidati:
il 34% degli elettori sono a livello di X, 26% a livello di Y , Il 18% della Z e il 22% W. Le distanze tra i candidati sono quindi quelle indicate sul disegno sottostante, in modo che le seguenti preferenze per gli elettori (“x > y” significato “x è preferito a Y “):

L’esempio della scacchiera

ui, a sinistra, un politico Configurazione della scacchiera Tale che, se ci sono il 34% degli elettori in X, 26% in Y, 18% in Z e 22% in W, e che ogni elettore preferisce i candidati di cui è più vicino, allora nessun candidato è il Candidato Vincitore: sulla destra, il diagramma di preferenza binario corrispondente.

  • x > y > z > w per il 34% delle elezioni Rs;
  • y > z > x > w per 26% degli elettori;
  • w > z > x > Y per il 22% degli elettori;
  • z > w > y > x per il 18% degli elettori.

Quindi, in questa configurazione, x non è un vincitore del condorcetto (perché è battuto dalla Z al 66%) né y (battuto da da x al 56%), né Z (battuto da Y al 60%), né w (battuto dalla Z al 78%): quindi abbiamo il paradosso di Condorcet!

i teoremi del votatore medio

Nell’esempio della scacchiera, abbiamo fatto una fase politica della dimensione 2, vale a dire con 2 coordinate (una per le colonne e una per le linee). Non era una coincidenza! Perché se la scacchiera politica ha solo una dimensione, può essere dimostrata che c’è ancora un vincitore del condominio:

teorema (primo il teorema del votante mediano, nero 1958)

Quando la scacchiera politica è Un asse graduato (che generalmente interpretiamo come posizionamento politico del “più a sinistra” verso il “più giusto”), c’è sempre un vincitore del condominio.

per dimostrare questo teorema, noi introdurrà prima una definizione che ci sarà utile nella prova:

definizione (profilo preferenziale in λ)

Si dice che un elettore in un profilo di preferenze in λ (leggi “lambda” ) Quando, quando si percorre l’elenco dei candidati da sinistra a destra a destra, la preferenza di questo elettore sale fino a raggiungere il suo candidato preferito, poi scende. (Forse, il candidato preferito può essere il più a sinistra o il diritto a destra di tutti; la cosa importante non è mai tornare indietro dopo aver perso).

Ad esempio, se assumiamo che i candidati del presidenziale I ranghi elettori da sinistra a destra in base all’ordine “M, H, B, S, L”, quindi le preferenze “B > H > s > il > m “o” l > s > b > h > m” sono profili in λ, ma non “h > M > S > B > L, Da questo Una preferenza scende tra H e B prima di salire tra B e S.

Dimostrazione del primo teorema dell’elettore mediano

il primo il punto è notare che, quando la scacchiera politica è un asse graduato, tutti gli elettori hanno un PR OFF preferibilmente in λ. In effetti, considera qualsiasi elettore.Quando attraversiamo la scacchiera politica da sinistra a destra, iniziamo avvicinando a questo elettore prima di allontanarci, in modo che le preferenze dell’elettore aumentino (finché siamo rimasti a sinistra di questo elettore) prima di scendere (una volta che siamo Più a destra): corrisponde a un profilo di preferenza in λ. (Se nessun candidato si trova esattamente nella stessa posizione dell’Elettore, sarà necessario guardare le distanze precise da sapere se il candidato preferito di questo elettore è quello immediatamente situato sulla sua sinistra o immediatamente alla sua destra, ma nel Due caso abbiamo un profilo in λ).

Ora dimostriamo il teorema. Per evitare i problemi di ticchettizzazione, supponiamo che vi sia un numero dispari di elettori. Ognuno di questi elettori ha un candidato preferito. Immagina di aver chiesto a ciascun elettore di scrivere il nome del suo candidato preferito su una newsletter e classifica le newsletter ottenute dal candidato più sinistro del candidato più a destra, e chiamiamo x il candidato che si trova sul bollettino candidato situato nel mezzo di questa classifica. Asserisco che x è un vincitore del Condorcet. In effetti, considera un candidato situato, ad esempio, più giusto di x (per un candidato sulla sinistra, sarebbe sufficiente per invertire “giusto” e “sinistra” nel resto). Come X è nel mezzo della nostra classificazione delle newsletter, c’è una maggioranza assoluta di newsletter che per favore di X o un candidato più sinistro di X, il che significa che c’è una maggioranza assoluta degli elettori il cui candidato preferito è x o un candidato situato di più a sinistra di X. Quindi considera un tale elettore, di cui chiamiamo Z il candidato preferito (Z che può essere lo stesso di x). Sappiamo attraverso il paragrafo sopra che il nostro elettore ha un profilo di preferenze in λ, quindi quando si allontana dalla Z a destra, le preferenze dell’elettore diminuiscono solo. Ma qui x è almeno come Desk come z e y è ancora più giusto di x, quindi attraverseremo lì più avanti fino a x durante questa lontananza; Pertanto il nostro elettore preferisce X a Y. Poiché è lo stesso per una maggioranza assoluta degli elettori, significa che X è prevalentemente preferito a Y, e come possiamo fare lo stesso ragionamento per tutti i possibili possibili, dimostra che x è un condominio vincitore. Si noti che questa dimostrazione mostra che il teorema rimane valido non appena tutti gli elettori hanno un profilo delle preferenze in λ.

La mancanza Di questo primo teorema dell’elettore mediano (e modellazione della scacchiera politica in generale) è che ritiene che l’unica qualità dei candidati che avrebbe interessato gli elettori sia il loro posizionamento politico. Tuttavia, con uguale posizione politica, alcuni candidati possono essere “migliori” o “peggiori”, ad esempio a causa delle loro qualità intellettuali o carismatiche. Un modello più fine è quindi il seguente: Da un lato, c’è un asse graduato su cui sono collocati i candidati e gli elettori, e dall’altro è anche associato a ciascun candidato un “valore intrinseco”. Ogni elettore calcola quindi per i vari candidati un “punteggio” pari al valore intrinseco del candidato meno la distanza del candidato, e classificava i candidati dai candidati dal punteggio decrescente: un esempio è dato sul disegno sottostante.

Asse politico con valori intrinseci

Qui è un esempio che prende in considerazione sia il posizionamento candidati sull’asse politico “sinistra – destra” e il valore intrinseco dei candidati. In questo esempio, ci sono cinque candidati avvistati da punti, il valore intrinseco di ciascuno di essi indicato tra parentesi. Se consideriamo un elettore situato nella posizione “E”, questo elettore dà quindi un punteggio m parità pari a 9 (valore) – 5 (distanza) = 4, a h a un punteggio di 8 – 1 = 7, a b un punteggio di 5 – 1 = 4 e dello stesso per S e L dei rispettivi punteggi di 5 e 3. Pertanto, l’ordine delle preferenze di questo elettore è “H > M > s > b > l “- quale non è un profilo in λ.

Bene, in questo modello, siamo ancora assicurati dell’esistenza di un vincitore del comando:

teorema (secondo teorema del votante mediano, Roberts 1977)

Se i candidati e gli elettori sono posizionati sullo stesso asse graduato da un lato, a ciascun candidato è associato a un valore intrinseco sull’altro, e che le preferenze di ciascun elettore sono determinate dalla differenza “valore intrinseco – distanza dal candidato “, Poi c’è sempre un vincitore di Condomret.

Per dimostrare questo teorema, stiamo anche iniziando qui introducendo una definizione:

definizione (definizione preferenze archiviato)

che vengono forniti i candidati classificati da sinistra a destra e Gli elettori classificati da sinistra a destra, dice che la configurazione delle preferenze è impedita se è impossibile trovare un candidato x sulla sinistra che un altro candidato y e un elettore ha più a sinistra di un altro elettore B che preferisce X Ma B preferisce x a y (in altre parole, che sono tali che l’elettore a sinistra preferisce il candidato giusto e il giusto elettore il candidato a sinistra).

Dimostrazione del secondo teorema dell’elettore mediano

Il primo punto è notare che, sotto le ipotesi del teorema, la configurazione delle preferenze è privata. Considera due candidati X e Y, con te più a destra di X. Diciamo che la configurazione delle preferenze è descritta significa che come elettore fittizio si muove da sinistra a destra sull’asse politico, non può essere una preferenza “Y > x “a una preferenza” x > y “; Per dimostrarlo, è sufficiente stabilire che la differenza “X punteggio del punteggio” può aumentare solo quando andiamo da sinistra a destra. Ora, in questa differenza nel punteggio, l’unica cosa che cambia da un elettore all’altra è la parte del punteggio che dipende dalla distanza: quella che dipende dal punteggio è la stessa! Quindi, è sufficiente mostrare che la differenza “distanza da y – distanza di x” è solo diminuendo quando si passa da sinistra a destra. Quindi, cosa succede quando andiamo da sinistra a destra? All’inizio, a condizione che siamo ancora rimasti di X, ogni passo a destra più vicino come x come di y, e quindi la differenza “distanza a y – distanza da x” non varia. Quindi, quando si è tra X e Y, ogni passo a destra non solo diminuisce la distanza da Y, ma aumenta anche quella a X, in modo che la differenza “distanza a y – distanza a x” diminuisce. Infine, al di là di y, ogni passo a destra ci sposta il maggior numero di x come da y, e quindi di nuovo la differenza di distanze rimane costante. Quindi abbiamo una configurazione di preferenze declosed.

Ora dimostriamo il teorema. Per evitare i problemi di ex-æquo, supponiamo che vi sia un numero dispari di elettori. Se classifichiamo questi elettori da sinistra a destra sull’asse politico, allora c’è uno che si trova nel mezzo di questa classifica, che chiameremo il “Elettore Mediano”. Dico che le preferenze di maggioranza sono esattamente le stesse di quelle di questo elettore mediano, e quindi in particolare il candidato preferito dell’Elettore Mediano è un vincitore del Condorcet.
In effetti, supponiamo che tra due candidati X e Y, l’elettore mediano preferisce x; Per fissare le idee, diciamo che è più giusto di x (altrimenti, invertirsi “a destra” e “sinistra”). Quindi, secondo il risultato intermedio sopra, ancora più sugli elettori sinistro che l’elettore mediano preferisce anche X a Y, e quindi c’è la maggioranza degli elettori che preferiscono X a Y, cosa volevamo dimostrare. Si noti che questa dimostrazione mostra che il teorema rimane valido non appena la configurazione delle preferenze è privata.

Oltre a dimostrare l’esistenza dell’esistenza dell’esistenza dell’esistenza dell’esistenza dell’esistenza di L’esistenza dell’esistenza dell’esistenza del conquistatore di Condomret, le prove di cui sopra ci dice cosa è questo vincitore: è il candidato preferito dell’Elettore situato “nel mezzo” di tutti sull’asse delle preferenze (da cui il nome di “Teorema” del Elettore Mediano “). Un fenomeno simile si è verificato per il primo teorema dell’elettore mediano, dove il risultato delle elezioni corrispondeva alla scelta più centrale tra i candidati preferiti dei vari costituenti. Una moralità che possiamo nel disegno è che il criterio di CondoRcet promuove i candidati “centrici” rispetto ai candidati più orientati o estremi Ist. È un comportamento desiderabile? I pareri differiscono su questa domanda:
per alcuni, per promuovere i centrici rischia i disgustosi elettori non centrici che avrebbero l’impressione di mai presi in considerazione e promuovere la politica del consenso del MOU a spese di più ambiziosi progetti; Altri, al contrario, ritengono che una politica centrista avrebbe placato il dibattito consentendo a tutti di navigare un po ‘, e quella grande stabilità politica sarebbe più favorevole alla creazione di progetti a lungo termine..

e Quando non c’è nessun vincitore di condomm?

I teoremi dell’elettore mediano tendono a indicare che in situazioni concrete, avremo la maggior parte del tempo un vincitore del Condorcet, quale sia la storia delle elezioni in realtà corroborando.
questo detto, la modellazione puramente dimensionale su cui questi teoremi riposano sono chiaramente troppo riducendo, e l’esempio della scacchiera ci mostra che è solo un caso più complesso per rivedere il paradosso del condominio .. In breve, Se desideriamo applicare un metodo elettorale che soddisfa il criterio di Condorcet, sarà necessario dare una regola per designare il candidato eletto quando non c’è vincitore del condominio. Ma quale? Questa domanda ha iniziato ad essere studiato solo pochi decenni, soprattutto perché prima dell’invenzione della scienza informatica è stato praticamente impossibile rendere il conteggio di un voto in cui gli elettori indicano le loro preferenze tra tutti i candidati. Questa è una ricerca su questo argomento che ora parleremo.

il metodo minimax

Iniziamo con un approccio molto semplice. Si può dire: “Alla base, un vincitore del Condomret è un candidato che svolge più del 50% contro tutti gli altri. Se nessuno dei candidati riesce, possiamo abbassare la soglia del 50% da dire:” Se c’è solo uno dei candidati che riescono a raggiungere, per esempio, il 45% contro qualsiasi altro, allora è questo candidato che deve essere eletto “. In altre parole, il protocollo è il seguente: per ciascuno dei candidati, guardiamo il peggio dei punteggi che avrebbe fatto nelle sue diverse facce facciali, quindi dichiariamo che i candidati il cui punteggio peggiore è il migliore. Questo metodo è chiamato metodo minimax, perché sembra chi è il migliore (“max”) nel Situazione in cui è il meno buono (“Mini”).

Quindi, per l’esempio della scacchiera presentata sopra (dove non c’è vincitore del condominio), la peggiore sconfitta di X avviene contro Z di 66 %, la peggiore sconfitta di Y contro X del 56%, la peggiore sconfitta della Z contro Y del 60% e la peggiore sconfitta di W contro Z di 78%. La più leggera di queste peggiori sconfitte è quella di Y, che è quindi il vincitore del minimox.

Sembra naturale! Ahimè, questo metodo apre la strada a una forma di “manipolazione” (Pejpolazione “del” Voto strategico “) particolarmente pericoloso. Supponiamo infatti che nell’esempio della scacchiera affrontata in precedenza, abbiamo più di un gruppo V composto da” ” Anarchici “. Questi anarchici sono relativamente numerosi poiché costituiscono il 40% della popolazione totale, in modo che abbiamo la seguente distribuzione generale: x 20%, Y 16%, Z 11%, w 13%, v 40%. Tuttavia gli anarchici sono unanimi contro di loro al di fuori del loro gruppo: così come i sostenitori di X e Y a partire da Z quello di W Classify V Ultima posizione nel loro ordine delle preferenze! È qui che gli anarchici hanno una grande idea per prendere il potere nonostante questo importante handicap. Dicono: “Piuttosto che votare in modo equilibrato tra i nostri concorrenti, organizzeremo per amplificare i peggiori sconfitti il più possibile!”.

Per fare ciò, gli elettori del gruppo V sono divisi in Tre sottogruppi (d’altra parte, hanno ancora solo un candidato):

  • sottogruppo $ v_1 $ account 18% di tutti gli elettori e voto “v > z > y > x > w “;
  • il sottogruppo $ V_2 $ ha il 12% degli elettori e vota “V > Y > X > z > w “;
  • il sottogruppo $ v_3 $ account 10% elettori e voto” v > x > z > y > w “.

>

Con questa strategia, abbiamo i seguenti voti:

  • x y > z > w > V per il 20% degli elettori;
  • v > x > y > z > w per il 18% degli elettori;
  • y > z > x > w > v per il 16% degli elettori;
  • w > z > x > y > v per 13% degli elettori;
  • v > z > x > Y > w per il 12% degli elettori;
  • z > w > y > x > v per l’11% degli elettori;
  • v > y > z > x > w per il 10% degli elettori.

Questo porta al seguente diagramma di preferenza binario (a destra):

La manipolazione degli anarchici

Qui ci sono i diagrammi corrispondenti all’esempio della scacchiera con anarchici, a sinistra nel caso in cui gli anarchici votano sinceramente (assumiamo che le preferenze degli anarchici tra X, Y e Z sono casuali E w è ancora il loro candidato odiato), e proprio con la manipolazione abbiamo spiegato (le modifiche sono indicate in rosso). Nel primo caso, il vincitore del minico è lì; Nel secondo, è V, a chi sono ancora tutti gli altri candidati!

Quindi, le peggiori sconfitte di X, Y e Z sono rispettivamente del 62%, 63% e 64% (rispettivamente contro Z, X e Y), la peggiore sconfitta di W è dell’87% (contro Z) e la peggiore sconfitta del V è del 60% (contro uno qualsiasi dei suoi avversari): è quindi V chi diventa il vincitore del minimax ! “Ovviamente, i sostenitori di x, y, z e w hanno quindi l’opportunità di allearsi per designare Y come un candidato comune e fallire il piano di V, ma abbiamo detto alcuni paragrafi più in alto della filosofia del criterio di Condorcet doveva Risparmia il più possibile per gli elettori i tormenti del voto strategico! Sembra quindi, secondo questo punto di vista, che il metodo di minimax non è rilevante quando non vi è alcun vincitore del condominio.

il metodo Schulze

Ora stiamo andando ora presente ora un metodo Concepito nel 1997 da uno studente di fisica tedesco denominato Markus Schulze, che non ha la disabilità con il metodo Minix. La filosofia dietro al metodo Schulze è la seguente: “In fondo, un’elezione, non è mai un trucco per evitare l’inconveniente delle rivoluzioni: consultiamo i costituenti per sapere chi alla fine avrebbe vinto la rivoluzione senza dover battere!”.

Che cosa sarà chiamato “rivoluzione” qui, è quando un gran numero di elettori concordano di abbattere il presidente e sostituirlo con un altro, sulla cui identità hanno concordato prima. In questo senso, è facile capire il criterio di Condorcet: se un candidato (call-it) è il vincitore di condominio, qualsiasi altro candidato che accadrebbe al potere sarebbe rapidamente invertito dalla maggioranza che preferisce X a questo candidato, mentre una volta x sarà al potere non ci sarà mai la maggioranza per rovesciarlo, che farà il suo posto molto più stabile.
Alla fine, dal momento che abbiamo rapidamente transizioni da n ‘importazioni che a X e raramente X transizioni a chiunque, è X che sarà al potere la maggior parte del tempo. (Nota che qui non affermiamo che è impossibile rovesciare un presidente senza avere una maggioranza ligagata contro di lui: diciamo solo che questo è molto più facile farlo non appena abbiamo qualche persona in più per guidare la rivoluzione) .

Diamo un’occhiata a cosa succederebbe in un telaio del genere per l’esempio della scacchiera con anarchici. Le rivoluzioni tendono a rovesciare i presidenti nella direzione indicata dalle frecce e molto più raramente nella direzione opposta. Pertanto, alla fine di alcune rivoluzioni, il presidente è necessariamente x, y o z, da una volta arrivati in uno di questi tre non c’è modo lungo le frecce che portano in W o V! Quindi vediamo già (come sembrava naturale per noi) che non è V che le rivoluzioni porteranno al potere la maggior parte del tempo.

Continuiamo. Sappiamo che sarà essenzialmente x, y e z che condividerà il potere, ma in quali proporzioni? Se guardiamo alle frecce su questi tre candidati, abbiamo il diagramma sinistro qui sotto:

il metodo Schulze contro la manipolazione degli anarchici

Questi diagrammi spiegano cosa succede quando il metodo Schulze viene applicato alla situazione in cui gli anarchici stanno cercando di gestire la manipolazione. Il gruppo capo del diagramma delle preferenze binarie in questa situazione è quindi costituito dai tre candidati {x, y, z}: in particolare V viene eliminato da quando è stato picchiato da tutti gli altri candidati! In un secondo passo, guardiamo il diagramma delle preferenze binarie tra questi tre candidati. Per visualizzare un colpo di testa più piccolo, cancelliamo la freccia più debole. Il nuovo diagramma ha quindi un colpo di testa costituito dall’unico candidato X: quindi è colui che è dichiarato vincitore dal metodo.

Ora l’idea è così simile, era così Molto più difficile fare una rivoluzione con meno del 50% delle persone di oltre il 50%, è molto più difficile fare una rivoluzione con il 62% rispetto al 63% o al 64%.Quindi, cancelliamo la freccia contrassegnata “62%” per significare che questa rivoluzione è rara e arriviamo al diagramma destro sopra. Alla fine di alcune rivoluzioni, è necessariamente X che è il presidente: l’idea del metodo Schulze è dire che è colui che deve essere proclamato vincitore delle elezioni!

Ora che abbiamo spiegato il principio del metodo Schulze, finiremo per dare una definizione rigorosa e accertiamo in modo che dia un vincitore unico in tutti i casi. Supponiamo semplicemente che non ci siano mai due candidati esattamente legati o due frecce che hanno esattamente la stessa forza nel diagramma delle preferenze binarie, che è sempre il caso in pratica quando ci sono molti elettori.

Nota che in questo Paragrafo, a volte incontreremo diagrammi di preferenza binaria incompleta, cioè, dove alcuni candidati non sono collegati dalle frecce.

definizione (gruppo di testa)

in un diagramma di preferenze binarie (possibilmente incomplete), Si dice che un candidato (chiamato qui x) appartiene al gruppo leader quando, a partire da qualsiasi altro candidato, è possibile seguire un percorso in base alle frecce che inizia da questo candidato e termina in x.

Qui è importante notare che se il diagramma è completo, il fulcro non è mai vuoto:

teorema

In un diagramma di preferenza binario completo, il colpo di testa non è mai vuoto.

dimostrazione

presenteremo un modo per costruire il gruppo della testa che mostra che questo non è mai vuoto. Chiamerò qui “Headgree” qualsiasi gruppo di candidati come, quando partiamo da qualsiasi candidato che non è in questo gruppo, possiamo raggiungere qualsiasi candidato del gruppo seguendo le frecce.

I Prima osserva il gruppo di tutti i candidati è una one-erba di testa, poiché non c’è candidato che non appartiene a questo gruppo!

Ora, dico quanto segue: Quando hai un alto invaso,

  • o questo aggiornamento è il gruppo reale di testa;
  • o, tra questo aggiornamento, possiamo selezionare un determinato numero zero di candidati che formano un gruppo eccessivo rigorosamente più piccolo.

In effetti, supponiamo che il nostro supergroup non sia il vero gruppo di testa. L’unico modo in cui ciò accade è che ci sia almeno un candidato x in questo followgroup a cui non è possibile avere successo da un altro candidato y, che è necessariamente nell’overgroup, dal momento che sappiamo che possiamo portare a qualsiasi candidato dell’aggiornamento da qualsiasi candidato al di fuori del foodgroup. Ora, seleziono i candidati dell’aggiornamento che sono tali che, quando iniziamo da uno di questi candidati, non possiamo arrivare a X. Questo nuovo gruppo non è vuoto poiché contiene lì, ed è strettamente più piccolo del colpo di testa iniziale Dal momento che non contiene X. Dico che questo nuovo gruppo è ancora una nonna di testa. In effetti, considera un candidato Z che non è in questo nuovo gruppo. O questo candidato non era nel nostro aggiornamento iniziale, e quindi sappiamo che possiamo passare dalla Z in qualsiasi punto del nostro primo piano superiore e quindi soprattutto in qualsiasi punto del nostro nuovo gruppo. O questo candidato era nel nostro aggiornamento iniziale ma non nel nuovo gruppo. Quindi, la Z candidata, possiamo tornare al candidato x seguendo le frecce (per definizione del nuovo gruppo). Ma candidato x, possiamo andare a qualsiasi candidato w del nuovo gruppo: anzi, c’è una freccia tra x e w perché il nostro diagramma è completo, e necessariamente punta a x a w poiché non c’è modo da w a x ! Alla fine, abbiamo dimostrato che per qualsiasi candidato Z che non è nel nostro nuovo gruppo, possiamo andare da questo candidato a qualsiasi candidato del nuovo gruppo seguendo le frecce, il che significa che il nuovo gruppo è un aggiornamento.

Andiamo sul toproup della testa formata da tutti i candidati, e purché non abbiamo ancora trovato il vero gruppo di testa, applicare il metodo sopra riportato per formare overgroup di piombo più e più piccoli, ma tutti non vuoti. Necessariamente alla volta dovremo fermarsi, e in quel momento il nostro aggiornamento sarà il vero colpo di testa secondo l’alternativa sopra, e questo gruppo di testa sarà ben vuoto, il che dimostra il teorema.

Definizione (metodo Schulze)

Da un diagramma di preferenza binario completo (in cui tutte le frecce trasportano punteggi diversi), definiamo il vincitore di Schulze dal seguente metodo:

  1. Iniziamo dal diagramma delle preferenze binarie per tutti i candidati.
  2. Se c’è infatti solo un candidato, l’unico -CI è proclamato vincitore e stop.
  3. Altrimenti, guardiamo il gruppo di testa: se rigorosamente più piccolo del set iniziale, cancelliamo tutti i candidati che non sono in questo gruppo di testa (così come le frecce che li riguardano) e il metodo viene riavviato di nuovo come se Non c’erano più candidati rimanenti.
  4. Se, d’altra parte, il gruppo della testa contiene tutti i candidati, le frecce di punteggi più piccoli vengono gradualmente cancellate fino a quando il leader del diagramma ottenuto cancellando le frecce escluse almeno uno di i candidati (che succede necessariamente, perché una volta tutto Le frecce sarebbero state cancellate che non ci sarebbe nessuno nel gruppo della testa). A quel tempo, cancelliamo tutti i candidati che non sono in questo nuovo capo gruppo (così come le frecce che li riguardano), e il metodo è ricominciato da come se ci fossero più dei restanti candidati.

Per garantire che il metodo porta alla designazione di un vincitore, rimane da verificare che durante la procedura di cancellazione delle frecce, non è probabile che non rientri su un gruppo di testa vuoto:

teorema

Se si dispone di un diagramma di preferenza binario per diversi candidati (possibilmente incompleti) in cui il gruppo della testa contiene tutti i candidati, quindi cancella una delle frecce non può portare a una situazione in cui il nuovo gruppo di testa sarebbe vuoto . Pertanto, quando si parte da un diagramma di preferenze binarie in cui il gruppo di testa contiene tutti i candidati e che si cancella le sue frecce uno per uno, il primo momento in cui il gruppo della testa cessa di contenere tutti i candidati dona una testa non vuota Gruppo.

dimostrazione

Dimostriamo solo l’inizio della dichiarazione, la parte seguente “di conseguenza” risultante immediatamente. Andiamo da un diagramma di preferenza binario in cui il colpo di testa contiene tutti i candidati e cancellano una freccia, che chiamiamo x il candidato che se ne andò. Mostreremo che X è necessariamente nel nuovo gruppo capo, che sarà quindi non vuoto. Per fare questo, considera qualsiasi candidato y e mostrare che possiamo andare da y a x seguendo le frecce nonostante la cancellazione fatta. Come, prima della cancellazione della freccia, il gruppo della testa conteneva tutti i candidati, poi abbiamo avuto un sentiero che è passato da Y a X. Ma inevitabilmente questo percorso non ha preso in prestito la freccia cancellata, poiché questa freccia inizia da x allora che nel nostro way x è il punto di arrivo! È quindi che il percorso possa essere sempre seguito una volta che la freccia viene cancellata, cosa volevamo.

Abbiamo detto che l’interesse del metodo Schulze era di evitare manipolazioni come quella degli anarchici nell’esempio della scacchiera. Si può effettivamente dimostrare che tale manipolazione è impossibile con questo metodo:

teorema (robustezza alla manipolazione)

Supponiamo che ci siano due tipi di candidati: i candidati “irragionevoli” e i candidati “ragionevoli” (noi Supponiamo che ci sia almeno un candidato ragionevole) e chiamare “elettore ragionevole” un elettore che classifica tutti i candidati irragionevoli alla fine del suo ordine di preferenze. Quindi se c’è una maggioranza assoluta di elettori ragionevoli e questi elettori votano sinceramente, nessun candidato irragionevole può vincere con il metodo Schulze.

Dalla definizione del metodo Schulze, dimostra semplicemente che nessun candidato irragionevole appartiene al gruppo della testa in una situazione del genere. Tuttavia, quando iniziamo da un candidato ragionevole e dalla freccia del diagramma delle preferenze binarie, portiamo inevitabilmente a un altro candidato ragionevole: in effetti, la maggior parte dei ragionevoli elettori garantisce che nessuna freccia possa sottolineare un candidato ragionevole a un candidato irragionevole. Pertanto, è impossibile avere un percorso che lascia un candidato ragionevole e conduce a un candidato irragionevole, cosa volevamo.

conclusione

The Condomret Criterio per un metodo elettorale democratico, che afferma che un candidato preferito in qualsiasi altro faccia a faccia deve essere sempre eletto, consente una certa misura per evitare i problemi del voto strategico.Quando non c’è il vincitore di Condomret, possiamo immaginare diversi metodi “Condorcet”: tra questi, il metodo Schulze ha il vantaggio di avere sia una semplice giustificazione euristica e di essere più robusta ad alcune forme di manipolazione solo, ad esempio, il minimox metodo. Questo è attualmente uno dei metodi di voto più popolari dei teorici della democrazia, ed è usato per esempio da Debian GRATUITO Sistema operativo Sviluppatori – Geeks ancora in prima linea del progresso bizzarro …; -)

in a Articolo futuro, presenteremo altri metodi originali, non soddisfiamo necessariamente il criterio di Condorcet, ma che sono stati anche sostenuti da teorici per le loro proprietà matematiche.

Riferimenti

  • in Black Track: The Wikipedia Pagine “Metodo CondoRcet”, “Condomret Paradox” e “Metodo Schulze” (questa ultima pagina è piuttosto in pista rossa).
  • sui teoremi dell’elettore mediano: fondamentali della scelta sociale Teoria, di Roger B. Myerson (1996); Testo gratuito disponibile su Internet (off-piste).
  • wiki.electororma.com: un wiki.electororma.com: un wiki che ha i diversi metodi di condorcetta e le loro rispettive proprietà (off-piste).

Igienico

Leave a comment

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *