# Théorie du choix social

Plusieurs résultats d'économistes résonnent en math et en informatique par les aspects algorithmiques qui sous-tendent ces résultats.

* 1950 [Théorème d'impossibilité d'Arrow](https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem)
* 1950 [stratégies dans des jeux et équilibre de Nash](https://en.wikipedia.org/wiki/Nash_equilibrium)
* 1962 [algorithme de Gale et Shapley pour calculer un mariage stable](https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm)

Vous avez évoqué le dernier résultat sur le calcul d'un mariage stable avec Luc Pelissier, algorithme qui est essentiellement simulé par Parcoursup.

Nous allons expliquer dans ce cours le premier théorème.

## introduction.

Derrière le mot "voter" se cache un corpus vaste.

En tant que juriste vous avez probablement une sensibilité naturelle à la question, et vous n'êtes pas sans savoir que même si c'est un [droit fondamental en France](https://www.elections.interieur.gouv.fr/comprendre-elections/pourquoi-je-vote/limportance-du-droit-de-vote), les problèmes de représentativité réel ou perçus peuvent [détourner les électeurs des urnes](https://fr.wikipedia.org/wiki/Abstention_%C3%A9lectorale_en_France).

On peut s'intéresser à l'usage et au fonctionnement de [machines electroniques](https://en.wikipedia.org/wiki/Voting_machine) voir de machines mécaniques, y compris avec un élément de hasard [déjà en usage en Grèce antique](https://en.wikipedia.org/wiki/Kleroterion). Ces machines influencent d'ailleurs le langage comme dans l'expression anglaise [blackballing](https://en.wikipedia.org/wiki/Blackballing).

De manière générale la [fraude](https://en.wikipedia.org/wiki/Electoral_fraud) présente dans un système classique sur papier, est encore possible voir encore plus prévalente dans un système de vote dématérialisé. L'acceptabilité du résultat de l'élection est également influencé par la capacité de vérifier le résultat facilement. Une procédure claire standardisée [comme employée en France](https://mobile.interieur.gouv.fr/Archives/Archives-elections/Comment-voter/Fonctionnement-d-un-bureau-de-vote) offre de nombreux avantages. Le taux d'erreur d'une telle procédure manuelle n'est pas forcément plus mauvais d'ailleurs qu'un recomptage automatisé, même si dans le second cas une fraude est peut-être plus simple à organiser.

Il existe tout de même des procotoles permettant aux électeurs de vérifier la présence de leur bulletin tout en préservant une certaine anonymité.
* [reçus et résistance aux manipulations](https://en.wikipedia.org/wiki/End-to-end_auditable_voting_systems)
Ce genre de méthode est proposé par exemple dans un service gratuit de l'INRIA.
* [électronique et en ligne](https://www.belenios.org/howitworks.html)

Dans ce cours, je souhaite faire un pas de côté et me concentrer sur l'aspect purement mathématique de la méthode utilisée pour désigner un choix collectif à partir des choix individuels des citoyens.

En effet, on peut considérer des systèmes de vote et les comparer en s'intéressant à ces systèmes en tant qu'objet d'étude mathématique. On peut proposer divers propriétés souhaitables d'un système de vote pour le bon fonctionnement d'une démocratie et indiquer pour chaque système de vote s'il satisfait ou non une propriété souhaitable.

Cette approche remonte aux alentours de la révolution française, quand des mathématiciens comme Condorcet et Borda ont montré les défauts du système de vote majoritaire et proposé des méthodes concurrentes pour y remédier.

On verra en particulier le [théorème dû à Arrow](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_d%27impossibilit%C3%A9_d%27Arrow) publié en 1950 qui value à Arrow de recevoir le prix Nobel d'économie en 1972. Ce résultat appartient à un champs d'étude pluridisciplinaire, la [théorie du choix social](https://fr.wikipedia.org/wiki/Th%C3%A9orie_du_choix_social).
On discutera si le temps le permet des variantes de ce théorème.


## Flashback : Le paradoxe de Condorcet

Condorcet remarque qu'on peut parfois obtenir si on a 3 alternatives (A, B et C), et plusieurs choix "rationnels" et "transitifs" exprimés (les individus classent A, B et C strictement), un résultat qui n'est pas transitif si on utilise la majorité pour comparer 2 à 2 des éléments parmi A,B,C en terme de choix "consensuel global".

Exemple tiré de la page wikipedia du [paradoxe de Condorcet](https://fr.wikipedia.org/wiki/Paradoxe_de_Condorcet)

Considérons par exemple une assemblée de 60 votants ayant le choix entre trois propositions A, B et C. Les préférences se répartissent ainsi (en notant A > B, le fait que A est préféré à B) :

        23 votants préfèrent : A > B > C
        17 votants préfèrent : B > C > A
        2 votants préfèrent :  B > A > C
        10 votants préfèrent : C > A > B
        8 votants préfèrent :  C > B > A

Dans les comparaisons majoritaires par paires, on obtient :

        33 préfèrent A > B contre 27 pour B > A
        42 préfèrent B > C contre 18 pour C > B
        35 préfèrent C > A contre 25 pour A > C

Ce qui conduit à la contradiction interne A > B > C > A . 

Quand ce paradoxe ne se produit pas, Condorcet propose d'élire ce vainqueur.

## Théorème d'Arrow
Ce résultat vient confirmer l'intuition de Condorcet et démontrer que l'on ne peut pas dès qu'on a au moins 3 alternatives proposer de système de vote qui permette de garantir 3 propriétés simultanées pourtant en apparence fortement souhaitables.

Il s'agit donc d'un résultat d'**impossibilité**.

On part d'une collection de préférences des individus.
(En pratique beaucoup plus d'électeurs que d'alternatives).
Une **fonction de choix social** est une fonction d'agrégat qui à partir des préférences individuelles va construire une préférence collective.

Une seconde hypothèse de travail.
* universalité. La fonction de choix totale est toujours définie et n'utilise pas de hasard (elle est déterministe, si on recompte alors les résultat est le même).

Les propriétés.
* pas de dictateur.
* unanimité (optimum de Pareto) : si tout le monde a une préférence alors l'agrégat également.
* indépendances des options non pertinentes ;

Cette dernière propriété n'est pas spécialement la plus facile à expliquer.
Sa [page wikipedia anglaise](https://en.wikipedia.org/wiki/Independence_of_irrelevant_alternatives) présente une histoire humoristique qui donne une première intuition.

> Morgenbesser, ordering dessert, is told by a waitress that he can choose between blueberry or apple pie. He orders apple. Soon the waitress comes back and explains cherry pie is also an option. Morgenbesser replies "In that case, I'll have blueberry."


## Les propriétés plus formellement.

Il est utile de lire formellement les propriétés pour mieux comprendre leur signification.

Voir [ici](https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem#Formal_statement_of_the_theorem)

## Une preuve simplifiée
Voir [ici](https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem#Proof_by_the_pivotal_voter)

Cette preuve suppose un ordre strict pour les préférence.
Le théorème reste correct pour un ordre partiel.

## Dépasser le paradoxe d'Arrow

Certaines méthodes sont concernés par le théorème d'Arrow, mais sont plébiscités par certaines chercheurs, comme par exemple une méthode utilisée en Irlande et aux US :
* [instant runoff ou alternative vote](https://en.wikipedia.org/wiki/Instant-runoff_voting)
Cette méthode est relativement complexe pour compter les votes manuellement, mais permet d'indiquer des préférences nuancés et de se passer d'un second tour.


Plus généralement, on peut se pencher sur des méthodes qui tentent d'apporter un élément quantitatif pour préciser les préférences. On parle de vote par valeurs (cardinal voting ou rated voting en anglais).
Ceci est par opposition à la méthode de classement (ordinal voting en anglais).


Il existe divers méthodes proposées par des chercheurs en théorie du choix social comme par exemple :
* [Le jugement majoritaire](https://en.wikipedia.org/wiki/Majority_judgment)


* [Comparaison de différentes méthodes, en particulier en terme d'acceptabilité sociale](https://www.gate.cnrs.fr/vote/)

## Survol d'autres résultats du domaine.

L'article suivant présente d'autres résultats en les expliquant sans trop rentrer dans les détails mathématiques.
* [article cairn](https://www.cairn.info/revue-cahiers-d-economie-politique-1-2004-2-page-53.htm)

L'article suivant est beaucoup plus large que le précédent si vous souhaitez creuser le sujet.
* [Choix social dans l'encyclopédie de Stanford](https://plato.stanford.edu/entries/social-choice/)

Cet article récent donne une version quantitative du théorème d'Arrow.
* [arrow quantitatif](https://arxiv.org/pdf/0903.2574.pdf)


## Liens

* [Paradoxe de Condorcet](https://fr.wikipedia.org/wiki/Paradoxe_de_Condorcet)
* [Théorème d'Arrow (encyclopédie de philosophie de Stanford)](https://plato.stanford.edu/entries/arrows-theorem/)
* [Gibbard–Satterthwaite theorem](https://en.wikipedia.org/wiki/Gibbard%E2%80%93Satterthwaite_theorem))
* [Paradoxe de Sen](https://fr.wikipedia.org/wiki/Paradoxe_de_Sen)

* [Système de votes](https://fr.wikipedia.org/wiki/Syst%C3%A8me_%C3%A9lectoral)
* [Comme au Royaume-uni Majoritaire un tour (first pas the post)](https://fr.wikipedia.org/wiki/Scrutin_uninominal_majoritaire_%C3%A0_un_tour)
* [Comme la présidentielle française](https://fr.wikipedia.org/wiki/Scrutin_uninominal_majoritaire_%C3%A0_deux_tours)
* [Méthode de Borda](https://fr.wikipedia.org/wiki/M%C3%A9thode_Borda)
* [Méthode de Condorcet](https://fr.wikipedia.org/wiki/M%C3%A9thode_de_Condorcet)
* [instant runoff ou alternative vote](https://en.wikipedia.org/wiki/Instant-runoff_voting)
* [Vote par valeurs](https://en.wikipedia.org/wiki/Rated_voting)
* [Le jugement majoritaire](https://en.wikipedia.org/wiki/Majority_judgment)

* [Article vulgarisé inspiré élection 2017](https://www.lamsade.dauphine.fr/~lang/runoff.pdf)
* [Vote tactique pour le perdant d'une élection tripartite qui veut faire barrage](https://www.lamsade.dauphine.fr/~lang/grand-est.pdf)

* [Comparaison de différentes méthodes, en particulier en terme d'acceptabilité sociale](https://www.gate.cnrs.fr/vote/)

* [Gerrymandering](https://en.wikipedia.org/wiki/Gerrymandering)
* [blackballing](https://en.wikipedia.org/wiki/Blackballing)
