Navigation : << 15-CooperativeGames | Index | 17-MultiAgent-RL >>
Side tracks : sous-serie Social Choice — SC-01 Arrow (Python) | SC-02 Lean | SC-03 Méthodes de vote | SC-04 SAT/Z3
La théorie des mécanismes (mechanism design) est la “théorie des jeux inversee” : au lieu d’analyser un jeu donne, on concoit des règles pour atteindre un objectif.
Un designer (concepteur) veut implementer une fonction sociale \(f(\theta)\) ou \(\theta = (\theta_1, ..., \theta_n)\) sont les types (informations privees) des agents.
Problème : Les agents connaissent leur type \(\theta_i\), mais le designer ne le connait pas directement.
| Contexte | Objectif | Mécanisme |
|---|---|---|
| Encheres | Maximiser revenu ou efficacite | Vickrey, encheres anglaises |
| Biens publics | Financement efficient | Mécanisme de Clarke |
| Appariement | Stabilite | Gale-Shapley |
| Vote | Agregation des préférences | Différentes règles electorales |
# Installation des dependances
import subprocess
import sys
packages = ['numpy', 'matplotlib', 'scipy']
for pkg in packages:
subprocess.check_call([sys.executable, '-m', 'pip', 'install', '-q', pkg])
import numpy as np
import matplotlib.pyplot as plt
from typing import List, Tuple, Dict, Callable, Optional
from dataclasses import dataclass, field
from abc import ABC, abstractmethod
import itertools
print("Imports reussis")Imports reussisTheoreme (Gibbard, 1973; Myerson, 1979) : Pour tout mécanisme indirect qui implemente \(f\) en equilibre, il existe un mécanisme direct ou : 1. Chaque agent reporte son type 2. Dire la verite est un equilibre 3. Le résultat est le même que dans le mécanisme original
On peut se restreindre aux mécanismes directs incitatifs (truthful) sans perte de generalite.
Nous allons maintenant implementer une structure orientee objet pour modeliser et tester différents mécanismes.
Classes principales :
is_ic() pour tester l’incitativite, is_ir() pour la rationalite individuelleCette structure nous permettra de comparer systematiquement différents formats d’encheres et de verifier leurs proprietes théoriques (IC, IR, efficacite).
@dataclass
class Agent:
"""Agent avec un type (valuation privee)."""
id: int
true_type: float # Valuation reelle
def utility(self, allocation: float, payment: float) -> float:
"""Utilite = valuation * allocation - paiement."""
return self.true_type * allocation - payment
class Mechanism(ABC):
"""Classe abstraite pour un mecanisme."""
@abstractmethod
def allocate(self, reports: List[float]) -> List[float]:
"""Determine l'allocation basee sur les reports."""
pass
@abstractmethod
def compute_payments(self, reports: List[float],
allocations: List[float]) -> List[float]:
"""Determine les paiements."""
pass
def run(self, reports: List[float]) -> Tuple[List[float], List[float]]:
"""Execute le mecanisme."""
allocations = self.allocate(reports)
payments = self.compute_payments(reports, allocations)
return allocations, payments
def is_ic(self, agents: List[Agent], epsilon: float = 0.01) -> bool:
"""
Verifie la compatibilite incitative (IC) en strategie dominante.
IC: Pour tout agent, dire la verite est optimal quel que soit
ce que les autres disent.
"""
for i, agent in enumerate(agents):
# Tester avec differents reports des autres
other_reports_samples = [
[a.true_type for a in agents if a.id != agent.id],
[0.0] * (len(agents) - 1),
[100.0] * (len(agents) - 1)
]
for other_reports in other_reports_samples:
# Utilite en disant la verite
truth_reports = other_reports.copy()
truth_reports.insert(i, agent.true_type)
alloc_truth, pay_truth = self.run(truth_reports)
u_truth = agent.utility(alloc_truth[i], pay_truth[i])
# Tester des deviations
for deviation in [0, agent.true_type * 0.5, agent.true_type * 1.5, agent.true_type * 2]:
lie_reports = other_reports.copy()
lie_reports.insert(i, deviation)
alloc_lie, pay_lie = self.run(lie_reports)
u_lie = agent.utility(alloc_lie[i], pay_lie[i])
if u_lie > u_truth + epsilon:
return False
return True
def is_ir(self, agents: List[Agent]) -> bool:
"""
Verifie la rationalite individuelle (IR).
IR: Tout agent a une utilite non-negative en participapant.
"""
reports = [a.true_type for a in agents]
allocations, payments = self.run(reports)
for i, agent in enumerate(agents):
if agent.utility(allocations[i], payments[i]) < 0:
return False
return True
print("Classes de base definies")Classes de base definiesSous certaines conditions (valuations privees independantes, neutralite au risque), tous les formats d’encheres generent le même revenu espere.
Nous allons maintenant implementer ces deux formats d’enchere et comparer leurs résultats sur un exemple concret.
Stratégie : 1. Implementer FirstPriceAuction et SecondPriceAuction en heritant de Mechanism 2. Les tester avec 3 agents ayant des valuations différentes (100, 80, 60) 3. Verifier les proprietes IC et IR pour l’enchere de Vickrey 4. Observer la différence d’utilite pour le gagnant entre les deux formats
class FirstPriceAuction(Mechanism):
"""Enchere au premier prix : le gagnant paie son offre."""
def allocate(self, reports: List[float]) -> List[float]:
"""Le plus offrant gagne (allocation = 1)."""
n = len(reports)
allocations = [0.0] * n
winner = int(np.argmax(reports))
allocations[winner] = 1.0
return allocations
def compute_payments(self, reports: List[float],
allocations: List[float]) -> List[float]:
"""Le gagnant paie son offre."""
payments = [0.0] * len(reports)
for i, alloc in enumerate(allocations):
if alloc > 0:
payments[i] = reports[i]
return payments
class SecondPriceAuction(Mechanism):
"""Enchere au second prix (Vickrey) : le gagnant paie la 2e offre."""
def allocate(self, reports: List[float]) -> List[float]:
n = len(reports)
allocations = [0.0] * n
winner = int(np.argmax(reports))
allocations[winner] = 1.0
return allocations
def compute_payments(self, reports: List[float],
allocations: List[float]) -> List[float]:
"""Le gagnant paie la deuxieme plus haute offre."""
payments = [0.0] * len(reports)
sorted_reports = sorted(reports, reverse=True)
second_price = sorted_reports[1] if len(sorted_reports) > 1 else 0
for i, alloc in enumerate(allocations):
if alloc > 0:
payments[i] = second_price
return payments
# Demonstration
print("Comparaison : Enchere premier prix vs second prix")
print("="*60)
agents = [
Agent(0, 100), # Valuation 100
Agent(1, 80), # Valuation 80
Agent(2, 60) # Valuation 60
]
fpa = FirstPriceAuction()
spa = SecondPriceAuction()
# Avec reports veridiques
true_reports = [a.true_type for a in agents]
print(f"\nValuations vraies: {true_reports}")
print("\n--- Enchere au premier prix ---")
alloc_fpa, pay_fpa = fpa.run(true_reports)
print(f"Allocations: {alloc_fpa}")
print(f"Paiements: {pay_fpa}")
print(f"Utilites: {[a.utility(alloc_fpa[i], pay_fpa[i]) for i, a in enumerate(agents)]}")
print("\n--- Enchere au second prix ---")
alloc_spa, pay_spa = spa.run(true_reports)
print(f"Allocations: {alloc_spa}")
print(f"Paiements: {pay_spa}")
print(f"Utilites: {[a.utility(alloc_spa[i], pay_spa[i]) for i, a in enumerate(agents)]}")
print(f"\nIC (second prix): {spa.is_ic(agents)}")
print(f"IR (second prix): {spa.is_ir(agents)}")Comparaison : Enchere premier prix vs second prix
============================================================
Valuations vraies: [100, 80, 60]
--- Enchere au premier prix ---
Allocations: [1.0, 0.0, 0.0]
Paiements: [100, 0.0, 0.0]
Utilites: [0.0, 0.0, 0.0]
--- Enchere au second prix ---
Allocations: [1.0, 0.0, 0.0]
Paiements: [80, 0.0, 0.0]
Utilites: [20.0, 0.0, 0.0]
IC (second prix): True
IR (second prix): TrueLa comparaison entre les deux formats d’encheres revele une différence fondamentale dans les utilites des participants.
Premier prix vs Second prix :
| Aspect | Premier prix | Second prix (Vickrey) |
|---|---|---|
| Gagnant | Agent 0 | Agent 0 |
| Paiement | 100 (sa propre offre) | 80 (2e plus haute offre) |
| Utilite gagnant | 0 (100 - 100) | 20 (100 - 80) |
Observations cles :
Premier prix : Si l’agent encherit sa vraie valeur, son utilite est nulle (il paie exactement ce que l’objet vaut pour lui). En pratique, les agents sous-encherissent strategiquement.
Second prix : L’agent gagne avec une rente informationnelle de 20 (la différence entre sa valuation et le prix paye). Il n’a pas besoin de deviner les autres offres.
IC et IR : L’enchere au second prix est a la fois incentive-compatible (dire la verite est optimal) et individuellement rationnelle (utilite non-negative).
Note : Ces résultats supposent des reports veridiques. Dans une enchere au premier prix reelle, l’agent 0 encherir ait moins de 100, ce qui change l’analyse.
Objectif : Implementer le mécanisme d’enchere all-pay ou le gagnant obtient l’objet mais tous les joueurs paient leur offre. Verifier que ce mécanisme n’est pas incitatif-compatible (IC) avec la fonction is_ic.
Contexte : Les encheres au premier prix et au second prix ont ete comparees ci-dessus. L’enchere all-pay est un autre format classique, utilise dans les concours de lobbying.
class AllPayAuction(Mechanism):
"""
Enchere all-pay : le plus offrant gagne, mais tous paient leur offre.
"""
def allocate(self, bids):
# TODO etudiant : retourner l'allocation du gagnant
return [0.0] * len(bids) # TODO etudiant: placeholder
def compute_payments(self, bids, allocations):
# TODO etudiant : chaque joueur paie sa propre offre
return [0.0] * len(bids) # TODO etudiant: placeholder
# Test : 3 agents avec evaluations [10, 20, 15]
agents_ap = [Agent(i, v) for i, v in enumerate([10, 20, 15])]
auction_ap = AllPayAuction()
# Verifier IC (methode de la classe Mechanism)
ic_result = auction_ap.is_ic(agents_ap)
print(f"All-pay auction IC: {ic_result}")
print(f"(Attendu: False - les joueurs sous-encherissent)")
print("Exercice a completer")All-pay auction IC: True
(Attendu: False - les joueurs sous-encherissent)
Exercice a completer# Demonstration de l'incitativite de Vickrey
print("\nIncitativite de l'enchere au second prix")
print("="*60)
# Agent 0 (valuation = 100) considere differentes strategies
agent0 = agents[0]
other_bids = [80, 60] # Offres des autres (veridiques)
strategies = [0, 50, 79, 80, 81, 100, 120, 150]
results = []
for bid in strategies:
reports = [bid] + other_bids
alloc, pay = spa.run(reports)
utility = agent0.utility(alloc[0], pay[0])
results.append((bid, alloc[0], pay[0], utility))
print(f"\nAgent 0 (valuation = 100) vs offres adverses [80, 60]")
print(f"\n{'Offre':<10} {'Gagne?':<10} {'Paie':<10} {'Utilite':<10}")
print("-"*40)
for bid, alloc, pay, utility in results:
gagne = "Oui" if alloc > 0 else "Non"
print(f"{bid:<10} {gagne:<10} {pay:<10.0f} {utility:<10.0f}")
print(f"\n=> Utilite maximale ({max(r[3] for r in results):.0f}) atteinte en encherissant la vraie valeur (100)")
Incitativite de l'enchere au second prix
============================================================
Agent 0 (valuation = 100) vs offres adverses [80, 60]
Offre Gagne? Paie Utilite
----------------------------------------
0 Non 0 0
50 Non 0 0
79 Non 0 0
80 Oui 80 20
81 Oui 80 20
100 Oui 80 20
120 Oui 80 20
150 Oui 80 20
=> Utilite maximale (20) atteinte en encherissant la vraie valeur (100)Ce tableau illustre pourquoi l’enchere au second prix est incentive-compatible (IC).
Analyse des stratégies de l’agent 0 (valuation = 100, adversaires a 80 et 60) :
| Stratégie | Résultat | Pourquoi? |
|---|---|---|
| Sous-encherir (0-79) | Utilite = 0 | Ne gagne pas, donc aucun gain |
| Au seuil (80) | Utilite = 20 | Gagne a egalite, paie 80 |
| Verite ou plus (81-150) | Utilite = 20 | Gagne, paie toujours 80 (2e offre) |
Points cles : 1. Sous-encherir est risque : on peut perdre une enchere profitable 2. Sur-encherir ne change rien : le paiement depend des autres, pas de soi 3. La verite est faiblement dominante : aussi bien que toute autre stratégie, jamais pire
Intuition economique : En payant la 2e offre (pas la sienne), l’agent est “protege” de ses propres exagerations. Il n’a donc aucune incitation a mentir.
# Simulation : equivalence des revenus
print("\nSimulation : Equivalence des revenus (1er prix vs 2nd prix)")
print("="*60)
np.random.seed(42)
n_simulations = 10000
n_bidders = 3
revenues_fpa = []
revenues_spa = []
for _ in range(n_simulations):
# Valuations uniformes [0, 100]
valuations = np.random.uniform(0, 100, n_bidders)
# Second prix : encheres veridiques
_, pay_spa = spa.run(list(valuations))
revenues_spa.append(sum(pay_spa))
# Premier prix : equilibre b(v) = (n-1)/n * v
bids_fpa = valuations * (n_bidders - 1) / n_bidders
_, pay_fpa = fpa.run(list(bids_fpa))
revenues_fpa.append(sum(pay_fpa))
print(f"\nResultats sur {n_simulations} encheres avec {n_bidders} encherisseurs:")
print(f" Revenu moyen (1er prix): {np.mean(revenues_fpa):.2f}")
print(f" Revenu moyen (2nd prix): {np.mean(revenues_spa):.2f}")
print(f" Difference: {abs(np.mean(revenues_fpa) - np.mean(revenues_spa)):.2f}")
# Revenu theorique : E[2eme max sur n uniformes [0,100]] = 100 * (n-1)/(n+1)
theoretical_revenue = 100 * (n_bidders - 1) / (n_bidders + 1)
print(f" Revenu theorique: {theoretical_revenue:.2f}")
# Visualisation
fig, axes = plt.subplots(1, 2, figsize=(12, 5))
ax1 = axes[0]
ax1.hist(revenues_fpa, bins=50, alpha=0.5, label='1er prix', density=True)
ax1.hist(revenues_spa, bins=50, alpha=0.5, label='2nd prix', density=True)
ax1.axvline(theoretical_revenue, color='red', linestyle='--', label=f'Theorique: {theoretical_revenue:.1f}')
ax1.set_xlabel('Revenu')
ax1.set_ylabel('Densite')
ax1.set_title('Distribution des revenus')
ax1.legend()
ax2 = axes[1]
ax2.scatter(revenues_fpa[:500], revenues_spa[:500], alpha=0.3, s=10)
ax2.plot([0, 100], [0, 100], 'r--', label='y=x')
ax2.set_xlabel('Revenu (1er prix)')
ax2.set_ylabel('Revenu (2nd prix)')
ax2.set_title('Correlation des revenus')
ax2.legend()
plt.tight_layout()
plt.savefig('auction_revenue_equivalence.png', dpi=150, bbox_inches='tight')
plt.show()
Simulation : Equivalence des revenus (1er prix vs 2nd prix)
============================================================
Resultats sur 10000 encheres avec 3 encherisseurs:
Revenu moyen (1er prix): 49.92
Revenu moyen (2nd prix): 50.01
Difference: 0.09
Revenu theorique: 50.00
La simulation sur 10 000 encheres confirme le theoreme d’equivalence des revenus.
Résultats statistiques :
| Mécanisme | Revenu moyen | Revenu théorique | Différence |
|---|---|---|---|
| Premier prix | ~50 | 50 | < 1% |
| Second prix | ~50 | 50 | < 1% |
Le revenu théorique pour 3 encherisseurs avec valuations uniformes sur [0, 100] est : \[E[\text{2eme max}] = 100 \times \frac{n-1}{n+1} = 100 \times \frac{2}{4} = 50\]
Observations visuelles : - Les histogrammes se superposent presque parfaitement (même distribution) - Le nuage de points suit la ligne y=x, confirmant l’equivalence
Implication pratique : Du point de vue du vendeur, le choix du format d’enchere n’a pas d’impact sur le revenu espere. Cependant, l’enchere au second prix est preferable car incitative (plus simple pour les encherisseurs).
Le mécanisme VCG generalise l’enchere de Vickrey a tout problème d’allocation.
Structure : 1. Allocation efficace : maximise le bien-etre social \(\sum_i v_i(x, \theta_i)\) 2. Paiement : l’agent \(i\) paie l’externalite qu’il impose aux autres
\[p_i = \sum_{j \neq i} v_j(x^*_{-i}, \theta_j) - \sum_{j \neq i} v_j(x^*, \theta_j)\]
Ou : - \(x^*\) est l’allocation optimale avec tous les agents - \(x^*_{-i}\) est l’allocation optimale sans l’agent \(i\)
Nous passons maintenant au cas general : le mécanisme VCG pour des encheres multi-objets.
Principe de l’implementation : 1. Chaque agent declare sa valuation pour chaque objet 2. L’allocation est efficace : chaque objet va a l’agent qui le valorise le plus 3. Le paiement VCG est l’externalite : ce que les autres perdent parce que l’agent i participe
Exemple concret : 3 agents, 2 objets (A et B). Nous allons : - Calculer l’allocation efficace - Determiner les paiements VCG - Verifier que dire la verite est optimal (IC)
class VCGAuction(Mechanism):
"""
Mecanisme VCG pour une enchere multi-objets.
Chaque agent a une valuation pour chaque objet.
Allocation: chaque objet va a l'agent qui le valorise le plus.
Paiement: externalite imposee aux autres.
"""
def __init__(self, n_items: int):
self.n_items = n_items
def allocate(self, valuations: List[List[float]]) -> List[List[float]]:
"""
valuations[i][j] = valuation de l'agent i pour l'objet j.
Retourne allocations[i][j] = 1 si agent i recoit objet j.
"""
n_agents = len(valuations)
allocations = [[0.0] * self.n_items for _ in range(n_agents)]
for j in range(self.n_items):
# Objet j va au plus offrant
bids_for_j = [valuations[i][j] for i in range(n_agents)]
winner = int(np.argmax(bids_for_j))
allocations[winner][j] = 1.0
return allocations
def compute_social_welfare(self, valuations: List[List[float]],
allocations: List[List[float]]) -> float:
"""Calcule le bien-etre social total."""
welfare = 0.0
for i, alloc in enumerate(allocations):
for j, a in enumerate(alloc):
welfare += a * valuations[i][j]
return welfare
def compute_payments(self, valuations: List[List[float]],
allocations: List[List[float]]) -> List[float]:
"""
Paiement VCG : externalite imposee aux autres.
p_i = SW_{-i}(sans i) - SW_{-i}(avec i)
"""
n_agents = len(valuations)
payments = [0.0] * n_agents
# Bien-etre des autres avec allocation actuelle
for i in range(n_agents):
# SW des autres avec i present
sw_others_with_i = 0.0
for j_agent in range(n_agents):
if j_agent != i:
for j_item in range(self.n_items):
sw_others_with_i += allocations[j_agent][j_item] * valuations[j_agent][j_item]
# SW des autres si i absent (recalculer l'allocation optimale)
valuations_without_i = [v for k, v in enumerate(valuations) if k != i]
if valuations_without_i:
alloc_without_i = self._allocate_subset(valuations_without_i)
sw_others_without_i = self.compute_social_welfare(
valuations_without_i, alloc_without_i
)
else:
sw_others_without_i = 0.0
# Paiement = externalite negative
payments[i] = sw_others_without_i - sw_others_with_i
return payments
def _allocate_subset(self, valuations: List[List[float]]) -> List[List[float]]:
"""Allocation pour un sous-ensemble d'agents."""
n_agents = len(valuations)
allocations = [[0.0] * self.n_items for _ in range(n_agents)]
for j in range(self.n_items):
bids_for_j = [valuations[i][j] for i in range(n_agents)]
winner = int(np.argmax(bids_for_j))
allocations[winner][j] = 1.0
return allocations
def run(self, valuations: List[List[float]]
) -> Tuple[List[List[float]], List[float]]:
"""Execute le mecanisme VCG."""
allocations = self.allocate(valuations)
payments = self.compute_payments(valuations, allocations)
return allocations, payments
# Exemple : encheres multi-objets
print("Mecanisme VCG : Enchere multi-objets")
print("="*60)
# 3 agents, 2 objets
# valuations[i][j] = valuation agent i pour objet j
valuations = [
[50, 30], # Agent 0
[40, 60], # Agent 1
[35, 25] # Agent 2
]
vcg = VCGAuction(n_items=2)
allocations, payments = vcg.run(valuations)
print(f"\nValuations:")
for i, v in enumerate(valuations):
print(f" Agent {i}: Objet A = {v[0]}, Objet B = {v[1]}")
print(f"\nAllocations VCG:")
for i, alloc in enumerate(allocations):
items = [f"Objet {'AB'[j]}" for j, a in enumerate(alloc) if a > 0]
print(f" Agent {i}: {items if items else 'Rien'}")
print(f"\nPaiements VCG:")
for i, pay in enumerate(payments):
print(f" Agent {i}: {pay:.2f}")
print(f"\nUtilites:")
for i in range(len(valuations)):
value = sum(allocations[i][j] * valuations[i][j] for j in range(2))
utility = value - payments[i]
print(f" Agent {i}: valeur={value:.0f}, paiement={payments[i]:.0f}, utilite={utility:.0f}")Mecanisme VCG : Enchere multi-objets
============================================================
Valuations:
Agent 0: Objet A = 50, Objet B = 30
Agent 1: Objet A = 40, Objet B = 60
Agent 2: Objet A = 35, Objet B = 25
Allocations VCG:
Agent 0: ['Objet A']
Agent 1: ['Objet B']
Agent 2: Rien
Paiements VCG:
Agent 0: 40.00
Agent 1: 30.00
Agent 2: 0.00
Utilites:
Agent 0: valeur=50, paiement=40, utilite=10
Agent 1: valeur=60, paiement=30, utilite=30
Agent 2: valeur=0, paiement=0, utilite=0Le mécanisme VCG alloue chaque objet de maniere efficace (a celui qui le valorise le plus) et calcule les paiements selon le principe de l’externalite.
Allocations : - Objet A : Agent 0 (valuation 50) gagne contre Agent 1 (40) et Agent 2 (35) - Objet B : Agent 1 (valuation 60) gagne contre Agent 0 (30) et Agent 2 (25)
Calcul des paiements VCG :
| Agent | Obtient | Sans lui, les autres auraient | Avec lui, les autres ont | Externalite = Paiement |
|---|---|---|---|---|
| 0 | A | A irait a Agent 1 (40) | Agent 1 recoit 0 sur A | 40 - 0 = 40 |
| 1 | B | B irait a Agent 0 (30) | Agent 0 recoit 0 sur B | 30 - 0 = 30 |
| 2 | Rien | Aucun changement | Inchange | 0 |
Point cle : Chaque agent paie exactement le cout social qu’il impose aux autres en participant. C’est ce qui rend le mécanisme incitatif : mentir ne change pas ce cout social reel.
# Verification de l'incitativite VCG
print("\nVerification de l'incitativite VCG")
print("="*60)
# Agent 0 (valuations [50, 30]) considere mentir
true_val_0 = [50, 30]
lie_strategies = [
[50, 30], # Verite
[60, 40], # Sur-encherir
[35, 20], # Sous-encherir
[50, 70], # Sur-encherir sur B (qu'il veut moins)
]
print(f"\nAgent 0 (vraie valuation: {true_val_0})")
print(f"Autres agents: Agent 1 = [40, 60], Agent 2 = [35, 25]")
print(f"\n{'Report':<15} {'Allocation':<15} {'Paiement':<12} {'Utilite vraie':<15}")
print("-"*57)
for report in lie_strategies:
# Construire les valuations avec le report de l'agent 0
test_valuations = [report, [40, 60], [35, 25]]
alloc, pay = vcg.run(test_valuations)
# Utilite VRAIE (basee sur vraie valuation, pas le report)
true_value = sum(alloc[0][j] * true_val_0[j] for j in range(2))
true_utility = true_value - pay[0]
items = "AB"[0] if alloc[0][0] > 0 else ""
items += "AB"[1] if alloc[0][1] > 0 else ""
print(f"{str(report):<15} {items if items else 'Rien':<15} {pay[0]:<12.0f} {true_utility:<15.0f}")
print(f"\n=> L'utilite est maximale en disant la verite (strategie dominante)")
Verification de l'incitativite VCG
============================================================
Agent 0 (vraie valuation: [50, 30])
Autres agents: Agent 1 = [40, 60], Agent 2 = [35, 25]
Report Allocation Paiement Utilite vraie
---------------------------------------------------------
[50, 30] A 40 10
[60, 40] A 40 10
[35, 20] Rien 0 0
[50, 70] AB 100 -20
=> L'utilite est maximale en disant la verite (strategie dominante)Cette verification demontre la robustesse de l’incitativite VCG face aux tentatives de manipulation.
Stratégies testees par l’Agent 0 (vraie valuation [50, 30]) :
| Report | Allocation | Paiement | Utilite vraie | Analyse |
|---|---|---|---|---|
| Verite [50, 30] | A | 40 | 10 | Optimal |
| Sur-encherir [60, 40] | A | 40 | 10 | Mêmes résultats |
| Sous-encherir [35, 20] | Rien | 0 | 0 | Perd l’objet A |
| Manipuler [50, 70] | AB | 100 | -20 | Penalise |
Points cles : 1. Sur-encherir ne change pas l’allocation ni le paiement (VCG “immunise” contre l’exageration) 2. Sous-encherir risque de perdre un objet desirable (utilite = 0) 3. Mentir sur les préférences (ex: declarer aimer B plus) peut mener a une allocation sous-optimale et une penalite financiere
Propriete fondamentale : Dans VCG, le paiement depend de l’externalite (impact sur les autres), pas de sa propre declaration. Mentir ne change pas cette externalite reelle, d’ou l’incitativite.
VCG est efficace (allocation optimale en bien-etre social) et incitatif (veracite est un equilibre dominant) sur tout domaine des valuations. Pourtant, ce n’est pas un mecanisme parfait : en presence de fortes complementarites entre objets, VCG souffre de pathologies que les encheres combinatoires ascendantes (Ausubel-Milgrom) corrigent.
Intuition : on s’attendrait a ce qu’ajouter un enchérisseur augmente le revenu du vendeur (plus de concurrence). Avec VCG combinatoire et des complementarites, c’est l’inverse qui se produit : ajouter un agent peut faire chuter le revenu, tout en augmentant le bien-etre social.
Reference : Conitzer & Sandholm (2006), Failures of the VCG Mechanism in Combinatorial Auctions.
Cette section est la demonstration Python du contre-exemple formellement prouve dans
game_theory_lean/SocialChoice/MechanismDesign.lean(theoremevcg_revenue_non_monotone).
On definit une enchere combinatoire ou chaque agent exprime une valuation par sous-ensemble d’objets (pas seulement par objet individuel). L’agent 1 a une complementarite forte : A et B ensemble valent 10 pour lui, mais isoles valent 0 (il veut les DEUX ou rien). Les agents 2 et 3 sont des singletons : l’un veut seulement A, l’autre seulement B.
| Setting | Agent 1 (bundle AB) | Agent 2 (objet A) | Agent 3 (objet B) |
|---|---|---|---|
| 2 enchérisseurs | present | present | absent |
| 3 enchérisseurs | present | present | present |
# VCG combinatoire : valuations par sous-ensemble d'objets.
# Les objets sont {A, B}. Une allocation est un couple (oA, oB) donnant
# l'indice de l'agent qui recoit A et celui qui recoit B.
from itertools import product
def vcg_combinatorial(bidders):
"""
bidders: dict {idx: callable(subset) -> valuation}.
subset est un frozenset d'indices d'objets (0=A, 1=B).
Retourne (allocation_opt, payments, sw_opt).
Modele Conitzer-Sandholm : oA,oB parcourent TOUS les indices d'agent
(un agent absent peut 'tenir' un objet mais sa valuation n'est pas
comptee dans le welfare-without — cf formalisation Lean
MechanismDesign.lean, maxSW2_without1).
"""
n = len(bidders)
indices = list(range(n))
def bundle_of(oA, oB, i):
"""Sous-ensemble d'objets recu par l'agent i dans l'alloc (oA, oB)."""
s = []
if oA == i: s.append(0)
if oB == i: s.append(1)
return frozenset(s)
def total_welfare(oA, oB):
return sum(bidders[i](bundle_of(oA, oB, i)) for i in indices)
def welfare_of(oA, oB, keep):
"""Welfare d'un sous-ensemble d'agents 'keep' pour l'alloc (oA, oB)."""
return sum(bidders[i](bundle_of(oA, oB, i)) for i in keep)
best = max(product(indices, repeat=2), key=lambda t: total_welfare(*t))
sw_opt = total_welfare(*best)
payments = {}
for i in indices:
others = [j for j in indices if j != i]
# maxSW sans i : on re-optimise l'allocation en ne comptant que 'others'.
# L'agent absent peut toujours 'tenir' un objet (contribution 0 au welfare).
sw_without = max(welfare_of(oA, oB, others) for oA in indices for oB in indices)
w_others_in_opt = welfare_of(*best, others)
payments[i] = sw_without - w_others_in_opt
return best, payments, sw_opt
# --- Setting a 2 enchérisseurs ---
# Agent 0 : complementarite. v({A,B}) = 10, sinon 0.
v1 = lambda s: 10 if s == frozenset({0, 1}) else 0
# Agent 1 : veut seulement A. v({A}) = 8.
v2 = lambda s: 8 if s == frozenset({0}) else 0
alloc2, pay2, sw2 = vcg_combinatorial({0: v1, 1: v2})
revenue2 = sum(pay2.values())
print("=== 2 enchérisseurs {1 (bundle AB), 2 (objet A)} ===")
print(f" Allocation optimale : A -> agent {alloc2[0]}, B -> agent {alloc2[1]}")
print(f" Bien-etre social : {sw2}")
print(f" Paiements VCG : {pay2}")
print(f" Revenu du vendeur : {revenue2}")
# --- Setting a 3 enchérisseurs : on AJOUTE l'agent 3 (veut B) ---
v3 = lambda s: 8 if s == frozenset({1}) else 0 # veut seulement B
alloc3, pay3, sw3 = vcg_combinatorial({0: v1, 1: v2, 2: v3})
revenue3 = sum(pay3.values())
print("\n=== 3 enchérisseurs (+ agent 3 veut B) ===")
print(f" Allocation optimale : A -> agent {alloc3[0]}, B -> agent {alloc3[1]}")
print(f" Bien-etre social : {sw3}")
print(f" Paiements VCG : {pay3}")
print(f" Revenu du vendeur : {revenue3}")
print("\n" + "="*60)
print(f"BIEN-ETRE : 2 agents = {sw2} -> 3 agents = {sw3} ({'hausse' if sw3 > sw2 else 'baisse'})")
print(f"REVENU : 2 agents = {revenue2} -> 3 agents = {revenue3} ({'hausse' if revenue3 > revenue2 else 'BAISSE !'})")
assert sw3 > sw2, "le bien-etre doit monter"
assert revenue3 < revenue2, "le revenu doit chuter (Conitzer-Sandholm)"
print("\nVCG n'est PAS monotone en revenu : prouve.")=== 2 enchérisseurs {1 (bundle AB), 2 (objet A)} ===
Allocation optimale : A -> agent 0, B -> agent 0
Bien-etre social : 10
Paiements VCG : {0: 8, 1: 0}
Revenu du vendeur : 8
=== 3 enchérisseurs (+ agent 3 veut B) ===
Allocation optimale : A -> agent 1, B -> agent 2
Bien-etre social : 16
Paiements VCG : {0: 0, 1: 2, 2: 2}
Revenu du vendeur : 4
============================================================
BIEN-ETRE : 2 agents = 10 -> 3 agents = 16 (hausse)
REVENU : 2 agents = 8 -> 3 agents = 4 (BAISSE !)
VCG n'est PAS monotone en revenu : prouve.Le paradoxe de Conitzer-Sandholm se manifeste ici en chiffres concrets :
| Quantite | 2 enchérisseurs | 3 enchérisseurs | Variation |
|---|---|---|---|
| Bien-etre social | 10 (agent 1 prend AB) | 16 (agents 2+3 prennent A,B) | +60% |
| Revenu du vendeur | 8 | 4 | -50% |
Pourquoi le revenu chute :
Lecon : VCG fait payer chaque agent selon son externalite marginale, mais avec des complementarites, cette externalite peut devenir tres faible meme quand l’agent contribue beaucoup au bien-etre global. Le vendeur encaisse alors moins qu’avec moins d’enchérisseurs.
Lien avec la formalisation Lean : le theoreme
vcg_revenue_non_monotone : revenue3 < revenue2dansMechanismDesign.leanprouve ce meme resultat sur le domaine fini (17 lemmes viadecide, 0 sorry). La demonstration Python ci-dessus en est la version executable pedagogique.
La section 4.5 vient de montrer que VCG peut perdre en efficacite (revenu non monotone, Conitzer-Sandholm 2006). Ce resultat est une pathologie : on observe un mecanisme truth-telling qui fait moins bien que d’autres alternatives en presence de complementarites.
Mais que se passe-t-il quand un agent devie de son equilibre ? Si le mecanisme etait concu en sachant que certains agents ne jouent pas leur manipulation optimale (erreur de calcul, biais cognitif, ou simplement byzantinisme), peut-on faire mieux que tout mecanisme truthful ?
Reference : Othman & Sandholm (2009), Better with Byzantine: Manipulation-Optimal Mechanisms, SAGT 2009. (Oui, c’est encore Conitzer et Sandholm : la “manipulation optimality” avait ete introduite par Conitzer & Sandholm [2006 EC “Computing the Optimal Strategy to Commit To”], mais c’est l’article SAGT 2009 qui la formalise comme concept de comparaison avec les mecanismes truthful.)
Le concept (Definition 6, MOM stricte) : un mecanisme manipulable \(\hat{M}\) est strictement manipulation-optimal (strict MOM) si : 1. Aucune mecanisme truthful ne Pareto-domine \(\hat{M}\) quand tous les agents jouent optimalement (egalite sur les profils joues a l’equilibre). 2. Pour tout outcome \(\hat{o}\) qui peut apparaitre quand un agent devie de son equilibre, l’utilite du concepteur \(\mathcal{M}(\hat{o}) > \mathcal{M}(o^*)\) (l’utilite a l’equilibre optimal).
Dit autrement : on accepte de perdre un peu quand tous jouent rationnel, pour gagner systematiquement des qu’un seul agent fait une erreur.
Enonce : il existe des strict MOM multi-agents avec objectif de bien-etre social. Construction : 2 agents row et column, chacun a 2 types (\(a\) ou \(a'\)). Le mecanisme mappe les 4 profils de rapport sur 4 outcomes \(o_1, o_2, o_3, o_4\) :
colonne rapporte
a' a
row a' o_1 o_2
rapporte
a o_3 o_4Les utilites sont :
| Outcome | \(u_\text{row}^a\) | \(u_\text{row}^{a'}\) | \(u_\text{col}^a\) | \(u_\text{col}^{a'}\) |
|---|---|---|---|---|
| \(o_1\) | 1 | 3 | 1 | 4 |
| \(o_2\) | 4 | 5 | 0 | 0 |
| \(o_3\) | 0 | 0 | 3 | 6 |
| \(o_4\) | 3 | 0 | 0 | 0 |
Observation cle : rapporter \(a'\) est une strategie strictement dominante pour les deux types des deux agents (chaque agent gagne plus a rapporter \(a'\) quel que soit le rapport de l’autre). Par le principe de revelation, on peut “boxer” ce mecanisme en un mecanisme truthful \(M_1\) qui choisit systematiquement \(o_1\). Mais quand un agent de type \(a\) joue \(a\) au lieu de \(a'\), le bien-etre social de l’outcome produit est strictement superieur a celui de \(o_1\) – peu importe le rapport de l’autre agent.
# Proposition 6 d'Othman-Sandholm (SAGT 2009), construction explicite.
# 2 agents x 2 types -> 4 outcomes o1, o2, o3, o4.
# Utilites par (outcome, type d'agent). Lignes = type row, colonnes = type column.
# Symetrie : row et column jouent le meme role structurel.
u_row = {
"o1": {"a": 1, "a'": 3},
"o2": {"a": 4, "a'": 5},
"o3": {"a": 0, "a'": 0},
"o4": {"a": 3, "a'": 0},
}
u_col = {
"o1": {"a": 1, "a'": 4},
"o2": {"a": 0, "a'": 0},
"o3": {"a": 3, "a'": 6},
"o4": {"a": 0, "a'": 0},
}
outcomes = ["o1", "o2", "o3", "o4"]
# Vrai profil de types : (theta_row, theta_col)
true_profiles = [(tr, tc) for tr in ("a", "a'") for tc in ("a", "a'")]
print("Bien-etre social SW(o | theta_row, theta_col) = u_row(o|theta_row) + u_col(o|theta_col)")
print(f"{'Outcome':<8}", end="")
for tr, tc in true_profiles:
print(f" {tr},{tc} ", end="")
print()
mom_outcome = "o1" # outcome du mecanisme M_1 (boxed truthful = MOM)
sw_at_mom = {}
for o in outcomes:
row = f"{o:<8}"
for tr, tc in true_profiles:
sw = u_row[o][tr] + u_col[o][tc]
sw_at_mom[(o, tr, tc)] = sw
row += f" {sw:>4} "
print(row)
# Verification Caracteristique 2 du strict MOM :
# pour chaque profil de types, l'outcome non-M_1 avec SW > SW(o1) doit exister.
print("\nVerification Caracteristique 2 (strict MOM) :")
for tr, tc in true_profiles:
sw_o1 = sw_at_mom[("o1", tr, tc)]
better = [o for o in outcomes if sw_at_mom[(o, tr, tc)] > sw_o1]
print(f" Profil ({tr},{tc}) : SW(o1) = {sw_o1}, outcomes > SW(o1) : {better}")Bien-etre social SW(o | theta_row, theta_col) = u_row(o|theta_row) + u_col(o|theta_col)
Outcome a,a a,a' a',a a',a'
o1 2 5 4 7
o2 4 4 5 5
o3 3 6 3 6
o4 3 3 0 0
Verification Caracteristique 2 (strict MOM) :
Profil (a,a) : SW(o1) = 2, outcomes > SW(o1) : ['o2', 'o3', 'o4']
Profil (a,a') : SW(o1) = 5, outcomes > SW(o1) : ['o3']
Profil (a',a) : SW(o1) = 4, outcomes > SW(o1) : ['o2']
Profil (a',a') : SW(o1) = 7, outcomes > SW(o1) : []Resultat : des qu’un agent byzantin apparait (3 des 4 profils – tous sauf \((a', a')\)), il existe au moins un outcome different de \(o_1\) dont le bien-etre social depasse \(SW(o_1)\). (Le profil sans byzantin \((a', a')\) fait exception : \(o_1\) y est optimal.) Concretement :
C’est la Caracteristique 2 du strict MOM : des qu’un agent byzantin (joue \(a\) au lieu de \(a'\)) apparait, le mecanisme beneficie d’un outcome strictement meilleur. Le “mieux avec Byzantine” est realise.
Pourquoi ne pas simplement choisir l’outcome optimal pour le bien-etre social ? Reponse : on perdrait la propriete que le mecanisme \(M_1\) est truthful (strategie dominante \(a'\)). Le tableau \(SW\) montre que \(o_1\) est optimal pour le profil \((a', a')\), mais pas pour les autres – donc \(M_1\) n’est pas optimal en bien-etre social. C’est une degradation assumee.
Argument formel (sketch) : soit \(M_D\) un mecanisme truthful qui Pareto-domine \(M_1\). Alors \(M_D(a', a') = o_1\) (sinon il ne dominerait pas \(M_1\) sur ce profil). Mais si \(M_D(a, a') = o_3\) (le SW-optimal pour ce profil), l’agent row de type \(a\) aurait interet a rapporter \(a'\) pour forcer \(o_1\), ce qui contredit la truthfulness. Le seul mecanisme truthful compatible avec ces contraintes est \(M_D = M_1\) : \(M_1\) est Pareto-indomine.
Lien pedagogique avec VCG (section 4.5) : VCG est truthful par construction, donc son outcome depend des rapports ; il maximise le bien-etre social quand tous les agents sont truthful. Mais VCG n’a aucune propriete “byzantine-friendly” – il optimise, il ne gagne pas plus quand un agent fait une erreur. Le concept de MOM est orthogonal : il accepte de payer un cout en bien-etre sur les profils “tout-byzantin-joue-optimal” pour gagner quand un byzantin apparait.
Voir aussi : Issue CoursIA #1469 Track 3 (“Sandholm references : << Better with Byzantine >> – enonce fini”). La formalisation Lean (Track 2) est livree : prop6_strict_mom dans game_theory_lean/SocialChoice/MechanismDesign.lean prouve la construction par decide sur le domaine fini 2x2 (dominance stricte de rapporter a’ + caracteristique 2), avec la table SW de la page 9 verifiee ligne par ligne (issue #12329).
Nous allons maintenant implementer l’algorithme de Gale-Shapley pour le problème du mariage stable.
Algorithme de Deferred Acceptance : 1. Initialiser tous les hommes comme “libres” 2. Tant qu’il y a des hommes libres : - Un homme libre propose a sa femme preferee restante - Si elle est libre, elle accepte temporairement - Si elle est fiancee, elle compare et garde le meilleur 3. Retourner l’appariement final
Proprietes a verifier : - Stabilite : aucune paire bloquante - Optimalite pour les proposants (hommes) - Asymetrie : qui propose impacte le résultat
def gale_shapley(men_preferences: Dict[str, List[str]],
women_preferences: Dict[str, List[str]]) -> Dict[str, str]:
"""
Algorithme de Gale-Shapley (Deferred Acceptance).
men_preferences[m] = liste ordonnee des femmes preferees par m
women_preferences[w] = liste ordonnee des hommes preferes par w
Retourne un dictionnaire {homme: femme}.
"""
# Copie des preferences pour modification
remaining_prefs = {m: list(prefs) for m, prefs in men_preferences.items()}
# Etat courant
free_men = list(men_preferences.keys())
engaged = {} # femme -> homme
# Fonction pour comparer les preferences des femmes
def prefers(woman, m1, m2):
"""Retourne True si woman prefere m1 a m2."""
prefs = women_preferences[woman]
return prefs.index(m1) < prefs.index(m2)
iteration = 0
while free_men:
iteration += 1
man = free_men[0]
if not remaining_prefs[man]:
# Plus personne a proposer
free_men.pop(0)
continue
# L'homme propose a sa femme preferee restante
woman = remaining_prefs[man].pop(0)
if woman not in engaged:
# Femme libre, accepte temporairement
engaged[woman] = man
free_men.pop(0)
elif prefers(woman, man, engaged[woman]):
# Femme prefere le nouveau, rejette l'ancien
old_man = engaged[woman]
engaged[woman] = man
free_men.pop(0)
free_men.append(old_man)
# Sinon, la femme garde son fiance actuel (rejection implicite)
# Inverser pour avoir homme -> femme
matching = {m: w for w, m in engaged.items()}
return matching
def is_stable_matching(matching: Dict[str, str],
men_prefs: Dict[str, List[str]],
women_prefs: Dict[str, List[str]]) -> bool:
"""
Verifie si un appariement est stable.
Un appariement est instable s'il existe un couple (m, w) qui n'est pas
marie mais qui se prefere mutuellement a leurs partenaires actuels.
"""
# Inverser le matching
reverse_matching = {w: m for m, w in matching.items()}
for m, w_current in matching.items():
m_prefs = men_prefs[m]
# Femmes que m prefere a sa partenaire actuelle
better_women = m_prefs[:m_prefs.index(w_current)]
for w in better_women:
w_prefs = women_prefs[w]
w_current_man = reverse_matching.get(w)
# Si w prefere aussi m a son partenaire actuel
if w_current_man is None or w_prefs.index(m) < w_prefs.index(w_current_man):
return False # Paire bloquante trouvee
return True
# Exemple
print("Algorithme de Gale-Shapley (Matching Stable)")
print("="*60)
men_preferences = {
'A': ['X', 'Y', 'Z'],
'B': ['Y', 'X', 'Z'],
'C': ['Y', 'Z', 'X']
}
women_preferences = {
'X': ['B', 'A', 'C'],
'Y': ['A', 'B', 'C'],
'Z': ['A', 'B', 'C']
}
print("\nPreferences des hommes:")
for m, prefs in men_preferences.items():
print(f" {m}: {' > '.join(prefs)}")
print("\nPreferences des femmes:")
for w, prefs in women_preferences.items():
print(f" {w}: {' > '.join(prefs)}")
# Execution
matching = gale_shapley(men_preferences, women_preferences)
print(f"\nAppariement (hommes proposent):")
for m, w in sorted(matching.items()):
print(f" {m} <-> {w}")
print(f"\nStabilite: {is_stable_matching(matching, men_preferences, women_preferences)}")Algorithme de Gale-Shapley (Matching Stable)
============================================================
Preferences des hommes:
A: X > Y > Z
B: Y > X > Z
C: Y > Z > X
Preferences des femmes:
X: B > A > C
Y: A > B > C
Z: A > B > C
Appariement (hommes proposent):
A <-> X
B <-> Y
C <-> Z
Stabilite: TrueL’algorithme de Gale-Shapley produit l’appariement stable optimal pour les proposants (ici les hommes).
Analyse de l’exemple :
| Homme | Partenaire obtenue | Rang dans ses préférences |
|---|---|---|
| A | X | 1er choix |
| B | Y | 1er choix |
| C | Z | 2eme choix |
Les hommes A et B obtiennent leur premier choix, tandis que C doit se “contenter” de son deuxieme choix (Z au lieu de Y).
Verification de stabilite : L’appariement est stable car aucune paire (homme, femme) non mariee ne se prefere mutuellement. Par exemple : - C prefererait Y, mais Y est avec B qu’elle prefere a C - Aucune “paire bloquante” n’existe
Point cle : La stabilite garantit qu’aucun participant ne peut ameliorer sa situation par une deviation bilaterale. C’est une propriete fondamentale pour l’acceptabilite du mécanisme.
Objectif : Implementer une fonction qui compte les paires bloquantes dans un matching. Verifier que le résultat de Gale-Shapley a 0 paires bloquantes (matching stable) et qu’un matching aleatoire en a > 0.
Contexte : La stabilite d’un matching se mesure par l’absence de paires bloquantes. Gale-Shapley garantit la stabilite.
def exercice_count_blocking_pairs(matching: dict, men_pref: dict, women_pref: dict) -> int:
"""
Compte les paires bloquantes dans un matching.
Args:
matching: dict {man: woman}
men_pref: dict {man: [ordered list of women]}
women_pref: dict {woman: [ordered list of men]}
Returns:
Nombre de paires bloquantes
"""
return 0 # TODO etudiant
# Test avec les preferences de l'exemple Gale-Shapley
men_pref_test = {"A": ["X", "Y", "Z"], "B": ["Y", "X", "Z"], "C": ["X", "Y", "Z"]}
women_pref_test = {"X": ["B", "A", "C"], "Y": ["A", "B", "C"], "Z": ["A", "B", "C"]}
# Matching stable (Gale-Shapley)
gs_matching = gale_shapley(men_pref_test, women_pref_test)
stable_count = exercice_count_blocking_pairs(gs_matching, men_pref_test, women_pref_test)
print(f"Gale-Shapley matching: {gs_matching}, paires bloquantes: {stable_count}")
# Matching instable (aleatoire)
unstable_matching = {"A": "Z", "B": "X", "C": "Y"}
unstable_count = exercice_count_blocking_pairs(unstable_matching, men_pref_test, women_pref_test)
print(f"Matching instable: {unstable_matching}, paires bloquantes: {unstable_count}")
print("Exercice a completer")Gale-Shapley matching: {'A': 'X', 'B': 'Y', 'C': 'Z'}, paires bloquantes: 0
Matching instable: {'A': 'Z', 'B': 'X', 'C': 'Y'}, paires bloquantes: 0
Exercice a completer# Comparaison : hommes vs femmes proposent
print("Comparaison : Qui propose?")
print("="*60)
# Hommes proposent (deja calcule)
matching_men_propose = matching
# Femmes proposent (inverser les roles)
# gale_shapley retourne {proposeur: accepteur}
# Quand les femmes proposent: retourne {femme: homme}
matching_women_raw = gale_shapley(women_preferences, men_preferences)
# Inverser pour avoir {homme: femme}
matching_women_propose = {m: w for w, m in matching_women_raw.items()}
print(f"{'Homme':<8} {'Femme (H propose)':<20} {'Femme (F propose)'}")
print("-"*50)
for m in sorted(men_preferences.keys()):
w1 = matching_men_propose.get(m, '-')
w2 = matching_women_propose.get(m, '-')
print(f"{m:<8} {w1:<20} {w2}")
# Calculer le rang moyen
def average_rank(matching, preferences):
"""
Rang moyen du partenaire obtenu (1 = premier choix).
matching: {agent: partenaire}
preferences: {agent: [liste ordonnee de partenaires]}
"""
total_rank = 0
for agent, partner in matching.items():
prefs = preferences[agent]
rank = prefs.index(partner) + 1
total_rank += rank
return total_rank / len(matching)
print(f"Rang moyen des partenaires (1 = premier choix):")
# Hommes proposent: matching_men_propose = {homme: femme}
# Rang hommes: chaque homme obtient quelle femme dans son classement?
print(f" Hommes proposent -> Rang moyen hommes: {average_rank(matching_men_propose, men_preferences):.2f}")
# Rang femmes: on inverse pour avoir {femme: homme} et utiliser women_preferences
matching_inv_men = {w: m for m, w in matching_men_propose.items()}
print(f" Hommes proposent -> Rang moyen femmes: {average_rank(matching_inv_men, women_preferences):.2f}")
# Femmes proposent
if matching_women_propose:
# matching_women_propose = {homme: femme}
# Rang hommes: chaque homme obtient quelle femme dans son classement?
print(f" Femmes proposent -> Rang moyen hommes: {average_rank(matching_women_propose, men_preferences):.2f}")
# Rang femmes: matching_women_raw = {femme: homme}
print(f" Femmes proposent -> Rang moyen femmes: {average_rank(matching_women_raw, women_preferences):.2f}")
print(f"=> Les proposants obtiennent un meilleur resultat!")Comparaison : Qui propose?
============================================================
Homme Femme (H propose) Femme (F propose)
--------------------------------------------------
A X Y
B Y X
C Z Z
Rang moyen des partenaires (1 = premier choix):
Hommes proposent -> Rang moyen hommes: 1.33
Hommes proposent -> Rang moyen femmes: 2.33
Femmes proposent -> Rang moyen hommes: 2.00
Femmes proposent -> Rang moyen femmes: 1.67
=> Les proposants obtiennent un meilleur resultat!Cette comparaison illustre l’asymetrie de pouvoir dans Gale-Shapley : les proposants (ceux qui font les offres) obtiennent systematiquement un meilleur résultat.
Comparaison des appariements :
| Homme | Si H proposent | Si F proposent | Différence |
|---|---|---|---|
| A | X | Y | 1er vs 2e choix |
| B | Y | X | 1er vs 2e choix |
| C | Z | Z | Identique |
Analyse quantitative (rang moyen, 1 = meilleur) :
| Scénario | Rang hommes | Rang femmes | Avantage |
|---|---|---|---|
| Hommes proposent | 1.33 | 2.33 | Hommes |
| Femmes proposent | 2.00 | 1.67 | Femmes |
Intuition economique : - Les proposants ont l’initiative et peuvent “attaquer” leur premier choix - Les accepteurs sont en position defensive : ils subissent les propositions - C’est pourquoi les sites de rencontre (Tinder, etc.) donnent un avantage structurel a ceux qui font le premier pas
Application pratique : Cette asymetrie explique pourquoi, dans les marches ou l’un des cotes est “plus actif” (ex : recruteurs vs candidats), le cote proposeur obtient de meilleurs matchs.
Pour les fonctions de choix social (au moins 3 alternatives) : - Si la fonction est non-dictatoriale et surjective - Alors elle n’est pas implementable en stratégie dominante
Pour l’echange bilatéral : impossible d’avoir simultanement : - Efficacite (echange quand \(v_{acheteur} > v_{vendeur}\)) - Incitativite - Rationalite individuelle - Budget balance (pas de subvention externe)
Après avoir etudie plusieurs mécanismes reussis (Vickrey, VCG, Gale-Shapley), nous allons explorer leurs limites fondamentales.
Deux theoremes cle : 1. Gibbard-Satterthwaite : sans paiements, aucun mécanisme non-dictatorial n’est incitatif 2. Myerson-Satterthwaite : dans l’echange bilateral, on ne peut pas avoir simultanement efficacite + IC + IR + budget balance
Ces résultats expliquent pourquoi la conception de mécanismes est difficile : il existe des contraintes mathematiques sur ce qui est possible.
La section 6.1 enonce le theoreme de Gibbard-Satterthwaite : pour toute fonction de choix social sur au moins 3 alternatives, non-dictatoriale et surjective, il existe un profil ou un electeur a interet a mentir sur ses preferences. C’est un resultat d’impossibilite : il ne montre pas comment un electeur manipule, il affirme que l’occasion existe toujours.
Plutot que de l’admettre, nous le verifions computatoirement sur un cas concret : la regle de Borda (non-dictatoriale, surjective, \(\geq 3\) alternatives - donc dans le scope du theoreme). Pour chaque profil sincere de 3 electeurs sur 3 alternatives, nous cherchons par enumeration force brute si un electeur peut, en declarant un bulletin different de ses vraies preferences, faire elire un candidat qu’il prefere au gagnant sincere. Si le theoreme est exact, l’enumeration doit trouver un temoin.
from itertools import permutations
# 3 alternatives, regle de Borda (points m-1 ... 0, ex aequo resolus alphabetiquement).
ALTS = ('A', 'B', 'C')
m = len(ALTS)
def borda_winner(ballots):
score = {a: 0 for a in ALTS}
for ballot in ballots:
for rank, a in enumerate(ballot):
score[a] += (m - 1 - rank)
return max(ALTS, key=lambda a: (score[a], -ord(a)))
def rang(prefs, alt):
"""Position de alt dans prefs (0 = le meilleur)."""
return prefs.index(alt)
def trouver_manipulation(profile, regle):
"""Cherche un electeur qui gagne a mentir. Retourne (electeur, gagnant_sincere, mensonge, nouveau_gagnant) ou None."""
g_sincere = regle(profile)
for i in range(len(profile)):
vraies = profile[i]
for mensonge in permutations(ALTS):
if tuple(mensonge) == vraies:
continue
nouveau_profile = list(profile)
nouveau_profile[i] = tuple(mensonge)
nouveau_g = regle(nouveau_profile)
# l'electeur prefere-t-il strictement nouveau_g au gagnant sincere ?
if rang(vraies, nouveau_g) < rang(vraies, g_sincere):
return (i, vraies, tuple(mensonge), g_sincere, nouveau_g)
return None
toutes_prefs = list(permutations(ALTS))
# [1] Borda (non-dictatorial) : enumeration force brute sur les 6^3 = 216 profils.
print('Gibbard-Satterthwaite - demonstration computatoire')
print('=' * 64)
print('[1] Regle de Borda (non-dictatoriale, surjective, >= 3 alternatives) :')
temoin = None
for profile in permutations(toutes_prefs, 3):
r = trouver_manipulation(profile, borda_winner)
if r:
temoin = (profile, r)
break
if temoin:
profile, (i, vraies, mensonge, gs, gn) = temoin
print(f' Profil sincere : {profile}')
print(f' Gagnant sincere : {gs}')
print(f" L'electeur {i} (prefs vraies {vraies}) declare {mensonge}")
print(f' -> Nouveau gagnant : {gn} (qu\'il prefere a {gs})')
print(' => Borda est MANIPULABLE. Temoin trouve par enumeration des 216 profils.')
else:
print(' Aucune manipulation trouvee.')
# [2] Dictature (l'electeur 0 decide seul) : verifions qu'elle est strategy-proof.
def gagnant_dictature(profile):
return profile[0][0] # le premier choix de l'electeur 0
print()
print('[2] Dictature (l\'electeur 0 decide seul) :')
manip_dict = False
for profile in permutations(toutes_prefs, 3):
if trouver_manipulation(profile, gagnant_dictature):
manip_dict = True
break
print(' Aucune manipulation sur les 216 profils -> la dictature est STRATEGY-PROOF.' if not manip_dict
else ' Manipulation trouvee (!)')
# [3] Synthese : le theoreme en acte.
print()
print('[3] Gibbard-Satterthwaite en acte :')
print(' Borda (non-dictatorial) = manipulable ; Dictature = strategy-proof.')
print(' Sur >= 3 alternatives, les SEULS mecanismes strategy-proof sont dictatoriaux.')Gibbard-Satterthwaite - demonstration computatoire
================================================================
[1] Regle de Borda (non-dictatoriale, surjective, >= 3 alternatives) :
Profil sincere : (('A', 'B', 'C'), ('B', 'A', 'C'), ('C', 'B', 'A'))
Gagnant sincere : B
L'electeur 0 (prefs vraies ('A', 'B', 'C')) declare ('A', 'C', 'B')
-> Nouveau gagnant : A (qu'il prefere a B)
=> Borda est MANIPULABLE. Temoin trouve par enumeration des 216 profils.
[2] Dictature (l'electeur 0 decide seul) :
Aucune manipulation sur les 216 profils -> la dictature est STRATEGY-PROOF.
[3] Gibbard-Satterthwaite en acte :
Borda (non-dictatorial) = manipulable ; Dictature = strategy-proof.
Sur >= 3 alternatives, les SEULS mecanismes strategy-proof sont dictatoriaux.L’enumeration a trouve un temoin de manipulation : avec le profil sincere \((A \succ B \succ C),\ (B \succ A \succ C),\ (C \succ B \succ A)\), Borda elirait B. L’electeur 0, dont les vraies preferences sont \(A \succ B \succ C\), a interet a declarer \(A \succ C \succ B\) : Borda elire alors A, que l’electeur prefere a B. Le mensonge rationnel est recompense - et c’est l’enumeration qui l’a decouvert, non une construction ad hoc.
La deuxieme mesure est le contre-point du theoreme : la dictature (l’electeur 0 decide seul) est strategy-proof - sur les 216 profils, aucun electeur ne peut manipuler. Le dictateur n’a rien a gagner a mentir (son choix sincere gagne deja), et les autres electeurs sont ignores. C’est exactement la conclusion de Gibbard-Satterthwaite : les seules regles strategy-proof sur \(\geq 3\) alternatives sont dictatoriales.
Pourquoi Vickrey et VCG echappent-ils au theoreme ? Parce qu’ils utilisent des transferts monetaires - le theoreme de Gibbard-Satterthwaite porte sur les fonctions de choix social sans paiements. Des qu’on autorise un paiement (l’enchere au second prix, le critere de Clarke), on sort du cadre d’impossibilite et l’incitativite redevient possible. D’ou la section 6.2 : les mecanismes VCG sont l’exception qui confirme la regle.
Lien avec la formalisation Lean : la parente formelle est le theoreme d’impossibilite d’Arrow (formalise dans game_theory_lean/SocialChoice/), dont Gibbard-Satterthwaite est le pendant strategique - Arrow = l’aggregation honnete est impossible ; Gibbard-Satterthwaite = l’aggregation truthful (incitative) est impossible. Les deux borneent ce qu’un concepteur de mecanisme peut atteindre sans transferts.
# Illustration : Probleme d'echange bilateral
print("Theoreme de Myerson-Satterthwaite : Echange Bilateral")
print("="*60)
class BilateralExchange:
"""
Mecanisme d'echange entre un vendeur et un acheteur.
Vendeur a valuation v_s (cout de renonciation)
Acheteur a valuation v_b
Echange efficient si v_b > v_s
"""
def __init__(self, mechanism_type: str = 'double_auction'):
self.mechanism_type = mechanism_type
def run(self, v_seller: float, v_buyer: float) -> Tuple[bool, float, float]:
"""
Execute le mecanisme.
Retourne (echange_a_lieu, paiement_vendeur_recoit, paiement_acheteur_paie).
"""
if self.mechanism_type == 'double_auction':
# Prix = moyenne des reports
# Echange si offre acheteur >= demande vendeur
if v_buyer >= v_seller:
price = (v_buyer + v_seller) / 2
return True, price, price
return False, 0, 0
elif self.mechanism_type == 'vcg_like':
# Tentative VCG (non budget-balanced)
# Echange efficient
if v_buyer >= v_seller:
# Acheteur paie la valuation du vendeur
# Vendeur recoit la valuation de l'acheteur
return True, v_buyer, v_seller
return False, 0, 0
return False, 0, 0
def is_ic(self, v_s_true: float, v_b_true: float) -> Tuple[bool, bool]:
"""
Verifie l'incitativite pour vendeur et acheteur.
"""
# Test pour le vendeur
ic_seller = True
trade_true, pay_s_true, _ = self.run(v_s_true, v_b_true)
utility_s_true = pay_s_true - (v_s_true if trade_true else 0)
# Seuil de trade pour le report du vendeur = valuation de l'acheteur (v_b_true) :
# le vendeur veut sur-encherir juste sous v_b_true pour rester dans l'echange.
for v_s_lie in [0, v_s_true * 0.5, v_s_true * 1.5, v_s_true * 2, 100,
v_b_true - 0.01, v_b_true]:
trade_lie, pay_s_lie, _ = self.run(v_s_lie, v_b_true)
utility_s_lie = pay_s_lie - (v_s_true if trade_lie else 0)
if utility_s_lie > utility_s_true + 0.01:
ic_seller = False
break
# Test pour l'acheteur
ic_buyer = True
trade_true, _, pay_b_true = self.run(v_s_true, v_b_true)
utility_b_true = (v_b_true if trade_true else 0) - pay_b_true
# Seuil de trade pour le report de l'acheteur = valuation du vendeur (v_s_true) :
# l'acheteur veut sous-encherir juste au-dessus de v_s_true pour baisser le prix.
for v_b_lie in [0, v_b_true * 0.5, v_b_true * 1.5, v_b_true * 2, 100,
v_s_true, v_s_true + 0.01]:
trade_lie, _, pay_b_lie = self.run(v_s_true, v_b_lie)
utility_b_lie = (v_b_true if trade_lie else 0) - pay_b_lie
if utility_b_lie > utility_b_true + 0.01:
ic_buyer = False
break
return ic_seller, ic_buyer
# Comparaison des mecanismes
print("\nScenario: Vendeur (v=30), Acheteur (v=50)")
print("Echange efficient: Oui (50 > 30)\n")
v_s, v_b = 30, 50
for mech_type in ['double_auction', 'vcg_like']:
exchange = BilateralExchange(mech_type)
trade, pay_s, pay_b = exchange.run(v_s, v_b)
print(f"Mecanisme: {mech_type}")
print(f" Echange: {trade}")
if trade:
print(f" Vendeur recoit: {pay_s:.2f}, Acheteur paie: {pay_b:.2f}")
print(f" Budget balance: {abs(pay_s - pay_b) < 0.01}")
utility_s = pay_s - v_s
utility_b = v_b - pay_b
print(f" Utilite vendeur: {utility_s:.2f}, Utilite acheteur: {utility_b:.2f}")
ic_s, ic_b = exchange.is_ic(v_s, v_b)
print(f" IC vendeur: {ic_s}, IC acheteur: {ic_b}")
print()Theoreme de Myerson-Satterthwaite : Echange Bilateral
============================================================
Scenario: Vendeur (v=30), Acheteur (v=50)
Echange efficient: Oui (50 > 30)
Mecanisme: double_auction
Echange: True
Vendeur recoit: 40.00, Acheteur paie: 40.00
Budget balance: True
Utilite vendeur: 10.00, Utilite acheteur: 10.00
IC vendeur: False, IC acheteur: False
Mecanisme: vcg_like
Echange: True
Vendeur recoit: 50.00, Acheteur paie: 30.00
Budget balance: False
Utilite vendeur: 20.00, Utilite acheteur: 20.00
IC vendeur: True, IC acheteur: True
Nous allons illustrer le theoreme de Myerson-Satterthwaite avec un scénario simple : un vendeur et un acheteur.
Scénario : - Vendeur : valuation \(v_s = 30\) (cout d’opportunite) - Acheteur : valuation \(v_b = 50\) (valeur du bien) - Echange efficient : oui (50 > 30, gain de 20 a realiser)
Deux mécanismes a comparer : 1. Double enchere : prix = moyenne des offres, echange si \(v_b \geq v_s\) 2. VCG-like : chaque agent paie/recoit l’externalite
Nous allons tester l’incitativite et le budget balance pour chacun.
Cette expérience illustre le theoreme de Myerson-Satterthwaite : aucun mécanisme ne peut satisfaire simultanement toutes les proprietes desirees.
Comparaison des mécanismes (vendeur v=30, acheteur v=50) :
| Mécanisme | Echange | Budget Balance | IC vendeur | IC acheteur | Verdict |
|---|---|---|---|---|---|
| Double enchere | Oui | Oui (40=40) | Non | Non | Echec IC |
| VCG-like | Oui | Non (50≠30) | Oui | Oui | Echec BB |
Analyse du double auction (prix = moyenne des offres) : - Le vendeur a intérêt a sur-encherir (declarer v > 30) pour augmenter le prix - L’acheteur a intérêt a sous-encherir (declarer v < 50) pour reduire le prix - Résultat : pas d’equilibre veridique, le mécanisme n’est pas IC
Analyse du VCG-like (paiements externalites) : - Echange efficient : oui (50 > 30) - Incitativite : oui (les deux disent la verite) - MAIS : deficit de 20 (50 - 30) qui doit etre finance par l’exterieur
Conclusion : Le “triangle impossible” de l’echange bilateral - on ne peut avoir efficacite + IC + IR + budget balance. Tout mécanisme fait un compromis.
Implementez une enchere “all-pay” ou tous les encherisseurs paient leur offre (même les perdants). Montrez que ce n’est pas incitatif.
Implementez le mécanisme de Clarke pour le financement d’un bien public.
Montrez qu’une femme peut ameliorer son résultat en mentant sur ses préférences.
Etendez le VCG aux encheres ou les agents ont des valuations pour des combinaisons d’objets (complementarites/substituts).
# Espace pour les exercices
# Exercice 1 : Enchere All-Pay
class AllPayAuction(Mechanism):
"""Enchere all-pay : tous paient leur offre."""
def allocate(self, reports: List[float]) -> List[float]:
# TODO: Implementer l'allocation
# Le plus offrant gagne (allocation = 1.0), les autres ont 0.0
# Indice: utiliser np.argmax(reports) pour trouver le gagnant
pass
def compute_payments(self, reports: List[float],
allocations: List[float]) -> List[float]:
# TODO: Implementer les paiements
# Dans une enchere all-pay, TOUS les participants paient leur offre
# (pas seulement le gagnant)
pass
# Test incitativite (decommentez apres implementation)
# print("Exercice 1 : Enchere All-Pay")
# print("="*50)
# apa = AllPayAuction()
# agents_test = [Agent(0, 100), Agent(1, 80), Agent(2, 60)]
# print(f"IC: {apa.is_ic(agents_test)}")
# print("-> All-pay n'est pas incitatif (on veut encherir juste au-dessus de l'adversaire)")
print("Exercice a completer")Exercice a completerLes quatre exercices proposent d’explorer des extensions ou variantes des mécanismes etudies.
Progression : 1. Exercice 1 (All-Pay) : un format d’enchere non-incitatif courant en politique (lobbying, campagnes electorales) 2. Exercice 2 (Biens publics) : application du mécanisme de Clarke (cas particulier de VCG) 3. Exercice 3 (Manipulation GS) : montrer que les accepteurs peuvent beneficier a mentir (contrairement aux proposants) 4. Exercice 4 (Combinatoire) : extension aux cas ou les agents ont des préférences sur des combinaisons d’objets
Ces exercices consolident votre comprehension des concepts d’incitativite, d’efficacite et des limites fondamentales.
| Mécanisme | Allocation | Paiement | IC? |
|---|---|---|---|
| 1er prix | Max bid | Son bid | Non |
| 2nd prix (Vickrey) | Max bid | 2e bid | Oui |
| VCG | Maximise SW | Externalite | Oui |
| Gale-Shapley | Stable | - | Pour proposants |
Papiers fondateurs de la théorie des mécanismes, cités dans ce notebook :
Notebook suivant : GameTheory-17-MultiAgent-RL-Python - Apprentissage multi-agent et self-play
Lien avec la formalisation Lean : L’incitativite de l’enchere de Vickrey est prouvee formellement dans
game_theory_lean/SocialChoice/MechanismDesign.lean(0 sorry). On y trouve la fonction d’utilite pour 2 et 3 encherisseurs, les theoremesvickrey_truthful_bidder0/1(stratégie dominante de verite) prouves paromega+split_ifs, et le contre-exemplefirst_price_not_truthfulprouve parnative_decide. Le notebook s’inscrit dans la serie Lean du choix social (game_theory_lean/SocialChoice/) qui formalise également les theoremes d’Arrow (0 sorry), de Sen (0 sorry) et les méthodes de vote (0 sorry).