\documentclass[10pt]{article}
\usepackage{amsthm,amsfonts,amsmath,amscd,amssymb,latexsym,epsfig}
\usepackage{hyperref} %%% WARNING: Delete .aux on the first use.
\usepackage[all]{xy}
%\usepackage{showkeys}
%
%%%%%%%%%%%%%%%% header %%%%%%%%%%%%%%%%%
%
\title{Hyperbolic Fixed Points of $\C^*$ Actions}
\author{JWR \& DS}
\date{Thursday 13 July 2006 2:50}
%
%%%%%%%%%%%%%%%% Environments/macros %%%%%%%%%%
%
\newtheorem{PARA}{}[section]
\newtheorem{theorem}[PARA]{Theorem}
\newtheorem{corollary}[PARA]{Corollary}
\newtheorem{lemma}[PARA]{Lemma}
\newtheorem{proposition}[PARA]{Proposition}
\newtheorem{definition}[PARA]{Definition}
\newtheorem{remark}[PARA]{Remark}
\newtheorem{example}[PARA]{Example}
\newtheorem{conjecture}[PARA]{Conjecture}
%
\newcommand{\para}{\begin{PARA}\rm}
\newcommand{\arap}{\end{PARA}\rm}
\newcommand{\dfn}{\begin{definition}\rm}
\newcommand{\nfd}{\end{definition}\rm}
\newcommand{\rmk}{\begin{remark}\rm}
\newcommand{\kmr}{\end{remark}\rm}
\newcommand{\xmpl}{\begin{example}\rm}
\newcommand{\lpmx}{\end{example}\rm}
%
\newcommand{\jdef}[1]{{\bf #1}}
\newcommand{\ds}{\displaystyle}
\newcommand{\Iso}{\mathrm{Iso}}
\newcommand{\Times}[2]{{}_{#1}\!\!\times_{#2}}
\newcommand{\liftbox}{\par\vspace{-2em}}
%
The constitution says that apportionment of representatives
to a state should be proportional to its population.
If taken literally, this would mean
giving fractional representatives, so some method
of converting fractions to whole numbers must be used.
Over the years, the choice of method
has led to many battles in the U.S. House of Representatives,
and there will doubtless be more.
There is a vast
academic literature on the subject; see e.g.\ the
\href{http://www.ams.org/featurecolumn/archive/apportionII5.html}{
\underline{references section}}
of the websites~\cite{Apportionment},\cite{Apportionment II}.
The clearest exposition I have found so far is~\cite{BY-AMM};
this article also contains many amusing details on the
history of the problem. The notes at the end of the article give
the sources for the historical information in given here.
Some of the material which follows is copied
verbatim from various websites as indicated
in Appendix~\ref{app:notes}.
Various methods of apportionment have been used over the years.
Often the result seems unfair to many people and many bitter disputes
have resulted. Here is a list
of surprising things that happened
as a result of using one method or another.
\para \jdef{The Alabama Paradox.}\label{AlabamaParadox}
An increase in the total number of seats to be apportioned can cause a state to lose a seat.
The Alabama Paradox first surfaced after the 1870 census. With 270 members in the House of Representatives, Rhode Island got 2 representatives but when the House size was increased to 280, Rhode Island lost a seat. After the 1880 census,
C. W. Seaton (chief clerk of U. S. Census Office) computed apportionments for all House sizes between 275 and 350 members. He then wrote a letter to Congress pointing out that if the House of Representatives had 299 seats, Alabama would get 8 seats but if the House of Representatives had 300 seats, Alabama would only get 7 seats.
The method used at the time was Hamilton's method explained below
in paragraph~\ref{}.
\arap
% Illustrating the Alabama Paradox
\para \jdef{The Population Paradox.}\label{PopulationParadox}
An increase in a state's population can cause it to lose a seat.
The Population Paradox was discovered around 1900, when it was shown that a state could lose seats in the House of Representatives as a result of an increase in its population. (Virginia was growing much faster than Maine,
but Virginia lost a seat in the House while Maine gained a seat.)
The method used at the time was Hamilton's method explained below
in paragraph~\ref{}.
\arap
\para \jdef{The New States Paradox.}\label{NewStatesParadox}
Adding a new state with its fair share of seats can affect the number of seats due other states.
The New States Paradox was discovered in 1907 when Oklahoma became a state. Before Oklahoma became a state, the House of Representatives had 386 seats. Comparing Oklahoma's population to other states, it was clear that Oklahoma should have 5 seats so the House size was increased by five to 391 seats. The intent was to leave the number of seats unchanged for the other states.
However, when the apportionment was mathematically recalculated,
Maine gained a seat (4 instead of 3) and New York lost a seat (from 38 to 37).
The method used at the time was Hamilton's method explained below
in paragraph~\ref{}.
\arap
\para \jdef{The Quota Paradox.} \label{QuotaParadox}
A state may receive a number of seats
which is smaller than its lower quota or larger than its upper quota.
This happened in the apportionment
based on the 1820 census when
New York had a population of 1,368,775,
the total U.S. population was 8,969,878,
and the size of the house was 213.
New York's quota was thus
$
q=\frac{1,368,775}{8,969,878}\times 213=32.503.
$
However the apportionment method used at the time
(Jefferson's method explained below in paragraph~\ref{}) awarded New York
34 seats.
\arap
\begin{quote}\em
There seems to be no known apportionment method which avoids
all these paradoxes! See Remark~\ref{rmk:paradox} below.
\end{quote}
\section{Notation and Terminology}
\para
Assume that there are $n$ states numbered $i=1,2,\ldots,n$
and that $p_ i$ denotes the population of the $i$th state
so that
$$
p=p_1+p_2+\cdots+p_n
$$
is the total population of the entire country.
We call a sequence $(p_1,p_2,\ldots,p_n)$
of nonnegative integers a \jdef{population vector}.
We suppose that $h$ denotes the total number of seats
to be allocated and call it the \jdef{hpuse size}.
An
\jdef{apportionment} of length $n$ and house size $h$
is a sequence $(a_1,a_2,\ldots,a_n)$ of whole numbers such that
$$
h = a_1+a_2+\cdots+a_n.
$$
The number $a_i$ is the number of representatives assigned to the $i$th state
by the apportionment.
An \jdef{apportionment method} is a sequence of functions%\footnote{
%The notation
%$x\mapsto$\ y$ indicates a function which produces the output $y$
%for input $x$.
%)
$$
(h,p_1,p_2,\ldots,p_n)\mapsto (a_1,a_2,\ldots,a_n)
$$
(one for every value of $n$) which assign to every house size $h$
and every population vector $(p_1,p_2,\ldots,p_n)$ an apportionment
$(a_1,a_2,\ldots,a_n)$ of house size $h$.
The table in Figure~\ref{fig:ap} shows the outputs given
by five different apportionment methods based on
the U.S. census data for 1990. Here we have $n=50$, $h=435$, and
$p=249,022,783$. Wisconsin is the 49th state in alphabetical order
so $p_ {49}=4,906,735$. Four of the apportionment methods
award Wisconsin 9 representatives, but Jefferson's Method awards
Wisconsin only 8.
\arap
\begin{figure}[p]
\label{fig:ap}
\caption{Apportionment of the U.S. House of Representatives}
\bigskip
\tiny
\input{1990}
\end{figure}
\para
%
The \jdef{quota}\footnote{Some authors call this the {\em standard quota},
others call it the {\em exact quota}.} for $i$th state
is the fraction
$$
q_i = \frac{p_i}{p}\times h
$$
of the total number of seats a state would be entitled to if the seats were not indivisible. The \jdef{lower quota} of a state is its quota rounded down,
and the \jdef{upper quota} is its quota rounded up. In standard mathematical
notation the lower and upper quota of the $i$th state are
denoted $\lfloor q_i\rfloor$ and $\lceil q_i\rceil$ respectively.
\arap
An apportionment which avoids this paradox is said to
satisfy the quota condition, i.e. an apportionment
$(a_1,a_2,\ldots,a_n)$ satisfies the \jdef{quota condition} iff
$$
\lfloor q_i\rfloor\le a_i\le \lceil q_i\rceil
$$
for $i=1,2,\ldots,n$.
\section{Apportionment Methods}
\para\jdef{Hamilton's Method}. \label{Hamilton}
For each $i$ calculate the quota $q_i=p_i/h$ of the $i$th state. The sum
$h'=\lfloor q_1\rfloor+\lfloor q_2\rfloor+\cdots+\lfloor q_n\rfloor$
will satisfy $h-n\le h' \frac{a_j}{p_ j} \eqno(*)
$$
the people in $i$th state have more representatives per person
than those of the $j$th state and are thus ``better represented''.
A function $T(p_i,a_i,p_j,a_j)$ such that
$$
T(p_i,a_i,p_j,a_j)>0\iff \frac{a_i}{p_ i}>\frac{a_j}{p_ j}
$$
is called a \jdef{fairness measure}. The idea is that the bigger
$T(p_i,a_i,p_j,a_j)$ is the more unfair is the gap
between the representation of $i$th state and the $j$th state.
An allocation is called \jdef{stable} for a given fairness measure
iff for each pair of states, switching a representative
from the better represented state $i$ to the other state $j$ makes
state $j$ better represented and the measure larger, i.e. iff
$$
T(p_j,a_j+1, p_i,a_i-1)\ge T(p_i,a_i,p_j,a_j)
$$
for all pairs of states.
%%
\begin{theorem}[Huntington]\label{thm: Huntington}
Assume the apportionment $(a_1,a_2,\ldots,a_n)$
results from one of the aforementioned divisor methods.
Then
%%
\begin{itemize}
\item For
$\ds
T(p_i,a_i,p_j,a_j) =a_j-a_i(p_j/p_i)
$,
Adams' Method is stable.
\item For
$\ds
T(p_i,a_i,p_j,a_j) =p_i/a_i-p_j/a_j
$,
Dean's Method is stable.
\item For
$\ds
T(p_i,a_i,p_j,a_j) =(p_ja_i/p_ia_j)-1
$,
Huntington-Hill's Method is stable.
\item For
$\ds
T(p_i,a_i,p_j,a_j) =a_j/p_j-a_i/p_i
$,
Webster's Method is stable.
\item For
$\ds
T (p_i,a_i,p_j,a_j) =a_i(p_j/p_i)-a_i
$,
Jefferson's Method is stable.
\end{itemize}
%%
(In all definitions the $i$th state is better represented,
i.e. $p_i/a_i\ge p_j/a_j$.)
\end{theorem}
\rmk It is easy to see the appeal of Webster's Method;
it is the method which attempts to make the
number of representatives per person the same
in all states by minimizing the differences
$p_i/a_i-p_j/a_j$. Similarly Dean's Method
attempts to minimize the differences
$a_j/p_j- a_i/p_i$ in the average district size
for the various states. The Huntington-Hill Method
attempts to minimize the relative differences
of these quantities as we now explain.
The \jdef{relative difference} of two numbers
is the result of subtracting the larger from the smaller
and then dividing by the smaller.
Now the inequality~$(*)$ can be written in four ways:
$$
\frac{a_i}{p_ i}>\frac{a_j}{p_ j}\iff
\frac{p_j}{a_j}>\frac{p_i}{a_i} \iff
a_i>a_j\frac{p_i}{p_ j}\iff
a_i\frac{p_j}{p_i}>a_j.
$$
We can get four of the five fairness measures in
Theorem~\ref{thm: Huntington} from these four ways
by subtracting the right side from the left.
The differences of the two sides in each of these ways.
The relative difference between the two sides
is the same for all four ways, i.e.
$$
\frac{\frac{a_i}{p_ i}-\frac{a_j}{p_ j}}{\frac{a_j}{p_ j}}=
\frac{\frac{p_j}{a_j}-\frac{p_i}{a_i}}{\frac{p_i}{a_i}}=
\frac{a_i-a_j\frac{p_i}{p_ j}}{\frac{p_i}{p_ j}}=
\frac{a_i\frac{p_j}{p_i}-a_j}{a_j}=\frac{p_ja_i}{p_ia_j}-1.
$$
The last expression is the fairness measure for
the Huntington-Hill Method. Perhaps this is why Huntington thought
his fairness measure was the best, but which measure is the
best is a value judgment, not a mathematical question.
\kmr
\rmk\label{rmk:paradox}
In~\cite{BY-AMM} Balinski and Young
devised an ingenious method which they
call the \jdef{Quota Method}, which
avoids both
the Quota Paradox
and the Alabama paradox.% (see paragraph~\ref{AlabamaParadox}).
However, their Quota Method does not avoid the
Population Paradox. % (see paragraph~\ref{PopulationParadox}).
In their book~\cite{BY} they show that
\begin{itemize}
\item
Divisor methods avoid the Alabama Paradox, the Population Paradox,
and the New State Paradox, % (see paragraph~\ref{NewStatesParadox}),
but
%
\item No divisor method can avoid the Quota Paradox. In other words,
for any divisor method there exists $(p_1,p_2,\ldots,p_n)$ and $h$
such that the method assigns $(a_1,a_2,\ldots,a_n)$
where either $a_i<\lfloor q_i\rfloor$ for some $i$ or
$\lceil q_i\rceil