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

\title{Difficulté d'approximation}
\author{P. Pansu, Université Paris-Sud }
\date{19 novembre 2011}

\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{conj}[lem]{Conjecture}
\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\P{\mathbb{P}}
\def\E{\mathbb{E}}
\def\B{\{-1,1\}}
%\def\texorpdfstring#1#2{#1}

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

\begin{document}

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

\begin{frame}
Au menu aujourd'hui :
\begin{itemize}
  \item Un théorème de la théorie du choix social.
  \item Une application à la difficulté d'approximation, en informatique théorique.
\end{itemize}
\end{frame}

\section{Choix social}

\subsection{Influences}

\begin{frame}

Une \emph{fonction booléenne} est une fonction $\B^n \to\B$. On peut y penser comme à un procédé pour agréger des votes, i.e. produire une décision à partir des votes de $n$ électeurs.

\begin{ex}
Le $i$-ème {\em dictateur} est $Dict_i (x)=x_i$. La {\em majorité} est $Maj(x)=$ signe$(\sum x_i)$.
\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 chance de faire basculer le résultat.
\end{enumerate}\pause

\begin{defi}
L'{\em influence} $Inf_i (f)$ du $i$-ème électeur sur $f$ est la probabilité que, lorsque le $i$-ème électeur change d'avis, la valeur de $f$ change.
\begin{eqnarray*}
Inf_i (f)=\P(f(xe_i)\not= f(x)),
\end{eqnarray*}
où $e_i \in\B^{n}$ est le vecteur dont les coordonnées valent $1$ sauf la $i$-ème.
\end{defi}

\end{frame}

\subsection{Sensibilité au bruit}

\begin{frame}

\begin{defi}
La {\em sensibilité au $c$-bruit} de $f$ est la probabilité que, lorsque chaque vote est modifié indépendamment avec probabilité $c$, la valeur de $f$ change.
\begin{eqnarray*}
Sens_{c} (f)=\P_{x,z}(f(xz)\not= f(x)),
\end{eqnarray*}
où les coordonnées $z_i \in\B$ sont i.i.d., indépendantes de $x$, et $\P(z_i =-1)=c$.
\end{defi}

\medskip

\textbf{Exemple}.

Pour le dictateur $Dict_i$,
\begin{eqnarray*}
Inf_i (Dict_i)=1, \quad Inf_j (Dict_i)=0 \text{ si }j\not=i~;\quad 
Sens_c (Dict_i)=c.
\end{eqnarray*}

Pour la majorité, il résulte du Théorème Central Limite que
\begin{eqnarray*}
Inf_i (Maj)\sim\frac{2}{\sqrt{\pi n}};\quad \lim_{n\to\infty}Sens_c (Maj)=\frac{1}{\pi}\arccos(1-2c).
\end{eqnarray*}

\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 toutes les fonctions booléennes $\B^n \to \B$ de moyenne nulle, 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 (sans condition de moyenne nulle).
\end{thm}

En fait, l'énoncé est non asymptotique : pour tout $\epsilon>0$, il existe $\tau(\epsilon)$ tel que si toutes les influences $Inf_i (f)<\tau$, alors $Sens_c (f)\geq \frac{1}{\pi}\arccos(1-2c)-\epsilon$ (resp. $\leq$ si $c\in[\frac{1}{2},1]$).

\medskip

\textbf{Preuve}
\begin{enumerate}
  \item Principe d'invariance : on remplace le cube $\B^n$ muni de la mesure de probabilité uniforme, par l'espace gaussien, i.e. l'espace euclidien $\R^n$ muni de la mesure gaussienne $\gamma_n$, de densité $(2\pi)^{-n/2}\exp(-|x|^2 /2)$. 
  \item Dans l'espace gaussien, un argument de symétrisation dû à Ehrhard et Borell montre que parmi les fonctions de moyenne nulle, à valeurs dans $[-1,1]$, les fonctions ``signe de forme linéaire'' maximisent $Sens_c$, $c\leq\frac{1}{2}$.
\end{enumerate}
\end{frame}

\section{MAX CUT}

\subsection{Inimitiés}

\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=2in]{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. \pause 
Ici, 9 couples ennemis séparés.

\end{frame}


\begin{frame}

Ce plan de table a séparé 9 couples. Est ce qu'on peut 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 de table a séparé 9 couples. Est ce qu'on peut 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}

\subsection{Le problème MAX CUT}

\begin{frame}

\begin{defi}
Soit $G$ un graphe pondéré (i.e. une distribution de probabilité sur les arêtes du graphe complet). On appelle coupe maximale$(G)$ le maximum, sur tous les coloriages de $G$, de la probabilité qu'une arête soit coupée.
\end{defi}

Le graphe étudié jusqu'à présent a une coupe maximale de $\frac{11}{13}$.\pause

\begin{prob}
MAX CUT : Ecrire un algorithme qui, étant donnés un graphe $G$ à $n$ sommets, et un nombre entier $k$, décide si la coupe maximale de $G$ est $\geq k$ ou non.
\end{prob}\pause

\begin{defi}
Un problème est dit {\em NP-complet} s'il est NP, et si tout problème NP s'y ramène en temps polynomial.
\end{defi}

\begin{thm}[Cook, Levine 1971, Karp 1972]
MAX CUT est NP-complet.
\end{thm}

\end{frame}

\subsection{Problème MAX CUT approché}

\begin{frame}

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 algorithme qui, étant donné un graphe pondéré $G$ à $n$ sommets, trouve en un temps polynomial en $n$, un coloriage dont le nombre d'arêtes bicolores est $\geq \alpha\times$coupe maximale$(G)$. Cet algorithme 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}\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{L'algorithme 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

\textbf{Arithmétisation}. Un coloriage est une fonction booléenne $x:\{$sommets$\}\to\{-1,1\}$. Il faut maximiser
\begin{eqnarray*}
\textrm{OBJ}=\E_{\mathrm{aretes}\,ij}(\frac{1}{2}(1-x_i x_j)).
\end{eqnarray*}\pause

\textbf{Relaxation}. 
On maximise sur un ensemble plus grand, les applications $v:\{$sommets$\}\to S$, la sphère unité d'un espace euclidien de grande dimension.
\begin{eqnarray*}
\textrm{SDP}=\E_{\mathrm{aretes}\,ij}(\frac{1}{2}(1-v_i \cdot v_j)).
\end{eqnarray*}\pause
Il s'agit d'un problème de \emph{programmation semi-définie}. $\max$ SDP peut être calculé, avec une précision arbitraire, en temps polynomial. \pause

\textbf{Procédure d'arrondi}. A partir d'un plongement $v$ du graphe dans la sphère unité $S$, on construit un coloriage en coupant le graphe en deux au moyen d'un plan tiré au hasard. 

\begin{center}
\includegraphics[width=1in]{gw.pdf}
\end{center}
\end{frame}

\begin{frame}

\textbf{Analyse}.
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=\E_{ij}(\frac{1}{\pi}\arccos(v_i \cdot v_j)).
\end{eqnarray*}
Comme pour tout $x\in[0,1[$, 
\begin{eqnarray*}
\frac{\frac{1}{\pi}\arccos(x)}{\frac{1}{2}(1-x)}\geq 0.878..., 
\end{eqnarray*}
\begin{eqnarray*}
E\geq 0.878...\max \textrm{SDP}\geq 0.878...\times \max \textrm{OBJ} =0.878...\times \textrm{coupe maximale}.
\end{eqnarray*}\pause

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

\end{frame}

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


\begin{frame}


\begin{thm}[S. Khot, G. Kindler, E. Mossel, R. O'Donnell 2005]
Sous une hypothèse un peu plus forte que P$\not=$NP, 0.878... est le seuil optimal d'approximabilité pour MAX CUT. Autrement dit, si $\alpha>0.8785672057848516...$, 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 à Gödel (vérification de preuves, vérification probabiliste de preuves) et repose sur le théorème \texttt{Majority is Stablest}.

\medskip

L'hypothèse un peu plus forte que P$\not=$NP, c'est la Conjecture des Jeux Uniques \texttt{(Unique Games Conjecture)} de Subhash Khot.


\end{frame}

\section{Jeux uniques}

\subsection{Jeux coopératifs}

\begin{frame}

\begin{defi}
On s'intéresse à des jeux coopératifs à deux joueurs. Des couples de questions $(q,q')$ sont tirés suivant une distribution connue. Les joueurs doivent donner des réponses $r=S(q)$ et $r'=S(q')$ sans savoir quelle question a été posée à l'autre. Dans un {\em jeu projectif}, pour chaque question $q$, chaque question $q'$ et chaque réponse possible $r$ du premier joueur, il y a une unique réponse $r'=\pi_{qq'}(r)$ du second qui les fait gagner tous les deux. Les joueurs cherchent une stratégie commune $S$ qui maximise la probabilité de gain,
\begin{eqnarray*}
\textrm{Valeur du jeu}=\max_{S}\P_{(q,q')}(S(q')=\pi_{qq'}(S(q))).
\end{eqnarray*}
\end{defi}\pause

\begin{thm}
Soit $n$ le nombre de questions et $k$ le nombre de réponses par question. Pour tout $\epsilon>0$, il existe $k$ tel qu'il est NP-difficile de décider, pour un jeu projectif à $k$ questions, dans quel cas de figure on se trouve (sachant qu'on est dans l'un des deux).
\begin{enumerate}
  \item La valeur du jeu est $1$.
  \item La valeur du jeu est $< \epsilon$.
\end{enumerate}
\end{thm}

C'est une conséquence folklorique du théorème PCP (\texttt{Probabilistically Checkable Proofs}) de Arora, Safra et al. (1992), et du théorème de répétition parallèle de  Ran Raz (1995).


\end{frame}

\begin{frame}

\begin{defi}
Un {\em jeu unique} est un jeu projectif dans les deux sens, i.e. pour chaque question $q$, chaque question $q'$ et chaque réponse possible $r'$ du second joueur, il y a aussi une unique réponse $r=\pi_{qq'}^{-1}(r')$ du premier qui les fait gagner. 
\end{defi}\pause
Il est facile de décider si la valeur du jeu vaut $1$. En effet, dans ce cas, un choix quelconque de réponse à une question détermine uniquement les réponses à toutes les autres. Il suffit de vérifier la cohérence des réponses obtenues. \pause
En revanche, il semble difficile de décider si la valeur du jeu est proche de $1$ ou non.

\begin{conj}[S. Khot 2002]
Pour tout $\epsilon>0$ et tout $\delta>0$, il existe $k$ tel qu'il est NP-difficile de décider dans lequel des deux cas de figure suivants un jeu unique à $k$ questions se trouve (sachant qu'il est dans l'un des deux).
\begin{enumerate}
  \item La valeur du jeu est $>1-\delta$.
  \item La valeur du jeu est $< \epsilon$.
\end{enumerate}
\end{conj}

Les opinions sont partagées sur cette conjecture. En revanche, personne ne parie sur le fait que le problème des jeux uniques est dans P.

\end{frame}

\subsection{Réduction des jeux uniques à MAX CUT}

\begin{frame}

Une \emph{réduction} des jeux uniques à MAX CUT consiste à associer à un jeu unique $J$ un graphe pondéré $G$, de sorte que si la valeur du jeu $J$ est $>1-\delta$ (resp. $<\epsilon$), alors la coupe maximale de $G$ est $>c-\delta'$ (resp. $<s+\epsilon'$). 

\smallskip

Un algorithme calculant en temps polynomial coupe maximale$(G)$ à un facteur multiplicatif $\frac{s+\epsilon'}{c-\delta'}$ près décide si coupe maximale$(G)>c-\delta'$ ou si coupe maximale$(G)<s+\epsilon'$, donc décide si la valeur de $J$ est $>1-\delta$ ou $<\epsilon$. Ce qui est interdit par la conjecture des jeux uniques. 

\smallskip

On conclut qu'il n'existe pas d'algorithme d'$\alpha$-approximation de MAX CUT pour $\alpha>\frac{s}{c}$.\pause

\medskip

Pour tout $c\in]\frac{1}{2},1]$, la construction donne $s=\frac{1}{\pi}\arccos(1-2c)$. Le facteur optimal d'approximation est donc 
$$\
min_{c\in]\frac{1}{2},1]}\frac{\arccos(1-2c)}{\pi c}=0.8785672057848516....
$$

\end{frame}

\begin{frame}

L'idée de la réduction est de coder les stratégies par des coloriages. 

\medskip

Chaque réponse $r\in R$ est codée par une fonction booléenne sur $\{-1,1\}^{R}$, le dictateur $Dict_r$. Une stratégie $S$ est codée par la phrase constituée des dictateurs $(Dict_{S(q)})_{q\in Q}$, puis on applique un brouillage : on change chaque bit avec probabilité $c>\frac{1}{2}$. On obtient une fonction booléenne sur $Q\times
\{-1,1\}^{R}$. \pause

\medskip

On considère donc le graphe pondéré $G$ dont l'ensemble des sommets est $Q\times\{-1,1\}^{R}$. Une distribution de probabilité sur les arêtes est obtenue (grosso modo) en tirant les paires de points $(q,q')$ de $Q$ au hasard (suivant la loi du jeu), en tirant un vecteur $x\in\{-1,1\}^{R}$ au hasard, en changeant chaque bit de $x'=\pi_{qq'}(x)$ avec probabilité $c$ et en reliant $(q,x)$ à $(q',x')$. \pause

\medskip

Pour le coloriage de $G$ codant une stratégie $S$, la probabilité qu'une arête soit bicolore est au moins $c\times$valeur$(S)$. 

\medskip

Inversement, un coloriage de $G$ donne une phrase $(f_q)_{q\in Q}$ qu'il s'agit de décoder. Si la probabilité qu'une arête soit bicolore est $>s+\epsilon'$, alors en moyenne, $f_q$ a une sensibilité au $c$-bruit $>s+\epsilon'$. D'après le Théorème \texttt{Majority is Stablest}, $f_q$ possède au moins une variable $r=S(q)$ de forte influence. La stratégie $S$ obtenue a une valeur $>\epsilon$.

\end{frame}

\end{document}

% 0.8785672057848516
% 2.331122370414423