Navigation : << 01b-Lean-SocialChoice-Formal.ipynb | 04-Computational-Aggregation-SAT-Z3.ipynb >> | Index
Autres notebooks : 01-Arrow-Impossibility-Theorem.ipynb
Kernel : Python 3
Ce notebook compagnon du notebook 20 (Lean) fournit les implementations Python des concepts de choix social :
Le notebook 20 Lean contient les formalisations mathematiques, celui-ci les implementations pratiques.
Ancres savantes – Condorcet, Marquis de (1785), Essai sur l’application de l’analyse a la probabilite des decisions rendues a la pluralite des voix, Imprimerie Royale, Paris (paradoxe de Condorcet : les préférences individuelles transitives peuvent produire un cycle collectif, illustre ici par check_condorcet_cycle) ; Borda, J.-C. de (1781), Memoire sur les elections au scrutin, Histoire de l’Academie Royale des Sciences, Paris (compte de Borda, règle de vote ponderee implementee dans borda_rule) ; Black, D. (1948), On the Rationale of Group Decision-making, Journal of Political Economy 56(1):23-34 (theoreme de l’electeur median et préférences unimodales / single-peaked, condition de coherentise du vote) ; Sen, A.K. (1970), The Impossibility of a Paretian Liberal, Journal of Political Economy 78(1):152-157 (theoreme de Sen, exemple Lady Chatterley : liberte minimale et Pareto sont incompatibles) ; Downs, A. (1957), An Economic Theory of Political Action in a Democracy, Journal of Political Economy 65(2):135-150 (modèle de Downs : competition a deux partis convergeant vers l’electeur median, simulate_two_party_competition) ; Copeland, A.H. (1951), A ‘Reasonable’ Social Welfare Function, Seminar on Applications of Mathematics to the Social Sciences, University of Michigan, mimeographie (méthode de Copeland, implementee dans copeland_rule : score = victoires moins defaites en duels).
# Configuration
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import random
from collections import Counter, defaultdict
from itertools import permutations, combinations
print("Configuration OK : SocialChoice 03 - Methodes de Vote")Configuration OK : SocialChoice 03 - Methodes de VotePour structurer nos manipulations de préférences, nous definissons une classe Profile equivalente a la structure Lean du notebook SC-02 (Lean). Elle encapsule : - Les préférences individuelles (liste d’ordres stricts) - Des méthodes de requête : prefers(), majority_prefers() - Des critères d’agregation : is_pareto_unanimous(), social_ranking()
Nous allons maintenant tester la classe Profile avec un exemple concret : le profil cyclique de Condorcet. Ce test permettra de vérifier que les méthodes de requête (prefers, majority_prefers, is_pareto_unanimous) fonctionnent correctement avant de les utiliser pour détecter des cycles.
class Profile:
"""Represente un profil de preferences collectives.
Equivalent Python de la structure Lean Profile du notebook SC-02.
"""
def __init__(self, preferences, alternatives=None):
self.preferences = preferences
if alternatives is None:
self.alternatives = list(dict.fromkeys(
x for pref in preferences for x in pref
))
else:
self.alternatives = list(alternatives)
self.n_voters = len(preferences)
self.n_alternatives = len(self.alternatives)
def prefers(self, voter, x, y):
"""Le votant i prefere-t-il x a y ?"""
return self.preferences[voter].index(x) < self.preferences[voter].index(y)
def majority_prefers(self, x, y):
"""Majorite des votants prefere-t-elle x a y ?"""
x_count = sum(1 for i in range(self.n_voters) if self.prefers(i, x, y))
return x_count > self.n_voters / 2
def is_pareto_unanimous(self, x, y):
"""Tous les votants preferent-ils x a y ? (critere de Pareto)"""
return all(self.prefers(i, x, y) for i in range(self.n_voters))
def social_ranking(self, rule):
"""Calcule le classement social selon une regle de vote donnee.
Args:
rule: fonction prenant un profil (list de listes) et
retournant un classement (list)
Returns:
list: classement social (meilleur en premier)
"""
return rule(self.preferences)
def __repr__(self):
lines = [f"Profile({self.n_voters} votants, "
f"{self.n_alternatives} alternatives)"]
for i, pref in enumerate(self.preferences):
lines.append(f" Votant {i}: {' > '.join(map(str, pref))}")
return '\n'.join(lines)
# Test avec le profil de Condorcet
prof = Profile([
['A', 'B', 'C'],
['B', 'C', 'A'],
['C', 'A', 'B'],
], alternatives=['A', 'B', 'C'])
print(prof)
print(f"\nPareto(A, B) ? {prof.is_pareto_unanimous('A', 'B')}")
print(f"Majorite(A, B) ? {prof.majority_prefers('A', 'B')}")
print(f"Majorite(A, C) ? {prof.majority_prefers('A', 'C')}")Profile(3 votants, 3 alternatives)
Votant 0: A > B > C
Votant 1: B > C > A
Votant 2: C > A > B
Pareto(A, B) ? False
Majorite(A, B) ? True
Majorite(A, C) ? FalseRésultat : Le profil de Condorcet est correctement créé et les méthodes fonctionnent.
| Méthode | Résultat | Interprétation |
|---|---|---|
is_pareto_unanimous('A', 'B') |
False | Les 3 votants ne préfèrent pas tous A à B (votant 1: A>B, votant 2: B>A, votant 3: A>B) |
majority_prefers('A', 'B') |
True | Majorité (2/3) préfère A à B |
majority_prefers('A', 'C') |
False | Majorité (2/3) préfère C à A |
Structure de données : La classe Profile encapsule : - 3 votants, 3 alternatives (A, B, C) - Méthodes de requête : prefers(i, x, y) pour les préférences individuelles - Méthodes d’agrégation : majority_prefers(x, y) pour la préférence collective
Note : Ce profil cyclique sera utilisé pour illustrer le paradoxe de Condorcet dans la section suivante.
Le paradoxe de Condorcet (1785) montre qu’avec le vote majoritaire pairwise, on peut obtenir des cycles dans les préférences collectives, même si chaque individu a des préférences transitives.
\[A > B > C > A\]
def pairwise_majority(profile, x, y):
"""Calcule le resultat du vote majoritaire entre x et y."""
x_wins = sum(1 for pref in profile if pref.index(x) < pref.index(y))
y_wins = len(profile) - x_wins
return x if x_wins > y_wins else (y if y_wins > x_wins else None)
def check_condorcet_cycle(profile, alternatives):
"""Verifie s'il y a un cycle de Condorcet."""
results = {}
for x, y in combinations(alternatives, 2):
winner = pairwise_majority(profile, x, y)
results[(x, y)] = winner
print(f" {x} vs {y}: {winner if winner else 'egalite'}")
return results
# Profil de Condorcet classique
condorcet_profile = [
['A', 'B', 'C'], # Individu 1: A > B > C
['B', 'C', 'A'], # Individu 2: B > C > A
['C', 'A', 'B'], # Individu 3: C > A > B
]
print("PROFIL DE CONDORCET (cycle)")
print("=" * 40)
for i, pref in enumerate(condorcet_profile):
print(f"Individu {i+1}: {' > '.join(pref)}")
print("\nResultats pairwise:")
check_condorcet_cycle(condorcet_profile, ['A', 'B', 'C'])
print("\n=> CYCLE: A bat B, B bat C, C bat A!")PROFIL DE CONDORCET (cycle)
========================================
Individu 1: A > B > C
Individu 2: B > C > A
Individu 3: C > A > B
Resultats pairwise:
A vs B: A
A vs C: C
B vs C: B
=> CYCLE: A bat B, B bat C, C bat A!Résultat des duels pairwise : - A vs B : A gagne (2 votants préfèrent A, 1 préfère B) - A vs C : C gagne (2 votants préfèrent C, 1 préfère A) - B vs C : B gagne (2 votants préfèrent B, 1 préfère C)
Cycle identifié : A > B > C > A (relation intransitive)
| Votant | Préférences | Vote A vs B | Vote A vs C | Vote B vs C |
|---|---|---|---|---|
| 1 | A > B > C | A | A | B |
| 2 | B > C > A | B | C | B |
| 3 | C > A > B | A | C | C |
| Résultat | A gagne | C gagne | B gagne |
Conclusion : Chaque individu a des préférences transitives, mais la préférence collective (majorité) est cyclique. C’est le paradoxe de Condorcet (1785).
La fonction condorcet_winner() generalise condorcet_winner_single_peaked() : elle fonctionne pour tout profil, pas seulement les préférences unimodales. Quand aucun gagnant n’existe (cycle), elle retourne None.
Le graphe oriente (tournoi) construit avec networkx montre clairement les relations de domination pairwise. Un cycle dans ce graphe = paradoxe de Condorcet.
def condorcet_winner(profile_or_list, alternatives=None):
"""Trouve le gagnant de Condorcet pour un profil quelconque.
Version generale : fonctionne pour tout profil, pas seulement
les preferences single-peaked. Retourne None si aucun gagnant
n'existe (cycle de Condorcet).
"""
if isinstance(profile_or_list, Profile):
alts = profile_or_list.alternatives
prefs = profile_or_list.preferences
else:
alts = alternatives or list(dict.fromkeys(
x for p in profile_or_list for x in p
))
prefs = profile_or_list
for candidate in alts:
beats_all = True
for other in alts:
if other != candidate:
winner = pairwise_majority(prefs, candidate, other)
if winner != candidate:
beats_all = False
break
if beats_all:
return candidate
return None
# Test sur differents profils
profile_with_winner = [
['A', 'B', 'C'],
['A', 'C', 'B'],
['B', 'A', 'C'],
['C', 'A', 'B'],
['A', 'B', 'C'],
]
print("GAGNANT DE CONDORCET (version generale)")
print("=" * 40)
print(f"Profil cyclique : {condorcet_winner(condorcet_profile, ['A', 'B', 'C'])}")
print(f"Profil avec gagnant : {condorcet_winner(profile_with_winner, ['A', 'B', 'C'])}")
# Visualisation du cycle avec networkx
G = nx.DiGraph()
G.add_nodes_from(['A', 'B', 'C'])
for x, y in combinations(['A', 'B', 'C'], 2):
winner = pairwise_majority(condorcet_profile, x, y)
if winner == x:
G.add_edge(x, y)
elif winner == y:
G.add_edge(y, x)
fig, ax = plt.subplots(figsize=(7, 5))
pos = nx.circular_layout(G)
nx.draw_networkx_nodes(G, pos, node_color='lightblue',
node_size=1500, ax=ax)
nx.draw_networkx_labels(G, pos, font_size=16,
font_weight='bold', ax=ax)
nx.draw_networkx_edges(G, pos, edge_color='steelblue', width=2,
connectionstyle='arc3,rad=0.15',
arrowsize=20, ax=ax)
ax.set_title("Cycle de Condorcet (graphe oriente)", fontsize=14)
ax.axis('off')
plt.tight_layout()
plt.show()
cycles = list(nx.simple_cycles(G))
print(f"Cycle detecte par networkx : {cycles}")GAGNANT DE CONDORCET (version generale)
========================================
Profil cyclique : None
Profil avec gagnant : A
Cycle detecte par networkx : [['C', 'A', 'B']]Différentes règles de vote peuvent donner des résultats différents pour le même profil.
def plurality_rule(profile):
"""Regle de la pluralite : l'alternative avec le plus de premiers choix gagne."""
first_choices = [p[0] for p in profile]
counts = Counter(first_choices)
alternatives = set(sum(profile, []))
return sorted(alternatives, key=lambda x: (-counts.get(x, 0), x))
def borda_rule(profile):
"""Regle de Borda : points selon le rang."""
scores = defaultdict(int)
n = len(profile[0])
for pref in profile:
for rank, alt in enumerate(pref):
scores[alt] += (n - 1 - rank) # n-1 points pour le 1er, 0 pour le dernier
return sorted(scores.keys(), key=lambda x: (-scores[x], x))
def copeland_rule(profile):
"""Regle de Copeland : score = victoires pairwise - defaites."""
alternatives = list(set(sum(profile, [])))
scores = {a: 0 for a in alternatives}
for x, y in combinations(alternatives, 2):
winner = pairwise_majority(profile, x, y)
if winner == x:
scores[x] += 1
scores[y] -= 1
elif winner == y:
scores[y] += 1
scores[x] -= 1
return sorted(alternatives, key=lambda x: (-scores[x], x))
# Test avec le profil de Condorcet
print("COMPARAISON DES REGLES DE VOTE")
print("=" * 40)
print(f"\nPluralite: {' > '.join(plurality_rule(condorcet_profile))}")
print(f"Borda: {' > '.join(borda_rule(condorcet_profile))}")
print(f"Copeland: {' > '.join(copeland_rule(condorcet_profile))}")
print("\n=> Avec un profil cyclique, les resultats peuvent varier!")COMPARAISON DES REGLES DE VOTE
========================================
Pluralite: A > B > C
Borda: A > B > C
Copeland: A > B > C
=> Avec un profil cyclique, les resultats peuvent varier!Résultat : Sur le profil de Condorcet (cycle A > B > C > A), les trois règles donnent le même classement (A > B > C). Le profil étant parfaitement symétrique, chaque règle aboutit à une égalité parfaite ; le classement affiché n’est que le départage déterministe par ordre alphabétique, pas une réelle préférence collective.
| Règle | Classement (sortie) | Scores | Note |
|---|---|---|---|
| Pluralité | A > B > C | 1, 1, 1 | Un seul premier choix pour chaque alternative → ex æquo, départagé alphabétiquement |
| Borda | A > B > C | 3, 3, 3 | Chaque alternative occupe une fois chaque rang → ex æquo, départagé alphabétiquement |
| Copeland | A > B > C | 0, 0, 0 | Cycle pairwise (A bat B, B bat C, C bat A) → chacun +1/-1 → ex æquo, départagé alphabétiquement |
Pourquoi des égalités partout ? La symétrie du cycle de Condorcet donne à chaque alternative exactement le même profil de rangs et de duels. Aucune règle ne peut donc départager sur le fond : le classement affiché ne reflète qu’un départage conventionnel (l’ordre alphabétique des alternatives à égalité), pas une réelle préférence collective.
Attention : Avec un profil non symétrique (comme le suivant), les égalités disparaissent et les règles divergent réellement.
Le cycle de Condorcet illustre le coeur du théorème d’Arrow : il n’existe pas de règle d’agrégation qui satisfasse simultanément tous les critères de rationalité collective. Ici, aucune des trois règles ne peut désigner un vainqueur légitime — elles aboutissent toutes à une égalité (voir le tableau ci-dessus) que seul un départage conventionnel (ici l’ordre alphabétique) tranche.
Note : Le choix de la règle de vote n’est pas neutre — sur des préférences divisées (profil suivant), il peut déterminer le vainqueur.
# Exemple ou les regles donnent des resultats differents
divergent_profile = [
['A', 'B', 'C'],
['A', 'B', 'C'],
['B', 'C', 'A'],
['C', 'B', 'A'],
['C', 'B', 'A'],
]
print("PROFIL AVEC RESULTATS DIVERGENTS")
print("=" * 40)
for i, pref in enumerate(divergent_profile):
print(f"Individu {i+1}: {' > '.join(pref)}")
print(f"\nPluralite: {' > '.join(plurality_rule(divergent_profile))}")
print(f"Borda: {' > '.join(borda_rule(divergent_profile))}")
print(f"Copeland: {' > '.join(copeland_rule(divergent_profile))}")
print("\n=> Meme profil, resultats differents selon la regle!")PROFIL AVEC RESULTATS DIVERGENTS
========================================
Individu 1: A > B > C
Individu 2: A > B > C
Individu 3: B > C > A
Individu 4: C > B > A
Individu 5: C > B > A
Pluralite: A > C > B
Borda: B > C > A
Copeland: B > C > A
=> Meme profil, resultats differents selon la regle!Résultat sur le profil divergent : Borda et Copeland donnent le même classement (B > C > A, gagnant B) ; seule la Pluralité s’en écarte (A > C > B, gagnant A). Le choix de la règle change donc le vainqueur.
| Règle | Classement (sortie) | Gagnant | Explication |
|---|---|---|---|
| Pluralité | A > C > B | A | Premiers choix : A et C à 2 voix chacun, B à 1 → ex æquo A/C départagé vers A (ordre alphabétique) |
| Borda | B > C > A | B | Points selon le rang (6, 5, 4) : B profite de positions intermédiaires solides |
| Copeland | B > C > A | B | Scores pairwise : B = +2 (bat A et C), C = 0 (bat A, perd contre B), A = -2 (perd contre les deux) |
Pourquoi cette divergence ? - Pluralité ne regarde que les premiers choix : A et C sont à égalité (2 voix), le départage alphabétique donne A, alors que B (1 voix) est éliminé bien qu’il soit le vainqueur des deux autres règles. - Borda tient compte de la position complète, donc B (souvent bien placé) gagne avec 6 points. - Copeland regarde les duels : B bat A et C, ce qui en fait le vainqueur « consensuel ».
Leçon politique : Le choix de la règle électorale n’est pas neutre. Dans les élections réelles, la règle de vote peut changer le vainqueur lorsque les préférences sont polarisées.
Le theoreme de Sen (1970) montre un conflit entre liberte individuelle et efficacite Pareto.
# Theoreme de Sen (1970) : implementation Python
# Conflit entre liberte individuelle et efficacite Pareto
# Trois alternatives avec noms significatifs
np_alt = "np" # Nobody reads (Personne ne lit)
pr_alt = "pr" # Prude reads (Prude lit)
lr_alt = "lr" # Lewd reads (Lewd lit)
# Preferences individuelles
prude_pref = [np_alt, pr_alt, lr_alt] # Prude : np > pr > lr
lewd_pref = [pr_alt, lr_alt, np_alt] # Lewd : pr > lr > np
sen_profile = Profile(
[prude_pref, lewd_pref],
alternatives=[np_alt, pr_alt, lr_alt]
)
print("L'EXEMPLE DE LADY CHATTERLEY (Theoreme de Sen)")
print("=" * 50)
print(f"\nAlternatives : {np_alt} = personne ne lit, "
f"{pr_alt} = Prude lit, {lr_alt} = Lewd lit")
print(f"\nPreferences Prude : {' > '.join(prude_pref)}")
print(f"Preferences Lewd : {' > '.join(lewd_pref)}")
# Principe de liberte minimale
print("\n--- Principe de liberte minimale ---")
print(f"Prude decide entre {pr_alt} et {np_alt} : "
f"prefere {np_alt} > {pr_alt}")
print(f" => Socialement : {np_alt} > {pr_alt}")
print(f"Lewd decide entre {lr_alt} et {np_alt} : "
f"prefere {lr_alt} > {np_alt}")
print(f" => Socialement : {lr_alt} > {np_alt}")
# Transitivite
print("\n--- Par transitivite ---")
print(f"{lr_alt} > {np_alt} et {np_alt} > {pr_alt}")
print(f"=> {lr_alt} > {pr_alt}")
# Pareto
print("\n--- Principe de Pareto (unanimite) ---")
print(f"Prude prefere {pr_alt} > {lr_alt} ? "
f"{sen_profile.prefers(0, pr_alt, lr_alt)}")
print(f"Lewd prefere {pr_alt} > {lr_alt} ? "
f"{sen_profile.prefers(1, pr_alt, lr_alt)}")
print(f"Pareto({pr_alt}, {lr_alt}) = "
f"{sen_profile.is_pareto_unanimous(pr_alt, lr_alt)}")
print(f"=> Socialement : {pr_alt} > {lr_alt}")
# Contradiction
print("\n*** CONTRADICTION ***")
print(f"Liberte + Transitivite => {lr_alt} > {pr_alt}")
print(f"Pareto => {pr_alt} > {lr_alt}")
print("=> Liberte et Pareto sont incompatibles!")L'EXEMPLE DE LADY CHATTERLEY (Theoreme de Sen)
==================================================
Alternatives : np = personne ne lit, pr = Prude lit, lr = Lewd lit
Preferences Prude : np > pr > lr
Preferences Lewd : pr > lr > np
--- Principe de liberte minimale ---
Prude decide entre pr et np : prefere np > pr
=> Socialement : np > pr
Lewd decide entre lr et np : prefere lr > np
=> Socialement : lr > np
--- Par transitivite ---
lr > np et np > pr
=> lr > pr
--- Principe de Pareto (unanimite) ---
Prude prefere pr > lr ? True
Lewd prefere pr > lr ? True
Pareto(pr, lr) = True
=> Socialement : pr > lr
*** CONTRADICTION ***
Liberte + Transitivite => lr > pr
Pareto => pr > lr
=> Liberte et Pareto sont incompatibles!Contradiction démontrée : Liberte + Transitivite → lr > pr, mais Pareto → pr > lr
| Principe | Application | Résultat |
|---|---|---|
| Liberte Prude | Prude decide entre pr et np | np > pr socialement |
| Liberte Lewd | Lewd decide entre lr et np | lr > np socialement |
| Transitivite | lr > np et np > pr | lr > pr |
| Pareto (unanimité) | Tous préfèrent pr > lr | pr > lr |
Conclusion : Les trois principipes (liberte minimale, transitivité, Pareto) sont logiquement incompatibles. Un système social doit sacrifier l’un d’eux.
Portée philosophique : Ce théorème (Sen, 1970) montre qu’il existe des situations où les droits individuels et l’efficacité collective sont en conflit logique, pas seulement en désaccord politique. C’est un résultat d’impossibilité, pas une simple tension.
L’exemple illustre une impossibilite fondamentale : on ne peut pas simultanement respecter : - La liberte individuelle minimale (chacun decide pour soi) - L’efficacite Pareto (si tous preferent A a B, la societe aussi)
Structure du conflit :
| Principe | Implication | Résultat |
|---|---|---|
| Liberte Prude | c > a | c > a |
| Liberte Lewd | b > c | b > c |
| Transitivite | b > c > a | b > a |
| Pareto | Tous preferent a a b | a > b |
Portee philosophique : Ce theoreme remet en question l’idee qu’on peut toujours reconcilier droits individuels et bien-etre collectif. Dans certaines situations, ces deux objectifs sont logiquement incompatibles.
# Visualisation du paradoxe de Sen
fig, ax = plt.subplots(figsize=(10, 6))
# Noeuds
positions = {'a': (0, 1), 'b': (2, 1), 'c': (1, 0)}
for label, (x, y) in positions.items():
circle = plt.Circle((x, y), 0.15, color='lightblue', ec='black', lw=2)
ax.add_patch(circle)
ax.text(x, y, label, ha='center', va='center', fontsize=16, fontweight='bold')
# Aretes avec etiquettes
# Liberte Prude : c > a
ax.annotate('', xy=(0.15, 0.85), xytext=(0.85, 0.15),
arrowprops=dict(arrowstyle='->', color='green', lw=2))
ax.text(0.3, 0.4, 'Liberte Prude:\nc > a', fontsize=10, color='green')
# Liberte Lewd : b > c
ax.annotate('', xy=(1.15, 0.15), xytext=(1.85, 0.85),
arrowprops=dict(arrowstyle='->', color='green', lw=2))
ax.text(1.5, 0.4, 'Liberte Lewd:\nb > c', fontsize=10, color='green')
# Pareto : a > b
ax.annotate('', xy=(1.85, 1), xytext=(0.15, 1),
arrowprops=dict(arrowstyle='->', color='red', lw=2))
ax.text(1, 1.15, 'Pareto: a > b', fontsize=10, color='red')
# Contradiction implicite : b > a par transitivite
ax.annotate('', xy=(0.15, 1), xytext=(1.85, 1),
arrowprops=dict(arrowstyle='->', color='orange', lw=2, ls='--'))
ax.text(1, 0.75, 'Transitivite: b > a', fontsize=10, color='orange', style='italic')
ax.set_xlim(-0.5, 2.5)
ax.set_ylim(-0.5, 1.7)
ax.set_aspect('equal')
ax.axis('off')
ax.set_title("Paradoxe de Sen : Liberte vs Pareto", fontsize=14)
plt.tight_layout()
plt.show()
print("Rouge = Pareto, Vert = Liberte, Orange = Contradiction")
Rouge = Pareto, Vert = Liberte, Orange = ContradictionLe theoreme d’Arrow (1951) prouve qu’aucune fonction de bien-etre social (avec >= 3 alternatives) ne peut satisfaire simultanement : - Universalite : la règle accepte tout profil de préférences - Unanimite (Pareto) : si tous preferent A a B, la societe aussi - IIA (Indépendance des Alternatives Irrelevantes) : le classement entre A et B ne depend que des préférences entre A et B - Non-dictature : aucun individu ne determine seul le classement
Nous verifions empiriquement les violations de IIA par les règles usuelles et cherchons des dictateurs potentiels avec detect_dictator().
# Simulation du Theoreme d'Arrow
# Detection empirique des violations de IIA et des dictateurs
def check_iia_violations(profile_list, rule, x, y, alternatives,
n_tests=100):
"""Teste les violations de IIA pour une regle et une paire.
Genere n_tests profils alternatifs ou les preferences
individuelles entre x et y sont identiques au profil original.
Compte combien de fois le classement relatif x/y change.
"""
prefs = (profile_list if isinstance(profile_list, list)
else profile_list.preferences)
ranking_ref = rule(prefs)
x_above_y_ref = ranking_ref.index(x) < ranking_ref.index(y)
violations = 0
for _ in range(n_tests):
alt_prefs = []
for pref in prefs:
x_before_y = pref.index(x) < pref.index(y)
new_pref = list(alternatives)
random.shuffle(new_pref)
px, py = new_pref.index(x), new_pref.index(y)
if x_before_y and px > py:
new_pref[px], new_pref[py] = new_pref[py], new_pref[px]
elif not x_before_y and px < py:
new_pref[px], new_pref[py] = new_pref[py], new_pref[px]
alt_prefs.append(new_pref)
ranking_alt = rule(alt_prefs)
x_above_y_alt = ranking_alt.index(x) < ranking_alt.index(y)
if x_above_y_ref != x_above_y_alt:
violations += 1
return violations
def detect_dictator(profile_list, rule, alternatives, n_tests=50):
"""Detecte si une regle de vote est dictatoriale.
Teste si un individu determine toujours le vainqueur social.
Retourne l'index du dictateur, ou None.
"""
prefs = (profile_list if isinstance(profile_list, list)
else profile_list.preferences)
n_voters = len(prefs)
for d in range(n_voters):
is_dict = True
for _ in range(n_tests):
test_prefs = []
for i in range(n_voters):
p = list(alternatives)
random.shuffle(p)
test_prefs.append(p)
ranking = rule(test_prefs)
if ranking[0] != test_prefs[d][0]:
is_dict = False
break
if is_dict:
return d
return None
# Test systematique des trois regles
random.seed(42)
test_profile = [
['A', 'B', 'C'],
['B', 'C', 'A'],
['C', 'A', 'B'],
['A', 'C', 'B'],
['B', 'A', 'C'],
]
test_alts = ['A', 'B', 'C']
print("SIMULATION DU THEOREME D'ARROW")
print("=" * 50)
print("Test Monte-Carlo : 100 profils alternatifs par regle\n")
for name, rule_func in [("Pluralite", plurality_rule),
("Borda", borda_rule),
("Copeland", copeland_rule)]:
v = check_iia_violations(test_profile, rule_func,
'A', 'B', test_alts)
d = detect_dictator(test_profile, rule_func, test_alts)
# Un compteur empirique ne fonde qu'une affirmation existentielle :
# v > 0 prouve que la regle VIOLE IIA (contre-exemple observe),
# mais v = 0 ne prouve pas qu'elle respecte IIA (absence de preuve
# != preuve d'absence ; voir le contre-exemple Copeland ci-dessous).
if v > 0:
status_iia = (f"VIOLE IIA ({v} contre-exemples sur 100 profils)")
else:
status_iia = ("aucune violation observee sur 100 profils "
"(n'etablit pas que la regle respecte IIA)")
status_dict = (f"dictateur = votant {d}"
if d is not None else "non-dictatoriale")
print(f"{name:12s} : {v:3d}/100 violations IIA | {status_dict}")
print(f"{'':12s} => {status_iia}")
print("\nConclusion : aucune regle usuelle ne satisfait tous les "
"criteres d'Arrow simultanement.")SIMULATION DU THEOREME D'ARROW
==================================================
Test Monte-Carlo : 100 profils alternatifs par regle
Pluralite : 12/100 violations IIA | non-dictatoriale
=> VIOLE IIA (12 contre-exemples sur 100 profils)
Borda : 3/100 violations IIA | non-dictatoriale
=> VIOLE IIA (3 contre-exemples sur 100 profils)
Copeland : 0/100 violations IIA | non-dictatoriale
=> aucune violation observee sur 100 profils (n'etablit pas que la regle respecte IIA)
Conclusion : aucune regle usuelle ne satisfait tous les criteres d'Arrow simultanement.Le 0/100 renvoye par le Monte-Carlo pour Copeland ne prouve pas qu’elle respecte IIA. C’est meme plus subtil qu’un simple manque de chance : avec 3 alternatives, Copeland ne peut jamais inverser le classement relatif de A et B (un profil ou A bat B en duel donne toujours A.score >= B.score), et le test ci-dessus ne compte que les inversions strictes. Le tirage est donc structurellement aveugle a la violation.
Or Copeland est une regle Condorcet-consistante, et le theoreme de Arrow etablit que toute regle Condorcet-consistante viole IIA des qu’il y a au moins 3 alternatives. La demonstration vaut mieux que le deni : exhibons un profil ou retirer des alternatives non-pertinentes inverse le classement Copeland de deux autres.
# Contre-exemple constructif : Copeland viole IIA
# --------------------------------------------------
# Profil symetrique cyclique (3 votants, 4 alternatives).
# Les preferences A-vs-B sont identiques dans le profil complet
# et dans le profil restreint a {A,B} (c'est l'invariant IIA).
copeland_iia_profile = [
['A', 'B', 'C', 'D'], # votant 1
['B', 'C', 'D', 'A'], # votant 2
['C', 'D', 'A', 'B'], # votant 3
]
# restriction aux alternatives A, B (C et D deviennent non-pertinentes)
restricted_profile = [[a for a in p if a in ('A', 'B')]
for p in copeland_iia_profile]
print("CONTRE-EXEMPLE : Copeland viole IIA")
print("=" * 54)
print("Profil complet (3 votants, 4 alternatives) :")
for i, v in enumerate(copeland_iia_profile, 1):
print(f" votant {i} : {' > '.join(v)}")
print(f"\nDuel pairwise A vs B : {pairwise_majority(copeland_iia_profile, 'A', 'B')} gagne "
f"(les votants preferent majoritairement A a B)")
print(" -> invariant IIA : A vs B est identique sur le profil restreint.")
ranking_full = copeland_rule(copeland_iia_profile)
ranking_ab = copeland_rule(restricted_profile)
print(f"\nCopeland complet {{A,B,C,D}} : {' > '.join(ranking_full)}")
print(f"Copeland restreint {{A,B}} : {' > '.join(ranking_ab)}")
print("\n=> Avec C et D, Copeland classe B au-dessus de A.")
print(" Sans C ni D (alternatives non-pertinentes), Copeland classe A au-dessus de B.")
print(" Le classement relatif de A et B s'est INVERSE : Copeland VIOLE IIA.")
print(" (Theoreme : toute regle Condorcet-consistante viole IIA.)")CONTRE-EXEMPLE : Copeland viole IIA
======================================================
Profil complet (3 votants, 4 alternatives) :
votant 1 : A > B > C > D
votant 2 : B > C > D > A
votant 3 : C > D > A > B
Duel pairwise A vs B : A gagne (les votants preferent majoritairement A a B)
-> invariant IIA : A vs B est identique sur le profil restreint.
Copeland complet {A,B,C,D} : B > C > A > D
Copeland restreint {A,B} : A > B
=> Avec C et D, Copeland classe B au-dessus de A.
Sans C ni D (alternatives non-pertinentes), Copeland classe A au-dessus de B.
Le classement relatif de A et B s'est INVERSE : Copeland VIOLE IIA.
(Theoreme : toute regle Condorcet-consistante viole IIA.)Resultats empiriques sur 100 profils alternatifs generes aleatoirement (preferences A-vs-B preservees) :
| Regle | Violations IIA observees | Dictateur | Lecture empirique |
|---|---|---|---|
| Pluralite | 12/100 | Non | viole IIA (contre-exemples observes) |
| Borda | 3/100 | Non | viole IIA (contre-exemples observes) |
| Copeland | 0/100 | Non | aucune violation observee (ne prouve pas qu’elle respecte IIA) |
Lecture honnete du compteur : un Monte-Carlo ne fonde qu’une affirmation existentielle. v > 0 prouve que la regle viole IIA (un contre-exemple suffit). En revanche, v = 0 ne prouve pas que la regle respecte IIA : c’est seulement l’absence de violation observeee sur l’echantillon tire – l’absence de preuve n’est pas la preuve d’absence.
Pourquoi Copeland affiche 0/100 ici : avec 3 alternatives, Copeland ne peut pas inverser strictement le classement de A et B (un profil ou A bat B en duel donne toujours A.score >= B.score), et le test ne compte que les inversions strictes. Le tirage est donc structurellement aveugle a la violation. Le contre-exemple ci-dessus (4 alternatives) le demontre : retirer C et D inverse le classement Copeland de A et B -> Copeland viole bien IIA, comme toute regle Condorcet-consistante.
Note theorique : Le theoreme d’Arrow prouve qu’aucune regle ne peut satisfaire simultanement les 4 criteres (Universalite, Pareto, IIA, Non-dictature) avec >=3 alternatives. Les trois regles usuelles violent IIA ; la simulation empirique le confirme pour Pluralite et Borda, et le contre-exemple le demontre pour Copeland.
Avec des préférences unimodales (single-peaked), le vote majoritaire fonctionne bien : l’alternative preferee de l’electeur median est le vainqueur de Condorcet.
def single_peaked_preference(peak, alternatives):
"""Genere une preference unimodale avec pic donne."""
return sorted(alternatives, key=lambda x: abs(x - peak))
def find_median_voter(peaks):
"""Trouve l'electeur median."""
sorted_peaks = sorted(peaks)
return sorted_peaks[len(peaks) // 2]
def condorcet_winner_single_peaked(profile, alternatives):
"""Trouve le gagnant de Condorcet pour preferences unimodales."""
for candidate in alternatives:
beats_all = True
for other in alternatives:
if other != candidate:
winner = pairwise_majority(profile, candidate, other)
if winner != candidate:
beats_all = False
break
if beats_all:
return candidate
return None
# Exemple : 7 electeurs avec preferences unimodales sur [0, 10]
alternatives = [0, 2, 4, 6, 8, 10]
voter_peaks = [1, 3, 4, 5, 7, 8, 9] # 7 electeurs
# Generer les preferences
profile_sp = [single_peaked_preference(peak, alternatives) for peak in voter_peaks]
print("THEOREME DE L'ELECTEUR MEDIAN")
print("=" * 40)
print(f"Alternatives : {alternatives}")
print(f"Pics des electeurs : {voter_peaks}")
print(f"\nPreferences generees :")
for i, (peak, pref) in enumerate(zip(voter_peaks, profile_sp)):
print(f" Electeur {i+1} (pic={peak}): {pref}")
median_peak = find_median_voter(voter_peaks)
print(f"\nElecteur median : pic a {median_peak}")
# L'alternative la plus proche du median
median_choice = min(alternatives, key=lambda x: abs(x - median_peak))
print(f"Choix de l'electeur median : {median_choice}")
# Verifier que c'est le gagnant de Condorcet
condorcet = condorcet_winner_single_peaked(profile_sp, alternatives)
print(f"Gagnant de Condorcet : {condorcet}")
print(f"\n=> Theoreme verifie : {median_choice == condorcet}")THEOREME DE L'ELECTEUR MEDIAN
========================================
Alternatives : [0, 2, 4, 6, 8, 10]
Pics des electeurs : [1, 3, 4, 5, 7, 8, 9]
Preferences generees :
Electeur 1 (pic=1): [0, 2, 4, 6, 8, 10]
Electeur 2 (pic=3): [2, 4, 0, 6, 8, 10]
Electeur 3 (pic=4): [4, 2, 6, 0, 8, 10]
Electeur 4 (pic=5): [4, 6, 2, 8, 0, 10]
Electeur 5 (pic=7): [6, 8, 4, 10, 2, 0]
Electeur 6 (pic=8): [8, 6, 10, 4, 2, 0]
Electeur 7 (pic=9): [8, 10, 6, 4, 2, 0]
Electeur median : pic a 5
Choix de l'electeur median : 4
Gagnant de Condorcet : 4
=> Theoreme verifie : TrueRésultat : L’alternative 4 est à la fois le choix de l’électeur median (pic=5, donc préfère 4) ET le gagnant de Condorcet.
| Méthode | Résultat | Conclusion |
|---|---|---|
| Electeur median (pic=5) | Alternative 4 | Préférence : 4 > 6 > 2 > 8 > 0 > 10 |
| Gagnant de Condorcet | Alternative 4 | Bat tous les autres en duels pairwise |
Pourquoi ça marche : - L’électeur 4 (pic=5) est le pivot : 3 électeurs ont un pic ≤4, 3 ont un pic ≥6 - L’alternative 4 bat toute alternative <4 (majorité des électeurs 4-7) - L’alternative 4 bat toute alternative >4 (majorité des électeurs 1-4)
Note théorique : Ce résultat (Black, 1948; Downs, 1957) est un cas particulier important où le vote majoritaire est cohérent et stable, contrairement au cas général de Condorcet.
Le theoreme de l’electeur median est verifie empiriquement : l’alternative 4 (la plus proche du pic median 5) est bien le gagnant de Condorcet.
Mécanisme : - Avec des préférences unimodales, chaque electeur ordonne les alternatives par distance croissante a son pic - L’electeur median (pic=5) divise l’electorat en deux moities - Toute alternative plus proche du median bat toute alternative plus eloignee par majorite
| Electeur | Pic | Premier choix |
|---|---|---|
| 1-3 | 1, 3, 4 | Alternatives basses (0, 2, 4) |
| 4 (median) | 5 | 4 |
| 5-7 | 7, 8, 9 | Alternatives hautes (6, 8) |
Consequence pratique : Lorsque les préférences sont unimodales (enjeu gauche-droite typique), le vote majoritaire est stable et evite le paradoxe de Condorcet.
# Visualisation du theoreme de l'electeur median
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
# Graphique 1 : Distribution des pics
ax1.hist(voter_peaks, bins=range(0, 12), align='left', color='steelblue', edgecolor='black', alpha=0.7)
ax1.axvline(median_peak, color='red', linestyle='--', linewidth=2, label=f'Median = {median_peak}')
ax1.set_xlabel('Position (gauche-droite)')
ax1.set_ylabel('Nombre d\'electeurs')
ax1.set_title('Distribution des pics (preferences unimodales)')
ax1.legend()
ax1.set_xticks(range(0, 11))
# Graphique 2 : Preferences unimodales
x_line = np.linspace(0, 10, 100)
for i, peak in enumerate(voter_peaks[:3]): # Montrer 3 electeurs
utility = -np.abs(x_line - peak) # Utilite = - distance au pic
ax2.plot(x_line, utility, label=f'Electeur (pic={peak})', alpha=0.7)
ax2.set_xlabel('Alternative (position)')
ax2.set_ylabel('Utilite')
ax2.set_title('Exemples de preferences unimodales')
ax2.legend()
ax2.axhline(0, color='gray', linestyle='-', linewidth=0.5)
plt.tight_layout()
plt.show()
print("Avec des preferences unimodales, pas de cycle de Condorcet!")
Avec des preferences unimodales, pas de cycle de Condorcet!Visualisation générée : Deux graphiques illustrant le théorème de l’électeur median.
Graphique 1 - Distribution des pics : Histogramme montrant la répartition des 7 électeurs sur l’axe politique [0, 10], avec une médiane à 5. La distribution montre une concentration d’électeurs autour du centre.
Graphique 2 - Profils d’utilité : Trois courbes en forme de “∩” (pic inversé) illustrant que chaque électeur maximise son utilité à son pic préféré, et que l’utilité décroît avec la distance à ce pic.
Intuition clé : La forme unimodale (un seul pic) garantit qu’il n’y a pas de cycle dans les préférences sociales, contrairement au cas de Condorcet où les préférences peuvent être circulaires.
Le theoreme de l’electeur median a des implications importantes pour la competition electorale.
# Simulation : convergence vers le centre (modele de Downs)
def simulate_two_party_competition(voter_peaks, n_rounds=20):
"""Simule la competition entre deux partis qui ajustent leur position."""
# Positions initiales des partis
party_L = 2 # Parti de gauche
party_R = 8 # Parti de droite
history_L = [party_L]
history_R = [party_R]
median = sorted(voter_peaks)[len(voter_peaks) // 2]
for _ in range(n_rounds):
# Chaque parti se rapproche du median pour gagner plus de votes
if party_L < median:
party_L = min(party_L + 0.3, median)
if party_R > median:
party_R = max(party_R - 0.3, median)
history_L.append(party_L)
history_R.append(party_R)
return history_L, history_R, median
# Electeurs distribues normalement
np.random.seed(42)
voter_peaks_normal = list(np.random.normal(5, 2, 100).clip(0, 10))
history_L, history_R, median = simulate_two_party_competition(voter_peaks_normal)
# Visualisation
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))
# Distribution des electeurs
ax1.hist(voter_peaks_normal, bins=20, color='lightgray', edgecolor='black', alpha=0.7)
ax1.axvline(median, color='green', linestyle='--', linewidth=2, label=f'Median = {median:.1f}')
ax1.axvline(history_L[0], color='blue', linewidth=2, label=f'Gauche init = {history_L[0]}')
ax1.axvline(history_R[0], color='red', linewidth=2, label=f'Droite init = {history_R[0]}')
ax1.axvline(history_L[-1], color='blue', linewidth=2, linestyle=':', label=f'Gauche final = {history_L[-1]:.1f}')
ax1.axvline(history_R[-1], color='red', linewidth=2, linestyle=':', label=f'Droite final = {history_R[-1]:.1f}')
ax1.set_xlabel('Position politique')
ax1.set_ylabel('Nombre d\'electeurs')
ax1.set_title('Distribution des electeurs et positions des partis')
ax1.legend(loc='upper right', fontsize=8)
# Evolution des positions
rounds = list(range(len(history_L)))
ax2.plot(rounds, history_L, 'b-', linewidth=2, label='Parti Gauche')
ax2.plot(rounds, history_R, 'r-', linewidth=2, label='Parti Droite')
ax2.axhline(median, color='green', linestyle='--', linewidth=2, label='Electeur median')
ax2.set_xlabel('Iteration')
ax2.set_ylabel('Position politique')
ax2.set_title('Convergence vers l\'electeur median (Downs 1957)')
ax2.legend()
ax2.set_ylim(0, 10)
plt.tight_layout()
plt.show()
print("Les deux partis convergent vers la position de l'electeur median!")
Les deux partis convergent vers la position de l'electeur median!Résultat observe : Les deux partis convergent progressivement vers la position de l’electeur median (5.0).
| Parti | Position initiale | Position finale | Distance parcourue |
|---|---|---|---|
| Gauche | 2.0 | 5.0 | +3.0 |
| Droite | 8.0 | 5.0 | -3.0 |
Mécanisme stratégique : - A chaque itération, chaque parti ajuste sa position vers le median pour capturer plus de votes - Ce comportement rationnel conduit à une convergence au centre - Le modèle de Downs (1957) prédit cette convergence dans les systèmes bipartites
Implication politique : Lorsque les préférences des électeurs sont unimodales (axe gauche-droite classique), la competition électorale naturelle pousse les partis vers des positions modérées, ce qui peut expliquer la stabilité des démocraties occidentales.
Le theoreme d’Arrow requiert au moins 3 alternatives. Avec seulement 2 alternatives, la règle majoritaire fonctionne parfaitement.
print("AVEC 2 ALTERNATIVES : LA MAJORITE FONCTIONNE")
print("=" * 50)
print("""
Avec 2 alternatives A et B :
Regle majoritaire :
- A > B socialement ssi majorite prefere A a B
Cette regle satisfait :
- Pareto : Si tous preferent A, majorite prefere A
- IIA : Trivial avec 2 alternatives (pas d'autres alternatives)
- Non-dictature : Aucun individu seul ne decide
=> Le theoreme d'Arrow requiert |A| >= 3
Contre-exemple au paradoxe de Condorcet :
Avec 2 alternatives, pas de cycle possible!
A > B ou B > A (relation complete et antisymetrique)
""")
# Demonstration
profile_2alt = [
['A', 'B'], # Individu 1
['A', 'B'], # Individu 2
['B', 'A'], # Individu 3
]
print("Exemple avec 3 electeurs:")
for i, pref in enumerate(profile_2alt):
print(f" Individu {i+1}: {' > '.join(pref)}")
winner = pairwise_majority(profile_2alt, 'A', 'B')
print(f"\nResultat majoritaire: {winner} gagne (2 contre 1)")
print("Pas de cycle possible avec 2 alternatives!")AVEC 2 ALTERNATIVES : LA MAJORITE FONCTIONNE
==================================================
Avec 2 alternatives A et B :
Regle majoritaire :
- A > B socialement ssi majorite prefere A a B
Cette regle satisfait :
- Pareto : Si tous preferent A, majorite prefere A
- IIA : Trivial avec 2 alternatives (pas d'autres alternatives)
- Non-dictature : Aucun individu seul ne decide
=> Le theoreme d'Arrow requiert |A| >= 3
Contre-exemple au paradoxe de Condorcet :
Avec 2 alternatives, pas de cycle possible!
A > B ou B > A (relation complete et antisymetrique)
Exemple avec 3 electeurs:
Individu 1: A > B
Individu 2: A > B
Individu 3: B > A
Resultat majoritaire: A gagne (2 contre 1)
Pas de cycle possible avec 2 alternatives!Objectifs : 1. Implementer une fonction de recherche du gagnant de Condorcet 2. Implementer une detection de cycles dans les préférences majoritaires 3. Tester sur des profils avec et sans cycle
Fonctions déjà disponibles (section 1) : pairwise_majority(profile, x, y) et check_condorcet_cycle(profile, alternatives). Vous pouvez les reutiliser directement ou reimplementer leur logique.
Ce que vous devez implementer : - trouver_gagnant_condorcet() : retourne le gagnant de Condorcet ou None - detecter_cycle() : detecte et retourne un cycle s’il existe
# Exercice 1 : Paradoxe de Condorcet et Cycles
# =============================================
# Rappel : les fonctions pairwise_majority() et check_condorcet_cycle()
# sont definies dans la section 1 ci-dessus. Vous pouvez les reutiliser
# directement, ou reimplementer votre propre version pour mieux comprendre.
# --- Donnees de l'exercice ---
# Profil 1 : 5 electeurs, 4 candidats
# Determinez si un gagnant de Condorcet existe.
profil_1 = [
['A', 'B', 'D', 'C'], # Electeur 1
['B', 'C', 'A', 'D'], # Electeur 2
['C', 'D', 'A', 'B'], # Electeur 3
['D', 'A', 'B', 'C'], # Electeur 4
['A', 'C', 'D', 'B'], # Electeur 5
]
candidats_1 = ['A', 'B', 'C', 'D']
# Profil 2 : un profil SANS cycle (un gagnant de Condorcet existe)
profil_2 = [
['A', 'B', 'C'], # Electeur 1
['A', 'C', 'B'], # Electeur 2
['B', 'A', 'C'], # Electeur 3
['C', 'A', 'B'], # Electeur 4
['A', 'B', 'C'], # Electeur 5
]
candidats_2 = ['A', 'B', 'C']
# --- Question 1 : Trouver le gagnant de Condorcet ---
def trouver_gagnant_condorcet(profil, candidats):
"""Trouve le gagnant de Condorcet dans un profil de preferences.
Un gagnant de Condorcet bat tous les autres candidats en duel
majoritaire pairwise.
Args:
profil: liste de listes, chaque sous-liste est un classement
candidats: liste des noms de candidats
Returns:
Le nom du gagnant de Condorcet, ou None si aucun n'existe.
"""
# Exercice: Implementez ici
# Indice : pour chaque candidat, verifiez s'il bat TOUS les autres
# en duel majoritaire.
pass
# --- Question 2 : Detecter les cycles ---
def detecter_cycle(profil, candidats):
"""Detecte s'il existe un cycle dans les preferences majoritaires.
Args:
profil: liste de listes de preferences
candidats: liste des candidats
Returns:
tuple (bool, list): (True/False, liste formant le cycle ou [])
"""
# Exercice: Implementez ici
# Indice : construisez d'abord la matrice de victoires pairwise,
# puis cherchez un cycle (DFS ou verification exhaustive).
pass
# --- Question 3 : Tests ---
# Exercice: Testez vos fonctions sur profil_1 et profil_2
# - Affichez les preferences de chaque electeur
# - Appelez trouver_gagnant_condorcet() et detecter_cycle()
# - Attendu : profil_1 devrait avoir un cycle, profil_2 un gagnant
print("Exercice a completer : Paradoxe de Condorcet et Cycles")Exercice a completer : Paradoxe de Condorcet et CyclesObjectifs : 1. Appliquer les méthodes existantes a de nouveaux profils pour observer les divergences 2. Implementer une nouvelle méthode : le Vote par Elimination (IRV) 3. Construire un tableau comparatif des résultats
Fonctions déjà disponibles (section 2) : plurality_rule(), borda_rule(), copeland_rule(). Utilisez-les directement dans cet exercice.
Ce que vous devez implementer : - instant_runoff_voting() : vote par elimination successive (méthode NON presente dans les sections précédentes) - Analyse comparative des 4 méthodes sur les profils fournis
# Exercice 2 : Comparaison des methodes de vote
# ===============================================
# Rappel : les fonctions plurality_rule(), borda_rule() et copeland_rule()
# sont definies dans la section 2 ci-dessus.
# --- Donnees de l'exercice ---
profil_A = [
['X', 'Y', 'Z'], # 4 electeurs preferent X
['X', 'Y', 'Z'],
['X', 'Y', 'Z'],
['X', 'Y', 'Z'],
['Y', 'Z', 'X'], # 3 electeurs preferent Y
['Y', 'Z', 'X'],
['Y', 'Z', 'X'],
['Z', 'Y', 'X'], # 2 electeurs preferent Z
['Z', 'Y', 'X'],
]
candidats_A = ['X', 'Y', 'Z']
profil_B = [
['A', 'B', 'C', 'D'], # 2 electeurs
['A', 'B', 'C', 'D'],
['B', 'D', 'C', 'A'], # 2 electeurs
['B', 'D', 'C', 'A'],
['C', 'D', 'B', 'A'], # 2 electeurs
['C', 'D', 'B', 'A'],
['D', 'C', 'B', 'A'], # 1 electeur
]
candidats_B = ['A', 'B', 'C', 'D']
# --- Question 1 : Appliquer les methodes existantes ---
# Exercice: Appliquez plurality_rule(), borda_rule() et copeland_rule()
# sur profil_A et profil_B. Affichez les classements et identifiez
# les cas ou le gagnant differe entre les methodes.
# --- Question 2 : Vote par elimination (IRV) ---
def instant_runoff_voting(profil, candidats):
"""Applique le vote par elimination successive (IRV).
A chaque tour :
1. Comptez les premiers choix de chaque candidat restant
2. Si un candidat a la majorite absolue (> 50%), il gagne
3. Sinon, eliminez le candidat avec le moins de premiers choix
4. Mettez a jour les preferences (retirez le candidat elimine)
Args:
profil: liste de listes de preferences
candidats: liste des candidats
Returns:
tuple (str, list): (gagnant, historique des eliminations)
"""
# Exercice: Implementez ici
# Indice : travaillez sur une copie du profil, et a chaque tour
# retirez le candidat elimine de toutes les listes de preferences.
pass
# --- Question 3 : Tableau comparatif ---
# Exercice: Construisez un tableau recapitulatif pour profil_A :
# | Methode | Classement | Gagnant |
# Appliquez les 4 methodes et comparez les resultats.
# Question d'analyse : les 4 methodes donnent-elles le meme gagnant ?
# Si non, quelle methode vous semble la plus "juste" et pourquoi ?
print("Exercice a completer : Comparaison des methodes de vote")Exercice a completer : Comparaison des methodes de voteObjectifs : 1. Verifier experimentalement la propriete IIA sur la règle de Borda 2. Construire une règle dictatoriale et observer ses proprietes 3. Verifier la propriete de Pareto pour différentes règles
Fonctions déjà disponibles (section 2) : plurality_rule(), borda_rule(), copeland_rule(). Utilisez-les pour les verifications.
Ce que vous devez implementer : - verifier_iia_borda() : teste si Borda respecte IIA entre deux profils - dictature() : règle d’agregation dictatoriale (très simple) - verifier_pareto() : teste si une règle respecte le critere de Pareto
Données fournies : deux profils soigneusement construits pour mettre en evidence la violation de IIA par Borda, et un profil pour tester Pareto.
# Exercice 3 : Theoreme d'Arrow et proprietes d'agregation
# =========================================================
# Le theoreme d'Arrow (1951) prouve qu'aucune fonction d'agregation
# des preferences (avec >= 3 alternatives) ne peut satisfaire
# simultanement : Universalite, Unanimite (Pareto), IIA et Non-dictature.
from itertools import permutations
# --- Donnees de l'exercice ---
candidats = ['A', 'B', 'C']
# Deux profils qui different UNIQUEMENT sur la position de C
# (pour tester IIA sur la paire A-B)
profil_iia_1 = [
['A', 'B', 'C'], # Electeur 1
['B', 'A', 'C'], # Electeur 2
['A', 'C', 'B'], # Electeur 3
]
profil_iia_2 = [
['A', 'B', 'C'], # Electeur 1 (A>B inchange)
['B', 'A', 'C'], # Electeur 2 (B>A inchange)
['C', 'A', 'B'], # Electeur 3 (A>B inchange, mais C monte)
]
# Profil pour tester Pareto
profil_pareto = [
['A', 'B', 'C'], # Tous preferent A a B
['A', 'C', 'B'],
['A', 'B', 'C'],
]
# --- Question 1 : Verifier IIA pour Borda ---
def verifier_iia_borda(profil1, profil2, cand_x, cand_y):
"""Verifie si la regle de Borda respecte IIA pour une paire de candidats.
Args:
profil1, profil2: deux profils ou les preferences relatives
entre cand_x et cand_y sont identiques
cand_x, cand_y: les deux candidats a comparer
Returns:
bool: True si IIA est respectee, False sinon
"""
# Exercice: Implementez ici
# Indice : appliquez borda_rule() aux deux profils, puis comparez
# la position relative de cand_x et cand_y dans chaque classement.
pass
# --- Question 2 : Construire une dictature ---
def dictature(profil, dictateur_index):
"""Regle d'agregation dictatoriale.
Args:
profil: liste de listes de preferences
dictateur_index: indice de l'electeur dictateur (0, 1, 2...)
Returns:
list: le classement social (= les preferences du dictateur)
"""
# Exercice: Implementez ici (tres simple!)
pass
# --- Question 3 : Verifier Pareto pour differentes regles ---
def verifier_pareto(regle, profil, cand_x, cand_y):
"""Verifie si une regle respecte Pareto pour une paire de candidats.
Precondition: tous les electeurs preferent cand_x a cand_y.
Args:
regle: fonction qui prend un profil et retourne un classement (list)
profil: liste de listes de preferences
cand_x: candidat unanimement prefere
cand_y: candidat unanimement moins prefere
Returns:
bool: True si la regle classe cand_x avant cand_y
"""
# Exercice: Implementez ici
# Indice : appliquez la regle, trouvez les positions de cand_x et cand_y.
pass
# --- Verification finale ---
# Exercice: Testez vos 3 fonctions :
# 1. verifier_iia_borda sur profil_iia_1 vs profil_iia_2 pour A vs B
# (Attendu : False, Borda viole IIA)
# 2. dictature sur profil_iia_1 avec dictateur 0
# (Attendu : preferences de l'electeur 0)
# 3. verifier_pareto sur profil_pareto pour A vs B avec chaque regle
# (Attendu : toutes les regles respectent Pareto ici)
# Concluez sur le theoreme d'Arrow.
print("Exercice a completer : Theoreme d Arrow et proprietes d agregation")Exercice a completer : Theoreme d Arrow et proprietes d agregationLien avec la formalisation Lean : Les concepts de ce notebook — cycles de Condorcet, règles de vote (pluralite, Borda, Copeland), critères d’agregation (Pareto, IIA, non-dictature), préférences unimodales et theoreme de l’electeur median — sont formalises dans
game_theory_lean/SocialChoice/Voting.lean(0 sorry). On y trouve les definitions demargin,condorcet_winner,condorcet_loser, le typeSCC(Social Choice Correspondence), les critères de Condorcet et de monotonicite, ainsi que le theorememedian_voter_theorem_strict(préférences unimodales). Les axiomes d’Arrow (Pareto, IIA, non-dictature) sont définis dansFramework.lean(0 sorry) commeweak_pareto,ind_of_irr_alts,is_dictatorship. Le theoreme de Sen (liberte minimale + Pareto + transitivite) est prouve dansSen.lean(0 sorry).
| Concept | Implementation Python |
|---|---|
| Classe Profile | Profile, is_pareto_unanimous(), social_ranking() |
| Paradoxe Condorcet | check_condorcet_cycle(), visualisation networkx |
| Gagnant de Condorcet | condorcet_winner() (general), condorcet_winner_single_peaked() |
| Règles de vote | plurality_rule(), borda_rule(), copeland_rule() |
| Theoreme de Sen | Profil Prude/Lewd avec cycle np > pr > lr > np |
| Theoreme d’Arrow | check_iia_violations(), detect_dictator() |
| Préférences unimodales | single_peaked_preference(), find_median_voter() |
| Modèle de Downs | simulate_two_party_competition() |
Theoremes cles : - Arrow : Pas de SWF parfaite avec >= 3 alternatives (verifie empiriquement) - Sen : Conflit liberte/Pareto (exemple Lady Chatterley en code) - Electeur median : Avec préférences unimodales, majorite fonctionne
Navigation : << SC-02 Lean SocialChoice | Index | SC-04 SAT/Z3 >>