%This is a plain TeX file that produces 12 output pages.
%\input tex8bits
{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}

\catcode'32=9
\magnification=1200

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm8
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

%\to dactylographie fran\c caise \to\to\to\to\to\to\to\to\to\to\to

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

%\to\to\to\to\to\to format de sortie \to\to\to\to

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, vol.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr\`es une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\long\def\entourer#1{\vbox{\hrule\hbox{\vrule\kern3pt
\vbox{\kern3pt#1\kern3pt}\kern3pt\vrule}\hrule}}

\catcode`\@=12

%% fin du format

 \message{`lline' & `vector' macros from LaTeX}
 \catcode`@=11
\def\{{\relax\ifmmode\lbrace\else$\lbrace$\fi}
\def\}{\relax\ifmmode\rbrace\else$\rbrace$\fi}
\def\newcount{\alloc@0\count\countdef\insc@unt}
\def\newdimen{\alloc@1\dimen\dimendef\insc@unt}
\def\newwrite{\alloc@7\write\chardef\sixt@@n}

\newwrite\@unused
\newcount\@tempcnta
\newcount\@tempcntb
\newdimen\@tempdima
\newdimen\@tempdimb
\newbox\@tempboxa

\def\@spaces{\space\space\space\space}
\def\@whilenoop#1{}
\def\@whiledim#1\do #2{\ifdim #1\relax#2\@iwhiledim{#1\relax#2}\fi}
\def\@iwhiledim#1{\ifdim #1\let\@nextwhile=\@iwhiledim
        \else\let\@nextwhile=\@whilenoop\fi\@nextwhile{#1}}
\def\@badlinearg{\@latexerr{Bad \string\line\space or \string\vector
   \space argument}}
\def\@latexerr#1#2{\begingroup
\edef\@tempc{#2}\expandafter\errhelp\expandafter{\@tempc}%
%% error help message pieces.
\def\@eha{Your command was ignored.
^^JType \space I <command> <return> \space to replace it
  with another command,^^Jor \space <return> \space to continue without it.}
\def\@ehb{You've lost some text. \space \@ehc}
\def\@ehc{Try typing \space <return>
  \space to proceed.^^JIf that doesn't work, type \space X <return> \space to
  quit.}
\def\@ehd{You're in trouble here.  \space\@ehc}

\typeout{LaTeX error. \space See LaTeX manual for explanation.^^J
 \space\@spaces\@spaces\@spaces Type \space H <return> \space for
 immediate help.}\errmessage{#1}\endgroup}
\def\typeout#1{{\let\protect\string\immediate\write\@unused{#1}}}

% line & circle fonts
\font\tenln    = line10
\font\tenlnw   = linew10
%\font\tencirc  = circle10
%\font\tencircw = circlew10


\newdimen\@wholewidth
\newdimen\@halfwidth
\newdimen\unitlength 

\unitlength =1pt

%\newbox\@picbox
%\newdimen\@picht

\def\thinlines{\let\@linefnt\tenln \let\@circlefnt\tencirc
  \@wholewidth\fontdimen8\tenln \@halfwidth .5\@wholewidth}
\def\thicklines{\let\@linefnt\tenlnw \let\@circlefnt\tencircw
  \@wholewidth\fontdimen8\tenlnw \@halfwidth .5\@wholewidth}

\def\linethickness#1{\@wholewidth #1\relax \@halfwidth .5\@wholewidth}



\newif\if@negarg

\def\lline(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vline
  \else \ifnum\@yarg =0 \@hline \else \@sline\fi
\fi}

\def\@sline{\ifnum\@xarg< 0 \@negargtrue \@xarg -\@xarg \@yyarg -\@yarg
  \else \@negargfalse \@yyarg \@yarg \fi
\ifnum \@yyarg >0 \@tempcnta\@yyarg \else \@tempcnta -\@yyarg \fi
\ifnum\@tempcnta>6 \@badlinearg\@tempcnta0 \fi
\setbox\@linechar\hbox{\@linefnt\@getlinechar(\@xarg,\@yyarg)}%
\ifnum \@yarg >0 \let\@upordown\raise \@clnht\z@
   \else\let\@upordown\lower \@clnht \ht\@linechar\fi
\@clnwd=\wd\@linechar
\if@negarg \hskip -\wd\@linechar \def\@tempa{\hskip -2\wd\@linechar}\else
     \let\@tempa\relax \fi
\@whiledim \@clnwd <\@linelen \do
  {\@upordown\@clnht\copy\@linechar
   \@tempa
   \advance\@clnht \ht\@linechar
   \advance\@clnwd \wd\@linechar}%
\advance\@clnht -\ht\@linechar
\advance\@clnwd -\wd\@linechar
\@tempdima\@linelen\advance\@tempdima -\@clnwd
\@tempdimb\@tempdima\advance\@tempdimb -\wd\@linechar
\if@negarg \hskip -\@tempdimb \else \hskip \@tempdimb \fi
\multiply\@tempdima \@m
\@tempcnta \@tempdima \@tempdima \wd\@linechar \divide\@tempcnta \@tempdima
\@tempdima \ht\@linechar \multiply\@tempdima \@tempcnta
\divide\@tempdima \@m
\advance\@clnht \@tempdima
\ifdim \@linelen <\wd\@linechar
   \hskip \wd\@linechar
  \else\@upordown\@clnht\copy\@linechar\fi}

%\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
%\vrule \@height \@halfwidth \@depth \@halfwidth \@width
%\@linelen \ifnum \@xarg <0 \hskip -\@linelen \fi}


\def\@hline{\ifnum \@xarg <0 \hskip -\@linelen \fi
\vrule height \@halfwidth depth \@halfwidth width \@linelen
\ifnum \@xarg <0 \hskip -\@linelen \fi}

\def\@getlinechar(#1,#2){\@tempcnta#1\relax\multiply\@tempcnta 8
\advance\@tempcnta -9 \ifnum #2>0 \advance\@tempcnta #2\relax\else
\advance\@tempcnta -#2\relax\advance\@tempcnta 64 \fi
\char\@tempcnta}

\def\vector(#1,#2)#3{\@xarg #1\relax \@yarg #2\relax
\@linelen=#3\unitlength
\ifnum\@xarg =0 \@vvector
  \else \ifnum\@yarg =0 \@hvector \else \@svector\fi
\fi}

\def\@hvector{\@hline\hbox to 0pt{\@linefnt
\ifnum \@xarg <0 \@getlarrow(1,0)\hss\else
    \hss\@getrarrow(1,0)\fi}}

\def\@vvector{\ifnum \@yarg <0 \@downvector \else \@upvector \fi}

\def\@svector{\@sline
\@tempcnta\@yarg \ifnum\@tempcnta <0 \@tempcnta=-\@tempcnta\fi
\ifnum\@tempcnta <5
  \hskip -\wd\@linechar
  \@upordown\@clnht \hbox{\@linefnt  \if@negarg
  \@getlarrow(\@xarg,\@yyarg) \else \@getrarrow(\@xarg,\@yyarg) \fi}%
\else\@badlinearg\fi}

\def\@getlarrow(#1,#2){\ifnum #2 =\z@ \@tempcnta='33\else
\@tempcnta=#1\relax\multiply\@tempcnta \sixt@@n \advance\@tempcnta
-9 \@tempcntb=#2\relax\multiply\@tempcntb \tw@
\ifnum \@tempcntb >0 \advance\@tempcnta \@tempcntb\relax
\else\advance\@tempcnta -\@tempcntb\advance\@tempcnta 64
\fi\fi\char\@tempcnta}

\def\@getrarrow(#1,#2){\@tempcntb=#2\relax
\ifnum\@tempcntb < 0 \@tempcntb=-\@tempcntb\relax\fi
\ifcase \@tempcntb\relax \@tempcnta='55 \or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -6 \else \ifnum #1=3 \@tempcnta=49
\else\@tempcnta=58 \fi\fi\or
\ifnum #1<3 \@tempcnta=#1\relax\multiply\@tempcnta
24 \advance\@tempcnta -3 \else \@tempcnta=51\fi\or
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta -\tw@ \else
\@tempcnta=#1\relax\multiply\@tempcnta
\sixt@@n \advance\@tempcnta 7 \fi\ifnum #2<0 \advance\@tempcnta 64 \fi
\char\@tempcnta}



\def\@vline{\ifnum \@yarg <0 \@downline \else \@upline\fi}


\def\@upline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \@linelen depth \z@\hss}}

\def\@downline{\hbox to \z@{\hskip -\@halfwidth \vrule
  width \@wholewidth height \z@ depth \@linelen \hss}}

\def\@upvector{\@upline\setbox\@tempboxa\hbox{\@linefnt\char'66}\raise
     \@linelen \hbox to\z@{\lower \ht\@tempboxa\box\@tempboxa\hss}}

\def\@downvector{\@downline\lower \@linelen
      \hbox to \z@{\@linefnt\char'77\hss}}

%INITIALIZATION
\thinlines

\newcount\@xarg
\newcount\@yarg
\newcount\@yyarg
\newcount\@multicnt
\newdimen\@xdim
\newdimen\@ydim
\newbox\@linechar
\newdimen\@linelen
\newdimen\@clnwd
\newdimen\@clnht
\newdimen\@dashdim
\newbox\@dashbox
\newcount\@dashcnt
 \catcode`@=12


% macros supplementaires (J.D.)

\newbox\tbox
\newbox\tboxa

%\def\picbox(#1,#2,#3)#4{\setbox\tbox=\hbox{#4}%
%     \ht\tbox=#1 \wd\tbox=#2 \dp\tbox=#3 \box\tbox}

\def\leftzer#1{\setbox\tbox=\hbox to 0pt{#1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\rightzer#1{\setbox\tbox=\hbox to 0pt{\hss #1}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

\def\centerzer#1{\setbox\tbox=\hbox to 0pt{\hss #1\hss}%
     \ht\tbox=0pt \dp\tbox=0pt \box\tbox}

% sytaxe: \image(hauteur totale reservee, distance
%    verticale de l'origine par rapport au bas de
%    la place reservee){materiel a inserer}
% L'origine est toujours centre horizontalement
%
\def\image(#1,#2)#3{\vbox to #1{\offinterlineskip
    \vss #3 \vskip #2}}

% \leftput place le materiel avec son point de reference
%    en #1,#2 unites \unitlength
% De meme pour \centerput et \rightput

\def\leftput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\leftzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\rightput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\rightzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\def\centerput(#1,#2)#3{\setbox\tboxa=\hbox{%
    \kern #1\unitlength
    \raise #2\unitlength\hbox{\centerzer{#3}}}%
    \ht\tboxa=0pt \wd\tboxa=0pt \dp\tboxa=0pt\box\tboxa}

\unitlength=1mm

\def\cput(#1,#2)#3{\noalign{\nointerlineskip\centerput(#1,#2){#3}
                             \nointerlineskip}}

%fin du format pour les traits obliques

\def\Masc{\mathord{\rm Masc}}
\def\Fem{\mathord{\rm Fem}}

% fin du format local

%debut de l'article

\auteurcourant={D. DUMONT}
\titrecourant={MARIAGES STABLES}

%\raggedbottom
{\eightpoint
\noindent
S\'eminaire Lotharingien de Combinatoire, B23c (1990)
}
\vskip-10pt
\vskip 1.5cm
\centerline{{\bf MARIAGES STABLES}}
\vskip 2.8mm
\centerline{\sevenrm PAR}
\vskip 2.8mm
\centerline{{\petcap Dominique} DUMONT}
\vskip 1cm


\titre 1. L'agence matrimoniale honn\^ete|

L'agence matrimoniale que
nous  consid\'erons est honn\^ete dans le sens qu'elle pr\'etend
respecter les principes suivants :

\decale 1)|l'information la plus large : tout adh\'erent a acc\`es au fichier des
adh\'erents de l'autre sexe, et peut les rencontrer.

\decale 2)|la stabilit\'e des couples : l'agence ne forme que des couples
stables (contrairement \`a d'autres agences, celle-ci ne vit pas de
l'instabilit\'e des couples).

\decale 3)|l'efficacit\'e : tout adh\'erent est assur\'e de rencontrer au
moins un adh\'erent de l'autre sexe avec lequel il peut former un couple
stable (contrairement \`a d'autres agences, personne ne cotise en pure perte).

Notre objectif dans cette premi\`ere partie, sera de d\'emontrer qu'une telle
agence  matrimoniale honn\^ete n'existe pas, plus pr\'ecis\'ement que le ``syst\`eme
d'axiomes" constitu\'e par les trois principes \'enonc\'es ci-dessus est
contradictoire. A cet effet, nous allons d'abord leur donner un sens plus
pr\'ecis.

\section 1.1. Position du probl\`eme|Nous supposons que chaque
adh\'erent classe ceux de l'autre sexe selon son ordre de
pr\'ef\'erences (il peut le faire d'apr\`es l'axiome d'information, et
nous allons voir qu'il doit le faire pour satisfaire l'axiome de
stabilit\'e). Ainsi chaque gar\c con classe les filles selon un ordre
total, et r\'eciproquement. On obtient ainsi une {\it configuration
de pr\'ef\'erences.} En voici un exemple, avec $n$ gar\c cons et $n$
filles (ici, $n = 3$):

\medskip
$$\vbox{
\halign{\strut\vrule
\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule
&\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule\cr
\noalign{\hrule}
G_1:&F_1&F_2&F_3&F_1:&G_3&G_2&G_1\cr
G_2:&F_1&F_3&F_2&F_2:&G_2&G_1&G_3\cr
G_3:&F_2&F_3&F_1&F_3:&G_1&G_2&G_3\cr
\noalign{\hrule}
}}
$$

\centerline{Configuration de pr\'ef\'erences compl\`etes
$P_1$}

\goodbreak
On dit qu'on d\'etermine une {\it solution} en mariant gar\c cons
et filles, donc en formant $n$ couples.\footnote{$(^*)$}{Le mot
anglais est {\it matching}, son \'equivalent fran\c cais habituel, le
mot {\it couplage}, nous semble particuli\`erement malvenu dans le
contexte et nous pr\'ef\'erons donc parler de {\it solution},
celle-ci ne saurait \^etre finale\dots} Mais il existe deux
cat\'egories de solutions: les stables et les instables.

\goodbreak
Une {\it solution instable} est une solution telle qu'il existe
un gar\c con $G$ et une fille $F$ non mari\'es ensemble qui se
pr\'ef\`erent mutuellement \`a leur \'epouse et \'epoux respectifs. On dit
que $(G, F)$ est une {\it cause d'infid\'elit\'e} ou une {\it cause
d'instabilit\'e.}

\medskip
{\it Exemple:} la solution $(G_1,F_1),(G_2,F_3),(G_3,F_2)$ est
instable pour $P_1$, car
$(G_2,F_1)$ est une cause d'infid\'elit\'e. En effet, $G_2$ pr\'ef\`ere $F_1$ \`a son \'epouse $F_3$, et
$F_1$ pr\'ef\`ere $G_2$ \`a son \'epoux $G_1$.

\medskip
A l'inverse, une {\it solution stable} est une solution sans
cause d'infid\'elit\'e. Il suffit que chaque gar\c con constate que toute
fille qu'il pr\'ef\`ere \`a son \'epouse est mari\'ee \`a un gar\c con qu'elle
pr\'ef\`ere \`a lui (il s'ensuit que la r\'eciproque est vraie aussi).
 
\medskip
{\it Exemple:} la solution $A = (G_1,F_2)(G_2,F_3)(G_3,F_1)$ est
stable pour la configuration $P_1$. En effet, $G_1$ pr\'ef\`ere $F_1$
\`a son \'epouse mais ce n'est pas r\'eciproque,
$G_2$ est dans la m\^eme situation, $G_3$ aurait pr\'ef\'er\'e $F_2$ ou $F_3$ mais ce n'est pas
r\'eciproque. Il est clair qu'on ne trouve aucune cause d'infid\'elit\'e.

Nous allons d\'emontrer un peu plus loin qu'il existe toujours
une solution stable, quelle que soit la configuration de
pr\'ef\'erences. Cet optimiste th\'eor\`eme d'existence semble a priori
en contradiction avec la conclusion pessimiste annonc\'ee plus
haut. Il l'est en effet dans le cas tr\`es particulier que nous
avons consid\'er\'e ici, o\`u d'une part il existe le m\^eme nombre
d'adh\'erents pour chaque sexe, d'autre part chaque adh\'erent
classe tous ceux de l'autre sexe, donc admet implicitement qu'il
peut \'epouser chacun d'eux. Or ce ``mod\`ele id\'eal" ne refl\`ete
\'evidemment pas la r\'ealit\'e v\'ecue. Nous allons donc nous situer
dans un cadre plus g\'en\'eral, celui des {\it configurations de
pr\'ef\'erences incompl\`etes.} En voici un exemple:

$$\vbox{
\halign{\strut\vrule
\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule
&\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule\cr
\noalign{\hrule}
G_1:&(F_5)&F_1&F_2&F_4&&F_1:&G_2&(G_4)&G_1&\cr
G_2:&F_2&(F_5)&F_1&F_3&&F_2:&G_1&G_2&G_3&\cr
G_3:&F_3&F_2&F_4&F_5&(F_1)&F_3:&G_2&G_4&G_3&(G_1)\cr
G_4:&F_4&F_3&F_5&&&F_4:&(G_2)&G_3&G_1&G_4\cr
&&&&&&F_5:&G_3&G_4&&\cr
\noalign{\hrule}
}}
$$

\centerline{Configuration de pr\'ef\'erences incompl\`etes $P_2$}

\bigskip
\goodbreak
Comme on le voit, chaque adh\'erent ne classe qu'une partie de
ceux (ou celles) de l'autre sexe, seulement ceux qu'il juge {\it
acceptables.} On peut aussi consid\'erer qu'il a class\'e tous ceux
de l'autre sexe, comme dans le cas des pr\'ef\'erences compl\`etes,
mais qu'il s'est \'egalement class\'e lui-m\^eme parmi eux, en ce sens
qu'il pr\'ef\`ere les acceptables \`a lui-m\^eme (c'est-\`a-dire \`a son
c\'elibat), mais qu'il pr\'ef\`ere son c\'elibat plut\^ot qu'\`a former un
couple avec un(e) inacceptable, selon le sch\'ema suivant:
$$
\vbox{\halign{&#\cr
$G:\underbrace{F\ldots F}$&\ $G$\ &$\underbrace{F\ldots F}$\cr
{\eightrm acceptables}&&{\eightrm inacceptables}\cr}}
$$
Dans la configuration $P_2$ ci-dessus, nous n'avons reproduit
que les listes d'acceptables, pour all\'eger et parce que seules
ces listes importent. 

Dans le contexte d'une configuration de pr\'ef\'erences incompl\`etes
pour $m$ gar\c cons et $n$ filles, une solution est une partition de
l'ensemble des adh\'erents en $k$ couples $(G, F)$ et $m+n-2k$
c\'elibataires $(G)$ et/ou
$(F),$ o\`u $k\leq \min(m, n)$ (non n\'ecessairement \'egal). Ceux et celles qui restent
c\'elibataires  s'appellent les {\it laiss\'es-pour-compte} de la solution.

Une solution est dite {\it irrationnelle} si elle contient un
couple dont l'un des membres est jug\'e inacceptable par l'autre.
On rationnalise une configuration de pr\'ef\'erences en mettant
entre parenth\`eses sur la liste de chaque adh\'erent ceux de ses
acceptables qui le jugent, lui, inacceptable. C'est ainsi que dans
l'exemple de la configuration $P_2$, nous voyons que $G$ doit
mettre entre parenth\`eses les sentiments qu'il \'eprouve pour $F_5$.
 
La d\'efinition d'une solution instable est inchang\'ee, \`a cela pr\`es
qu'un c\'elibataire peut entrer dans une cause d'infid\'elit\'e.

\medskip
{\it Exemple:} la solution
$(G_1,F_1)(G_2,F_2)(G_3,F_5)(G_4,F_4)(F_3)$ est instable, car
$(G_3,F_3)$ est une cause d'infid\'elit\'e. (Notons en passant qu'une
solution irrationnelle n'est qu'un cas particulier de solution
instable.)
    
\medskip
Nous pouvons \`a pr\'esent \'enoncer et d\'emontrer le th\'eor\`eme
d'existence fondateur de la th\'eorie.

\sectiona 1.2. Th\'eor\`eme d'existence|

\th
Th\'eor\`eme {\rm (Gale-Shapley [5])}| Quelle que soit la
configuration de pr\'ef\'erences
$P$, il existe au moins une solution stable pour $P.$
\finth

\dem    
La d\'emonstration repose sur un algorithme de construction d'une
solution stable que nous appellerons {\it algorithme des
initiatives masculines.} Nous supposons que l'agence organise un
bal au cours duquel tous les adh\'erents se retrouvent pour
danser. Les garcons invitent les filles au cours de {\it
mouvements} successifs.

Au premier mouvement, chaque gar\c con invite la fille qu'il
pr\'ef\`ere. Si une fille se trouve alors prise entre plusieurs feux,
elle choisit pour danser celui qu'elle pr\'ef\`ere parmi ceux qu'elle
juge acceptables, et qui devient par le fait m\^eme son {\it
pr\'etendant}, tandis que les autres sont {\it rejet\'es} par la fille.
Ces gar\c cons, non pr\'etendants \`a l'issue du premier mouvement,
sont dits {\it libres.}

Au deuxi\`eme mouvement, chaque gar\c con libre invite la fille qui
suit dans l'ordre de ses pr\'ef\'erences, m\^eme si elle poss\`ede d\'ej\`a
un pr\'etendant. Chaque fille choisit \`a nouveau celui qu'elle
pr\'ef\`ere entre ceux qui l'invitent et son \'eventuel pr\'etendant, et
d\'esigne ainsi un nouveau pr\'etendant, les autres \'etant rendus \`a
leur libert\'e.

Et ainsi de suite\dots\ L'algorithme s'arr\^ete lorsqu'il n'y a plus
de gar\c cons libres (ce qui se produit au bout d'un nombre fini de
mouvements, puisqu'il n'y a qu'un nombre fini de gar\c cons, dont les
listes de filles acceptables sont de longueurs finies).  On marie
alors chaque fille avec son pr\'etendant. Reste c\'elibataire tout
gar\c con qui s'est fait rejeter par toutes les filles qu'il juge
acceptables, reste c\'elibataire aussi toute fille qui n'a \'et\'e
invit\'ee par aucun des gar\c cons qu'elle juge acceptables. Nous
notons $\Masc$ la solution ainsi d\'efinie.

Montrons que $\Masc$ est une solution stable. Soit $G$ un
gar\c con quelconque, et $F$ une fille qu'il pr\'ef\`ere \`a son \'epouse (ou
\`a son c\'elibat, dans le cas o\`u $\Masc$ le d\'esigne comme
c\'elibataire). Il est clair que $F$ l'a rejet\'e au cours de
l'algorithme, puisqu'il a invit\'e toutes les filles dans l'ordre
d\'ecroissant de ses pr\'ef\'erences. Elle l'a rejet\'e au profit d'un
certain $G'$ qu'elle pr\'ef\`ere \`a $G,$ or son \'epoux \`a l'issue de
l'algorithme est soit $G',$ soit un autre qu'elle aime encore plus,
car les pr\'etendants qui se sont succ\'ed\'es aupr\`es d'elle allaient
dans l'ordre croissant de ses pr\'ef\'erences. Il est donc exclu
qu'elle pr\'ef\`ere $G$ \`a son \'epoux, autrement dit $(G, F)$ n'est pas
une cause d'infid\'elit\'e. Par cons\'equent, la solution $\Masc$ est
stable.\cqfd

\medskip
Voyons par exemple ce que donne l'algorithme des initiatives
masculines sur la configuration $P_1$: au premier
mouvement,
$G_1$ et $G_2$ invitent $F_1$, qui choisit $G_2$ et rejette
$G_1$, tandis que $G_3$ invite $F_2.$ Au deuxi\`eme mouvement, le
gar\c con libre $G_1$ invite $F_2$, laquelle le pr\'ef\`ere au d\'etriment
de $G_3.$ Au troisi\`eme mouvement, celui-ci se console avec
$F_3.$ D'o\`u le r\'esultat, en t\^ete du tableau suivant:
$$
\eqalign{
\Masc(P_1)& = (G_1,F_2),(G_2,F_1),(G_3,F_3)\cr
A&= (G_1,F_2),(G_2,F_3),(G_3 ,F_1)\cr
\Fem(P_1)& = (G_1,F_3),(G_2,F_2),(G_3,F_1)\cr}
$$
En dessous de $\Masc$, nous avons fait figurer la solution $A$
propos\'ee en d\'ebut d'article comme exemple de solution stable
pour $P_1$, puis la solution $\Fem$ qui r\'esulte de mani\`ere
analogue (en un seul mouvement) d'un algorithme des initiatives
f\'eminines o\`u les r\^oles sont renvers\'es. Ainsi nous avons sur cet
exemple, parmi les $3! = 6$ solutions possibles en trois couples
(les solutions avec c\'elibataires sont \'evidemment instables,
puisque les pr\'ef\'erences sont compl\`etes), trois solutions stables,
et il est facile de v\'erifier que ce sont les seules.

    Quelle solution stable choisir lorsque plusieurs se pr\'esentent \`a nous ? Sur cet exemple
nous pouvons constater que des conflits entre les sexes apparaissent d\`es qu'on aborde cette
question, en l'occurrence les gar\c cons pr\'ef\`erent $\Masc$, les filles
$\Fem$ (alors que pour les gar\c cons c'est la pire des solutions
envisageables), et $A$ occupe une position interm\'ediaire. Nous
allons voir que cette situation de d\'esaccord est g\'en\'erale, sauf si
$\Masc = \Fem$, ce qui peut se produire. 

Nous montrerons au paragraphe 5 que les gar\c cons
pr\'ef\`erent $\Masc$ (et les filles $\Fem$) \`a toute autre solution
stable, selon le th\'eor\`eme suivant:

\th
Th\'eor\`eme {\rm d'optimalit\'e (Gale-Shapley)}|Soit une configuration
de pr\'ef\'erences $P$ et soit
$\Masc(P)$ la solution correspondante. Alors tout garcon est mari\'e
dans $\Masc(P)$ \`a la fille qu'il pr\'ef\`ere parmi toutes celles
qu'il \'epouserait selon les diverses solutions stables pour la
configuration~$P$.
\finth

\section 1.3. D\'esaccords conjugaux.
Laiss\'es-pour-compte|Nous allons \`a pr\'esent aborder deux
th\'eor\`emes pessimistes. Commen\c cons par \'etablir que si $A$ et $B$
sont deux solutions stables pour une configuration de
pr\'ef\'erences $P$ (compl\`ete ou incompl\`ete), alors deux \'epoux ne
sont jamais d'accord sur la pr\'ef\'erence \`a accorder \`a l'une ou
l'autre de ces deux solutions, sauf lorsque cela leur est
indiff\'erent \`a tous deux parce qu'ils sont mari\'es de la m\^eme
mani\`ere dans les deux solutions. Lorsque nous dirons
qu'un conjoint {\it pr\'ef\`ere} $A$ \`a $B$, nous
sous-entendrons {\it strictement} (il n'est pas mari\'e de
la m\^eme mani\`ere selon les deux solutions et pr\'ef\`ere son
conjoint dans
$A$ \`a son conjoint dans $B$). 

\th
Th\'eor\`eme {\rm des d\'esaccords conjugaux}| Soient $A$ et $B$ deux
solutions stables pour une configuration de pr\'ef\'erences $P$, et
soit $G$ un gar\c con qui pr\'ef\`ere $A$. Alors il est mari\'e dans $A$ et
son \'epouse $F$ dans $A$ pr\'ef\`ere~$B.$ En outre il est aussi mari\'e
dans $B$ et son \'epouse $F'$ dans $B$ pr\'ef\`ere \'egalement~$B.$
\finth

\dem    
Il est \'evident que $G$ est mari\'e dans $A.$ Si $G$ et $F$ pr\'ef\'eraient tous deux $A,$ ils
seraient une cause d'infid\'elit\'e pour $B,$ o\`u ils ne sont pas mari\'es, mais $B$ est stable.
Donc $F$ pr\'ef\`ere $B.$

D\'esignons par $\Gamma(A)$ l'ensemble des gar\c cons qui
pr\'ef\`erent $A$ et par $\Phi(B)$  l'ensemble des filles qui
pr\'ef\`erent $B.$ Il r\'esulte de ce qui pr\'ec\`ede que le mariage dans
$A$ est une application injective de $\Gamma(A)$ dans $\Phi(B)$.
Pour une raison sym\'etrique, le mariage dans $B$ est une
application injective de $\Phi(B)$ dans $\Gamma(A)$  (sinon, c'est
$A$ qui serait instable). Par cons\'equent les deux ensembles
$\Gamma(A)$ et $\Phi(B)$ ont m\^eme cardinal et les deux
applications sont en fait des bijections. Par suite $G$ est bien
mari\'e dans $B,$ et avec une fille de $\Phi(B)$, ce qui ach\`eve la
d\'emonstration du th\'eor\`eme.\cqfd

\th Th\'eor\`eme {\rm des laiss\'es-pour-compte
(Gale-Sotomayor [6])}|Soit $P$ une configuration
de pr\'ef\'erences incompl\`etes, l'ensemble des
laiss\'es-pour-compte (c'est-\`a-dire des non mari\'e(e)s dans
une solution) ne d\'epend pas de la solution stable choisie.
\finth

\dem
En effet, supposons que $G$ soit laiss\'e-pour-compte dans la
solution stable $B,$ et soit $A$ une autre solution
stable quelconque. Si $G$ \'etait mari\'e dans $A$ il
pr\'ef\'ererait $A$ \`a $B,$ mais nous venons de voir qu'il serait
\'egalement mari\'e dans $B$ ce qui est contradictoire. Donc $G$
est exclu de toute solution stable. Le m\^eme raisonnement
s'applique sym\'etriquement \`a une fille $F.$
\cqfd
  
\medskip 
{\it Exemple:} dans le cas de la configuration incompl\`ete $P_2$,
les quatre solutions stables (dont la liste sera donn\'ee au
paragraphe suivant) d\'esignent la m\^eme
laiss\'ee-pour-compte, $F_5.$

\medskip
Le th\'eor\`eme des laiss\'es-pour-compte montre bien que le
troisi\`eme axiome de l'agence matrimoniale honn\^ete est en
contradiction avec les deux autres. Deux rem\`edes sont
envisag\'es en pratique: soit on fait une entorse \`a
l'axiome d'information, en privil\'egiant dans les
rencontres certains clients au d\'etriment d'autres, soit
on fait patienter en attendant de nouveaux adh\'erents de
l'autre sexe.

\section 1.4. Treillis des solutions stables|Une configuration
de pr\'ef\'e\-rences compl\`etes ou incompl\`etes $P$ \'etant donn\'ee, il
existe un certain ensemble de solutions stables. Nous avons vu
que chaque adh\'erent (gar\c con ou fille) munit cet ensemble d'une
relation d'ordre partielle, celle de ses pr\'ef\'erences entre les
solutions. Consid\'erons la relation d'ordre partielle de {\it
pr\'ef\'erence masculine,} o\`u l'on dit que $A$ est pr\'ef\'er\'ee par les
gar\c cons \`a $B$ si et seulement si chacun d'eux soit pr\'ef\`ere
$A$ \`a $B$, soit est indiff\'erent (autrement dit $\Gamma(B)$ est
vide). Bien entendu d'apr\`es le th\'eor\`eme des d\'esaccords
conjugaux $B$ est pr\'ef\'er\'ee par les filles
\`a
$A,$ car
$\Phi(A)$ est vide. Cette relation d'ordre est partielle
car il peut arriver que $\Gamma(A)$ et $\Gamma(B)$ soient
simultan\'ement non vides. C'est le cas plus loin dans
l'exemple de $P_2$, contrairement au cas de $P_1$, o\`u
l'ordre entre les trois solutions stables \'etait total.

\th
Th\'eor\`eme {\rm (Conway)}| La relation d'ordre de pr\'ef\'erence
masculine d\'efinit une structure de treillis sur l'ensemble des
solutions stables pour une configuration $P$ donn\'ee.
\finth

\dem
En effet, soient $A$ et $B$ deux solutions stables
quelconques. D\'esignons par $C$ la solution qui consiste \`a
attribuer \`a chaque gar\c con celle qu'il pr\'ef\`ere entre ses
deux \'epouses selon $A$ et selon $B.$ 

Montrons d'abord qu'on d\'efinit bien ainsi une solution,
c'est-\`a-dire que deux gar\c cons $G$ et $G'$ ne risquent pas de se
voir attribuer la m\^eme fille $F$. Si cela \'etait, celle-ci
serait par exemple l'\'epouse de $G$ dans A et de $G'$ dans
$B.$ Alors $G$ pr\'ef\'ererait $A,$ et $G'$ pr\'ef\'ererait $B,$ 
elle devrait donc \^etre en d\'esaccord avec tous les deux
sur la pr\'ef\'erence \`a accorder entre les deux solutions, ce
qui est absurde. Donc $C$ est bien une solution. Notons en
passant que $C$ consiste \`a faire \'epouser \`a chaque fille le
gar\c con qu'elle aime le moins entre ses \'epoux selon~$A$
et~$B$.

Montrons que $C$ est stable. Soit $G$ un gar\c con
quelconque, $F$ une fille qu'il pr\'ef\`ere \`a son \'epouse dans
$C,$ autrement dit \`a ses deux \'epouses dans $A$ et dans
$B.$ Mais nous savons que $F$ pr\'ef\`ere son \'epoux dans $A$
\`a $G,$ car $A$ est stable, et elle pr\'ef\`ere \'egalement son
\'epoux dans $B$ \`a $G,$ car $B$ est stable. Or son \'epoux
dans $C$ est l'un d'eux, celui des deux qu'elle aime le
moins mais qu'elle pr\'ef\`ere quand m\^eme \`a $G.$ Donc $C$ est
stable.
 
On d\'esigne cette solution $C$ par $\sup(A, B)$ ($\sup$ pour
les gar\c cons, bien s\^ur), on d\'efinit de la m\^eme mani\`ere une
solution $\inf (A, B),$ et on v\'erifie sans difficult\'e que
l'ensemble des solutions stables muni de ce $\sup$ et de
cet $\inf$ est un treillis distributif.

\medskip
{\it Exemple: }voici le treillis des quatre solutions stables
de $P_2$, o\`u 
$\Masc =\sup(A,B)$ et $\Fem = \inf(A, B)$ :

\def\segment(#1,#2)\dir(#3,#4)\long#5{%
\leftput(#1,#2){\lline(#3,#4){#5}}}

{\eightpoint
\centerline{\vbox{\vskip 10mm
\offinterlineskip
%\Grille
\centerput(0,3){$\Masc=(G_1,F_1)(G_2,F_2)(G_3,F_3)(G_4,F_4)(F_5)$}
\segment(0,0)\dir(-1,-1)\long{20}
\segment(0,0)\dir(1,-1)\long{20}
\centerput(-32,-24){$A=(G_1,F_2)(G_2,F_1)(G_3,F_3)(G_4,F_4)(F_5)$}
\centerput(32,-24){$B=(G_1,F_1)(G_2,F_2)(G_3,F_4)(G_4,F_3)(F_5)$}
\segment(-20,-25)\dir(1,-1)\long{20}
\segment(20,-25)\dir(-1,-1)\long{20}
\centerput(0,-50){$\Fem=(G_1,F_2)(G_2,F_1)(G_3,F_4)(G_4,F_3)(F_5)$}
\vskip60mm
}\kern0mm}

}
Pour en revenir au cas g\'en\'eral, le treillis \'etant fini, il
existe toujours une solution maximum Max, et on peut
reformuler le th\'eor\`eme d'optimalit\'e annonc\'e plus haut
sous la forme suivante:
$${\rm Max} = \Masc.$$

Nous d\'emontrerons ce th\'eor\`eme comme corollaire d'un
r\'esultat plus pr\'ecis d\^u \`a Hwang, r\'esultat qui sera l'outil
central pour comprendre l'inefficacit\'e du mensonge
masculin.

\section 1.5. Infid\'elit\'e de l'\'epouse d'un revendicateur|Soit $P$
une configuration de pr\'ef\'erences (compl\`ete ou non),
$\Masc$ la solution stable issue de l'algorithme des initiatives
masculines, et $A$ une autre solution rationnelle. Un gar\c con $R$
est dit revendicateur de $A$ s'il pr\'ef\`ere cette solution \`a {\sl
Masc}, parce qu'il est mari\'e dans $A$ \`a une fille qu'il pr\'ef\`ere \`a
son \'epouse selon $\Masc$. On d\'esigne par $R(A)$ l'ensemble des
revendicateurs de~$A.$ 

Une autre formulation du th\'eor\`eme d'optimalit\'e consiste \`a
dire que si $R(A)$ est non vide, alors $A$ est instable. On
peut cependant donner un r\'esultat plus pr\'ecis.

\th
Th\'eor\`eme {\rm (Hwang [2])}|Soit $A$ une solution rationnelle
distincte de $\Masc$. Si l'ensemble $R(A)$ des
revendicateurs de $A$ est non vide, alors il existe
\'egalement des non revendicateurs et l'un d'eux, $G,$
constitue une cause d'infid\'elit\'e pour $A$ avec l'\'epouse
$F$ d'un revendicateur.
\finth

\dem
Notons d'abord que l'hypoth\`ese que $A$ est rationnelle
implique que les revendicateurs sont jug\'es acceptables par leurs
\'epouses dans $A,$ et cela implique qu'elles sont \'egalement
mari\'ees dans $\Masc$ sinon $\Masc$ serait instable. 

Il y a un cas o\`u le th\'eor\`eme est
\'evident, c'est quand il existe une fille $F$ qui est l'\'epouse d'un revendicateur $R$ dans
$A$ et l'\'epouse d'un non revendicateur $G$ dans $\Masc$. En effet
il est clair que $(G,F)$ est une cause d'infid\'elit\'e : d'une part, $G$
ne revendique pas $A,$ et pr\'ef\`ere donc $F$ \`a son \'epouse (ou \`a
son c\'elibat) selon $A,$ d'autre part $F$ pr\'ef\`ere $G$ \`a $R,$ sinon
$(R, F)$ serait une cause d'infid\'elit\'e pour $\Masc$, qui est stable.

Supposons \`a pr\'esent qu'une telle fille n'existe pas. Il en
r\'esulte que l'ensemble des \'epouses des revendicateurs de $A$ est
le m\^eme ensemble dans les deux solutions, et que ceux-ci
revendiquent ``simplement" de pouvoir \'echanger leurs \'epouses
entre eux !

Reportons-nous au d\'eroulement de l'algorithme des initiatives
masculines et consid\'erons le {\it dernier mouvement} au cours
duquel on trouve un revendicateur invitant une fille. Soit $R$ ce
revendicateur et $F$ cette fille. Il est clair que $R$ \'epouse $F$
\`a l'issue de Masc, sinon ce ne serait pas le dernier
mouvement de ce type puisque nous savons que de toute mani\`ere
$R$ se marie \`a l'issue de Masc. Donc R n'est pas le
revendicateur qui revendique $F$ comme \'epouse dans A, sinon il
serait indiff\'erent et non revendicateur. Celui qui la revendique
dans A est un certain $R',$ qui \'epouse une autre fille $F'$ \`a
l'issue de $\Masc$, mais qui pr\'ef\`ere F \`a cette $F'$ et qui par
cons\'equent s'est fait rejeter par F au cours de l'algorithme. De
cela on d\'eduit que $F$ avait un pr\'etendant \`a l'arriv\'ee de
$R.$ Appelons $G$ ce pr\'etendant qui s'est fait \'evincer par $R$ et montrons que $(G, F)$ est
la cause d'infid\'elit\'e annonc\'ee.

\goodbreak
En fait, le pr\'etendant $G$ n'est pas $R',$ ni aucun autre
revendicateur, sinon ce revendicateur reviendrait inviter
ult\'erieurement dans le cours de l'algorithme, ce qui est exclu
puique c'est au cours du {\it dernier mouvement d'invitation par
un revendicateur} que
$G$ s'est fait supplanter. $G$ est par cons\'equent un non revendicateur (il en existe donc).
Puisque $G$ est l'avant-dernier pr\'etendant de $F,$ elle le pr\'ef\`ere \`a $R',$ qu'elle a rejet\'e
ant\'erieurement et qui veut \^etre son \'epoux dans $A.$ D'autre part $G$ pr\'ef\`ere $F$ \`a son \'epouse
dans $\Masc$ (ou \`a son c\'elibat) puisque $F$ l'a rejet\'e. Enfin, $G$
aime au moins autant sa situation dans $\Masc$ (\'epouse ou
c\'elibat) \`a sa situation dans $A$ puisqu'il est non revendicateur.
Donc $(G,F)$ est une cause d'infid\'elit\'e pour~$A.$ \cqfd

\medskip
    En m\^eme temps nous avons donc d\'emontr\'e le th\'eor\`eme d'optimalit\'e, pour lequel il
existe des d\'emonstrations plus directes (\cf. [4], [5], [7]) mais
aucune vraiment facile. Cependant le principal int\'er\^et du
th\'eor\`eme de Hwang est qu'il permet d'obtenir imm\'ediatement le
th\'eor\`eme de Dubins et Freedman (\cf. la fin du pr\'esent article)
dont la preuve originale \'etait longue et technique.

\vskip-5pt
\titre 2. Mensonges et manipulations|

\vskip-5pt
\section 2.1. Pr\'evoir le destin de chacun|Nous supposons \`a
pr\'esent que l'agence matrimoniale est dirig\'ee par une dame plut\^ot
conformiste qui consid\`ere comme allant de soi qu'on doit laisser
toutes les initiatives aux gar\c cons, et que par cons\'equent d\`es que
la configuration de pr\'ef\'erences $P$ est connue, on
d\'etermine la solution stable qui lui correspond et qui
n'est autre que $\Masc(P)$, laquelle se d\'egagera tout
naturellement au cours du bal qu'elle compte organiser, au
cours duquel les ``convenances" exigent que ce soient les
garcons qui invitent.

Comme cette dame est curieuse de nature, elle exige de tous
ses adh\'erents qu'ils exp\'edient pr\'ealablement leurs listes de
pr\'ef\'erences (qu'ils auront \'etablies apr\`es consultations du
fichier et des rencontres au si\`ege de l'agence, car nous
supposons que la directrice respecte au moins l'axiome
d'information). Ainsi, prenant connaissance de la configuration de
pr\'ef\'erences, elle pourra pr\'evoir le d\'eroulement de l'algorithme et
connaitra avant tout le monde le destin de chacun.

Le prix de cette curiosit\'e, c'est \'evidemment le risque
d'indiscr\'etion. On peut imaginer que la secr\'etaire de l'agence
communique tout ou partie de la configuration des pr\'ef\'erences \`a
l'un(e) des adh\'erent(e)s, permettant ainsi que des manipulations
faussent le r\'esultat.

\goodbreak
\section 2.2. Manipulations f\'eminines|Supposons par exemple que
nous ayons trois gar\c cons et trois filles et la configuration de
pr\'ef\'erences compl\`etes que voici:

$$\vbox{
\halign{\strut\vrule
\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule
&\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule\cr
\noalign{\hrule}  
G_1:&F_1&F_2&F_3&F_1:&F_2&G_1&G_3\cr
G_2:&F_2&F_1&F_3&F_2:&G_1&G_2&G_3\cr
G_3:&F_2&F_3&F_1&F_3:&G_3&G_1&G_2\cr
\noalign{\hrule}
}}
$$

\centerline{Configuration des vraies pr\'ef\'erences $P_3$}

\medskip
Supposons que $F_2$ tarde \`a exp\'edier sa liste, et se fasse
discr\`etement communiquer par la secr\'etaire les listes de
pr\'ef\'erences des autres adh\'erents. Elle est en mesure de pr\'evoir
le d\'eroulement de l'algorithme des initiatives masculines:
au premier mouvement, $G_1$ devient pr\'etendant de $F_1$,
tandis que $G_2$ et $G_3$ sont en concurrence aupr\`es de $F_2$
qui choisit $G_2$; au deuxi\`eme mouvement, $G_3$ revient aupr\`es
de $F_3.$ D 'o\`u:
$$\Masc(P_3) = (G_1,F_1)(G_2,F_2)(G_3,F_3).$$

C'est pourquoi $F_2$ d\'ecide de mentir sur ses pr\'ef\'erences, et
d'agir comme si elle pr\'ef\'erait
$G_3$ \`a $G_2$. D'o\`u la configuration des fausses pr\'ef\'erences que voici:

$$\vbox{
\halign{\strut\vrule
\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule
&\ $#$\ &\ $#$\ &\ $#$\ &\ $#$\ \vrule\cr
\noalign{\hrule}  
G_1:&F_1&F_2&F_3&F_1:&G_2&G_1&G_3\cr
G_2:&F_2&F_1&F_3&F_2:&G_1&G_3&G_2\cr
G_3:&F_2&F_3&F_1&F_3:&G_3&G_1&G_2\cr
\noalign{\hrule}
}}
$$

\centerline{Configuration des fausses pr\'ef\'erences $P_4$}

\medskip
Voici en effet le d\'eroulement de l'algorithme sur la configuration
$P_4$:
au premier mouvement, $G_1$ devient pr\'etendant de $F_1$,
tandis que $G_2$ et $G_3$ sont en concurrence aupr\`es de $F_2$
qui choisit cette fois $G_3$ en mentant sur sa pr\'ef\'erence. Au
deuxi\`eme mouvement, $G_2$ invite $F_1,$ qui le pr\'ef\`ere et rejette
donc $G_1.$ Au troisi\`eme mouvement, $G_1$ vient aupr\`es de $F_2$
qui triomphe car elle obtient enfin celui qu'elle pr\'ef\`ere. Elle
rejette $G_3$ qui se consolera au quatri\`eme mouvement avec
$F_3.$ R\'esultat:
$$\Masc(P_4) = (G_1, F_2)(G_2,F_1)(G_3,F_3).$$

Autrement dit $F_2$ obtient par son mensonge la solution optimale pour les filles, qui n'est
autre que $\Fem(P_3)$ et qui est donc stable, m\^eme pour les
vraies pr\'ef\'erences.
 
Certes, on peut voir que ce type de manipulation f\'eminine n'est
pas toujours possible avec une configuration compl\`ete. Cependant,
dans le cas o\`u l'agence autorise les configurations de
pr\'ef\'erences incompl\`etes (ce qui est bien la moindre des choses,
le mariage forc\'e n'\'etant gu\`ere en vogue de nos jours), il est
facile de voir que toute configuration est manipulable par les
filles. Si les filles connaissent les pr\'ef\'erences des garcons (et
font patienter pour faire conna\^\i tre les leurs), elles
peuvent se r\'eunir, se d\'evoiler clandestinement leurs
vraies pr\'ef\'erences, \'etudier la configuration des vraies
pr\'ef\'erences $P,$ d\'eterminer
$\Fem(P)$ par l'algorithme des initiatives f\'eminines. Puis elles
d\'ecr\`etent inacceptable tout gar\c con qui vient apr\`es celui qui leur
est attribu\'e selon $\Fem(P)$. Il est clair que sur la
configuration incompl\`ete  $P'$ ainsi modifi\'ee, qu'elles
pr\'esenteront \`a l'agence, on a, in\'evitablement, 
$\Masc(P') = \Fem(P') = \Fem(P).$

\section 2.3. Impuissance du mensonge masculin|On pourrait
penser qu'un gar\c con, ou une coalition de garcons, peut en faire
autant, et obtenir une fille pr\'ef\'erable en mentant sur ses (ou
leurs) pr\'ef\'erences. Or nous pouvons d\'ej\`a pr\'evoir une premi\`ere
faiblesse du mensonge masculin, qui est que de toute mani\`ere en
pr\'etendant ``am\'eliorer" encore la solution $\Masc$, qui est la
solution optimale pour eux, il ne peut conduire qu'\`a des solutions
instables pour les vraies pr\'ef\'erences, or ce d\'efaut majeur
n'affectait nullement le mensonge f\'eminin comme nous venons de
le voir.

On peut cependant imaginer le cas d'un revendicateur
indiff\'erent au fait que la solution alt\'er\'ee par son mensonge soit
instable, d'autant que rien ne lui prouve que c'est son \'epouse qui
sera infid\`ele (le th\'eor\`eme de Hwang n'exclut pas que ce soit
l'\'epouse d'un autre revendicateur). Les tentatives manipulatoires
de ce genre d'individu seront ruin\'ees par le th\'eor\`eme suivant.

\th
Th\'eor\`eme {\rm (Dubins-Freedman [3])}|Si un gar\c con ment sur ses
pr\'ef\'erences au cours de l'algorithme des initiatives masculines,
il n'ob\-tien\-dra pas une fille pr\'ef\'erable \`a celle qu'il aurait
obtenu en agissant selon ses vraies pr\'ef\'erences.
\finth

\dem
Soit $P$ la configuration des vraies pr\'ef\'erences, $P'$ une
configuration modifi\'ee qui ne diff\`ere de $P$ que par la liste des
pr\'ef\'erences d'un gar\c con $R,$ que nous d\'esignons ainsi parce que
nous supposons qu'il pr\'ef\`ere $\Masc(P')$ \`a $\Masc(P).$ 

D'apr\`es le th\'eor\`eme de
Hwang, $A = \Masc(P')$ est instable pour $P,$ la cause
d'instabilit\'e \'etant un couple
$(G,F),$ o\`u $G$ est distinct de $R.$ Or les pr\'ef\'erences de $G$ et de $F$ selon $P'$ sont
rigoureusement les m\^emes que selon~$P,$ donc la solution $A$ est
\'egalement instable pour
$P'$, ce qui est absurde puisque c'est $\Masc(P').$\cqfd

Ce th\'eor\`eme illustre en quel sens on peut dire qu'on trouve
d'un c\^ot\'e ceux qui pr\'etendent d\'ecider, et de l'autre, celles qui
peuvent manipuler.


 \titre 3. Probl\`emes de recherche|
On peut compliquer ces probl\`emes de manipulation, li\'es \`a la
th\'eorie des jeux, par exemple en introduisant des dots, dans un
sens ou dans l'autre, qui font varier la configuration de
pr\'ef\'erences. Citons \`a ce sujet les travaux de Gabrielle Demange
[1].

     Sur le strict plan combinatoire et algorithmique, beaucoup d'aspects du sujet restent
m\'econnus. On trouvera une liste de probl\`emes de recherche sur les mariages stables dans
le livre de Knuth [7]. En voici quelques-uns:

\decale (1)|Existe-t-il des ``algorithmes d'initiatives
mixtes" permettant d'en\-gen\-drer les solutions stables
interm\'ediaires, ou n'a-t-on pas d'autre ressource pour
en dresser la liste que de tester toutes les solutions, en
cherchant syst\'ematiquement pour chacune d'elle une
\'eventuelle cause d'infid\'elit\'e ?

\decale (2)|Avec $n$ gar\c cons et $n$ filles, comment
fabriquer une configuration de pr\'ef\'erences compl\`etes qui
maximise le nombre de solutions stables ? Ce nombre
maximal est $3$ pour $n = 3,$ tr\`es probablement $10$ pour
$n = 4$ (\cf. [4], [7]). Quelle est la croissance de ce
nombre maximal en fonction de~$n$ ? On sait montrer
qu'elle est au moins exponentielle [7], peut-on esp\'erer
qu'elle soit de l'ordre de $n!$ (nombre total de solutions)
?

\bigskip\bigskip
{\eightpoint
\centerline{BIBLIOGRAPHIE}

\bigskip

\article 1|G. Demange, D. Gale|The strategy structure of two-sided matching 
markets|Econometrica|53|1985|873-878|

\article 2|G. Demange, M. Sotomayor|A further note on the
stable matching problem|Disc. Applied
Math.|16|1987|217-222|

\article3| L.E.Dubins, D.Freedman| Macchiavelli and the Gale-Shapley Algorithm|
Amer. Math. Monthly|88|1981|485-494|

\divers4|D.Dumont| Les mariages stables, Pour la Science,
oct.1989|

\article5|D.Gale, L.S.Shapley| College Admission and the
Stability of Marriage| Amer. Math. Monthly|69|1962|9-14|

\article6|D.Gale, M.Sotomayor| Ms Macchiavelli and the stable matching problem|
Amer. Math. Monthly|92|1985|61-268|

\livre7|D.Knuth|Mariages stables|Presses de l'Universit\'e de Montr\'eal|1976|

}

\tenpoint 
\nobreak 
\vskip 1cm
\rightline{\vbox{\hbox{Dominique {\petcap Dumont},}
                 \hbox{D\'epartement de math\'ematique,}
                 \hbox{Universit\'e Louis Pasteur,}
                 \hbox{7, rue Ren\'e-Descartes,}
\hbox{F-67084 Strasbourg.}}\qquad}

\bye


                                               


