\documentclass[8pt]{beamer}
\usepackage[ansinew]{inputenc}
\usepackage{amssymb, color}
\usepackage{graphicx}
\usepackage{beamerthemesplit}
\usepackage[french]{babel}

\title{Elections, inimitiés : deux aspects de l'informatique théorique}
\author{P. Pansu, Université Paris-Sud}
\date{12 avril 2012}

\newtheorem{thm}{Théorème}
\newtheorem{lem}{Lemme}
\newtheorem{prop}[lem]{Proposition}
\newtheorem{cor}[lem]{Corollaire}
\newtheorem{defi}[lem]{Définition}
\newtheorem{rem}[lem]{Remarque}
\newtheorem{nota}[lem]{Notation}
\newtheorem{ques}[lem]{Question}
\newtheorem{obj}[lem]{Objectif}
\newtheorem{prob}[lem]{Problème}
\newtheorem{sol}[lem]{Solution}
\newtheorem{conc}[lem]{Conclusion}
\newtheorem{ex}[lem]{Exemple}
\newtheorem{exs}[lem]{Exemples}
\newtheorem{res}[lem]{Resultats}
\newtheorem{plan}[lem]{Plan de l'exposé}
\newtheorem{preuve}[lem]{Preuve}

\def\proof{\par\medskip\noindent {\bf Preuve}}
\def\qed{~q.e.d.}

\def\R{\mathbb{R}}
\def\B{\{-1,1\}}
\def\texorpdfstring#1#2{#1}

\mode<presentation>{\usetheme{Warsaw}}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\section{Elections}

\subsection{Influences}

\begin{frame}

\includegraphics[width=1.5in]{vote-mjs1.pdf}\hskip.4cm\vbox{\hsize=2.5in

$n=30$ millions d'électeurs votent. Il s'agit de désigner un gagnant parmi deux candidats baptisés $A$ et $B$.

Un \emph{procédé d'agrégation des votes} est une boîte noire à laquelle on fournit les 30 millions de votes individuels et qui répond $A$ ou $B$.}

\begin{ex}
Le {\em dictateur} $Dict$ est le procédé qui consiste à répondre le vote de l'électeur Pansu. 

La {\em majorité} $Maj$ consiste à répondre celui de $A$ ou de $B$ qui a le plus de voix.
\end{ex}\pause

Un procédé d'agrégation devrait avoir les propriétés suivantes.
\begin{enumerate}
  \item Aucun électeur ne joue de rôle prépondérant.
  \item Des erreurs dans le dépouillement des votes ont peu de chances de faire basculer le résultat.
  \item Equilibre : lorsqu'on le teste sur toutes les combinaisons de votes possibles, $A$ sort autant de fois que $B$.
\end{enumerate}

\end{frame}

\subsection{Sensibilité au bruit}

\begin{frame}

\begin{defi}
L'{\em influence} $Inf_i$ du $i$-ème électeur sur le procédé est la probabilité que, lorsque le $i$-ème électeur change d'avis, le résultat change.
\end{defi}


\textbf{Exemples}.
Pour le dictateur, un électeur a une influence de $1$, tous les autres, de $0$. 

Pour la majorité, tous les électeurs ont la même influence, qui vaut 
environ $\frac{2}{\sqrt{\pi n}}$.

\begin{defi}
La {\em sensibilité au $c$-bruit} d'un procédé d'agrégation est la probabilité que, lorsque chaque vote est modifié indépendamment avec probabilité $c$, la valeur de $f$ change.
\end{defi}

\medskip

\textbf{Exemples}.

Pour le dictateur $Dict_i$, $ Sens_c (Dict_i)=c$. Pour la majorité, on montre que
\begin{eqnarray*}
\lim_{n\to\infty}Sens_c (Maj)=\frac{1}{\pi}\arccos(1-2c).
\end{eqnarray*}


\begin{center}
\includegraphics[width=1.5in]{arccos.pdf}
\end{center}

\end{frame}

\subsection{Le Théorème Majority is Stablest}

\begin{frame}

De tous les procédés d'agrégation, la majorité est celui qui satisfait le mieux aux deux critères d'influence et de sensibilité ci-dessus. C'est la substance du Théorème \texttt{(Majority is stablest)}.

\begin{thm}[Mossel, O'Donnell, Oleskiewicz 2005]
Soit $c\in[0,\frac{1}{2}]$. De tous les procédés d'agrégation de votes équilibrés dont les influences sont petites, $Maj$ est celle dont la sensibilité au $c$-bruit est asymptotiquement la plus faible, lorsque $n$ tend vers l'infini. Si $c\in[\frac{1}{2},1]$, $Maj$ a la sensibilité au $c$-bruit la plus forte.
\end{thm}

\medskip

La preuve utilise

- de l'algèbre linéaire,

- de la théorie des groupes finis,

- du calcul des probabilités,

- de l'analyse,

- de la géométrie.

\end{frame}

\section{Inimitiés}
\subsection{Plan de table}

\begin{frame}

Ce soir, je dois recevoir $9$ invités. Je dois les répartir sur deux tables. Je les connais bien, je sais quelle solide inimitié certains éprouvent pour d'autres. Par exemple, je dois absolument éviter de placer L... et M... à la même table. Et de même pour N... et P... Mais il y a trop de couples ennemis. Je vais tout de même chercher un plan de table qui maximise le nombre de couples séparés. \pause 


\begin{center}
\includegraphics[width=3in]{plan_de_table.pdf}
\end{center}

\end{frame}

\begin{frame}

Ce soir, je dois recevoir $9$ invités. Je dois les répartir sur deux tables. Je les connais bien, je sais quelle solide inimitié certains éprouvent pour d'autres. Par exemple, je dois absolument éviter de placer L... et M... à la même table. Et de même pour N... et P... Mais il y a trop de couples ennemis. Je vais tout de même chercher un plan de table qui maximise le nombre de couples séparés. Il y a 13 couples.

\begin{center}
\includegraphics[width=1.5in]{reseau4.pdf}
\end{center}

Les inimitiés constituent un graphe : ici, 9 sommets, 13 arêtes. \pause 
Le plan de table consiste à colorier une partie des sommets. 
L'objectif est d'avoir le plus possible d'arêtes bicolores. 

\end{frame}

\begin{frame}

Ce soir, je dois recevoir $9$ invités. Je dois les répartir sur deux tables. Je les connais bien, je sais quelle solide inimitié certains éprouvent pour d'autres. Par exemple, je dois absolument éviter de placer L... et M... à la même table. Et de même pour N... et P... Mais il y a trop de couples ennemis. Je vais tout de même chercher un plan de table qui maximise le nombre de couples séparés. Il y a 13 couples.

\begin{center}
\includegraphics[width=1.5in]{reseau2.pdf}
\end{center}

Les inimitiés constituent un graphe : ici, 9 sommets, 13 arêtes. Le plan de table consiste à colorier une partie des sommets.
L'objectif est d'avoir le plus possible d'arêtes bicolores. Ici, 9 arêtes bicolores.

\end{frame}

\begin{frame}

Peut-on faire mieux ? \pause

\begin{ques}
Existe-t'il un coloriage donnant plus de 9 arêtes bicolores ?
\end{ques}

\begin{center}
\includegraphics[width=2in]{reseau4.pdf}
\end{center}


\end{frame}

\begin{frame}

Ce plan coupe 9 arêtes. Peut-on faire mieux ? 

\begin{ques}
Existe-t'il un coloriage donnant plus de 9 arêtes bicolores ?
\end{ques}

\begin{center}
\includegraphics[width=2in]{reseau5.pdf}
\end{center}

Oui, 11 arêtes. Mais jamais davantage.
\end{frame}

\begin{frame}

\subsection{La coupe maximale}

\begin{defi}
Soit $G$ un graphe. On appelle coupe maximale$(G)$ le nombre maximal d'arêtes bicolores dans un coloriage de $G$.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de 11.

\begin{center}
\includegraphics[width=2in]{reseau5.pdf}
\end{center}

\end{frame}

\subsection{Le problème MAX CUT}

\begin{frame}

\begin{prob}
MAX CUT : Ecrire un programme d'ordinateur qui, étant donnés un graphe $G$ à $n$ sommets, calcule la coupe maximale de $G$.
\end{prob}\pause

\begin{sol}
Enumérer tous les coloriages, compter les arêtes bicolores. \end{sol}\pause

\textbf{Analyse}: Il est possible qu'il faille $2^n$ opérations. Pour un graphe à $n=90$ sommets (mes amis sur Facebook), ça fait plus de $10^{27}$ opérations. A une fréquence d'horloge de 1 GHz, ça prend 4 milliards d'années.\pause

$2^n$, c'est trop. Il faut trouver un programme qui accomplit la tâche en $n^d$ opérations. Par exemple, si $n=90$, $d=2$, $n^d =8100$ opérations, c'est l'affaire de quelques microsecondes. \pause
\begin{defi}
Lorsque le temps d'éxécution est borné par $c\,n^d$, où $c$ et $d$ sont constants, on dit que le temps d'éxécution est {\em polynômial}.
\end{defi}

\end{frame}


\section{Problème MAX CUT approché}

\begin{frame}

On ignore s'il existe une méthode de résolution de MAX CUT en temps polynômial (problème mis a prix 1000000\$ Par la Clay Foundation).

Puisqu'on ne peut problement pas résoudre exactement le problème MAX CUT, on tente de le résoudre de façon approchée.\pause

\begin{defi}
Soit $\alpha<1$. Une {\em résolution $\alpha$-approchée} de MAX CUT, c'est un programme d'ordinateur qui, étant donné un graphe $G$ à $n$ sommets, trouve en un temps polynômial en $n$, un coloriage dont le nombre d'arêtes bicolores est $\geq \alpha\times$coupe maximale$(G)$. Ce programme a le droit d'effectuer des tirages au hasard. On demande dans ce cas que le score annoncé soit obtenu avec probabilité $\geq \frac{1}{2}$.
\end{defi}\pause

\begin{ex}
Coloriage aléatoire. On tire indépendamment au hasard la couleur de chaque sommet.
\end{ex}\pause
\textbf{Analyse}: Chaque arête a une chance sur deux d'être bicolore. L'espérance du nombre d'arêtes bicolores vaut $\frac{1}{2}\times$nombre d'arêtes $\geq \frac{1}{2}\times$coupe maximale$(G)$. Par symétrie, avec probabilité $\geq \frac{1}{2}$, 
\begin{center}
nombre d'arêtes bicolores $\geq \frac{1}{2}$coupe maximale$(G)$.
\end{center}
Donc il s'agit d'une résolution $\frac{1}{2}$-approchée de MAX CUT.

\end{frame}

\subsection{La méthode de Goemans et Williamson}

\begin{frame}

\begin{thm}[Goemans-Williamson 1995]
Le problème MAX CUT possède une résolution $0.878...$-approchée.
\end{thm}\pause

\includegraphics[width=1in]{Coilspringscleaned.pdf}\hskip.5cm\vbox{\hsize=2.8in
On dessine le graphe sur la sphère unité d'un espace de grande dimension. Les arêtes sont remplacées par des ressorts comprimés. On laisse le graphe atteindre sa position d'équilibre. On admet qu'il y a un algorithme polynômial pour la calculer (il est basé sur l'algèbre linéaire). Elle minimise l'énergie potentielle $\mathcal{E}$.}\pause

L'idée est qu'à tout coloriage correspond une disposition particulière des vecteurs (superposés sur deux points diamétralement opposés), pour laquelle $\mathcal{E}$ est proportionnelle au nombre d'arêtes unicolores. En particulier, $1-\min\mathcal{E}\geq$ coupe maximale.\pause

\includegraphics[width=1.3in]{gw.pdf}\hskip1cm\vbox{\hsize=2in Inversement, on associe un coloriage à la disposition optimale comme suit : on coupe le graphe en deux au moyen d'un plan tiré au hasard.\vskip 1cm}

\end{frame}

\subsection{Le nombre 0.878... est-il le seuil optimal d'approximabilité ?}


\begin{frame}

\begin{rem}[U. Feige, G. Schechtman 2002]
Il existe des graphes pour lesquels la méthode donne une coupe arbitrairement proche de $I\times$coupe maximale.
\end{rem}\pause

\begin{thm}[S. Khot, G. Kindler, E. Mossel, R. O'Donnell 2005]
Sous une hypothèse un peu plus forte que P$\not=$NP, $I=0.8785672057848516...$ est le seuil optimal d'approximabilité pour MAX CUT. Autrement dit, si $\alpha>I$, il n'existe pas de résolution $\alpha$-approchée de MAX CUT.
\end{thm}\pause

\medskip

La preuve est l'aboutissement d'idées qui remontent au grand logicien Kurt Gödel (vérification de preuves, vérification probabiliste de preuves) et repose sur le Théorème \texttt{Majority is Stablest}.

\medskip

Pour en savoir davantage, utiliser les mots clés suivants : semi-definite programming, polynomial time approximation schemes, PCP theorem, Unique Games Conjecture.

\end{frame}

\subsection{Analyse de la méthode de Goemans-Williamson}

\begin{frame}

Calcul du facteur d'approximation (dans le cas d'un graphe à $3$ sommets et $3$ arêtes). 

Les sommets deviennent des vecteurs $v_1$, $v_2$ et $v_3$. La position d'équilibre rend la quantité suivante la plus grande possible
\begin{eqnarray*}
\textrm{SDP}=\frac{1}{2}(1-v_1 \cdot v_2)+\frac{1}{2}(1-v_2 \cdot v_3)+\frac{1}{2}(1-v_3 \cdot v_1).
\end{eqnarray*}\pause


La probabilité que l'arête $v_i v_j$ soit coupée (bicolore) vaut $\frac{1}{\pi}\arccos(v_i \cdot v_j)$. L'espérance du nombre d'arêtes bicolores est
\begin{eqnarray*}
E=\frac{1}{\pi}\arccos(v_1 \cdot v_2)+\frac{1}{\pi}\arccos(v_2 \cdot v_3)+\frac{1}{\pi}\arccos(v_3 \cdot v_1).
\end{eqnarray*}\pause

On constate que 
$E\geq I\times\max SDP\geq I\times$coupe maximale, où
\begin{eqnarray*}
I=\min_{-1\leq x\leq 1}\frac{\frac{1}{\pi}\arccos(x)}{\frac{1}{2}(1-x)}=\min_{0\leq t\leq \pi}\frac{2t}{\pi(1-\cos t)}. 
\end{eqnarray*}
Donc la méthode de Goemans-Williamson est une $I$-approximation de MAX CUT.

\end{frame}


\begin{frame}

Comment calculer $I$ ? On étudie la fonction $t\mapsto f(t)=\frac{\pi(1-\cos t)}{2t}$ sur l'intervalle $[0,\pi]$.

$$f'(t)=\frac{\pi}{2}\frac{t\sin t -(1-\cos t)}{t^2}$$\pause

$$g(t)=t\sin t -(1-\cos t)$$\pause

$$g'(t)=\sin t +t\cos t-\sin t =t\cos t$$\pause

\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$t$   & $0$ && $\pi/2$ && $\pi$ \\
\hline
$g'(t)$   & $0$  & $+$ & $0$ & $-$ &\\
\hline
$g(t)$   &  $0$ & $\nearrow$ & $g(\pi/2)$ & $\searrow$ & $-2$ \\
\hline
\end{tabular}
\end{center}\pause

\begin{center}
\begin{tabular}{|c|ccccc|}
\hline
$t$   & $0$ && $a$ && $\pi$ \\
\hline
$f'(t)$   & $0$  & $+$ & $0$ & $-$ &\\
\hline
$f(t)$   &  $0$ & $\nearrow$ & $f(a)$ & $\searrow$ & $1$ \\
\hline
\end{tabular}
\end{center}\pause

Par approximation successives, on trouve $a=2.331122370414423...$ puis $I=1/f(a)=0.8785672057848516...$.
\end{frame}

\end{document}

% 0.8785672057848516
% 2.331122370414423