Optimisation sous contraintes appliquée au calcul du report des voix#

Recopié depuis Optimisation sous contraintes appliquée au calcul du report des voix.

Poser le problème#

Entre les deux tours des élections présidentielles, on parle beaucoup du report des voix des élections. Dans la plupart des articles que j’ai trouvés Les 1.139.316 voix qui ont fait la victoire d’Hollande ces intentions sont estimées par sondage. Un blog parle d’une méthode d’estimation après seulement que les élections ont eu lieu : Estimation des reports de voix - explications techniques. La méthode proposée est bayésienne. Ici, j’ai utilisé l’optmisation sous contraintes car c’est la méthode que je souhaitais illustrer pour mes enseignements. J’ai pris les élections comme exemples d’application. Les données sont accessibles sur le site (data.gouv.fr, élections 2012) Elles incluent les chiffres aggrégés par départements et cantons dont je me suis servi et que j’ai regroupés ici : french_elections.zip.

On dispose donc des voix ventilées par candidats et disponibles pour chaque départements. On cherche à calculer une matrice de report de voix qui soit la même pour tous les départements.
ARTHAUD Abstentions BAYROU Blancs et nuls CHEMINADE Code dep DUPONT-AIGNAN HOLLANDE JOLY LE PEN Département MÉLENCHON POUTOU SARKOZY total
1794 65996 32650 6453 860 1 7208 73096 7268 66540 AIN 30898 3323 97722 393808
2490 72928 19895 5196 738 2 5853 80751 3455 78452 AISNE 30360 3860 72090 376068
1482 45266 17814 5059 457 3 4068 61131 3232 37736 ALLIER 27969 2584 49477 256275
487 21034 7483 2111 283 4 1845 24551 2933 20875 ALPES DE HAUTE PROVENCE 15269 1394 25668 123933
1576 153383 38980 9063 1238 6 9241 111990 12556 136982 ALPES MARITIMES 49493 4048 216738 745288
Abstentions Blancs et nuls Code HOLLANDE Département SARKOZY total
67279 19513 1 131333 AIN 175741 393866
73997 21056 2 147260 AISNE 133760 376073
45079 14924 3 111615 ALLIER 84593 256211
20314 6639 4 49498 ALPES DE HAUTE PROVENCE 47444 123895
146254 30067 6 203117 ALPES MARITIMES 366055 745493

On cherche une matrice V qui permet d’obtenir les voix Y du second tour en fonction des voix du premier tour X : Y = VX, \; X \in M_{nc}, \; Y \in M_{nd}, \; V \in M_{cd}. n est le nombre de départements, c est le nombre de candidats du premier tour (abstention et bulletin nuls inclus), d est le nombre de candidats du second tour. La matrice V définit le report des voix : V<sub>ij</sub> est la proportion des voix du candidat c allant au candidat d. Elle vérifie les contraintes suivantes :

\begin{array}{l} \forall c,d, \; V_{cd} \leqslant 0 \\ \forall c, \; \sum_{d=1}^{D} V_{cd} = 1 \end{array}

Une résolution#

Le problème n’est pas très éloigné d’une régression avec des contraintes sur les coefficients excepté que la matrice Y a plus d’une colonne. Pour contourner l’obstacle, on construit une autre matrice Y^* d’une seule colonne et quatre fois plus de lignes (D=4). On applique une transformation similaire sur X.

\begin{array}{l} Y^*_{k} = Y_{k \mod(n),[k/n]} \\ X^*_{k,i} = X_{k \mod(n),i} \end{array}

Par la suite, on désigne sous X,Y les matrices X^*, Y^*. On cherche à résoudre le problème d’optmisation sous contrainte :

\begin{array}{l} \min_V (Y-XV)'(Y-XV) \\ avec \; \left \{ \begin{array}{l} \forall c,d \; V_{cd} \geqslant 0 \\ \forall c \; \sum_{d=1}^{D} V_{cd} = 1 \end{array} \right . \end{array}

C’est un problème d”optimisation convexe sous contraintes linéaires qu’on peut résoudre avec le module cvxopt. La fonction qp est la plus adaptée. Elle résoud le problème présenté sous la forme :

\begin{array}{l} \min_x \frac{1}{2} x'Px + q'x \\ avec \; \left \{ \begin{array}{l} Gx \leqslant h \\ Ax = b \end{array} \right . \end{array}

Il suffit d’associer les lettres de ce problème P,q,G,h,A,b à nos données :

  • x,P,q dépendent de X,Y,V,

  • G = -<b>1</b>, vecteur composé de -1,

  • h=0,

  • A experiment le fait que les coefficients de V somment à 1 sur la même ligne,

  • b=<b>1</b>.

Les matrices P,Q sont construites en développant l’erreur de régression. Le vecteur x est une représentation de la matrice V cherchée.

\left\|(Y-XV)'(Y-XV)\right\| = \sum_{i=1}^D Y_i'Y_i \underbrace{- 2 \sum_{i=1}^D Y_i' X_i}_{p'} x + x' \underbrace{\sum_{i=1}^D X_i' X_i}_{\frac{1}{2}Q} x

Je passe les détails d’implémentation que vous pouvez trouver là : class ElectionResults, def vote_transfer et study_french_elections.py. Cette classe lit les fichiers Excel venant du site open.data.gouv.fr, puis construit les matrices P,q,G,h,A,b qui permettent de résoudre le problème d’optimisation. Elle corrige aussi les nombres d’inscrits pour chaque département. car le nombre d’inscrits est légèrement différents d’une tour à l’autre (voir les deux premiers tableaux). Avec une règle de trois, on s’assure que le nombre d’inscrits est identique aux deux tours.

*optimisation dynamique sous contrainte (aggrégation par départements) en 2012*
Abstentions Blancs et nuls HOLLANDE SARKOZY
ARTHAUD 30% 70%
Abstentions 100%
BAYROU 31% 18% 51%
Blancs et nuls 32% 68%
CHEMINADE 100%
DUPONT-AIGNAN 45% 55%
HOLLANDE 100%
JOLY 100%
LE PEN 33% 6% 61%
MELENCHON 100%
POUTOU 100%
SARKOZY 6% 94%

Quelques précautions#

Il est difficile d’interpréter ces résultats sans prendre quelques précautions. La fonction d’erreur donne le même poids à toutes les voix. Cela signifie que la précision de ces chiffres est meilleure pour les partis les plus représentés. Ci-dessous, les mêmes résultats mais en partant des résultats aggrégés par cantons (environ 4000).

*optimisation dynamique sous contrainte (aggrégation par cantons) en 2012*
Abstentions Blancs et nuls HOLLANDE SARKOZY
ARTHAUD 98% 2%
Abstentions 100%
BAYROU 46% 6% 48%
Blancs et nuls 46% 54%
CHEMINADE 100%
DUPONT-AIGNAN 28% 37% 35%
HOLLANDE 100%
JOLY 100%
LE PEN 17% 5% 8% 70%
MELENCHON 100%
POUTOU 100%
SARKOZY 9% 91%

Ces résultats sont assez fluctuants. Le bootstrap est une méthode statistique qui permet d’obtenir des intervalles de confiance. J’ai appliqué la méthode sur la série des cantons, plus longue, car elle réduit la variance du nombre d’inscrits après rééchantillonage. On retrouve le fait que la marge d’erreur est grande pour les candidats ayant obtenu peu de voix.

*intervalles de confiance à 20% (aggrégation par cantons) en 2012*
Abstentions Blancs et nuls HOLLANDE SARKOZY
ARTHAUD 0%-100% 0%-100%
Abstentions 100%
BAYROU 0%- 81% 0%- 33% 19%- 79%
Blancs et nuls 0%-100% 0%-100%
CHEMINADE 100%
DUPONT-AIGNAN 0%-100% 0%- 64% 0%- 96%
HOLLANDE 0%- 7% 93%-100%
JOLY 100%
LE PEN 0%- 31% 3%- 6% 2%- 14% 61%- 82%
MELENCHON 0%- 2% 98%-100%
POUTOU 100%
SARKOZY 0%- 24% 76%-100%

Petits candidats#

Pour réduire la fourchette de confiance pour les petits candidats, on peut s’inspirer d’un test statistique comme le test du chi-deux. On donne à chaque voix d’un candidat un poids inversement proportionnel à son nombre de votants. Pour ce faire, j’ai divisé chaque colonne par le nombre d’inscrits comptabilisés dans cette colonne (voir la matrice des inscrits du premier tour) puis j’ai normalisé chaque ligne de la matrice du second tour de façon à ce qu’il y ait le même nombre de voix aux premier et second tour dans chaque canton. J’ai ensuite calculé la matrice de transfert des votes.

*transferts de votes, chaque vote est divisé
par le nombre de voix obtenues par le candidat (aggrégation par cantons) en 2012*
Abstentions Blancs et nuls HOLLANDE SARKOZY
ARTHAUD 56% 7% 37%
Abstentions 100%
BAYROU 100%
Blancs et nuls 34% 36% 30%
CHEMINADE 100%
DUPONT-AIGNAN 14% 2% 20% 65%
HOLLANDE 100%
JOLY 69% 31%
LE PEN 100%
MELENCHON 100%
POUTOU 100%
SARKOZY 100%

Et on vérifie que les intervalles de confiance sont plus petits pour les derniers candidats.

*intervalles de confiance des transferts de votes,
chaque vote est divisé par le nombre de voix obtenues par le candidat (aggrégation par cantons) en 2012*
Abstentions Blancs et nuls HOLLANDE SARKOZY
ARTHAUD 45%- 69% 2%- 8% 27%- 48%
Abstentions 100%
BAYROU 0%- 11% 89%-100%
Blancs et nuls 18%- 59% 21%- 59% 5%- 40%
CHEMINADE 93%-100% 0%- 7%
DUPONT-AIGNAN 0%- 23% 0%- 5% 0%- 30% 54%-100%
HOLLANDE 100%
JOLY 49%- 92% 8%- 51%
LE PEN 0%- 3% 97%-100%
MELENCHON 100%
POUTOU 100%
SARKOZY 100%

2007#

Les mêmes résultats en 2007 laisse penser que les reports de voix étaient plus bruités :

*intervalles de confiance des transferts de votes,
chaque vote est divisé par le nombre de voix obtenues par le candidat (aggrégation par cantons) en 2007*
Abstentions Blancs et nuls ROYAL SARKOZY
Abstentions 84%-100% 0%- 16%
BAYROU 0%- 14% 39%- 87% 10%- 59%
BESANCENOT 100%
BOVET 3%- 44% 8%- 68% 4%- 67%
BUFFET 18%- 41% 33%- 71% 0%- 40%
Blancs et nuls 51%- 87% 5%- 45% 0%- 13%
LAGUILLER 61%- 91% 0%- 17% 0%- 38%
LE PEN 100%
NIHOUS 0%- 9% 0%- 6% 53%- 76% 16%- 41%
ROYAL 100%
SARKOZY 100%
SCHIVARDI 0%- 17% 0%- 4% 0%- 47% 40%- 98%
VOYNET 0%- 65% 32%-100%
de VILLIERS 0%- 13% 0%- 4% 0%- 25% 65%-100%

2002#

Les élections en 2002 montrent des résultats plutôt surprenants pour le candidats Chirac. L’hypothèse de proabilités de reports uniformes est probablement fausse dans ce cas même si ces résultats paraissent dans l’ensemble sensés. C’est comme ci les électeurs de Chirac du premier avaient considérés les élections comme gagnées et n’avaient pas cru utile de se déplacer au second tour.

*intervalles de confiance des transferts de votes,
chaque vote est divisé par le nombre de voix obtenues par le candidat (aggrégation par cantons) en 2002*
Abstentions Blancs et nuls CHIRAC LE PEN
Abstentions 100%
BAYROU 0%- 19% 81%-100%
BESANCENOT 100%
BOUTIN 6%- 65% 35%- 94%
Blancs et nuls 0%- 48% 52%-100%
CHEVENEMENT 100%
CHIRAC 100%
GLUCKSTEIN 0%- 25% 75%-100%
HUE 6%- 47% 49%- 81% 3%- 11%
JOSPIN 0%-100% 0%-100%
LAGUILLER 0%-100% 0%-100%
LE PEN 0%- 25% 0%- 19% 68%-100%
LEPAGE 100%
MADELIN 0%- 69% 31%-100%
MAMERE 0%- 72% 28%-100%
MEGRET 33%- 62% 38%- 67%
SAINT-JOSSE 5%- 12% 58%- 64% 27%- 33%
TAUBIRA 48%- 72% 28%- 52%