[Origami] SocialChoice-09 STV/Monroe/Chamberlin-Courant (tranche 3 #19263) — multi-winner elections Handbook ch. 6 #19371

Tranche 3 — committees multi-winners (STV / Monroe / Chamberlin-Courant)

Suite logique de la tranche 1 (refs anchoring, PR #19331 livree c.1059) et de la tranche 2 (SC-08 Kemeny/RankedPairs/Dodgson, PR #19337 livree c.1060) de l'EPIC #19263 « [GameTheory] Ancrer le cluster choix social sur le Handbook of Computational Social Choice ».

L'EPIC body mentionne explicitement cette tranche comme troisieme livrable : « Ranked Pairs et Dodgson (ch. 5) en tranches suivantes si la fenetre le permet ». SC-08 a livre Kemeny + Ranked Pairs + Dodgson (les trois regles NP-dures du chapitre 2 et 5). La tranche 3 attaque le chapitre 6 du Handbook (multi-winner elections) avec les trois regles representatives.

Livrable

Carnet MyIA.AI.Notebooks/GameTheory/SocialChoice/09-Committees-STV-Monroe-ChamberlinCourant.ipynb (kernel coursia-ml-training, Python), execute bout-en-bout, committe avec outputs reels (C.2) :

• Section 1 - STV (Single Transferable Vote, Hare 1857) : quota de Droop, depouillement par tour, electeur le moins vote transfere son surplus, jusqu'a attribution complete. Complexite polynomiale (algorithmiquement).
• Section 2 - Monroe (1995) : assignation proportionnelle multi-winners par backtracking, chaque gagnant represente approximativement le meme nombre d'electeurs (|floor(n/k)| ou |ceil(n/k)|). NP-dur (proportionnel multi-winners).
• Section 3 - Chamberlin-Courant (1983) : assignation proportionnelle representationnelle, chaque gagnant represente un sous-ensemble d'electeurs (visant la satisfaction maximale via Borda ou score similaire). NP-dur.
• Section 4 - Z3 confrontation : formulation Z3 (z3.Optimize + Int ranks + contraintes cardinalite) confrontee a l'enumeration brute-force pour Monroe et Chamberlin-Courant sur petits profils. Axe 2 SOTA non-trivial (cf. SC-08) : determination du committee NP-dure met le solveur en valeur.
• Section 5 - Resume comparatif + 3 exercices (convention C.1) + references Handbook ch. 6 + footer navigation chainee vers SC-10 (prochaine tranche).

Criteres d'acceptation

• Le carnet existe, execute bout-en-bout, outputs commites (C.2).
• execution_count non-null sur toutes les cellules code ; pas d'erreur volontaire (C.1).
• 3 cellules-types verifiees post-exec (STV sur 5 candidats / Monroe par Z3 / Chamberlin-Courant par Z3).
• 3 exercices C.1 presents, alignes a la convention.
• Bibliographie Handbook ch. 6 (Elkind et al. 2017 « Handbook of Computational Social Choice », ch. 6 Multiwinner Elections).
• Verdict SOTA documente (SOTA-OK : Z3 + Python pur, pas de GPU).
• Pas de secret. Pas de scrub d'output. Anti-regression §D (n/a : from-scratch, pas de code de production touche).

Ancrage bibliographique

• Handbook of Computational Social Choice ch. 6 « Multi-Winner Elections » (Elkind et al. 2017, ISBN 978-1-107-06043-2, deja au gisement cluster : G:\Mon Drive\MyIA\IA\Bibliographie IA\GameTheory\2016 - Brandt Conitzer Endriss Lang - Handbook of Computational Social Choice.pdf).
• Hare 1857 (STV, systeme electoral australien).
• Monroe 1995 (proportionnalite par assignment).
• Chamberlin & Courant 1983 (representation proportionnelle).
• Procaccia et al. 2008 (complexite NP-dure Chamberlin-Courant sous Borda).

Pre-condition et verrouillage

• Pre-condition : aucun. La tranche 1 (refs) et la tranche 2 (SC-08) sont livrees (PR docs(gametheory,#19263): Handbook of Computational Social Choice - tranche 1 refs anchoring #19331 + PR feat(socialchoice,#19263): SC-08 Kemeny/RankedPairs/Dodgson (tranche 2) #19337 ripe, en attente de merge coord).
• Verrouillage SC-10 (prochaine tranche) : la tranche 3 doit etre livree et validee avant qu'une sous-issue SC-10 ne soit deplacee.
• Lane recommandee : myia-po-2023:CoursIA-2 (adjacence avec SC-08 Kemeny tranche 2 livree c.1060), lane de portage de l'EPIC depuis le depart. Faisable CPU-only (Z3, pas de Lean, pas de GPU). A piocher des que la file DEEP/CONTENU CPU-only se deverrouille.

Suite

• Tranche 4 (future) : mecanismes de manipulation strategique sous regles multi-winners (Gibbard-Satterthwaite etendu, Conitzer et al. 2010).

See #19263 #19331 #19337

🤖 Generated with Claude Code