\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