\documentstyle[12pt,twoside,amstex,amsfonts,psfig]{article}

\raggedbottom

\input{macros-course}

\newtheorem{falsethm}[theorem]{False Theorem}

\begin{document}

\tutprobn{4}{2/26/99}{February 26, 1998}

\begin{problems}

\problem \emph{Stable marriages}.  To seek fairer stable marriages than the
man-optimal one provided by the Gale-Shapley procedure (or the
woman-optimal one obtained by reversing gender roles) described in
lecture, we might allow both men and women to \emph{both} propose and be
proposed to.  At any stage, the men and women have a list of potential
fiance's who have not rejected them.  Each person proposes to their top
remaining choice.  Then any person with more than one suitor may reject
any of their suitors but the best.  The process continues until no more
rejections are possible.

Analyze this process.  Here are some questions to consider: is the process
guaranteed to halt?  when it halts, is everybody always married?  when it
halts, is the marriage set stable?  can it reach a halt at more than one
marriage set?

\problem
In this problem we'll examine a two-person game.  It is not one you're
likely to be familiar with because it allows an \emph{infinite number}
of different possible moves.  Here are the rules:

Player 1 chooses any integer $n\geq 1$.  Then player 2 chooses any
$n$-tuple of natural numbers.  After that, the players alternate moves,
choosing at each move any $n$-tuple of natural numbers which is NOT
coordinatewise $\geq$ any previously chosen $n$-tuple.  The game ends when
some player cannot move.

For example, player 1 might begin by choosing $n=3$.  Then player 2 might
choose the 3-tuple (8, 9, 10).  Possible subsequent choices might then be
\[
(7,8,9), (0,1,67), (83, 0,0), (1,0,0), (0,0,1) (0,1,0)
\]
This finally leaves player 1 with only the move (0,0,0), and the game ends
since no more moves are possible.

\bparts

\ppart  Suppose player 1 chooses $n=2$ and player 2 chooses the pair
(0,1).  Show that there is still no finite bound on how long the game
might continue.

\medskip
Although there are arbitrarily long games, it turns out that every game
must end at some point; no game can go on forever!  We'll help you to
prove this remarkable fact by developing properties of a special class of
well-founded posets.

\ppart Let us make the following definition.  A poset$(P,\preceq)$ is 
\emph{well-quasi-ordered} iff, for every infinite 
sequence $p_1, p_2, \dots p_n \dots$ of elements in $P$, there are positive
integers $i<j$ such that $p_i \preceq p_j$.

\medskip
Prove that if $(P,\preceq)$ is well-quasi-ordered then it is
well-founded.

\ppart Prove that if $(P,\preceq)$ is well-quasi-ordered and $S$ is a
subset of $P$, then $S$ has only a \emph{finite} number of minimal
elements.  (Remember, $m \in S$ is \emph{minimal} iff no other element of
$S$ is $\preceq m$.)

\ppart Prove that any infinite sequence of elements in a
well-quasi-ordered poset contains an infinite nondecreasing subsequence.
That is, if $(P,\preceq)$ is a well-quasi-ordered poset, and $p_1, p_2,
\dots p_n \dots$ is an infinite sequence of elements in $P$, then there is
an infinite sequence of integers $i_1 < i_2 < i_3< \dots$ such that
$p_{i_1} \preceq p_{i_2} \preceq p_{i_3} \preceq \dots$.  \hint Explain
why there must be a minimal element in the sequence which is $\preceq$ an
infinite number of $p_i$'s.  

\ppart Prove that if $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered
posets, then so is $P \times Q$ under the coordinatewise partial order.

\ppart Now prove that the game must end.

\eparts

\end{problems}

\end{document}

