this sample. In some instances, the pool of households from which this sample
is taken includes all households that were surveyed in the original census. In
other cases, such as in the US census, this pool of potential households is
constructed independently of the original census. Our suggested census RLA
method applies for both options.

After sampling the households to be included in the PES, a new and independent
survey contacts each household and asks them the exact same questions as the
original census. Since the PES is conducted a few months or years after the
census, the household members report their answers as they were on the date of
the original census. For our purposes, the only information of interest is the
number of residents living at each household999Some countries may allocate
representatives to federal-states according to the number of a specific sector
of the population that they hold (e.g. eligible voters or citizens). In this
work, we assume it’s simply the number of residents, but our methods apply in
the same manner otherwise.. If a sampled household did not respond during the
PES, it reports that it holds no residents.

We denote the information given by the census as follows:

  * •

$H^{cen}$: A list of households that were surveyed.

  * •

$g^{cen}(h)$: The number of residents a household $h\in H^{cen}$ has according
to the census.

And denote the information given by the PES as:

  * •

$H^{PES}$: A list of households from which the sample used by the PES was
chosen. This may or may not be identical to $H^{cen}$.

  * •

$\tilde{H}^{PES}$: The households which were surveyed by the PES. Must be a
subset of $H^{PES}$.

  * •

$g^{PES}(h)$: The number of residents a household $h\in{\tilde{H}^{PES}}$
holds according to the PES.

####  4.1.2 The Census RLA Model

In our model a nation allocates $R$ representatives to its federal-states,
whose set we denote as $\mathcal{S}$, in proportion to their population as
measured by a country-wide census. We assume that after the census is
finished, a PES is conducted as described in Section 4.1.1. Following the
census and the PES, we learn $H^{cen}$ and $g^{cen}$ from the census, and
$H^{PES},\tilde{H}^{PES}$ and $g^{PES}$ from the PES.

We assume that the nation allocates its $R$ representatives to its federal-
states using the census results, according to a highest averages method.
Highest averages methods, such as the D’Hondt method described in Section 3.1,
are a class of methods which allocate representatives to federal-states using
an imaginary table. Each row in this table represents a state, and each column
represents a potential number of representatives it may win. Each cell of this
table holds a value which depends on its federal-state (its row), the number
of representatives it represents (its column) and the number of residents in
its federal-state according to the census. The $R$ cells with the highest
values in the table are colored, and each federal-state receives a number of
representatives equal to the number of colored cells it has in its row. The
value at cell $[s,r]$, where $s\in\mathcal{S}$ and $r\in[R]$, is:

$\displaystyle\frac{g^{cen}(s)+c_{s}}{d(r)},$ (12)

where $c_{s}$ is a constant which depends on the state $s$, and
$d:{\mathbb{N}}\rightarrow{\mathbb{N}}$ is a monotonically increasing
function. Since $d$ is monotonically increasing, the values in each row of the
table are monotonically decreasing.

The choice of $c_{s}$ and $d$ determines the exact allocation method within
the class of highest averages methods. For example, setting $d(j)=j$ and
$c_{s}=0$ for any $s\in\mathcal{S}$ results in the D’Hondt method described in
Section 3.1.

The additive factor in (12), $c_{s}$, allows our model some added flexibility,
meaning it can include more political systems. If, for example,
representatives are allocated to federal-states according to a weighted sum of
their population and their land-area, as done in Denmark [35], this model
supports this type of seat allocation by defining $c_{s}$ to be the land-area
of $s$ in appropriate units. This additive factor can also be used in cases
where part of a state’s population is not included in the PES. In the US, for
example, we would want to exclude people living in group residence (e.g.
homeless people, nursing home residents, people living in remote Alaska, etc’)
from the audit, since they are not covered by the PES. If we wish to exclude
them from the RLA, we can assume their number according to the census is
accurate and run the audit over the rest of the population. To do so within
this model, we can define $c_{s}$ to be the number of persons without
permanent residence in state $s$ according to the census.

More formally, a census-RLA is defined as follows:

######  Definition 7.

Let $f$ be a social choice function which allocates representatives to
federal-states based on census data. Let $\mathcal{C}$ be a randomized
algorithm which outputs a non-negative value, and takes the following inputs:

  * •

A list of households according to the census $H^{cen}$ and according to the
PES $H^{PES}$, where the state of each household is known.

  * •

A subset of households which were surveyed during the PES:
$\tilde{H}^{PES}\subseteq H^{PES}$.

  * •

Census results $g^{cen}:H^{cen}\rightarrow{\mathbb{N}}_{0}$.

  * •

PES results $g^{PES}:\tilde{H}^{PES}\rightarrow{\mathbb{N}}_{0}$.

$\mathcal{C}$ is a census risk-limiting audit for the social choice function
$f$ if for any $H^{cen},H^{PES}$, $g^{cen}$ and PES results over all
households $g^{PES}:H^{PES}\rightarrow{\mathbb{N}}_{0}$ , given a random
subset of PES households $\tilde{H}^{PES}\subseteq H^{PES}$ of a certain pre-
determined size, we have:

$\displaystyle f(g^{cen}(\cdot))\neq f\left(g^{PES}(\cdot)\right)$
$\displaystyle\Downarrow$
$\displaystyle\forall\alpha\in[0,1],\Pr\left[\mathcal{C}\left(H^{cen},H^{PES},\tilde{H}^{PES},g^{cen}(\cdot),g^{PES}\left(\tilde{H}^{PES}\right)\right)\leq\alpha\right]<\alpha.$

Where $g^{PES}\left(\tilde{H}^{PES}\right)$ denotes that $\mathcal{C}$ only
receives access to the PES results over the surveyed households
$\tilde{H}^{PES}$.

Note that in this definition, $g^{PES}$ encodes the results of the PES if it
was to run over all households. However, $\mathcal{C}$ only receives access to
$g^{PES}$ over households that were actually surveyed during the PES. Thus, if
$f(g^{cen}(\cdot))\neq f\left(g^{PES}(\cdot)\right)$ is true, it means if the
PES had surveyed all of $H^{PES}$, it would result in a different allocation
of representatives than that of the census. If this is true, the census RLA
guarantee demands that for any $\alpha\in[0,1]$ a census RLA will output a
value smaller than $\alpha$ w.p. of at most $\alpha$, which is exactly the
demand stated in the definition above.

### 4.2 The Census RLA Algorithm

This section suggests a new method to performs census RLAs, which relies on
the SHANGRLA framework. In Section 4.2.3, we design SHANGRLA assertions for
auditing the census’ resulting allocation of representatives to the federal-
states. While these assertions can be used as-is to perform a census RLA, they
are only an intermediate step in the development of more efficient assertions
that are eventually presented in Section 4.2.4. These assertions are used by
an adapted version of the ALPHA martingale test to perform a census RLA, as
described in Section 4.2.5.

####  4.2.1 Assumption and Notation

Our census RLA method relies on one simplifying assumption:

######  Assumption.

In both the census and in the PES, the number of residents in a single
household is upper-bounded by a known value, denoted as $g^{max}$.

The value $g^{max}$ must be set before the PES is conducted. Both the census
and the PES must report that all households have $g^{max}$ residents at most.

This assumption is necessary due to a critical difference between elections
and censuses; In elections, a single ballot has very limited power. In a
census, if it was not for this assumption, a single household could hold an
arbitrarily large number of residents and completely swing the allocation of
representatives to the states.

Under this assumption, the number of residents at a household according to the
census is given by the function
$g^{cen}:H^{cen}\rightarrow[g^{max}]\cup\\{0\\}$, and the number of residents
according to the PES is given by
$g^{PES}:\tilde{H}^{PES}\rightarrow[g^{max}]\cup\\{0\\}$. Throughout the next
sections, we sometimes abuse notation by applying $g^{cen}$ on households that
are not from $H^{cen}$, or applying $g^{PES}$ on households that were not
surveyed during the PES. In any such case, we assume that these functions
return 0. Finally, for a state $s\in\mathcal{S}$ and a household $h\in H$, we
denote the number of residents from state $s$ at household $h$ by
$g^{cen}_{s}(h)$ (according to the census) and $g^{PES}_{s}(h)$ (according to
the PES). If $h$ is not in state $s$, we simply have
$g^{PES}_{s}(h)=g^{cen}_{s}(h)=0$.

####  4.2.2 Census Assorters

We begin by adapting the definition of assertions and assorters to the
language of census RLAs. When auditing elections, an assorter is defined as a
non-negative function over the set of possible ballots a voter may cast. When
auditing a census, we define an assorter as a non-negative function over the
set of all households, meaning $a\colon H\rightarrow[0,\infty)$. An assorter
$a$ satisfies the assertion $\frac{1}{|H|}\sum_{h\in H}{a(h)}>\frac{1}{2}$ if
and only if some condition regarding the allocation of representatives to the
federal states is true.

######  Definition 8.

A set of functions: $a_{1},...,a_{\ell}:H\rightarrow[0,\infty)$ are census
assorters if the allocation of representatives according to the census and the
PES match iff for all $k\in[\ell]$:

$\frac{1}{|H|}\sum_{h\in H}{a_{k}(h)}>\frac{1}{2}.$

These $\ell$ inequalities are referred to as the census assertions.

####  4.2.3 Designing Household-Level Assorters

In this section, we present assorters that can be used for a census RLA in our
described model. In Section 4.2.2, we use these assorters to develop new, more
efficient assorters which are used during the census RLA method described in
Section 4.2.5.

These assorters are developed by reducing the problem of confirming the
census’ allocation of representatives to the problem of verifying that a set
of linear inequalities are all true (Theorem 4). Once we have such
inequalities, we use the method described in Section 1.6.2 to convert them to
equivalent SHANGRLA assertions, giving us our census assorters.

######  Theorem 4.

Assume the PES surveyed all households. The allocation of representatives
according to the census and according to the PES match, if and only if for any
two states $s_{1},s_{2}\in\mathcal{S}$:

$\displaystyle\frac{\sum_{h\in
H}g_{s_{1}}^{PES}(h)+c_{s_{1}}}{d(r^{cen}(s_{1}))}>\frac{\sum_{h\in
H}g_{s_{2}}^{PES}(h)+c_{s_{2}}}{d(r^{cen}(s_{2})+1)}.$ (13)

Where $r^{cen}(s)$ is the number of representatives that state $s$ is
allocated according to the census. The rest of the notation is defined in
Section 4.1.2.

###### Proof.

First, assume that the two allocations of representatives match. Examine the
imaginary table with which representatives are allocated to states according
to the PES, as described in Section 4.1.2. Recall that each state has exactly
its first $r^{PES}(s)$ cells colored. Since we assume that for any
$s\in\mathcal{S}$, $r^{PES}(s)=r^{cen}(s)$, we have it that for any
$s_{1},s_{2}\in\mathcal{S}$, the cell at index $[s_{1},r^{cen}(s_{1})]$ is
colored, while the cell at $[s_{2},r^{cen}(s_{2})+1]$ is not. Since the
colored cells are the ones which hold the largest values in the table, the
cell at $[s_{1},r^{cen}(s_{1})]$ has a larger value than the cell at
$[s_{2},r^{cen}(s_{2})+1]$. Writing these values out results exactly in (13)-
the larger term is the value at $[s_{2},r^{cen}(s_{2})+1]$, and the smaller is
the value at $[s_{1},r^{cen}(s_{1})]$.

Towards proving the other direction of the equivalence, we show that if (13)
is true for any $s_{1},s_{2}\in\mathcal{S}$, then a certain condition (14)
holds for any $s_{1},s_{2}$. We then show that if this condition is true, then
the allocation of representatives according to the census and according to the
PES match.

######  Claim 4.1.

Let $r^{PES}(s)$ be the number of representatives a state $s$ is allocated
according to the full PES results. For any $s_{1},s_{2}\in\mathcal{S}$, if
(13) is true then:

$\displaystyle\left(r^{PES}(s_{1})\geq
r^{cen}(s_{1})\right)\vee\left(r^{PES}(s_{2})\leq r^{cen}(s_{2})\right)$ (14)

###### Proof.

Assume towards contradiction that for some $s_{1},s_{2}\in\mathcal{S}$, the
condition (14) is false, meaning that its negation,
$\left(r^{PES}(s_{1})<r^{cen}(s_{1})\right)\wedge\left(r^{PES}(s_{2})>r^{cen}(s_{2})\right)$,
is true.

Examine the table used to allocate representatives to states according to the
PES results. According to this table, $s_{2}$ is awarded $r^{PES}(s_{2})$
representatives. Since $r^{PES}(s_{2})>r^{cen}(s_{2})$, and since the row
$s_{2}$ has exactly its first $r^{PES}(s_{2})$ cells colored, the cell at
$[s_{2},r^{cen}(s_{2})+1]$ is colored. Additionally, since $s_{1}$ was awarded
exactly $r^{PES}(s_{1})$ representatives and since
$r^{PES}(s_{1})<r^{cen}(s_{1})$, the cell at $[s_{1},r^{cen}(s_{1})]$ is not
colored.

By the paragraph above, if $\left(r^{PES}(s_{1})\geq
r^{cen}(s_{1})\right)\vee\left(r^{PES}(s_{2})\leq r^{cen}(s_{2})\right)$ is
false, then the cell at $[s_{2},r^{cen}(s_{2})+1]$ is colored while the cell
at $[s_{1},r^{cen}(s_{1})]$ is not. Since the colored cells are the ones which
hold the largest values, it follows that the cell at
$[s_{2},r^{cen}(s_{2})+1]$ has a larger value than the cell at
$[s_{1},r^{cen}(s_{1})]$, meaning that:

$\frac{\sum_{h\in
H}g_{s_{1}}^{PES}(h)+c_{s_{1}}}{d(r^{cen}(s_{1}))}\leq\frac{\sum_{h\in
H}g_{s_{2}}^{PES}(h)+c_{s_{2}}}{d(r^{cen}(s_{2})+1)}.$

The larger term in this inequality is the value at index
$[s_{2},r^{cen}(s_{2})+1]$ and the smaller one is the value at index
$[s_{1},r^{cen}(s_{1})]$. This contradicts (13), and thereby proves this
claim. ∎

######  Claim 4.2.

If (14) is true for any $s_{1},s_{2}\in\mathcal{S}$, then the allocation of
representatives according to the census and according to the full PES are
identical.

###### Proof.

Assume towards contradiction that the two allocations are not identical.
Therefore, there must be at least one state $s$ with $r^{PES}(s)\neq
r^{cen}(s)$. If $r^{PES}(s)>r^{cen}(s)$, since the number of total
representatives is constant, there must be another state $s^{\prime}$ with
$r^{PES}(s^{\prime})<r^{cen}(s^{\prime})$. Similarly, if
$r^{PES}(s)<r^{cen}(s)$, there must be another state $s^{\prime}$ with
$r^{PES}(s^{\prime})>r^{cen}(s^{\prime})$. Either way, either

$\left(r^{PES}(s)\geq r^{cen}(s)\right)\vee\left(r^{PES}(s^{\prime})\leq
r^{cen}(s^{\prime})\right)$

or

$\left(r^{PES}(s^{\prime})\geq
r^{cen}(s^{\prime})\right)\vee\left(r^{PES}(s)\leq r^{cen}(s)\right)$

are false, meaning that (14) is not true regarding all pairs of states. Thus,
if (14) is true for every pair of states, then the two allocations must be
identical, completing the proof. ∎

Using these two claims, we can now complete the proof of this theorem. Assume
(13) is true for any pair of states. By 4.1, (14) is also true for any pair of
states, and by 4.2, this makes the allocation of representatives according to
the census and according to the PES identical. This proves the other direction
of the equivalence and concludes the proof of this theorem. ∎

##### Finding the Assorters - Goal

By Theorem 4, to prove that the census and PES lead to the same allocation of
representatives, it suffices to verify that (13) is true for any pair of
states. Next, for every pair of states $s_{1},s_{2}\in\mathcal{S}$, we develop
a SHANGRLA assertion which is equivalent to (13), giving us our census RLA
assorters. Towards this goal, we slightly re-arrange (13) into an equivalent
form that is simpler to work with:

$\displaystyle\frac{\sum_{h\in
H}g_{s_{1}}^{PES}(h)}{d(r^{cen}(s_{1}))}-\frac{\sum_{h\in
H}g_{s_{2}}^{PES}(h)}{d(r^{cen}(s_{2})+1)}>\frac{c_{s_{2}}}{d(r^{cen}(s_{2})+1)}-\frac{c_{s_{1}}}{d(r^{cen}(s_{1}))}.$
(15)

For every $s_{1},s_{2}\in\mathcal{S}$, we wish to find a non-negative function
$a^{PES}_{s_{1},s_{2}}$ such that (15) is equivalent to:

$\frac{1}{|H|}\sum_{h\in H}{a^{PES}_{s_{1},s_{2}}(h)}>\frac{1}{2}.$

This is done using the method described in Section 1.6.2, which converts
linear inequalities regarding ballot tallies to SHANGRLA assertions. This
method originally applies on elections, and not on censuses. To use it here,
we need to view the census as a an election.

##### From Census to Elections

To view the census as an election, we define an election system where each
ballot corresponds to a household in the census, and the elections result in
an allocation of representatives to states, just as is done in the census. In
this election system, each ballot holds the state and number of residents of
its corresponding household according to the PES.

More formally, the set possible ballots a voter may cast in these elections is
$\mathcal{C}:=\mathcal{S}\times\\{[g^{max}|\cup\\{0\\}\\}$, and the ballots
that were truly cast are $B=\\{(s_{h},g^{PES}(h))\\}_{h\in H}$, where $s_{h}$
denotes the state of household $h$. Additionally, we use $v(s,k)$ to denote
the number of ballots cast for $(s,k)$. Using this notation, we can rewrite
(15) as:

$\displaystyle\sum^{g^{max}}_{k=0}{\left(\frac{1}{d(r^{cen}(s_{1}))}kv(s_{1},k)-\frac{1}{d(r^{cen}(s_{2})+1)}kv(s_{2},k)\right)}>\frac{c_{s_{2}}}{d(r^{cen}(s_{2})+1)}-\frac{c_{s_{1}}}{d(r^{cen}(s_{1}))}.$
(16)

This is equivalent to (15) since both $\sum^{g^{max}}_{k=0}{kv(s,k)}$ and
$\sum_{h\in H}{g^{PES}_{s}(h)}$ count the number of residents at state $s$.

(16) is a linear inequality regarding the vote tallies in some elections,
which allows us to apply the method from Section 1.6.2 to convert it to an
equivalent SHANGRLA assertion. The resulting assertions are
$\frac{1}{|B|}\sum_{b\in B}{a_{s_{1},s_{2}}(b)}>\frac{1}{2}$ for each
$s_{1},s_{2}\in\mathcal{S}$, with:

$\displaystyle
a_{s_{1},s_{2}}(s,k)=\frac{k{\mathbbm{1}}_{s=s_{1}}}{cd(r^{cen}(s_{1}))}+\frac{g^{max}-k{\mathbbm{1}}_{s=s_{2}}}{cd(r^{cen}(s_{2})+1)},$
(17)

where we denote:

$\displaystyle
c:=2\left(\frac{g^{max}}{d(r^{cen}(s_{2})+1)}+\frac{c_{s_{2}}}{|H|d(r^{cen}(s_{2})+1)}-\frac{c_{s_{1}}}{|H|d(r^{cen}(s_{1}))}\right)$
(18)

##### Back From Elections to the Census

The assorter above is intended for our imagined elections. We now wish to
convert it to an assorter which operates on households instead of ballots.
Towards this purpose, observe that for a household $h$ and its conversion to a
ballot $(s_{h},k)$, we have for any $s\in\mathcal{S}$:
$k{\mathbbm{1}}_{s_{h}=s}=g^{PES}_{s}(h)$. Meaning that defining
$a^{pes}_{s_{1},s_{2}}$ to operate directly on the households results in the
following:

######  Definition 9.

The census assorter $a^{PES}_{s_{1},s_{2}}$ is defined as:

$a^{PES}_{s_{1},s_{2}}(h):=\frac{g^{PES}_{s_{1}}(h)}{cd(r^{cen}(s_{1}))}+\frac{g^{max}-g^{PES}_{s_{2}}(h)}{cd(r^{cen}(s_{2})+1)},$

where $r^{cen}(s)$ is the number of representatives state $s$ is awarded
according to the census, $c$ is defined as in (18).

Since we used the method from Section 1.6.2, we have, for any two states
$s_{1},s_{2}$:

$\displaystyle\left(\frac{1}{|H|}\sum_{h\in
H}{a^{PES}_{s_{1},s_{2}}(h)}>\frac{1}{2}\right)\Longleftrightarrow\left(\frac{\sum_{h\in
H}g_{s_{1}}^{PES}(h)+c_{s_{1}}}{d(r^{cen}(s_{1}))}>\frac{\sum_{h\in
H}g_{s_{2}}^{PES}(h)+c_{s_{2}}}{d(r^{cen}(s_{2})+1)}\right).$

And by Theorem 4, the allocation of representatives according to the census
and PES match iff for all $s_{1},s_{2}\in\mathcal{S}$:

$\displaystyle\frac{1}{|H|}\sum_{h\in H}{a_{s_{1},s_{2}}(h)}>\frac{1}{2}.$
(19)

####  4.2.4 Designing Household-Comparison Assorters

For each assorter $a^{PES}_{s_{1},s_{2}}$ from Definition 9, we now define a
new assorter $A_{s_{1},s_{2}}$ which can also be used to audit the same
census. $A_{s_{1},s_{2}}$ has a significant advantage over
$a^{PES}_{s_{1},s_{2}}$, which motivates us to use it instead. Each assorter
$a^{PES}_{s_{1},s_{2}}$ essentially audits the number of residents per
household according to the PES, without using the per-household census data.
Meanwhile, $A_{s_{1},s_{2}}$ audits the discrepancy in the number of household
members between the census and the PES. Since we typically expect this
discrepancy to be small, this yields a more stable and efficient audit.

##### Some Intuition

This next part is only meant to explain how these final assorters are deduced,
and not to prove that auditing them results in a valid census-RLA. A formal
proof that these assorters satisfy the condition described above is shown in
Theorem 5.

First, note that each assorter $a_{s_{1},s_{2}}^{PES}$ can also be defined
over the census population counts instead of the PES counts. We denote this as
$a_{s_{1},s_{2}}^{cen}$:

######  Definition 10.

$\displaystyle a_{s_{1},s_{2}}^{cen}(h)$
$\displaystyle:=\frac{g^{cen}_{s_{1}}(h)}{cd(r^{cen}(s_{1}))}+\frac{g^{max}-g^{cen}_{s_{2}}(h)}{cd(r^{cen}(s_{2})+1)}.$

As mentioned previously, we would like $A_{s_{1},s_{2}}$ to operate over the
per-household discrepancy between the census and the PES as it relates to
$a^{PES}_{s_{1},s_{2}}$. Meaning, it should operate over:

$a_{s_{1},s_{2}}^{PES}(h)-a_{s_{1},s_{2}}^{cen}(h),$

A simple way of doing so is to define our new assorter $A_{s_{1},s_{2}}$ to
have a similar form to the Batchcomp assorter from Definition 3:

$\displaystyle
A_{s_{1},s_{2}}(h)=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{\cdots},$
(20)

with some choice of denominator in place of $(\cdots)$. $m_{s_{1},s_{2}}$ here
is the margin of $a^{cen}_{s_{1},s_{2}}$:

$\displaystyle m_{s_{1},s_{2}}:=\frac{1}{|H|}\sum_{h^{\prime}\in
H}{a^{cen}_{s_{1},s_{2}}(h^{\prime})}-\frac{1}{2}.$ (21)

Observe that for any $s_{1},s_{2}\in\mathcal{S}$, $m_{s_{1},s_{2}}>0$. This is
true since otherwise, $\frac{1}{|H|}\sum_{h^{\prime}\in
H}{a^{cen}_{s_{1},s_{2}}(h^{\prime})}\leq\frac{1}{2}$, meaning that if the PES
and census results completely match on all households, we have
$\frac{1}{|H|}\sum_{h^{\prime}\in
H}{a^{PES}_{s_{1},s_{2}}(h^{\prime})}\leq\frac{1}{2}$, contradicting (19).

With this definition of $A_{s_{1},s_{2}}$, for any positive denominator we use
in place of the dots ($\cdots$), we would have:

$\left(\frac{1}{|H|}\sum_{h\in
H}{a_{s_{1},s_{2}}(h)}>\frac{1}{2}\right)\Longleftrightarrow\left(\frac{1}{|H|}\sum_{h\in
H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}\right),$

as we show while proving 4.4. What remains is to choose the denominator.

##### Choosing the Denominator

Ideally, we would like $A_{s_{1},s_{2}}$ to return large values when the
census and the PES agree on the number of residents of a certain household,
since this would cause the audit to approve a correct census (one that matches
the PES) sooner. When the census and the PES agree on some household $h$, we
have:

$A_{s_{1},s_{2}}(h)=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+\overbrace{a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}^{=0}}{\cdots}=\frac{1}{2}+\frac{m_{s_{1},s_{2}}}{\cdots}.$

And since, as explained right after after (21), $m_{s_{1},s_{2}}>0$, this
value will be larger the smaller our chosen denominator is. However, if we
choose a denominator which is too small, $A_{s_{1},s_{2}}$ could potentially
return negative values. By these two observations, we should choose the
denominator to be the smallest positive such that $A_{s_{1},s_{2}}$ is non-
negative. To find which value satisfies this, we find the minimal value that
the nominator may have. By the definition of $a^{PES}_{s_{1},s_{2}}$ and
$a^{cen}_{s_{1},s_{2}}$, the value of the nominator is:

$m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)\\\
=m_{s_{1},s_{2}}+\frac{g^{PES}_{s_{1}}(h)-g^{cen}_{s_{1}}(h)}{cd(r^{cen}(s_{1}))}+\frac{g^{cen}_{s_{2}}(h)-g^{PES}_{s_{2}}(h)}{cd(r^{cen}(s_{2})+1)}.$

$h$ is either from $s_{1}$, from $s_{2}$ or from neither of them. If it’s from
neither, than this expression is equal $m_{s_{1},s_{2}}$. If it’s from
$s_{1}$, then:

$\displaystyle m_{s_{1},s_{2}}+\frac{\overbrace{g^{PES}_{s_{1}}(h)}^{\geq
0}-\overbrace{g^{cen}_{s_{1}}(h)}^{\leq
g^{max}}}{cd(r^{cen}(s_{1}))}+\frac{\overbrace{g^{cen}_{s_{2}}(h)-g^{PES}_{s_{2}}(h)}^{=0}}{cd(r^{cen}(s_{2})+1)}$
$\displaystyle\geq m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{1}))},$ where
$g^{max}$ is the maximal number of residents a single household may have. If
$h$ is from $s_{2}$, then: $\displaystyle
m_{s_{1},s_{2}}+\frac{\overbrace{g^{PES}_{s_{1}}(h)-{g^{cen}_{s_{1}}(h)}}^{=0}}{cd(r^{cen}(s_{1}))}+\frac{\overbrace{g^{cen}_{s_{2}}(h)}^{\geq
0}-\overbrace{g^{PES}_{s_{2}}(h)}^{\leq g^{max}}}{cd(r^{cen}(s_{2})+1)}$
$\displaystyle\geq m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{2})+1)}.$

So for any $h\in H$:

$\displaystyle
m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)$
$\displaystyle\geq$
$\displaystyle\min\left\\{m_{s_{1},s_{2}},m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{2})+1)},m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{1}))}\right\\}$
(22)

We can now set the denominator to be the smallest value for which
$A_{s_{1},s_{2}}$ is non-negative:

$A_{s_{1},s_{2}}(h):=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{-2\min\left\\{m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{2})+1)},m_{s_{1},s_{2}}-\frac{g^{max}}{cd(r^{cen}(s_{1}))},m_{s_{1},s_{2}}\right\\}}.$

For brevity, we denote:

$\displaystyle
z_{s_{1},s_{2}}:=\max\left\\{\frac{g^{max}}{cd(r^{cen}(s_{2})+1)},\frac{g^{max}}{cd(r^{cen}(s_{1}))},0\right\\}.$
(23)

And write $A_{s_{1},s_{2}}$ as follows:

######  Definition 11.

The census comparison assorter for states $s_{1},s_{2}\in\mathcal{S}$ is
defined as:

$A_{s_{1},s_{2}}(h):=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}.$

We now prove that the assorters
$\\{A_{s_{1},s_{2}}\,|\,s_{1},s_{2}\in\mathcal{S}\times\mathcal{S},s_{1}\neq
s_{2}\\}$ are valid for auditing the census’ allocation of representatives to
the federal states.

######  Theorem 5.

Assume that the PES surveyed all households. The assorters
$\\{A_{s_{1},s_{2}}\,|\,s_{1},s_{2}\in\mathcal{S}\\}$, as defined above, are
all non-negative and satisfy the following condition: The allocation of
representatives according to the census and the PES match iff for all
$s_{1},s_{2}\in\mathcal{S}$:

$\frac{1}{|H|}\sum_{h\in H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}.$

###### Proof.

We first prove that $A_{s_{1},s_{2}}$ is non-negative for any
$s_{1},s_{2}\in\mathcal{S}$, and then show that the equivalence above holds.

######  Claim 4.3.

For any $s_{1},s_{2}\in\mathcal{S}$, $A_{s_{1},s_{2}}$ is non-negative.

###### Proof.

Fix two states $s_{1},s_{2}\in\mathcal{S}$. By (4.2.4) and by the definition
of $z_{s_{1},s_{2}}$:

$\displaystyle
m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)\geq
m_{s_{1},s_{2}}-z_{s_{1},s_{2}}.$ (24)

Meaning that for any $h\in H$:

$\displaystyle A_{s_{1},s_{2}}$
$\displaystyle=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}$
$\displaystyle\geq\frac{1}{2}+\frac{m_{s_{1},s_{2}}-z_{s_{1},s_{2}}}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}$
$\displaystyle=0,$

proving the claim. ∎

######  Claim 4.4.

The allocation of representatives according to the census and the PES match
iff for all $s_{1},s_{2}\in\mathcal{S}$:

$\frac{1}{|H|}\sum_{h\in H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}.$

###### Proof.

In Section 4.2.3, we developed assorters $a^{PES}_{s_{1},s_{2}}$ such that the
allocation of representatives according to the census and the PES match iff
for all $s_{1},s_{2}\in\mathcal{S}$:

$\frac{1}{|H|}\sum_{h\in H}{a^{PES}_{s_{1},s_{2}}(h)}>\frac{1}{2}$

Therefore, to prove this claim, it suffices to prove that for every
$s_{1},s_{2}\in\mathcal{S}$:

$\left(\frac{1}{|H|}\sum_{h\in
H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}\right)\Longleftrightarrow\left(\frac{1}{|H|}\sum_{h\in
H}{a_{s_{1},s_{2}}(h)}>\frac{1}{2}\right).$

Fix any two federal-states $s_{1},s_{2}\in\mathcal{S}$. We show that the two
inequalities above are equivalent:

$\displaystyle\frac{1}{|H|}\sum_{h\in H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}$
$\displaystyle\Longleftrightarrow$ $\displaystyle\frac{1}{|H|}\sum_{h\in
H}{\left(\frac{1}{2}+\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}\right)}>\frac{1}{2}$
$\displaystyle\Longleftrightarrow$ $\displaystyle\frac{1}{|H|}\sum_{h\in
H}{\frac{m_{s_{1},s_{2}}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}}>0.$
Now, using the definition of $m_{s_{1},s_{2}}$ and re-arranging the summation
yields the desired equivalence: $\displaystyle\Longleftrightarrow$
$\displaystyle\frac{1}{|H|}\sum_{h\in
H}{\frac{\frac{1}{|H|}\sum_{h^{\prime}\in
H}{a^{cen}_{s_{1},s_{2}}(h^{\prime})}-\frac{1}{2}+a^{PES}_{s_{1},s_{2}}(h)-a^{cen}_{s_{1},s_{2}}(h)}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}}>0$
$\displaystyle\Longleftrightarrow$
$\displaystyle\frac{\frac{1}{|H|}\sum_{h^{\prime}\in
H}{a^{cen}_{s_{1},s_{2}}(h^{\prime})}+\frac{1}{|H|}\sum_{h\in
H}{a^{PES}_{s_{1},s_{2}}(h)}-\frac{1}{|H|}\sum_{h\in
H}{a^{cen}_{s_{1},s_{2}}(h)}-\frac{1}{2}}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}>0$
$\displaystyle\Longleftrightarrow$ $\displaystyle\frac{\frac{1}{|H|}\sum_{h\in
H}{a^{PES}_{s_{1},s_{2}}(h)}-\frac{1}{2}}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}>0$
$\displaystyle\Longleftrightarrow$ $\displaystyle\frac{1}{|H|}\sum_{h\in
H}{a^{PES}_{s_{1},s_{2}}(h)}>\frac{1}{2},$

The last transition relies on the fact that $z_{s_{1},s_{2}}>m_{s_{1},s_{2}}$,
which is true since:

$\displaystyle z_{s_{1},s_{2}}\geq\max_{h\in H}{a^{cen}(h)}\geq
m_{s_{1},s_{2}}.$

This concludes the proof of this claim. ∎

The combination of these two claims completes this theorem’s proof. ∎

####  4.2.5 Census RLA Description

The algorithm presented next is a slightly altered version of the ALPHA
martingale test from Section 1.6.3, when thinking of each household as a
ballot whose content is the household’s state and its number of residents.

##### Adapting the ALPHA Martingale Test to Censuses

Unlike an election RLA, where the paper-backup ballots are read as the audit
is ran, a census RLA is performed after the PES, meaning that the households
were re-surveyed before the audit begins. We handle this by sampling
households such that from the auditor’s perspective, if it doesn’t know which
households were surveyed by the PES, it receives a previously unsampled
household uniformly at random. This is performed according to a subroutine
that takes as its input 4 arguments:

  * •

$H^{1}$: the set of households that have yet to be audited.

  * •

$H^{cen}$: the list of households according to the census.

  * •

$H^{PES}$: the list from which the PES randomly chose the households it
surveyed ($\tilde{H}^{PES}$).

  * •

$\tilde{H}^{PES}$: a list of households that were surveyed during the PES.

Sample_Household($H^{1},H^{cen},H^{PES},\tilde{H}^{PES}$): With probability
$\frac{|H^{PES}\cap H^{1}|}{|H^{1}|}$, sample a household uniformly at random
from $\tilde{H}^{PES}\cap H^{1}$. Otherwise, sample a household uniformly at
random from $\left(H\setminus H^{PES}\right)\cap H^{1}$.

Additionally, recall that instead of pre-setting the risk-limit $\alpha$, the
algorithm outputs the smallest value $\alpha$ with which it can approve the
representative allocation of the census, as described in the Census RLA
guarantee. This is done by keeping, at all times, the risk-limit of each
assertion, $\frac{1}{T^{max}}$. When the audit runs out of households to
sample, the procedure outputs the maximal risk-limit across all the assertions
(step 3).

Before presenting the algorithm, recall that the variables $\mu,\eta$ and $U$
represent guesses regarding the value that their corresponding assorter will
return in the next iteration. $\mu$ is that guess given that the assorter has
a mean of exactly $\frac{1}{2}$, $\eta$ is the guess assuming that the census
and PES agree on all households, and $U$ is a parameter which controls how
significantly $T$ changes per iteration. $T$ is the inverse of the risk-limit
with which we can approve that its corresponding assertion is true, and
$T^{max}$ holds the maximal value of $T$ throughout the audit.

##### The Census RLA Algorithm

  1. 1.

Initialization

    1. 1.1.

Initialize $H^{1}=H$ and $H^{0}=\emptyset$. $H^{1}$ holds the households that
have yet to be audited, and $H^{0}$ holds the households which were already
audited.

    2. 1.2.

For each $(s_{1},s_{2})\in\mathcal{S}\times\mathcal{S}$ s.t. $s_{1}\neq s_{2}$
initialize:

       * •

$T_{s_{1},s_{2}}:=1$.

       * •

$T^{max}_{s_{1},s_{2}}:=1$.

       * •

$\mu_{s_{1},s_{2}}:=\frac{1}{2}$.

       * •

$\eta_{s_{1},s_{2}}:=\frac{1}{2}+\frac{m_{s_{1},s_{2}}}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}$.

       * •

$U_{s_{1},s_{2}}:=\frac{1}{2}+\frac{m_{s_{1},s_{2}}+\delta}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})}$,
where $\delta>0$.

For definitions of $m_{s_{1},s_{2}}$ and $z_{s_{1},s_{2}}$ see (21) and (23).

  2. 2.

Auditing Stage: While $H^{1}\cap\tilde{H}^{PES}\neq\emptyset$, perform:

    1. 2.1.

Sample a household $h$ using the subroutine
$\text{Sample\\_Household}(H^{1},H^{cen},H^{PES},\tilde{H}^{PES})$.

    2. 2.2.

Remove $h$ from $H^{1}$ and add it to $H^{0}$.

    3. 2.3.

For each $s_{1},s_{2}$, update $T_{s_{1},s_{2}}$ and $T^{max}_{s_{1},s_{2}}$:

       * •

$T_{s_{1},s_{2}}\leftarrow
T_{s_{1},s_{2}}\frac{1}{U_{s_{1},s_{2}}}\left(A_{s_{1},s_{2}}(h)\frac{\eta_{s_{1},s_{2}}}{\mu_{s_{1},s_{2}}}+(U_{s_{1},s_{2}}-A_{s_{1},s_{2}}(h))\frac{U_{s_{1},s_{2}}-\eta_{s_{1},s_{2}}}{U_{s_{1},s_{2}}-\mu_{s_{1},s_{2}}}\right)$.

       * •

$T^{max}_{s_{1},s_{2}}\leftarrow\max\left\\{T^{max}_{s_{1},s_{2}},T_{s_{1},s_{2}}\right\\}$.

    4. 2.4.

For each $s_{1},s_{2}$ update $\mu_{s_{1},s_{2}},\eta_{s_{1},s_{2}}$ and
$U_{s_{1},s_{2}}$ to be:

       * •

$\mu_{s_{1},s_{2}}\leftarrow\frac{\frac{1}{2}|H|-\sum_{h^{\prime}\in
H^{0}}{A_{s_{1},s_{2}}(h^{\prime})}}{|H_{1}|}$.

       * •

$\eta_{s_{1},s_{2}}\leftarrow
max\left\\{\frac{1}{2}+\frac{m_{s_{1},s_{2}}}{2(z_{s_{1},s_{2}}-m_{s_{1},s_{2}})},\mu_{s_{1},s_{2}}+\epsilon\right\\}$.

       * •

$U_{s_{1},s_{2}}\leftarrow
max\\{U_{s_{1},s_{2}},\eta_{s_{1},s_{2}}+\epsilon\\}$.

Where $\epsilon$ is some very small positive meant to ensure that
$\mu_{s_{1},s_{2}}<\eta_{s_{1},s_{2}}<U_{s_{1},s_{2}}$. We assume these
variables are updated according to the order of their listing above.

    5. 2.5.

For any $s_{1},s_{2}$, if $\mu_{s_{1},s_{2}}<0$, we must have
$\frac{1}{|H|}\sum_{h\in H}{A_{s_{1},s_{2}}(h)}>\frac{1}{2}$, so set
$T_{s_{1},s_{2}}^{max}=\infty$. This means that we can approve this assertion
with risk-limit 0 - this assertion is necessarily true.

  3. 3.

Output: The result of the audit is the maximal risk-limit across all
assertions:

$\max_{s_{1},s_{2}\in\mathcal{S}}\left\\{\frac{1}{T^{max}_{s_{1},s_{2}}}\right\\}.$

Before proving that this algorithm satisfies the census RLA guarantee, we make
one preliminary claim.

######  Claim 4.5.

If the PES is conducted over a random subset of households from $H^{PES}$, the
sample_household subroutine returns a household which is selected uniformly at
random from $H^{1}$.

###### Proof.

Fix any call to sample_household during the audit. During this proof, we
denote $H^{1}$ as the set $H^{1}$ is while executing this call. Denote by $j$
the number of households from $H^{1}$ that were surveyed during the PES.

Examine any unsampled household from the PES household list $h\in H^{PES}\cap
H^{1}$. $h$ will be returned by sample_household if and only if these 3 events
all occur:

  * •

$h$ was surveyed during the PES\- there are $j$ households in $H^{1}$ that
were surveyed in the PES, and $|H^{1}\cap H^{PES}|$ households in $H^{1}$ that
were considered for surveying by the PES. This puts the probability of $h$
being surveyed during the PES at $\frac{j}{|H^{1}\cap H^{PES}|}$.

  * •

sample_household sampled a household that was surveyed during the PES \- this
happens w.p. $\frac{|H^{1}\cap H^{PES}|}{|H^{1}|}$.

  * •

sample_household chose $h$, given that the two previous events happened \-
there are $j$ households in $H^{1}$ that were surveyed during the PES, so the
probability of this occurring is $\frac{1}{j}$.

The probability of $h$ getting sampled by sample_household is therefore:

$\displaystyle\frac{j}{|H^{1}\cap H^{PES}|}\frac{|H^{1}\cap
H^{PES}|}{|H^{1}|}\frac{1}{j}=\frac{1}{|H^{1}|}.$

This establishes that the probability of any single household from $H^{1}\cap
H^{PES}$ being returned is $\frac{1}{|H_{1}|}$. Now, since sample_household
may only return households from $H^{1}$, and since any household from
$H^{1}\setminus H^{PES}$ is returned with equal probability, the probability
of any household from $H^{1}$ getting returned must be $\frac{1}{|H^{1}|}$.
This shows that sample_household returns a household uniformly at random from
$H^{1}$, proving the claim. ∎

We can now prove that this audit is a census RLA.

######  Theorem 6.

For any nation with federal-states $\mathcal{S}$, that allocates
representatives to its federal-states in proportion to their population using
a highest averages method, this suggested census RLA satisfies the census RLA
guarantee: For any $0<\alpha\leq 1$, if running the PES over all households
would lead to a different allocation of representatives than the census, then
the probability that a census RLA returns a value $\alpha^{\prime}$ such that
$\alpha^{\prime}\leq\alpha$ is at most $\alpha$.

###### Proof.

This proof is similar to the proof of correctness for the ALPHA martingale
test in Theorem 1. The key point here is that from the perspective of the
auditor, the households it receives are sampled uniformly at random and
without replacement from the set of all households. Given this observation,
the census RLA algorithm can be viewed as a regular election RLA, where each
ballot corresponds to a household and contains the household’s state and
number of residents.

Fix a highest-averages allocation method (meaning a monotonically increasing
function $d:{\mathbb{N}}\rightarrow{\mathbb{N}}$ and $c_{s}\in{\mathbb{R}}$
for each $s\in\mathcal{S}$), lists of households $H^{cen},H^{PES}$ and census
results $g^{cen}$ as specified in Section 4.1.2. Assume that extending the PES
such that it surveys all households leads to a different allocation of
representatives than the census, and denote the function which returns these
full PES results as $g^{PES}:H^{PES}\rightarrow[g^{max}]\cup\\{0\\}$. Let
$\tilde{H}^{PES}$ be a set of randomly selected households of a pre-determined
size from $H^{PES}$ which were actually surveyed during the PES, and fix
$\alpha\in[0,1]$. We wish to show that when running the census RLA over these
inputs, the probability of the census RLA outputting a value $\alpha^{\prime}$
s.t. $\alpha^{\prime}<\alpha$ is at most $\alpha$.

By 4.4, since the representative allocations according to the census and
according to the PES are different, there must be some census-assorter whose
mean is at most $\frac{1}{2}$. Denote this assorter as
$A_{s^{\prime}_{1},s^{\prime}_{2}}$:

######  Assumption.

$\frac{1}{|H|}\sum_{h\in
H}{A_{s^{\prime}_{1},s^{\prime}_{2}}(h)}\leq\frac{1}{2}.$

$T^{max}_{s^{\prime}_{1},s^{\prime}_{2}}$ cannot become $\infty$ in step
22.5., since that would mean, for any $H^{0}\subseteq H$:

$\mu_{s_{1},s_{2}}<0\Longrightarrow\frac{1}{2}|H|-\sum_{h^{\prime}\in
H^{0}}{A_{s_{1},s_{2}}(h^{\prime})}<0\Longrightarrow\frac{1}{2}<\frac{1}{|H|}\sum_{h^{\prime}\in
H^{0}}{A_{s_{1},s_{2}}(h^{\prime})}\leq\frac{1}{|H|}\sum_{h^{\prime}\in
H}{A_{s_{1},s_{2}}(h^{\prime})}$

contradicting our assumption. Therefore,
$T^{max}_{s^{\prime}_{1},s^{\prime}_{2}}$ receives its final update in step
22.3..

Denote the values $T_{s^{\prime}_{1},s^{\prime}_{2}}$ has after every sampled
household during the audit as
$T^{0}_{s^{\prime}_{1},s^{\prime}_{2}},T^{1}_{s^{\prime}_{1},s^{\prime}_{2}},...,T^{q}_{s^{\prime}_{1},s^{\prime}_{2}}$,
where $T^{0}_{s^{\prime}_{1},s^{\prime}_{2}}$ is its initial value and $q$ is
any natural number. Since the algorithm outputs:

$\max_{s_{1},s_{2}\in\mathcal{S}}\left\\{\frac{1}{T^{max}_{s_{1},s_{2}}}\right\\},$

it outputs a value that is smaller than $\alpha$ only if at the end of the
audit we have $T^{max}_{s^{\prime}_{1},s^{\prime}_{2}}<\frac{1}{\alpha}$. By
this and by the fact $T^{max}_{s^{\prime}_{1},s^{\prime}_{2}}$ receives its
final value at step 22.3., to prove this theorem, it suffices to prove that:

$\displaystyle\Pr\left[\max_{j}\\{T^{j}_{s^{\prime}_{1},s^{\prime}_{2}}\\}>\frac{1}{\alpha}\right]\leq\alpha.$
(25)

To achieve this, we show that
$T^{0}_{s^{\prime}_{1},s^{\prime}_{2}},...,T^{q}_{s^{\prime}_{1},s^{\prime}_{2}}$
is a non-negative supermartingale, and then use Ville’s inequality, similarly
to Theorem 1. Note that the update rules of $T_{s_{1},s_{2}}$ and of $T_{k}$
are identical in the census RLA and in the ALPHA martingale test respectively,
and that the update rules for
$U_{s_{1},s_{2}},\eta_{s_{1},s_{2}},\mu_{s_{1},s_{2}}$ always maintain
$U_{s_{1},s_{2}}>\eta_{s_{1},s_{2}}>\mu_{s_{1},s_{2}}$. Moreover, just like
the ALPHA martingale test samples ballots randomly and without replacement,
the census RLA samples households randomly and without replacement, by 4.5.
For these reasons, 1.1 applies here too - given a non-negative assorter, our
update rule for $T_{s_{1},s_{2}}$ makes it non-negative itself, meaning that
$T^{0}_{s^{\prime}_{1},s^{\prime}_{2}},...,T^{q}_{s^{\prime}_{1},s^{\prime}_{2}}$
are all non-negative.

Additionally, for the same arguments as in 1.2, we have it that for any
$i\in[q]$:

${\mathbb{E}}[T^{i}_{s^{\prime}_{1},s^{\prime}_{2}}\,|\,T_{s^{\prime}_{1},s^{\prime}_{2}}^{1},...,T_{s^{\prime}_{1},s^{\prime}_{2}}^{i-1}]\leq
T_{s^{\prime}_{1},s^{\prime}_{2}}^{i-1}.$

This is true because both $T_{s^{\prime}_{1},s^{\prime}_{2}}$ here and $T_{1}$
in 1.2 belong to assertions which are false (their assorters have a mean of
$\frac{1}{2}$ or less), and are updated in the exact same manner. This makes
$T^{0}_{s^{\prime}_{1},s^{\prime}_{2}},...,T^{q}_{s^{\prime}_{1},s^{\prime}_{2}}$
a non-negative supermartingale, meaning that by Ville’s inequality [12]:

$\displaystyle\Pr\left[\max_{j}\\{T^{j}_{s^{\prime}_{1},s^{\prime}_{2}}\\}>\frac{1}{\alpha}\right]\leq\alpha\cdot
T^{0}_{s^{\prime}_{1},s^{\prime}_{2}}=\alpha.$

Which proves (25) and thereby completes the proof of this theorem. ∎

### 4.3 Census RLA Simulations

This section simulates the suggested census RLA on the Cypriot census and its
resulting allocation of representatives to districts in the House of
Representatives of Cyprus. Our original intention was to simulate the
suggested census RLA method on the US census and its resulting allocation of
representatives in the US House of Representatives to the states. This turned
out to be infeasible, however, due to the relatively large number of states
(50) and representatives (435). Allocating many representatives to many states
increases the probability of there being a single representative whose
allocation is determined by a very small number of state residents. Therefore,
such systems require a very small enumeration error to change the census’
allocation, and are therefore more difficult to audit. Using our suggested
method on the American setting, a PES which surveys 10% of households results
in a risk-limit of only 0.75. In reality, the US PES surveys around 1% of
households [4].

To show that the census RLA is useful in other cases, we chose to simulate the
audit on the House of representatives of Cyprus, where 56 representatives are
allocated to 5 districts. Due to the somewhat limited available resources in
English regarding the Cypriot census, we view this as a pet-setting for
testing our census RLA method, and not as a ready-as-is implementation.

####  4.3.1 The House of Representatives of Cyprus

The House of representatives of Cyprus is its sole legislating body.
Officially, The house holds 80 seats, where 56 are to be elected by the Greek
Cypriot community and 24 by the Turkish Cypriot community. In 1964, the
Turkish-Cypriots withdrew from the political decision-making process, leaving
their house seats vacant [10].

Since then, the remaining 56 seats of the house are allocated to 5 districts.
Currently, the allocation of seats to the districts is amended by law when
found necessary, and does not change automatically following a census
according to a set method. Our census RLA could be useful when performing
these amendments, to ensure that the resulting allocation of seats to
districts is sufficiently reliable.

####  4.3.2 Data Generation and Technical Details

The data used to perform this simulation is based on the population census
conducted in 2021 [30]. The Statistical Service of Cyprus publicly reports the
total number of residents in every district, but not the individual household
data, which the census RLA requires. To generate this data, we assumed that
the number of residents per household distributes as it does in the United
States, as reported by its census [8]. We additionally assumed that 1% of
households do not respond to the census and are counted as if they have no
residents. The per-household data used in these simulations was generated as
follows:

##### Generating the Census Data

  1. 1.

The number of households per district was calculated by dividing the
district’s population by the expected number of residents per household.

  2. 2.

The number of residents in each household was drawn from the distribution
specified in the US census [8].

  3. 3.

Due to the randomness involved in the previous step, the real census and our
generated one might disagree on the population of the districts. To balance
this, the constant of each district ($c_{s}$ in (12) at Section 4.1.2) was set
as the difference between the population of the district according to the real
census and according to our generated one. With this definition, the
allocation of representatives to districts by the real census and by our
generated one is necessarily identical.

##### Audit Parameters and Other Details

We allocated representatives to districts using the D’Hondt method. D’Hondt
was chosen since it’s currently used in the Cypriot elections to allocate
seats to political parties. The audit was run assuming that each household
holds 15 residents at most, and with $\delta=10^{-10}$. We assumed that the
list of households according to the census and the PES match, meaning
$H^{PES}=H^{cen}$. The simulation’s code was written in Python and is
available in https://github.com/TGKar/Batch-and-Census-RLA.

####  4.3.3 Results

We present the outputted risk-limit of the census RLA as a factor of the size
of the PES. The x-axis shows the share of households that were surveyed of the
PES, and each point in the plot represents the audit’s outputted risk-limit
when using a PES of that specified size. The results are averaged across 10
simulations.

#### Results When Census and PES Completely Match

The audit’s output when the census and PES fully agree on the number of
residents in each household. Under these conditions, a PES which samples 0.66%
of households is sufficient for a risk limit of 0.1, and a sample of 0.87% is
sufficient for a risk-limit of 0.05. A PES often surveys around 1% of
households [18], meaning that our census RLA can confidently approve its
resulting allocation of representatives to districts under these specified
conditions.

##### Results with Small Enumeration Errors

The next plot shows the same results when the census and PES potentially
disagree on 5% of households. For these 5% of households, which are selected
uniformly at random, the number of residents according to the PES is re-drawn
from the distribution of residents per household described in Section 4.3.1.
The following simulations were run over census and full PES results that lead
to the same allocation of representatives to states. During the simulated
census RLA, the audit only receives the PES results over a subset of randomly
selected households.

These results appear very similar to the previous plot, where the census and
PES agreed on the number of residents at all households. With the described
rate of disagreement between the PES and the census, a PES which surveys 0.72%
of households is required for the audit to approve the allocation with a risk
limit of 0.1, compared to 0.66% if there were no enumeration disagreements. To
get a risk-limit of 0.05, the PES would need to survey 1% of households,
compared to 0.87% with no enumeration errors.

####  4.3.4 Simulation Conclusions

##### Settings Where Our Method is Applicable

As mentioned previously, our original goal was to run the census RLA over the
US census and House of Representatives, but our method could not confirm such
representative allocations with sufficient confidence unless the PES was very
large. In nations with less representatives and federal-states, such as
Cyprus, our method can approve the census with a relatively low risk-limit
with a PES which covers 1% of households. More generally, our method is
applicable when the minimal census enumeration error which leads to a change
in the resulting allocation of representatives is relatively large (0.25%
appears to be sufficient for Cyprus based on simulations). When there are many
representatives and federal-states, even a small mistake in the census can
lead to a wrongful allocation of representatives and auditing the census
results requires a larger PES sample.

##### Tolerance to Census and PES Disagreements

Our method appears to be tolerant to small disagreements between the census
and the PES results under these specified settings. A disagreement over 5% of
households leads to a small decrease in the audit’s resulting risk-limit for
any given PES sample size. A PES usually surveys around 1% of households,
which is sufficient for a risk-limit of 0.05 when the census and PES disagree
on 5% of households, compared to a risk-limit of 0.03 when there are no such
disagreements.

#### Recovering From Assertions with a High Risk-Limit

Even when there are relatively few representatives and states, it’s possible
that a small enumeration error could lead to a different allocation of
representatives. In such cases, a full census RLA would struggle to approve
the census results with a sufficiently low risk-limit. If this occurs, the
auditing body can examine the risk-limit of the individual assertions
($\frac{1}{T^{max}_{s_{1},s_{2}}}$ for each $s_{1},s_{2}\in\mathcal{S}$) to
see which assertions have a higher risk-limit. As seen while simulating an
election RLA in Section 3.3, in many cases, one specific assertion is
significantly more difficult to approve than others, meaning that its risk-
limit is significantly higher. If the risk-limit of all other assertions is
sufficiently low, we might still decide that the census’ allocation of
representatives is reliable, with the exception of a single representative
whose state-allocation could not be determined with confidence.

If the audit results in an insufficient risk-limit, we can also examine the
risk-limit of each state, i.e. the risk-limit that would be outputted if we
only wanted to approve that the number of representatives a specific state
receives according to the census and according to the PES match. For a state
$s$, this risk-limit is the maximal risk-limit of all assertions which involve
$s$, meaning:

$\max_{s^{\prime}\in\mathcal{S}\setminus\\{s\\}}\left\\{\frac{1}{T^{max}_{s,s^{\prime}}},\frac{1}{T^{max}_{s^{\prime},s}}\right\\}.$

## 5 Discussion and Further Research

Throughout this work, we can observe that an election’s social choice function
and setting can severely limit the efficiency of their RLAs. Systems like the
Israeli Knesset elections and the US House of Representatives’ allocation of
representatives to states are very sensitive to enumeration errors, making it
difficult to audit them efficiently.

When designing new election systems, the ability to audit their social choice
function in a risk-limiting manner should be examined in advance. If a system
has a sensitive social-choice function, it should be compensated by other
means. E.g., it can use a vote tabulation system which returns the specific
interpretation it gave each paper-backup ballots and ensure individual ballots
can be accessed efficiently, allowing for ballot-comparison audits. If a
system cannot be audited efficiently at all, implementing electronic vote
tabulations for it should be done with extra care or avoided altogether.

### The Batchcomp RLA

In current literature, different RLA methods are usually compared by showing
their simulated performance over some reported election results. Most RLA
methods, including the ones presented in this work, are not analyzed in terms
of query-complexity. This issue is especially prominent in the field of batch
RLAs, where the performance of methods which can audit social choice functions
beyond a simple plurality is often not analyzed at all, neither analytically
or by using simulations.

The simulations presented in this work (Section 3.3) indicate that Batchcomp
provides a noticeable improvement over ALPHA-batch in the limited settings
that were tested. Despite this relative success, we cannot definitively say it
outperforms existing methods without a clear, rigorous way of analyzing their
efficiency.

### Auditing the Knesset Elections

Section 3.3 shows the difficulties in auditing the Knesset election. Due to
the small margins these election results some times have, implementing RLAs
for them seems could be problematic, since they will require a full recount
when any constraint is close to be unsatisfied.

Currently, a more practical use for RLAs in Israel could be to approve
specific conditions regarding the election results. E.g., confirm that a
certain party is above or below the electoral threshold. In such cases, the
audit should be simulated in advance to ensure that the number of ballots it
would require to read is manageable.

### Census RLAs

The census RLA method appears to be useful in some limited settings, and can
be implemented using existing post-enumeration surveys. In systems where our
method is currently not sufficient, a census RLA could perhaps aim for a
weaker guarantee - that the number of representatives each state should
receive according to the PES is close to the number it has according to the
census.

The work raises many open questions and potential research directions:

Applying RLAs in Additional Settings: Generally speaking, RLAs are relevant
and can be applied whenever one wishes to verify the computation of some
function over a large number of inputs obtained through potentially error-
prone processes. While political elections provide a natural environment for
their application, we advocate for their use in a wider range of settings to
ensure reliable results.

As an example of such settings, RLAs could potentially be used to verify that
decisions taken based on datasets which were altered in order to satisfy
differential privacy are correct according to the real data. This could be
achieved by running an RLA in a protected environment (enclave) which holds a
subsample of the original, noiseless data. In this setting, the noisy,
(differential private) dataset is seen as the reported result, while the
noiseless dataset is the true results. An RLA can verify that the results of
some computation over the differential private dataset and over the original
noiseless dataset are likely to be identical, based on a (hopefully) small
random sample from the original dataset. One challenge is to make sure that
the very fact that the data passed the test does not hurt the desired
differential privacy property.

Analytical Analysis of the Efficiency of RLAs: Most recent literature in the
field, including this work, focuses on suggesting new RLA algorithms and
fitting them to additional electoral systems and settings. There is little to
no analytical analysis of the efficiency and capabilities of many RLA methods.
Without a more rigorous analysis, it is not possible to definitively determine
which RLA methods are better for which settings. Such analysis could help, for
instance, to argue analytically whether Batchcomp is indeed preferable over
ALPHA-Batch.

Analyzing the Ability to Audit Different Systems: Future research should
analyze how efficiently different social choice functions can be audited. The
”audatibility” of a social choice function might be connected to the its noise
stability, i.e., the probability of its outputted winners changing if every
vote is changed with some equal, independent probability. If a social choice
function has low noise-stability, it’s more likely to lead to election results
which have small margins, meaning they would be difficult to audit
efficiently. The noise-stability of different voting rules has been examined
previously in literature [16, 17]. Connecting these works to the field of RLAs
may aid in determining the potential capabilities of RLAs for different
election systems.

Connection Between RLAs and Computational Models: Thus far, advancements in
the field of RLAs were done mostly independently and without connection to
computational models. Finding such connections may inspire new RLA algorithms,
or suggest new methods for analyzing the capabilities and efficiency of
existing methods. As an example of these connections, RLAs can essentially be
viewed as randomized decision trees, where each branch represents a different
sequence of paper-backup ballots that can be uncovered during the audit.
Viewing RLAs in this manner allows us to analyze their query complexity
(number of ballots examined) or instance complexity (best possible performance
over specific election results) and to apply existing results from other
fields onto RLAs.

Unlabeled Instance Complexity and RLAs: Future research may find lower bounds
for the query-complexity of RLAs by analyzing the randomized unlabeled
certificate complexity of the social choice function they operate on, as
defined by Grossman, Komargodski and Naor [15]. The randomized unlabeled
certificate complexity is a complexity measure of a function over some
specific input. It’s defined roughly as the minimal number of queries, in
expectation, that any randomized decision tree which computes this function
has to perform over the specified input, given a permuted version of it as a
certificate. This notion is relevant for RLAs since they are essentially
randomized decision trees which calculate a social choice function’s output
(the true winners) while using the reported election results. In the ballot-
level RLA setting, these reported results are given as a reported tally of the
votes, which is equivalent to an unlabeled certificate - a randomly permuted
version of the paper-backup ballots. Therefore, it appears that an RLA’s
expected query-complexity over accurate reported results is lower bounded by
the election’s social choice function’s randomized unlabeled certificate
complexity over these same results.

Making such an observation, however, requires some adjustments in the
definition of the randomized unlabeled instance complexity. RLAs are expected
to be efficient even if their certificate is nearly accurate. Meaning, if the
reported tally they receive only contains small errors which do not change the
election winners, they are still expected to be relatively efficient. Decision
trees which are optimal for a specific input may be very inefficient when the
certificate is even slightly inaccurate. Thus, the unlabeled instance
complexity of a function may be determined by randomized decision trees which
would make for bad RLAs, as they may lead to a full recount if the reported
results contain negligible mistakes. Without adjusting its definition, lower
bounds which rely on this complexity measure may therefore be too loose.

The Expressibility of SHANGRLA: Future research should attempt to assess the
capabilities and limitations of different RLA frameworks, such as SHANGRLA.
Such research could, for example, find bounds on the efficiency (number of
examined ballots) of a SHANGRLA based RLA given some reported election
results, or discover classes of social choice functions which can and cannot
be audited using SHANGRLA. Some social choice functions, such as instant
runoff voting, do not currently have reductions to SHANGRLA assertions which
are both sufficient and necessary for the reported winners of the elections to
be correct [40]. Finding clear limitations for SHANGRLA can prevent
researchers from trying to develop SHANGRLA based RLAs for systems where it
cannot apply.

Batch-Level RLAs Beyond SHANGRLA: Currently, There are few batch-level RLA
algorithms for social choice functions beyond a simple plurality. This work
suggests a generic method for converting any SHANGRLA based RLA to a batch-
level RLA. Some election systems, such as instant runoff voting, do not
currently have a reduction to SHANGRLA assertions that are both sufficient and
necessary for the reported winners of the elections to be correct. This raises
the need for an even more general batch-level RLA method, which can be used in
systems that cannot currently be audited using SHANGRLA.

Census RLAs: This work presents the first RLA for population censuses. It is
possible and even likely that other RLA algorithms could be adapted to audit
censuses, perhaps with different goals or guarantees than our suggested
method.

Additionally, our census RLA method could potentially be optimized further.
This method operates iteratively, by sequentially sampling households and
reading their census results, and maintains a probability with which it can
approve the census at all times. It is possible that other algorithms, which
use the entirety of the census and PES data in one shot, could outperform our
method.

## 6 References

## References

  * [1] “A full list of U.S.A. states that conduct risk-limiting audits is available on the National Conference of State Legislature’s website”, https://www.ncsl.org/research/elections-and-campaigns/risk-limiting-audits.aspx
  * [2] Stephen Ansolabehere, Barry C. Burden, Kenneth R. Mayer and Charles Stewart III  “Learning from recounts”  In _Election Law Journal: Rules, Politics, and Policy_ 17.2 Mary Ann Liebert, Inc. 140 Huguenot Street, 3rd Floor New Rochelle, NY 10801 USA, 2018, pp. 100–116
  * [3] American Statistical Association  “American Statistical Association statement on risk-limiting post-election audits”, 2010
  * [4] National Governor’s Association  “Briefing On Post Enumeration Census Results”, https://www.nga.org/updates/briefing-on-post-enumeration-census-results/#::̃text=The%20Post%2DEnumeration%20Survey%20is,independent%20of%20the%20census%20operations, 2022
  * [5] Michelle Blom, Jurlind Budurushi, Ronald L. Rivest, Philip B. Stark, Peter J. Stuckey, Vanessa Teague and Damjan Vukcevic  “Assertion-based approaches to auditing complex elections, with application to party-list proportional elections”  In _International Joint Conference on Electronic Voting_ , 2021, pp. 47–62  Springer
  * [6] Michelle Blom, Andrew Conway, Peter J. Stuckey, Vanessa J. Teague and Damjan Vukcevic  “Random errors are not necessarily politically neutral”  In _International Joint Conference on Electronic Voting_ , 2020, pp. 19–35  Springer
  * [7] Michelle Blom, Peter J. Stuckey and Vanessa Teague  “RAIRE: Risk-limiting audits for IRV elections”  In _arXiv preprint arXiv:1903.08804_ , 2019
  * [8] United States Census Bureau  “Historical Households Tables” Table HH-4, https://www.census.gov/data/tables/time-series/demo/families/households.html, 2022
  * [9] Bipartisan Policy Center  “Presidential Commission on Election Administration”, 2013
  * [10] Giorgos Charalambous  “The House of Representatives”  In _The Politics and Government of Cyprus. Oxford: Peter Lange_ , 2008, pp. 143–168
  * [11] “Constitution of the Argentine Nation” Sections 45-46, http://www.biblioteca.jus.gov.ar/argentina-constitution.pdf
  * [12] Rick Durrett  “Probability: theory and examples”  Cambridge university press, 2019, pp. 235
  * [13] Michael Gallagher  “Proportionality, disproportionality and electoral systems”  In _Electoral studies_ 10.1 Elsevier, 1991, pp. 33–51
  * [14] Federal Returning Officer Germany (Bundeswahlleiter)  “Musterberechnung: Sitzverteilung nach dem Fünfundzwanzigsten Gesetz zur Änderung des Bundeswahlgesetzes” In German. An unofficial explanation in English based on this document is available at https://mikebeneschan.medium.com/the-algorithm-that-fills-germanys-parliament-fa1e10c85917, https://www.bundeswahlleiter.de/dam/jcr/05c1185a-173f-4bab-80d6-51027c94b1bc/bwg2021_mustersitzberechnung_ergebnis2017.pdf, 2020
  * [15] Tomer Grossman, Ilan Komargodski and Moni Naor  “Instance Complexity and Unlabeled Certificates in the Decision Tree Model”  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_ , 2020  Schloss Dagstuhl-Leibniz-Zentrum für Informatik
  * [16] Steven Heilman  “Noise Stability of Ranked Choice Voting”  In _arXiv preprint arXiv:2209.11183_ , 2022
  * [17] Steven Heilman and Alex Tarter  “Three candidate plurality is stablest for small correlations”  In _Forum of Mathematics, Sigma_ 9, 2021  Cambridge University Press
  * [18] Guihua Hu, Ting Wen and Yuhuan Liu  “Determining the sample size of a post-enumeration survey: The case of China, 2020”  In _Mathematical Population Studies_ Taylor & Francis, 2022, pp. 1–31
  * [19] The Central Election Committee Israel  “Decisions and guidelines from the elections of the 19th Knesset”, https://bechirot24.bechirot.gov.il/election/Decisions/AllDecisions/PreviousEllections/Documents/decisions_rubinstein_knesset19_2012_2013.pdf, 2013, pp. 359–360
  * [20] Kenneth C. Johnson  “Election certification by statistical audit of voter-verified paper ballots”  In _Available at SSRN 640943_ , 2004
  * [21] Zeev Kam  “Vaadat habchriot layamin hadash: ”Hateanot hasrot shachar, novot memetzuka” [The Central Election Committee to the new right party: ”The claims are baseless, born of distress”]”  In _Kan (Israeli Public Broadcasting Corporation)_ , https://www.kan.org.il/item/?itemid=50550, 2019
  * [22] Mark Lindeman, Neal McBurnett, Kellie Ottoboni and Philip B. Stark  “Next steps for the Colorado risk-limiting audit (corla) program”  In _arXiv preprint arXiv:1803.00698_ , 2018
  * [23] Mark Lindeman and Philip B. Stark  “A gentle introduction to risk-limiting audits”  In _IEEE Security & Privacy_ 10.5 IEEE, 2012, pp. 42–49
  * [24] Mark Lindeman, Philip B. Stark and Vincent S. Yates  “BRAVO: Ballot-polling Risk-limiting Audits to Verify Outcomes”  In _EVT/WOTE_ , 2012
  * [25] John McCarthy, Howard Stanislevic, Mark Lindeman, Arlene S. Ash, Vittorio Addona and Mary Batcher  “Percentage-based versus statistical-power-based vote tabulation audits”  In _The American Statistician_ 62.1 Taylor & Francis, 2008, pp. 11–16
  * [26] Medicine National Academies of Sciences  “Securing the Vote: Protecting American Democracy”  National Academies Press, 2018, pp. 29–30
  * [27] “National Assembly of Pakistan - Composition”, https://na.gov.pk/en/composition.php
  * [28] “NCSL Risk-Limiting Audits”, https://www.ncsl.org/research/elections-and-campaigns/risk-limiting-audits.aspx
  * [29] Lawrence D. Norden, Aaron Burstein, Joseph Lorenzo Hall and Margaret Chen  “Post-election audits: Restoring trust in elections”  Brennan Center for Justice, 2007
  * [30] Statistical Service Republic of Cyprus  “Census of Population and Housing 2021: Preliminary Results”, https://www.pio.gov.cy/en/press-releases-article.html?id=27965, 2022
  * [31] Ronald L. Rivest  “On estimating the size of a statistical audit”, 2006
  * [32] Roy G. Saltman  “Effective use of computing technology in vote-tallying”  US Department of Commerce, National Bureau of Standards, 1978
  * [33] Carsten Schürmann  “A risk-limiting audit in Denmark: A pilot”  In _International Joint Conference on Electronic Voting_ , 2016, pp. 192–202  Springer
  * [34] J.. Simon and B. O’Dell  “An end to ‘faith-based’ voting: universal precinct-based handcount sampling to check computerized vote counts in federal and statewide elections”, 2006
  * [35] The Danish Ministry Social Affairs  “The Electoral System in Denmark - Parliamentary elections”, https://elections.sim.dk/media/10507/the-electoral-system-in-denmark.pdf
  * [36] Jacob V. Spertus and Philip B. Stark  “Sweeter than SUITE: Supermartingale Stratified Union-Intersection Tests of Elections”  In _International Joint Conference on Electronic Voting_ , 2022, pp. 106–121  Springer
  * [37] Philip B. Stark  “ALPHA: Audit that Learns from Previously Hand-Audited Ballots”  In _arXiv preprint arXiv:2201.02707_ , 2022
  * [38] Philip B. Stark  “Conservative statistical post-election audits”  In _The Annals of Applied Statistics_ 2.2 Institute of Mathematical Statistics, 2008, pp. 550–581
  * [39] Philip B. Stark  “Risk-limiting postelection audits: Conservative $P$-values from common probability inequalities”  In _IEEE Transactions on Information Forensics and Security_ 4.4 IEEE, 2009, pp. 1005–1014
  * [40] Philip B. Stark  “Sets of half-average nulls generate risk-limiting audits: SHANGRLA”  In _International Conference on Financial Cryptography and Data Security_ , 2020, pp. 319–336  Springer
  * [41] Philip B. Stark, Vanessa Teague and Aleksander Essex  “Verifiable European elections: Risk-limiting audits for D’Hondt and its relatives”  In _$\\{$ USENIX$\\}$ Journal of Election Technology and Systems ($\\{$JETS$\\}$)_ 1, 2014, pp. 18–39
  * [42] “The Distribution of Knesset Seats (Bader-Ofer Method)” This page wrongly states that the electoral threshold is 2.0%. It was since changed to 3.25%, https://m.knesset.gov.il/en/about/lexicon/pages/seats.aspx
  * [43] Department of Economics United Nations Secretariat and Statistics Division Social Affairs  “Post Enumeration Surveys Operational guidelines”, https://unstats.un.org/unsd/demographic/standmeth/handbooks/Manual_PESen.pdf, 2010
  * [44] Ian Waudby-Smith, Philip B. Stark and Aaditya Ramdas  “RiLACS: Risk limiting audits via confidence sequences”  In _International Joint Conference on Electronic Voting_ , 2021, pp. 124–139  Springer


# Feature and Variable Selection in Classification

Aaron Karper

###### Abstract

The amount of information in the form of features and variables available to
machine learning algorithms is ever increasing. This can lead to classifiers
that are prone to overfitting in high dimensions, high dimensional models do
not lend themselves to interpretable results, and the CPU and memory resources
necessary to run on high-dimensional datasets severly limit the applications
of the approaches.

Variable and feature selection aim to remedy this by finding a subset of
features that in some way captures the information provided best.

In this paper we present the general methodology and highlight some specific
approaches.

##  1 Introduction

As machine learning as a field develops, it becomes clear that the issue of
finding good features is often more difficult than the task of using the
features to create a classification model. Often more features are available
than can reasonably be expected to be used, because using too many features
can lead to overfitting, hinders the interpretability, and is computationally
expensive.

###  1.1 Overfitting

One of the reasons why more features can actually hinder accuracy is that the
more features we have, the less can we depend on measures of distance that
many classifiers (e.g. SVM, linear regression, k-means, gaussian mixture
models, …) require. This is known as the curse of dimensionality.

Accuracy might also be lost, because we are prone to overfit the model if it
incorporates all the features.

######  Example.

In a study of genetic cause of cancer, we might end up with 15 participants
with cancer and 15 without. Each participant has 21’000 gene expressions. If
we assume that any number of genes in combination can cause cancer, even if we
underestimate the number of possible genomes by assuming the expressions to be
binary, we end with $2^{21^{\prime}000}$ possible models.

In this huge number of possible models, there is bound to be one arbitrarily
complex that fits the observation perfectly, but has little to no predictive
power [Russell et al., 1995, Chapter 18, Noise and Overfitting]. Would we in
some way limit the complexity of the model we fit, for example by discarding
nearly all possible variables, we would attain better generalisation.

###  1.2 Interpretability

If we take a classification task and want to gain some information from the
trained model, model complexity can hinder any insights. If we take up the
gene example, a small model might actually show what proteins (produced by the
culprit genes) cause the cancer and this might lead to a treatment.

###  1.3 Computational complexity

Often the solution to a problem needs to fulfil certain time constraints. If a
robot takes more than a second to classify a ball flying at it, it will not be
able to catch it. If the problem is of a lower dimensionality, the
computational complexity goes dows as well.

Sometimes this is only relevant for the prediciton phase of the learner, but
if the training is too complex, it might become infeasible.

###  1.4 Previous work

This article is based on the work of [Guyon and Elisseeff, 2003], which gives
a broad introduction to feature selection and creation, but as ten years
passed, the state-of-the-art moved on.

The relevance of feature selection can be seen in [Zhou et al., 2005], where
gene mutations of cancer patients are analysed and feature selection is used
to conclude the mutations responsible.

In [Torresani et al., 2008], the manifold of human poses is modelled using a
dimensionality reduction technique, which will presented here in short.

Kevin Murphy gives an overview of modern techniques and their justification in
[Murphy, 2012, p. 86ff]

###  1.5 Structure

In this paper we will first discuss the conclusions of Guyon and Elisseeff
about the general approaches taken in feature selection in section 2, discuss
the creation of new features in section 3, and the ways to validate the model
in section 4. Then we will continue by showing some more recent developments
in the field in section 5.

##  2 Classes of methods

In [Guyon and Elisseeff, 2003], the authors identify four approaches to
feature selection, each of which with its own strengths and weaknesses:

Ranking

orders the features according to some score.

Filters

build a feature set according to some heuristic.

Wrappers

build a feature set according to the predictive power of the classifier

Embedded methods

learn the classification model and the feature selection at the same time.

If the task is to predict as accurately as possible, an algorithm that has a
safeguard against overfitting might be better than ranking. If a pipeline
scenario is considered, something that treats the following phases as blackbox
would be more useful. If even the time to reduce the dimensionality is
valuable, a ranking would help.

###  2.1 Ranking

Variables get a score in the ranking approach and the top $n$ variables are
selected. This has the advantage that $n$ is simple to control and that the
selection runs in linear time.

######  Example.

In [Zhou et al., 2005], the authors try to find a discriminative subset of
genes to find out whether a tumor is malignant or benign111Acutally they
classify the tumors into 3 to 5 classes.. In order to prune the feature base,
they rank the variables according to the correlation to the classes and make a
preliminary selection, which discards most of the genes in order to speed up
the more sophisticated procedures to select the top 10 features.

There is an inherrent problem with this approach however, called the xor
problem[Russell et al., 1995]:

Figure 1: A ranking procedure would find that both features are equally
useless to separate the data and would discard them. If taken together however
the feature would separate the data very well.

It implicitly assumes that the features are uncorrelated and gives poor
results if they are not. On figure 1, we have two variables $X$ and $Y$, with
the ground truth roughly being $Z=X>5\;\mathtt{xor}\;Y>5$. Each variable taken
separately gives absolutely no information, if both variables were selected
however, it would be a perfectly discriminant feature. Since each on its own
is useless, they would not rank high and would probably be discarded by the
ranking procedure, as seen in figure 1.

######  Example.

Take as an example two genes $X$ and $Y$, so that if one is mutated the tumor
is malignant, which we denote by $M$, but if both mutate, the changes cancel
each other out, so that no tumor grows. Each variable separately would be
useless, because $P(M=true|X=true)=P(Y=false)$, but
$P(M=true|X=true,Y=false)=1$ –

###  2.2 Filters

While ranking approaches ignore the value that a variable can have in
connection with another, filters select a subset of features according to some
determined criterion. This criterion is independent of the classifier that is
used after the filtering step. On one hand this allows to only train the
following classifier once, which again might be more cost-effective. On the
other hand it also means that only some heuristics are available of how well
the classifier will do afterwards.

Filtering methods typically try to reduce in-class variance and to boost
inter-class distance. An example of this approach is a filter that would
maximize the correlation between the variable set and the classification, but
minimize the correlation between the variables themselves. This is under the
heuristic, that variables, that correlate with each other don’t provide much
additional information compared to just taking one of them, which is not
necessarily the case, as can be seen on figure 2: If the variable is noisy, a
second, correlated variable can be used to get a better signal, as can be seen
in figure 2.

Figure 2: Features might be identically distributed, but using both can reduce
variance and thus confusion by a factor of $\sqrt{n}$

A problem with the filtering approach is that the performance of the
classifier might not depend as much as we would hope on the proxy measure that
we used to find the subset. In this scenario it might be better to assess the
accuracy of the classifier itself.

###  2.3 Wrappers

Wrappers allow to look at the classifier as a blackbox and therefore break the
pipeline metaphor. They optimize some performance measure of the classifier as
the objective function. While this gives superior results to the heuristics of
filters, it also costs in computation time, since a classifier needs to be
trained each time – though shortcuts might be available depending on the
classifier trained.

Wrappers are in large search procedures through feature subset space – the
atomic _movements_ are to add or to remove a certain feature. This means that
many combinatorical optimization procedures can be applied, such as simulated
annealing, branch-and-bound, etc. Since the subset space is $2^{N}$, for $N$
the number of features, it is not feasible to perform an exhaustive search,
therefore greedy methods are applied: The start can either be the full feature
set, where we try to reduce the number of features in an optimal way
(_backward elimination_) or we can start with no features and add them in a
smart way (_forward selection_). It is also possible to replace the least
predictive feature from the set and replace it with the most predictive
feature from the features that were not chosen in this iteration.

###  2.4 Embedded

Wrappers treated classifiers as a black box, therefore a combinatorical
optimization was necessary with a training in each step of the search. If the
classifier allows feature selection as a part of the learning step, the
learning needs to be done only once and often more efficiently.

A simple way that allows this is to optimize in the classifier not only for
the likelihood of the data, but instead for the posterior probability (MAP)
for some prior on the model, that makes less complex models more probable. An
example for this can be found in section 5.2.

Somewhat similar is SVM with a $\ell_{1}$ weigth constraint
222$\ell_{p}(\mathbf{w})=\|\mathbf{w}\|_{p}=\sqrt[p]{\sum|w_{i}|^{p}}$ . The
1:1 exchange means that non-discriminative variables will end up with a 0
weight. It is also possible to take this a step further by optimizing for the
number of variables directly, since $l_{0}(w)=\lim_{p\rightarrow 0}l_{p}(w)$
is exactly the number of non-zero variables in the vector.

##  3 Feature creation

In the previous chapter the distinction between variables and features was not
necessary, since both could be used as input to the classifier after feature
selection. In this section _features_ is the vector offered to the classifier
and _variables_ is the vector handed to the feature creation step, i.e. the
_raw inputs_ collected. For much the same reasons that motivated feature
selection, feature creation for a smaller number of features compared to the
number of variables provided.

Essentially the information needs to be compressed in some way to be stored in
fewer variables. Formally this can be expressed by mapping the high-
dimensional space through the bottleneck, which we hope results in recovering
the low dimensional concepts that created the high-dimensional representation
in the first place. In any case it means that typical features are created,
with a similar intuition to efficient codes in compression: If a simple
feature occurs often, giving it a representation will reduce the loss more
than representing a less common feature. In fact, compression algorithms can
be seen as a kind of feature creation[Argyriou et al., 2008].

This is also related to the idea of manifold learning: While the variable
space is big, the actual space in that the variables vary is much smaller – a
manifold333A manifold is the mathematical generalization of a surface or a
curve in 3D space: Something smooth that can be mapped from a lower
dimensional space. of hidden variables embedded in the variable space.

######  Example.

In [Torresani et al., 2008] the human body is modelled as a low dimensional
model by _probabilistic principal component analyis_ : It is assumed that the
hidden variables are distributed as Gaussians in a low dimensional space that
are then linearly mapped to the high dimensional space of positions of pixels
in an image. This allows them to learn _typical_ positions that a human body
can be in and with that track body shapes in 3d even if neither the camera,
nor the human are fixed.

##  4 Validation methods

The goal up to this point was to find a simple model, that performs well on
our training set, but we hope that our model will perform well in data, it has
never seen before: minimizing the _generalization error_. This section is
concerned with estimating this error.

A typical approach is _cross-validation_ : If we have independent and
identically distributed datapoint, we can split the data and train the model
on one part and measure its performance on the rest. But even if we assume
that the data is identically distributed, it requires very careful curation of
the data to achieve independence:

######  Example.

Assume that we take a corpus of historical books and segment them. We could
now cross-validate over all pixels, but this would be anything but
independent. If we are able to train our model on half the pixels of a page
and check against the other half, we would naturally perform quite well, since
we are actually able to learn the style of the page. If we split page-wise, we
can learn the specific characteristics of the author. Only if we split author-
wise, we might hope to have a resemblence of independence.

Another approach is _probing_ : instead of modifying the data set and
comparing to other data, we can modify the _feature space_. We add random
variables, that have no predictive power to the feature set. Now we can
measure how well models fare against pure chance444 This can take the form of
a significance test.. Our performance measure is then the signal-to-noise
ratio of our model.

##  5 Current examples

###  5.1 Nested subset methods

In the nested subset methods the feature subset space is greedily examined by
estimating the expected gain of adding one feature in forward selection or the
expected loss of removing one feature in backward selection. This estimation
is called the _objective function_. If it is possible to examine the objective
function for a classifier directly, a better performance is gained by
embedding the search procedure with it. If that is not possible, training and
evaluating the classifier is necessary in each step.

######  Example.

Consider a model of a linear predictor $p(\mathbf{y}|\mathbf{x})$ with $M$
input variables needing to be pruned to $N$ input variables. This can be
modeled by asserting that the real variables $x_{i}^{\star}$ are taken from
$\mathbb{R}^{N}$, but a linear transformation $A\in\mathbb{R}^{N\times M}$ and
a noise term $n_{i}=\mathcal{N}(0,\sigma_{x}^{2})$ is added:

$\mathbf{x_{i}}=A\mathbf{x^{\star}_{i}}+n_{i}$

In a classification task555The optimization a free interpretation of [Guo,
2008], we can model
$y=\mathop{\mathrm{Ber}}\nolimits(\mathop{\mathrm{sigm}}\nolimits(\mathbf{w}\cdot\mathbf{x}^{\star}))$.

This can be seen as a generalisation of PCA666Principal component analysis
reduces the dimensions of the input variables by taking only the directions of
the largest eigenvalues. to the case where the output variable is taken into
account ([West, 2003] and [Bair et al., 2006] develop the idea). Standard
supervised PCA assumes that the output is distributed as a gaussian
distribution, which is a dangerous simplification in the classification
setting[Guo, 2008].

The procedure iterates over the eigenvectors of the natural parameters of the
joint distribution of the input and the output and adds them if they show an
improvement to the current model in order to capture the influence of the
input to the output optimally. If more than $N$ variables are in the set, the
one with the least favorable score is dropped. The algorithms iterates some
fixed number of times over all features, so that hopefully the globally
optimal feature subset is found.

###  5.2 Logistic regression using model complexity regularisation

In the paper _Gene selection using logistic regressions based on AIC, BIC and
MDL criteria_[Zhou et al., 2005] by Zhou, Wang, and Dougherty, the authors
describe the problem of classifying the gene expressions that determine
whether a tumor is part of a certain class (think malign versus benign). Since
the feature vectors are huge ($\approx 21^{\prime}000$ genes/dimensions in
many expressions) and therefore the chance of overfitting is high and the
domain requires an interpretable result, they discuss feature selection.

For this, they choose an embedded method, namely a normalized form of logistic
regression, which we will describe in detail here:

Logistic regression can be understood as fitting

$p_{\mathbf{w}}(\mathbf{x})=\frac{1}{1+e^{\mathbf{w}\cdot\mathbf{x}}}=\mathop{\mathrm{sigm}}\nolimits(\mathbf{w}\cdot\mathbf{x})$

with regard to the separation direction $\mathbf{w}$, so that the confidence
or in other words the probability $p_{\mathbf{w}^{\star}}(\mathbf{x}_{data})$
is maximal.

This corresponds to the assumption, that the probability of each class is
$p(c|\mathbf{w})=\mathop{\mathrm{Ber}}\nolimits(c|\mathop{\mathrm{sigm}}\nolimits(\mathbf{w}\cdot\mathbf{x}))$
and can easily be extended to incorporate some prior on $\mathbf{w}$,
$p(c|\mathbf{w})=\mathop{\mathrm{Ber}}\nolimits(c|\mathop{\mathrm{sigm}}\nolimits(\mathbf{w}\cdot\mathbf{x}))\,p(w)$
[Murphy, 2012, p. 245].

The paper discusses the priors of the Akaike information criterion (AIC), the
Bayesian information criterion (BIC) and the minimum descriptor length (MDL):

#### AIC

The Akaike information criterion penaltizes degrees of freedom, the $\ell_{0}$
norm, so that the function optimized in the model is $\log
L(\mathbf{w})-\ell_{0}(\mathbf{w})$. This corresponds to an exponential
distribution for $p(\mathbf{w})\propto\exp(-\ell_{0}(\mathbf{w}))$. This can
be interpreted as minimizing the variance of the models, since the variance
grows exponentially in the number of parameters.

#### BIC

The Bayesian information criterion is similar, but takes the number of
datapoints $N$ into account: $p(\mathbf{w})\propto
N^{-\frac{\ell_{0}(\mathbf{w})}{2}}$. This has an intuitive interpretation if
we assume that a variable is either ignored, in which case the specific value
does not matter, or taken into account, in which case the value influences the
model. If we assume a uniform distribution on all such models, the ones that
ignore become more probable, because they accumulate the probability weight of
all possible values.

#### MDL

The minimum descriptor length is related to the algorithmic probability and
states that the space necessary to store the descriptor gives the best
heuristic on how complex the model is. This only implicitly causes variable
selection. The approximation for this value can be seen in the paper itself.

Since the fitting is computationally expensive, the authors start with a
simple ranking on the variables to discard all but the best 5’000. They then
repeatedly fit the respective models and collect the number of appearances of
the variables to rank the best 5, 10, or 15 genes. This step can be seen as an
additional ranking step, but this seems unnecessary, since the fitted model by
construction would already have selected the best model. Even so they still
manage to avoid overfitting and finding a viable subset of discriminative
variables.

###  5.3 Autoencoders as feature creation

Autoencoders are deep neural networks777Deep means multiple hidden layers.
that find a fitting information bottleneck (see 3) by optimizing for the
reconstruction of the signal using the _inverse_ transformation888A truely
inverse transformation is of course not possible..

Figure 3: An autoencoder network

Deep networks are difficult to train, since they show many local minima, many
of which show poor performance [Murphy, 2012, p. 1000]. To get around this,
Hinton and Salakhutdinov [Hinton and Salakhutdinov, 2006] propose pretraining
the model as stacked restricted Bolzmann machines before devising a global
optimisation like stochastical gradient descent.

Restricted Bolzmann machines are easy to train and can be understood as
learning a probability distribution of the layer below. Stacking them means
extracting probable distributions of features, somewhat similar to a
distribution of histograms as for example HoG or SIFT being representative to
the visual form of an object.

It has long been speculated that only low-level features could be captured by
such a setup, but [Le et al., 2011] show that, given enough resources, an
autoencoder can learn high level concepts like recognizing a cat face without
any supervision on a 1 billion image training set.

The impressive result beats the state of the art in supervised learning by
adding a simple logistic regression on top of the bottleneck layer. This
implies that the features learned by the network capture the concepts present
in the image better than SIFT visual bag of words or other human created
features and that it can learn a variety of concepts in parallel. Further
since the result of the single best neuron is already very discriminative, it
gives evidence for the possibility of a _grandmother neuron_ in the human
brain – a neuron that recognizes exactly one object, in this case the
grandmother. Using this single feature would also take feature selection to
the extreme, but without the benefit of being more computationally
advantageous.

###  5.4 Segmentation in Computer Vision

A domain that necessarily deals with a huge number of dimensions is computer
vision. Even only considering VGA images, in which only the actual pixel
values are taken into account gives $480\times 640=307^{\prime}200$ datapoints
per image.

For a segmentation task in document analysis, where pixels need to be
classified into regions like border, image, and text, there is more to be
taken into account than just the raw pixel values in order to incorporate
spartial information, edges, etc. With up to 200 heterogeneous features to
consider for each pixel, the evaluation would take too long to be useful.

This section differs from the previous two in that instead of reviewing a
ready made solution to a problem, it shows the process of producing such a
solution.

The first thing to consider is whether or not we have a strong prior of how
many features are useful. In the example of cancer detection, it was known
that only a small number of mutation caused the tumor, so a model with a
hundred genes could easily be discarded. Unfortunately this is not the case
for segmentation, because our features don’t have a causal connection to the
true segmentation. Finding good features for segmentation requires finding a
good proxy feature set for the true segmentation.

Next we might consider the loss of missclassification: In a computer vision
task, pixel missclassifications are to be expected and can be smoothed over.
Computational complexity however can severely limit the possible applications
of an algorithm. As [Russell et al., 1995] note, using a bigger dataset can be
more advantageous than using the best algorithm, so we would favour an
efficient procedure over a very accurate one, because it would allow us to
train on a bigger training set. Since the variables are likely to be
correlated, ranking will give bad results.

Taking this into account, we would consider $L_{1}$ normalized linear
classifiers, because of the fast classification and training (the latter due
to [Yuan et al., 2010], in which linear time training methods are compared).
Taking linear regression could additionally be advanageous, since its _soft_
classification would allow for better joining of continuous areas of the
document.

##  6 Discussion and outlook

Many of the concepts presented in [Guyon and Elisseeff, 2003] still apply,
however the examples fall short on statistical justification. Since then
applications for variable and feature selection and feature creation were
developed, some of which were driven by advances in computing power, such as
high-level feature extraction with autoencoders, others were motivated by
integrating prior assumptions about the sparcity of the model, such as the
usage of probabilistic principal component analysis for shape reconstruction.

The goals of variable and feature selection – avoiding overfitting,
interpretability, and computational efficiency – are in our opinion problems
best tackled by integrating them into the models learned by the classifier and
we expect the embedded approach to be best fit to ensure an optimal treatment
of them. Since many popular and efficient classifiers, such as support vector
machines, linear regression, and neural networks, can be extended to
incorporate such constraints with relative ease, we expect the usage of
ranking, filtering, and wrapping to be more of a pragmatic first step, before
sophisticated learners for sparse models are employed. Advances in embedded
approaches will make the performance and accuracy advantages stand out even
more.

Feature creation too has seen advances, especially in efficient
generalisations of the principal component analysis algorithm, such as kernel
PCA (1998) and supervised extensions. They predominantly rely on the bayesian
formulation of the PCA problem and we expect this to drive more innovation in
the field, as can be seen by the spin-off of reconstructing a shape from 2D
images using a bayesian network as discussed in [Torresani et al., 2008].

## References

  * [Argyriou et al., 2008] Argyriou, A., Evgeniou, T., and Pontil, M. (2008).  Convex multi-task feature learning.  Machine Learning, 73(3):243–272.
  * [Bair et al., 2006] Bair, E., Hastie, T., Paul, D., and Tibshirani, R. (2006).  Prediction by supervised principal components.  Journal of the American Statistical Association, 101(473).
  * [Guo, 2008] Guo, Y. (2008).  Supervised exponential family principal component analysis via convex optimization.  In Advances in Neural Information Processing Systems, pages 569–576.
  * [Guyon and Elisseeff, 2003] Guyon, I. and Elisseeff, A. (2003).  An introduction to variable and feature selection.  The Journal of Machine Learning Research, 3:1157–1182.
  * [Hinton and Salakhutdinov, 2006] Hinton, G. E. and Salakhutdinov, R. R. (2006).  Reducing the dimensionality of data with neural networks.  Science, 313(5786):504–507.
  * [Le et al., 2011] Le, Q. V., Ranzato, M., Monga, R., Devin, M., Chen, K., Corrado, G. S., Dean, J., and Ng, A. Y. (2011).  Building high-level features using large scale unsupervised learning.  arXiv preprint arXiv:1112.6209.
  * [Murphy, 2012] Murphy, K. P. (2012).  Machine learning: a probabilistic perspective.  The MIT Press.
  * [Russell et al., 1995] Russell, S. J., Norvig, P., Canny, J. F., Malik, J. M., and Edwards, D. D. (1995).  Artificial intelligence: a modern approach, volume 74.  Prentice hall Englewood Cliffs.
  * [Torresani et al., 2008] Torresani, L., Hertzmann, A., and Bregler, C. (2008).  Nonrigid structure-from-motion: Estimating shape and motion with hierarchical priors.  Pattern Analysis and Machine Intelligence, IEEE Transactions on, 30(5):878–892.
  * [West, 2003] West, M. (2003).  Bayesian factor regression models in the ”large p, small n” paradigm.  Bayesian statistics, 7(2003):723–732.
  * [Yuan et al., 2010] Yuan, G.-X., Chang, K.-W., Hsieh, C.-J., and Lin, C.-J. (2010).  A comparison of optimization methods and software for large-scale l1-regularized linear classification.  The Journal of Machine Learning Research, 9999:3183–3234.
  * [Zhang et al., 2011] Zhang, X., Yu, Y., White, M., Huang, R., and Schuurmans, D. (2011).  Convex sparse coding, subspace learning, and semi-supervised extensions.  In AAAI.
  * [Zhou et al., 2005] Zhou, X., Wang, X., and Dougherty, E. R. (2005).  Gene selection using logistic regressions based on aic, bic and mdl criteria.  New Mathematics and Natural Computation, 1(01):129–145.