# Fair, Manipulation-Robust, and Transparent Sortition

Carmel Baharav<EMAIL_ADDRESS>0009-0004-3634-6721 ETH
ZurichZurichSwitzerland<EMAIL_ADDRESS>and  Bailey Flanigan
<EMAIL_ADDRESS>0000-0002-7805-1989 Carnegie Mellon
UniversityPittsburghPAUSA<EMAIL_ADDRESS>
###### Abstract.

Sortition, the random selection of political representatives, is increasingly
being used around the world to choose participants of deliberative processes
like Citizens’ Assemblies. Motivated by the practical importance of sortition,
there has been a recent flurry of computer science research on sortition
algorithms, whose task it is to randomly select a panel that satisfies several
quotas enforcing representation of key population subgroups. This existing
work has contributed an algorithmic approach for sampling a quota-satisfying
set of willing participants while ensuring their chances of selection are
maximally equal, as measured by any convex equality objective. The question,
then, is which equality objective is the right one? Past work has mainly
studied the objectives Minimax and Leximin, which respectively minimize the
maximum and maximize the minimum chance of selection given to any willing
participant. Recent work showed that both of these objectives have key
weaknesses: Minimax is highly robust to manipulation, but it is arbitrarily
unfair; and oppositely, Leximin is highly fair but arbitrarily manipulable.

In light of this gap, we propose a new equality objective, Goldilocks, that
aims to achieve these ideals simultaneously by ensuring that no potential
participant receives too little or too much chance of selection. We give tight
theoretical bounds on the extent to which Goldilocks achieves this, finding
that in a very important sense, Goldilocks recovers among the best available
solutions in a given instance. We then extend these theoretical bounds to the
case where the output of Goldilocks is transformed to achieve a third goal,
Transparency. Our empirical analysis of Goldilocks in real data is even more
promising: we find that this objective achieves nearly instance-optimal
minimum and maximum selection probabilities simultaneously in most real
instances — an outcome not even guaranteed to be possible for any algorithm.
In many respects, Goldilocks closes the question of whether we can
simultaneously achieve three key ideals of sortition — Fairness, Manipulation
Robustness, and Transparency — and contributes a practicable algorithm for
doing so.

††conference: ; ;

##  1\. Introduction

In a citizens’ assembly, a panel of randomly-selected everyday people is
convened to discuss and collectively weigh in on a policy issue. Each year,
more and more cities, regions, countries, and even supranational bodies are
turning to citizens’ assemblies111Citizens’ assemblies belong to a broader
category of closely-related methods called deliberative minipublics, which
consist also of citizens’ juries, citizens’ panels, deliberative polls, and
other processes of similar form. We will discuss citizens’ assemblies as the
primary application domain of this paper. to involve the public in
policymaking; prominent recent examples include multiple national citizens’
assemblies in France (Giraudet et al., 2022; Bürgerrat, 2023), Scotland’s
national climate assembly (gov.scot, 2021), and a permanent assembly instated
in the Ostbelgien government (OIPD, 2024).

The subject of this paper is the process used to randomly select the panel
members, called sortition. Broadly defined, sortition just means “random
selection”, and it is often thought of as a simple uniform lottery over the
population. In practice, however, the task of sortition is more complicated:
practitioners require the panel to satisfy custom quotas, which enforce near-
proportional representation of key population sub-groups. These groups are
usually defined by individual features (e.g., women or right-leaning voters),
but can be defined by intersections of features as well. While representation
of groups would in theory be achieved by a uniform lottery, there is selection
bias: different subgroups tend to agree to participate at very different
rates, meaning that a simple lottery would produce a panel that is far from
representative. To ensure representation despite selection bias, in practice
panels are selected via the following two-stage process:

  1. (1)

First, a uniform sample of the population is invited to participate. Those who
respond affirmatively form the pool of volunteers. Due to selection bias, this
pool is typically very skewed compared to the population.

  2. (2)

All pool members are asked to report their values of the features on which
quotas will be imposed. Then, a selection algorithm is used to find a panel
within the pool, which must satisfy the practitioner-defined quotas and be of
predetermined size $k$.

Our focus is the design of the selection algorithm in Stage (2), whose task it
is to sample a representative panel from the skewed pool. The skew of the pool
relative to the panel prevents any selection algorithm from randomizing over
the pool members perfectly uniformly, as would a simple lottery.222If a group
is disproportionately overrepresented in the pool compared to their quota-
allotted fraction of the panel, satisfying the quotas requires giving at least
one member of this overrepresented group below-average chance of selection.
However, recent work by Flanigan et al. (2021a) has made it possible to
randomize as equally as possible over pool members: they introduce an
algorithmic framework that can make volunteers’ probabilities maximally equal
subject to the quotas, as measured by any convex equality objective
$\mathcal{E}$ (i.e., any mapping from a vector of pool members’ selection
probabilities to a real number measuring how equal they are). The ability to
make selection probabilities maximally equal is desirable because it offers
hope of retaining — at least to a maximum degree possible — the normative
ideals granted by a simple lottery, such as Fairness, Manipulation Robustness,
and Transparency (to be defined shortly). The question is then: what equality
objective $\mathcal{E}$ should we optimize, in order to maximally achieve
these ideals? Subsequent work, which we overview now, has revealed how the
choice of $\mathcal{E}$ can have important consequences for these ideals.

The originally proposed equality objective was Leximin (a refinement of
Maximin), which measures equality according to the minimum selection
probability and thereby aims to ensure that no selection probability is too
low. This choice of objective was motivated by the ideal of Fairness: that
every willing participant is entitled to their fair share of the chance to
participate.

Leximin made substantial fairness gains over existing state-of-the-art
algorithms, but subsequent work identified a major weakness of this objective:
in theory and in practice, it allows pool members to ensure they are
deterministically selected for the panel by misreporting their features at the
beginning of Stage (2) (Flanigan et al., 2024). In light of this finding,
Flanigan _et al._ defined a new ideal: a selection algorithm’s Manipulation
Robustness is the extent to which it limits how much any agent can increase
their chance of selection by misreporting.

Flanigan et al. (2024) then diagnose the reason Leximin is so vulnerable to
manipulation: it raises low probabilities without regard for high
probabilities. Then, if a prospective participant can guess which identities
are essential to raising the lowest probabilities, they can misreport these
identities and the algorithm will push their selection probability all the way
up to 1. They further show that the well-known equality objective Nash Welfare
(the geometric mean of selection probabilities) suffers the same problem for
the same reason. Motivated by these negative results, they propose a new
equality objective, Minimax, which minimizes the maximum selection
probability.333Technically, Flanigan et al. (2024) study the
$\ell_{\infty}$-norm rather than Minimax; in our context, these objectives are
essentially the same, so for simplicity we consider Minimax. They show that
Minimax minimizes agents’ incentives for manipulating, thereby achieving
optimal Manipulation Robustness. Unfortunately, they find that Minimax has
essentially the opposite problem as Leximin: because Minimax does not control
low probabilities, it often gives many people zero selection probability,
thereby performing unacceptably poorly with respect to Fairness.

From this related work, we distill three observations: low probabilities are a
problem for Fairness; high probabilities are a problem for Manipulation
Robustness; and no known objective controls both simultaneously. These
observations motivate the first two questions we will tackle in this paper:

Question 1: Can we design an equality objective $\mathcal{E}$ that ensures
optimal simultaneous lower and upper bounds on selection probabilities? and
consequently,

Question 2: To what extent do these bounds on the minimum and maximum
selection probability permit simultaneous guarantees on $\mathcal{E}$’s
Fairness and Manipulation Robustness?

Much of the paper will be dedicated to simultaneously achieving Fairness and
Manipulation Robustness, because these ideals trade off with one another and
are similarly determined by $\mathcal{E}$. Then, we will investigate whether
we can achieve these two ideals alongside a third ideal of sortition
algorithms considered in previous work: Transparency.

Colloqually, transparency means that the public should be able to confirm that
the selection process is actually random, and the organizers are not stacking
the panel behind the scenes. Flanigan et al. (2021b) proposed a more precise
version of this definition: without reasoning in-depth about probability, the
public should be able to observe all volunteers’ chances of selection.
Flanigan et al. (2021a) proposed a method for achieving this ideal: to round
the output of a maximally equal algorithm into a uniform lottery over $m$
(potentially duplicated) panels (Flanigan et al., 2021a), and then select the
panel by performing this uniform lottery live. This approach permits
transparency as follows: prior to the lottery, organizers release an
(anonymized) list of panels containing each pool member, allowing any pool
member’s selection probability to be tabulated by simply counting how many
panels they are on and dividing by the total number of panels (usually 1000 in
practice).

The catch, of course, is that transforming the output of a maximally equal
algorithm into a uniform lottery over panels could require significant loss in
equality. Fortunately, Flanigan et al. (2021b) proved that there exist
rounding procedures guaranteed to produce uniform lotteries that are near-
optimal—at least with respect to Leximin and Nash Welfare, objectives which
both target fairness alone. Given that this uniform lottery approach is used
in practice, for our new equality objective to be viable, we must ensure that
rounding approximately preserves its Fairness and Manipulation Robustness.
This motivates our third question:

Question 3: If we achieve Transparency by rounding the output of our
$\mathcal{E}$-optimal algorithm to a uniform lottery, to what extent does
$\mathcal{E}$ still achieve Fairness and Manipulation Robustness?

###  1.1. Approach and Contributions

Unification of existing models, and a new equality objective (Section 2).
First, we undertake the considerable task of unifying existing models of
fairness, manipulation robustness, and transparency. As in past work (Flanigan
et al., 2024), we study three manipulation incentives: increasing one’s own
selection probability, decreasing someone else’s, or misappropriating panel
seats from other groups. We permit manipulating coalitions of up to linear
size (in the pool size $n$), and we permit agents to misreport any features
costlessly with full knowledge of the selection algorithm and the pool’s
composition.444While these assumptions may seem extremely pessimistic, we
adopt them because our algorithm is to be implemented in practice, and we want
guarantees that do not depend on any specific assumed behavioral model. Given
the insufficiency of known equality objectives, we propose a new one,
Goldilocksγ, defined below. Here, (slightly informally for now)
$\boldsymbol{\pi}$ is an assignment of selection probabilities to pool
members, and $\max(\boldsymbol{\pi}),\min(\boldsymbol{\pi}),$ and
$\text{avg}(\boldsymbol{\pi})$ describe the maximum, minimum, and average
selection probability, respectively.

$\textit{Goldilocks}_{\gamma}(\boldsymbol{\pi}):=\
\frac{\max(\boldsymbol{\pi})}{\text{avg}(\boldsymbol{\pi})}+\gamma\cdot\frac{\text{avg}(\boldsymbol{\pi})}{\min(\boldsymbol{\pi})}.$

In the style of multi-objective optimization, the first and second term
respectively aim to control high and low selection probabilities, and
$\gamma\in[0,\infty)$ is a scalar determining the extent to which the
objective prioritizes controlling the minimum versus the maximum probability.
For intuition about this objective’s behavior, consider $\gamma=1$: minimizing
$Goldilocks_{1}$ (essentially) minimizes the maximum multiplicative deviation
of any probability from the average. Although we will occasionally consider
other values of $\gamma$, our analysis will mainly focus on Goldilocks1.

Establishing the existence of “good” solutions (Section 3). Guaranteeing
Fairness and Manipulation Robustness depends on the ability to simultaneously
ensure that no selection probability is too low (to ensure fairness) nor too
high (to ensure manipulation robustness). In turn, the extent to which any
algorithm can do so depends on the quality of feasible solutions, which we
observe can be diminished by manipulation. In particular, we show that a
coalition of agents can misreport their features in a way that creates or
worsens fundamental gaps between agents’ probabilities, thereby eliminating
candidate-optimal solutions.555This issue does not arise when one aims only to
control Manipulation Robustness. To see this, see Flanigan et al. (2024),
which shows that Minimax optimally achieves manipulation robustness. This is
possible, however, because when manipulating coalitions induce gaps between
two groups’ probabilities, Minimax can simply give these groups zero selection
probability in other words, when fairness is not a concern, manipulating
coalitions do not affect the set of potentially optimal solutions. In
contrast, any objective controlling both high and low probabilities must
respond to such fundamental gaps in selection probabilities, so manipulating
coalitions can affect the set of potentially optimal solutions. This brings us
to the fundamental challenge associated with ensuring both Fairness and
Manipulation Robustness: we must first establish the quality of existing
solutions, which may depend on both the original instance and the number of
manipulators. We address this challenge in Section 3, giving matching upper
and lower bounds on the extent to which manipulation can eliminate solutions
with high minimum probabilities and/or low maximum probabilities. Among these
results, we demonstrate a fundamental trade-off between controlling high and
low probabilities.

Fairness, Manipulation Robustness and Transparency of Goldilocks1 (Sections 4
and 5). To bound Goldilocks1’s fairness and manipulation robustness, we first
show that Goldilocks1 guarantees lower and upper bounds on selection
probabilities that scale naturally — and in many relevant cases, tightly —
with the quality of available solutions. These bounds translate almost
directly to bounds on fairness and manipulation robustness. For reasons
described in Section 3, our bounds will depend on two quantities: $c$, the
number of agents who are willing to misreport, and $n_{min}$, the minimum
number of agents with given vector of features in the pool. Algorithms can be
best distinguished when $n_{min}$ is large (otherwise, all algorithms are
subject to the same impossibility), so we recap our results here assuming that
$n_{min}$ is large (our results handle general $n_{min}$, though). We are
particularly interested in how our guarantees depend on $n$, as increasing $n$
is a practically-implementable way to potentially diminish manipulation
incentives (Flanigan et al., 2024).

Regarding Goldilocks1’s manipulation robustness, we find that no manipulating
coalition of size $c$ can increase a single member’s selection probability by
more than order $\sqrt{c}/n$ — a quantity that diminishes quickly in $n$, even
if $c$ grows linearly with $n$. We give similar bounds for the other two
manipulation incentives. Regarding fairness, we find that Goldilocks1
guarantees Maximin fairness (i.e., minimum probability) of at least order
$1/(\sqrt{c}n)$. We then give a lower bound on the extent to which any
algorithm can simultaneously guarantee fairness and manipulation robustness,
revealing that our bounds are tight in a natural subset of regimes and nearly
tight in the rest. Finally, in Section 5 we bound the extent to which these
results (approximately) hold after the output of Goldilocks1 is rounded to a
uniform lottery, thereby establishing the extent to which fairness and
manipulation robustness can be achieved alongside transparency.

Empirical study of Goldilocks1 (Section 6). Finally, we analyze Goldilocks1 in
real citizens’ assembly datasets, and we find that it performs even better
than our bounds guarantee. Our first key finding is that Goldilocks1 achieves
near Leximin-optimal minimum probabilities and Minimax-optimal maximum
probabilities — an outcome whose possibility by any algorithm was not
guaranteed. On our ideals, we compare Goldilocks1’s performance to the other
previously-studied equality objectives, — Leximin, Nash Welfare, and Minimax.
We additionally compare these algorithms to Legacy, a heuristic standing in
for the wide variety of heuristic selection algorithms still used in practice
today. Our main finding is that Goldilocks1 performs nearly as well as Leximin
on fairness and Minimax on manipulation robustness, and it far outperforms all
other algorithms in its ability to achieve both these goals at once. In our
evaluation, we find that our theoretical results translate to the more
realistic case where manipulators are not worst-case, but rather use a natural
heuristic to decide how to manipulate. Finally, we find that Goldilocks1 can
be made transparent with little-to-no cost to the maximum and minimum
selection probabilities.

###  1.2. Related Work

In addition to the existing work on fairness (Flanigan et al., 2021a),
manipulation robustness (Flanigan et al., 2024), and transparency (Flanigan et
al., 2021b) on which we directly build, there is a growing body of work
pursuing selection algorithms achieving similar ideals. There is especially a
wealth of literature considering the interplay of two ideals: fairness (as we
define it), and proportional representation of the underlying population,
which we enforce with quotas. However, much of this work is done in the
distinct model of sortition where it is possible to sample the population
directly, and all chosen will participate (i.e., there is no selection bias).
For example, Ebadian and Micha (2023) study how to achieve exact fairness and
deterministic proportional representation simultaneously; closely related is
work by Benadè et al. (2019), which focuses on uniform-like stratified
sampling while preserving subgroup-level representation. Ebadian et al. (2022)
ask richer questions about the nature of representation that can be achieved
when individual people can serve as representatives for others to varying
extents. Outside the uniform selection model, Gasiorowska (2023) does a
qualitative survey across many selection process case studies, evaluating them
on the basis of randomness (closely related to our ideal of fairness) as well
as representation. Beyond related work on sortition, the existing theoretical
results we build on in this paper use tools from across several fields,
including randomized rounding (Gandhi et al., 2006), discrepancy theory (Beck
and Fiala, 1981), and optimization of large linear programs (Bradley et al.,
1977).

##  2\. Model

We use $\Delta(S)$ to represent the set of all distributions over the elements
of set $S$. Let $[n]$ be the pool, where $i\in[n]$ is an individual agent. The
pool is formed by inviting a uniform sample of the population to participate;
the agents in $[n]$ are those who responded affirmatively to this invitation.

Features, feature-values, and feature-vectors. Let $F$ be a predefined set of
features, where each feature $f\in F$ can take on some predefined set of
values $V_{f}$. For example, $F$ could be $\\{$age, gender$\\}$, and $V_{age}$
might be $\\{18\,\text{-}\,40,\,41\,\text{-}\,60,\,61\,+\\}$. We call each
$v\in V_{f}$ a feature-value and each $f,v$ a feature-value pair.
$FV:=\\{(f,v)|f\in F,v\in V_{f}\\}$ is the set of all feature-value pairs.

We assume that for each feature $f$, its possible values $V_{f}$ are
exhaustive and mutually exclusive, so every agent has exactly one value $v\in
V_{f}$ for every feature $f$. We denote $i$’s value for feature $f$ as $f(i)$,
thereby using each $f$ as a function $f:[n]\to V_{f}$. We let $i$’s feature
vector $w_{i}:=(f(i)|f\in F)$ summarize their feature-values, and
$\boldsymbol{w}:=(w_{i}|i\in[n])$ contains all agents’ feature vectors. We let
$\mathcal{W}:=\prod_{f\in F}V_{f}$ be the set of all possible feature vectors;
then, $w_{i}\in\mathcal{W}$ and $\boldsymbol{w}\in\mathcal{W}^{n}$.

The panel selection task. Our task is to choose a panel $K\subseteq[n]$ of
some pre-chosen size $k\in\mathbb{N}$. The main constraint on $K$ is that it
must satisfy upper and lower quotas on all feature-values. Formally, for each
$f,v\in FV$, we define lower and upper quotas $\ell_{f,v}\in\mathbb{N}^{+}$
and $u_{f,v}\in\mathbb{N}^{+}$ We summarize these quotas in
$\boldsymbol{\ell}=\\{\ell_{f,v}|f,v\in FV\\}$ and
$\boldsymbol{u}=\\{u_{f,v}|f,v\in FV\\}$. The set of all valid panels — i.e.,
those satisfying all requirements — is then

$\mathcal{K}:=\left\\{K:K\subseteq[n]\ \ \land\ \ |K|=k\ \ \land\ \
\ell_{f,v}\leq|\\{i\in K:f(i)=v\\}|\leq u_{f,v}\ \forall f,v\in FV\right\\}.$

An instance of the panel selection task is defined as
$\mathcal{I}:=([n],\boldsymbol{w},k,\boldsymbol{\ell},\boldsymbol{u}).$ Given
an instance, the panel selection task is to output a valid panel
$K\in\mathcal{K}$.

In a given instance $\mathcal{I}$, we will sometimes refer to $\boldsymbol{w}$
as the pool’s vector composition, as it encodes how many times each feature
vector $w\in\mathcal{W}$ appears in the pool, a number we denote as
$n_{w}(\mathcal{I}):=|\\{i\in[n]|w_{i}=w\\}|$. When $\mathcal{I}$ is clear, we
will simply write $n_{w}$. Because the pool will generally not contain all
possible feature vectors, we let
$\mathcal{W}_{\mathcal{I}}\subseteq\mathcal{W}$ denote the set of unique
feature vectors present in the pool in $\mathcal{I}$ (so
$n_{w}(\mathcal{I})>0$ iff $w\in\mathcal{W}_{\mathcal{I}}$). We assume that
the instance is not degenerate in that $|\mathcal{W}_{\mathcal{I}}|>1$ (the
pool contains more than one type of person). We let
$n_{min}(\mathcal{I}):=\min_{w\in\mathcal{W}_{\mathcal{I}}}n_{w}(\mathcal{I})$
be the size of the smallest vector group present in the pool. Note that
$|\mathcal{W}_{\mathcal{I}}|>1$ implies that $n_{min}(\mathcal{I})\leq n/2$.

Panel distributions and selection probabilities. In instance $\mathcal{I}$
with valid panels $\mathcal{K}$, $\Delta(\mathcal{K})$ is the set of all
possible randomizations over valid panels. We call each
$\mathbf{d}\in\Delta(\mathcal{K})$ a panel distribution, where $d_{K}$ then
denotes the probability of drawing $K$ from $\mathbf{d}$. Any given
$\mathbf{d}$ must imply some selection probability for each agent $i\in N$,
defined as

$\pi_{i}(\mathbf{d}):=\sum_{K\in\mathcal{K}:i\in K}d_{K}\qquad\text{for all
}i\in[n].$

In words, $\pi_{i}(\mathbf{d})$ is the probability that $i$ is included on the
panel when the panel is drawn from $\mathbf{d}$. We refer to
$\boldsymbol{\pi}(\mathbf{d}):=(\pi_{i}(\mathbf{d})|i\in[n])$ as an assignment
of selection probabilities to all agents in the pool. A generic selection
probability assignment will be $\boldsymbol{\pi}$. We use the shorthand
$\max(\boldsymbol{\pi}):=\max_{i\in[n]}\pi_{i}$ and
$\min(\boldsymbol{\pi}):=\min_{i\in[n]}\pi_{i}$ to respectively represent the
maximum and minimum selection probability assigned by $\boldsymbol{\pi}$ to
any agent.

In any instance $\mathcal{I}$, the space of all realizable selection
probability assignments is
$\Pi(\mathcal{I}):=\\{\boldsymbol{\pi}(\mathbf{d}):\mathbf{d}\in\Delta(\mathcal{K})\\}.$
In words, $\Pi(\mathcal{I})$ is the set of all selection probability
assignments that are implied by some randomization over exclusively valid
panels. Observe that for any $\boldsymbol{\pi}\in\Pi(\mathcal{I})$,
$\sum_{i\in[n]}\pi_{i}=k$. Therefore, in any given instance, the selection
probability assignment that gives all agents equal selection probability must
be $\boldsymbol{\pi}=k/n\mathbf{1}^{n}$, the $n$-length vector in which every
entry is $k/n$ (note that in most instances, this selection probability
assignment will not be in $\Pi(\mathcal{I})$).

Finally, we say that $\boldsymbol{\pi}$ is anonymous iff it gives all agents
with the same feature vector the same selection probability — that is, for all
$w\in\mathcal{W}$, there exists a constant $z_{w}$ such that $\pi_{i}=z_{w}$
for all $i$ : $w_{i}=w$. As we will typically work with anonymous selection
probability assignments, we define vector-indexed selection probabilities
$\textsf{p}_{w}(\boldsymbol{\pi})=z_{w}$. Let
$\textsf{p}(\boldsymbol{\pi})=(\textsf{p}_{w}(\boldsymbol{\pi})|w\in\mathcal{W})$.
When $\boldsymbol{\pi}$ is clear from context or when we work with arbitrary
vector-indexed probabilities, we simply write p.

Equality objectives. Let an equality objective
$\mathcal{E}:[0,1]^{n}\to\mathbb{R}$ be a function that intakes a selection
probability assignment and outputs a scalar measure of how equal the selection
probabilities within it are. All equality objectives we will consider are
convex. They will also all have the property that $\boldsymbol{\pi}$ is “more
equal” than $\boldsymbol{\pi}^{\prime}$ according to $\mathcal{E}$ if
$\mathcal{E}(\boldsymbol{\pi})\leq\mathcal{E}(\boldsymbol{\pi}^{\prime})$.
Then, a selection probability assignment $\boldsymbol{\pi}$ is maximally equal
in $\mathcal{I}$ iff
$\boldsymbol{\pi}\in\text{arg}\inf_{\boldsymbol{\pi}\in\Pi(\mathcal{I})}\mathcal{E}(\boldsymbol{\pi})$.
The set of all maximally equal selection probability assignments in
$\mathcal{I}$, as measured by $\mathcal{E}$, is

$\Pi^{\mathcal{E}}(\mathcal{I}):=\text{arg}\inf_{\boldsymbol{\pi}\in\Pi(\mathcal{I})}\mathcal{E}(\boldsymbol{\pi})\subseteq\Pi(\mathcal{I})$.

We will study the three equality objectives considered in past work on
sortition (Flanigan et al., 2021a, b, 2024), defined below. Here, Nash is the
Nash Welfare.

$Maximin(\boldsymbol{\pi}):=-\min(\boldsymbol{\pi}),\qquad
Minimax(\boldsymbol{\pi}):=\max(\boldsymbol{\pi}),\qquad
Nash(\boldsymbol{\pi}):=-\left(\prod_{i\in[n]}\pi_{i}\right)^{1/n}$.

We also study Leximin, which is not strictly an equality objective, but is a
previously-studied refinement of Maximin. Leximin first maximizes the minimum
selection probability (i.e., finds the Maximin-optimal solution), then
maximizes the second-lowest selection probability, then the third-lowest, and
so on. Finally, we newly introduce the objective Goldilocksγ, which penalizes
multiplicative deviations both above and below $k/n$ with
$\gamma\in\mathbb{R}_{\geq 0}$ controlling the relative priority placed on
either type of deviation.

$\textit{Goldilocks}_{\gamma}(\boldsymbol{\pi}):=\frac{\max(\boldsymbol{\pi})}{k/n}+\gamma\,\frac{k/n}{\min(\boldsymbol{\pi})}.$

In addition to being convex (Proposition 1), all objectives we
consider666Because Leximin is not an equality objective, it cannot formally
satisfy these properties. However, as will be clear throughout the paper,
Leximin effectively satisfies these properties to the extent we need it to.
satisfy two other natural axioms — conditional equitability (Proposition 2)
and anonymity (Proposition 3). These axioms are both weak requirements
reflecting that equality objectives truly measure the level of equality of
selection probabilities. In words, conditional equitability requires
$\mathcal{E}$ to consider $\boldsymbol{\pi}=k/n\mathbf{1}^{n}$ the most equal
possible probability assignment, and anonymity requires that $\mathcal{E}$
does not penalize giving identical agents identical selection probabilities.

###### Axiom 1.

$\mathcal{E}$ is conditionally equitable iff for all $\mathcal{I}$,
$k/n\mathbf{1}^{n}\in\Pi(\mathcal{I})\implies
k/n\mathbf{1}^{n}\in\Pi^{\mathcal{E}}(\mathcal{I})$.

###### Axiom 2.

$\mathcal{E}$ is anonymous iff for all $\mathcal{I}$, there exists an
anonymous $\boldsymbol{\pi}\in\Pi^{\mathcal{E}}(\mathcal{I})$.

Because all objectives $\mathcal{E}$ we consider satisfy anonymity, we will
without loss of generality redefine $\Pi(\mathcal{I})$ and
$\Pi^{\mathcal{E}}(\mathcal{I})$ to contain only anonymous selection
probability assignments.

Selection algorithms. A selection algorithm
$\textsc{A}:\mathcal{I}\to\mathcal{K}$ is any (potentially randomized) mapping
from an instance to a valid panel $K\in\mathcal{K}$. Note that in a given
instance, any selection algorithm must induce a panel distribution; we denote
the panel distribution implied by A in $\mathcal{I}$ as
$\mathbf{d}^{\textsc{A}}(\mathcal{I})\in\Delta(\mathcal{K})$. Its implied
selection probability assignment is then
$\boldsymbol{\pi}(\mathbf{d}^{\textsc{A}}(\mathcal{I}))$; for simplicity of
notation, when the panel distribution is not directly relevant, we will
shorten this to $\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I})$.

A selection algorithm A is maximally equal with respect to $\mathcal{E}$ iff
$\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I})\in\Pi^{\mathcal{E}}(\mathcal{I})$
for all $\mathcal{I}.$

Fortunately, the optimization framework proposed by Flanigan et al. (2021a)
gives an algorithmic implementation for any maximally equal selection
algorithm whose corresponding equality objectives $\mathcal{E}$ is convex,
which we will use to optimize the equality objectives defined above. At a high
level, their algorithmic approach works in two steps: first, it explicitly
computes a panel distribution implying maximally equal selection probabilities
per $\mathcal{E}$; then, it draws the final panel from this panel
distribution, thereby realizing those maximally equal selection probabilities.
As shorthand, we will refer to the algorithm from this framework optimizing
$\mathcal{E}$ as E (e.g., the algorithm optimizing Maximin is called Maximin).

###  2.1. Ideals: Manipulation Robustness, Fairness, and Transparency

Manipulation Robustness. To capture the fact that agents may misreport their
feature-values to the algorithm, we denote $i$’s reported feature vector as
$\tilde{w}_{i}\in\mathcal{W}$, to distinguish it from $w_{i}$. We refer to the
set of agents who may misreport their vectors as a coalition, denoted
$C\subseteq[n]$. We denote the vector of agents’ reported feature vectors as
$\boldsymbol{\tilde{w}}:=(\tilde{w}_{i}|i\in[n])$. We define the instance
$\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}}:=([n],\tilde{\boldsymbol{w}},k,\boldsymbol{\ell},\boldsymbol{u})$
as the instance created when a coalition $C$ misreports such that the vector
composition of the pool changes from $\boldsymbol{w}$ to
$\tilde{\boldsymbol{w}}$. Note that not all $\tilde{\boldsymbol{w}}$ can
result from a given $\mathcal{I},C$ pair; we let
$\boldsymbol{\mathcal{W}}_{\mathcal{I},C}\subseteq\mathcal{W}^{n}$ be the set
of all possible $\boldsymbol{\tilde{w}}$ that result from any misreports of
$C$ starting from $\mathcal{I}$. Formally, fixing $\mathcal{I}$ and
$C\subseteq[n]$,
$\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}$ iff
$\tilde{w}_{i}=w_{i}$ for all $i\notin C$ (for all $i\in C$, it can be that
$\tilde{w}_{i}\neq w_{i}\neq$ or $\tilde{w}_{i}=w_{i}$).

As in Flanigan et al. (2024), we assume that agents or coalitions can
costlessly misreport any feature vector in $\mathcal{W}$, and they do so with
full information about the selection algorithm and pool. We consider three
incentives for doing so: $\textsf{manip}_{\text{int}}$ captures how much a
coalition can increase the selection probability of someone internal to the
coalition; $\textsf{manip}_{\text{ext}}$ measures how much a coalition can
decrease the selection probability of someone external to the coalition; and
$\textsf{manip}_{\text{comp}}$ measures how many seats a coalition can, in
expectation, misappropriate from another group.

$\displaystyle\textsf{manip}_{\text{int}}(\mathcal{I},\textsc{A},c)$
$\displaystyle:=\max_{C\subseteq[n],|C|=c}\
\max_{\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}}\ \
\max_{i\in C}\ \
\pi^{\textsc{A}}_{i}(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}})-\pi^{\textsc{A}}_{i}(\mathcal{I}),$
$\displaystyle\textsf{manip}_{\text{ext}}(\mathcal{I},\textsc{A},c)$
$\displaystyle:=\max_{C\subseteq[n],|C|=c}\
\max_{\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}}\ \
\max_{i\notin C}\ \
\pi^{\textsc{A}}_{i}(\mathcal{I})-\pi^{\textsc{A}}_{i}(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}}),$
$\displaystyle\textsf{manip}_{\text{comp}}(\mathcal{I},\textsc{A},c)$
$\displaystyle:=\max_{C\subseteq[n],|C|=c}\
\max_{\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}}\ \
\max_{(f,v)\in
FV}\sum_{i:f(i)=v}\left(\pi^{\textsc{A}}_{i}(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}})-\pi^{\textsc{A}}_{i}(\mathcal{I})\right).$

These definitions can be interpreted as Nash equilibrium-style measures,
capturing how much a coalition can gain if everyone else is truthful. From a
formal game theoretic perspective, the argument of each maximum above can be
thought of as a utility function, which an agent or coalition may aim to
maximize. These definitions are worst-case (over coalitions and strategies) to
avoid assuming a behavioral model; importantly, they encompass the entire
range of cases where agents do not collude, but multiple agents pursue these
motives individually via any strategy.

Fairness. In accordance with past work on fairness in sortition (Flanigan et
al., 2021a, b), we evaluate the fairness of a selection algorithm A such that
a fairer algorithm makes the minimum selection probability higher. The
fairness of algorithm A in instance $\mathcal{I}$ is defined formally as
below; note that any algorithm optimizing Maximin is by definition optimally
fair in any given instance.

$\textsf{fairness}(\mathcal{I},\textsc{A}):=\min_{i\in[n]}\pi_{i}^{\textsc{A}}(\mathcal{I}).$

Because we want to guarantee fairness and manipulation robustness
simultaneously, we are actually interested in studying fairness in the
presence of manipulation. As such, the fairness of A in $\mathcal{I}$ in the
presence of the worst-case manipulating coalition of size $c$ is defined as

$\displaystyle\textsf{manip-
fairness}(\mathcal{I},\textsc{A},c):=\min_{C\subseteq[n],|C|=c}\
\min_{\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}}\ \
\textsf{fairness}(\pi_{i}^{\textsc{A}}(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}}),\textsc{A}).$

Transparency. We now formally define the components of Flanigan et al.
(2021b)’s algorithmic approach to transparency. For a given set of valid
panels $\mathcal{K}$, let $m\in\mathbb{Z}^{+}$ and define the set of all
$m$-uniform lotteries
$\overline{\Delta}_{m}(\mathcal{K}):=(\mathbb{Z}^{+}/m)^{|\mathcal{K}|}\cap\Delta(\mathcal{K})$
as the set of all panel distributions in which all probabilities are multiples
of $1/m$. $\overline{\mathbf{d}}\in\overline{\Delta}_{m}$ is called an
$m$-uniform lottery due to the following key observation:
$\overline{\mathbf{d}}$ contains exactly $m$ discrete blocs of $1/m$
probability mass, so we can sample a panel from $\overline{\mathbf{d}}$ via a
uniform lottery over $m$ panels (with duplicates) by numbering these
probability blocs $1\dots m$, and then uniformly drawing a number from $[m]$.
For example, if $m=1000$, we can execute this uniform lottery physically, by
drawing balls from bins corresponding to drawing 3 digits between 0 and 9, as
in Figure 3 of Flanigan et al. (2021a). Finally, we define
$\overline{\Pi}_{m}(\mathcal{I}):=\\{\boldsymbol{\pi}(\mathbf{\bar{d}})|\mathbf{\bar{d}}\in\overline{\Delta}_{m}(\mathcal{K})\\}$
as the set of all selection probability assignments realizable by $m$-uniform
lotteries in $\mathcal{I}$.

An $m$-uniform lottery is created by a rounding algorithm
$\mathcal{R}_{m}:\Delta(\mathcal{K})\to\overline{\Delta}_{m}(\mathcal{K})$,
which is any (possibly randomized) mapping from a panel distribution into an
$m$-uniform lottery. We apply a rounding algorithm $\mathcal{R}_{m}$ in
conjunction with maximally fair algorithm E as follows: first, run E to
compute panel distribution $\mathbf{d}^{\textsc{E}}(\mathcal{I})$; then, use
$\mathcal{R}_{m}$ to round $\mathbf{d}^{\textsc{E}}(\mathcal{I})$ to an
$m$-uniform lottery $\mathcal{R}_{m}(\mathbf{d}^{\textsc{E}}(\mathcal{I}))$.
Note that $\mathcal{R}_{m}\circ\textsc{E}$ is itself a selection algorithm,
mapping $\mathcal{I}$ to an $m$-uniform lottery
$\mathbf{d}^{\mathcal{R}_{m}\circ\textsc{E}}(\mathcal{I})$. We will define
specific rounding algorithms as needed.

###  2.2. Handling Structural Exclusion

We say that an instance $\mathcal{I}$ is structurally exclusive if there exist
one or more agents who are not included on any valid panel. We denote the set
of agents who are structurally excluded in $\mathcal{I}$ as
EX$(\mathcal{I}):=\\{i\in[n]|i\notin K\text{ for all }K\in\mathcal{K}\\}$. In
any instance where EX$(\mathcal{I})\neq\emptyset$, any algorithm must have
manip-fairness of 0 by construction. We now introduce restrictions to avoid
this trivial impossibility, which we prove are necessary in Proposition 4
(Section A.2).

First, Assumption 1 ensures that the truthful instance $\mathcal{I}$ does not
exhibit structural exclusion. This is a very weak restriction, and it is
satisfied by all real-world datasets we study in Section 6.

###### Assumption 1.

Instance $\mathcal{I}$ is such that EX$(\mathcal{I})=\emptyset$.

Second, we must handle structural exclusion that is caused by manipulation
(i.e., EX($\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}})\neq\emptyset$, even if
EX$(\mathcal{I})=\emptyset$). We avoid the structural exclusion of non-
coalition members (i.e.,
EX$(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}})\cap([n]\setminus
C)\neq\emptyset$) by considering only coalitions of limited size: in
$\mathcal{I}$, we consider $C\subseteq[n]$ such that

(Restriction 2.1) $|C|\leq\max\\{0,n_{min}(\mathcal{I})-k\\}.$

This restriction ensures that no vector group in the original pool is depleted
to a size below $k$, meaning that all valid panels in $\mathcal{K}$ remain
valid in $\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}}$ for all
$C\subseteq[n],\tilde{\boldsymbol{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}$.

Finally, we must handle coalition members who exclude themselves (i.e.,
EX$(\mathcal{I}^{\to_{C}\tilde{\boldsymbol{w}}})\cap C\neq\emptyset$). This is
an unnatural corner case (such a misreport would be costly to the agent while
barely affecting any other selection probability), so we do not risk
eliminating interesting cases with a new restriction. Instead, we simply do
not “count” such agents in our guarantees, and handle the resulting decrease
in pool size in our bounds. Formally, we henceforth implicitly redefine the
manipulated instance as $\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$ as
$([n^{\prime}],\tilde{\boldsymbol{w}}^{\prime},k,\boldsymbol{\ell},\boldsymbol{u})$,
where (re-indexing agents)
$[n^{\prime}]:=[n]\setminus(C\cap\textsc{EX}(\mathcal{I}))$, and
$\tilde{\boldsymbol{w}}^{\prime}:=(\tilde{w}_{i}|i\in[n^{\prime}])$, so any
manipulators who have excluded themselves are removed. In practice, this
approach corresponds to a natural and implementable algorithmic behavior:
detect and remove structurally excluding agents before running the algorithm.

##  3\. Existence of “Good” Solutions

###  3.1. Intuition: Problems 1 and 2 Prevent Good Solutions

Before analyzing any algorithms, we examine the extent to which it is
possible, in any given instance, to simultaneously control maximum and minimum
selection probabilities. We begin by identifying two potential barriers to
this goal.

Problem 1: Small groups. Sometimes, high probabilities can be required simply
due to the structure of the quotas and the pool. Consider Example 1 below: all
valid panels contain some minimum number of agents with a certain vector, and
there is a small number of such agents in the pool. As a result, any valid
panel distribution — and therefore any algorithm — must give each agent in
this group high selection probability.

###### Example 1 (small groups).

Let there be one feature $f$ with binary values $V_{f}=\\{0,1\\}$. Let
$\mathcal{I}$ such that the quotas require the panel to contain $k-1$ agents
with $f=0$ and 1 agent with $f=1$ ($\ell_{f,0}=u_{f,0}=1$). For any
$n_{min}\in\\{1,\dots,n-k+1\\}$, let the pool be such that $n_{0}=n-n_{min}$
and $n_{1}=n_{min}$. Then, any valid panel distribution must give each agent
with vector $1$ at least $1/n_{min}$ selection probability. It follows that
for any $\boldsymbol{\pi}\in\Pi(\mathcal{I})$, it must be that
$\max(\boldsymbol{\pi})\geq 1/n_{min}.$

Problem 2: Fundamental trade-offs between maximum, minimum probabilities. Even
in the absence of Problem 1, we can face another: the inclusion of one vector
group on a panel can necessitate the inclusion of another vector group. As
illustrated by Example 2 (based on an example from Flanigan et al. (2024)), if
these two “linked-fate” vector groups differ in size, then agents in the
smaller group must receive higher selection probabilities than those in the
larger group. This creates an inescapable trade-off between the maximum and
minimum selection probabilities.

###### Example 2 (fundamental trade-off).

Let there be two binary features $f_{1},f_{2}$ with
$V_{f_{1}}=V_{f_{2}}=\\{0,1\\}$. Let $\mathcal{I}$ be such that the quotas
require the panel be evenly split between 0/1 values of both features
($\ell_{f_{1},0}=u_{f_{1},0}=\ell_{f_{2},0}=u_{f_{2},0}=k/2$), and let the
pool be such that $n_{00}=n_{11}=n/4$, $n_{10}=n/2-1$, and $n_{01}=1$. The key
observation is that, to avoid upsetting the equal balance of 0 and 1 values of
either feature, any valid panel must contain an equal number of agents with 10
and 01, making them “linked-fate” groups. There are $n/2-1$ times as many
agents in the former group over which to spread these panel seats, so for any
panel distribution, it must be that
$\textsf{p}_{01}=\textsf{p}_{10}\,(n/2-1)\in\Theta(n\textsf{p}_{10})$ (see
Proposition 1 for full proof). Then, for all $z\in(0,1/n]$ and all
$\boldsymbol{\pi}\in\Pi(\mathcal{I})$,

$\displaystyle\min(\boldsymbol{\pi})\in\Omega(z)\implies\max(\boldsymbol{\pi})\in\Omega(\max\\{1/n,z\,n\\}).$

We remark that of these two problems, Problem 2 is far more interesting from
an algorithmic design perspective. This is because worst case, no algorithm
can do anything about Problem 1: this is illustrated by Example 1, whose lower
bound arises purely due to the quotas and pool structure, and thus must be
suffered by any algorithm. In contrast, when facing Problem 2, different
algorithms can make different trade-offs between the maximum and minimum
probability (effectively implementing different values of $z$). It is for this
reason that, as we will show, Goldilocks is tailored to the goal of addressing
Problem 2.

###  3.2. Formal Bounds on the Existence of Good Solutions

With some intuition about factors affecting the extent to which it is possible
to simultaneously control high and low probabilities in an instance, we now
pursue formal bounds. To do so, we must contend not only with the possibility
that Problems 1 and 2 exist in the original instance, but that they can be
created by manipulation where they did not previously exist. The following
lower bound captures both of these possibilities using an instance class that
almost directly combines Examples 1 and 2; we defer the proof to Section B.2.

###### Theorem 3 (Lower Bound).

Fix any even $k\in\\{6,\dots,n_{min}-3\\}$, any
$n_{min}\in\\{k+3,\dots,\lfloor n/2\rfloor\\}$, and any
$c\in\\{3,\dots,n_{min}-k\\}$. Then there exists $\mathcal{I}$ with $k$,
$n_{min}(\mathcal{I})=n_{min}$ satisfying Assumption 1, $C\subseteq[n]$ with
$|C|=c$, and
$\boldsymbol{\tilde{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}$ such that,
for all $z\in(0,1/n]$ and all
$\tilde{\boldsymbol{\pi}}\in\Pi(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$,

$\min(\tilde{\boldsymbol{\pi}})\geq
z\implies\max(\tilde{\boldsymbol{\pi}})\in\Omega(\max\\{cz,1/(n_{min}-c)\\}).$

Theorem 3 shows that manipulators can worsen Problems 1 or 2, or even create
them when they did not occur in the original instance (consider, e.g., the
lower bound construction with $n_{min}=n/4$). Then, the question is: to what
extent can manipulators eliminate good solutions via problems 1, 2, or other
kinds of problems? We now answer this question with Theorem 4, which gives an
upper bound matching Theorem 3. Conceptually, this tightness means that in the
worst case, we must handle Problems 1 and 2 and only these problems. Our
handling of these two problems will be reflected in our bounds: as in Theorem
3, Theorem 4 and many of our subsequent bounds contain a
$\max\\{\cdot,\cdot\\}$ term whose first and second entries handle Problem 2
and Problem 1, respectively.

###### Theorem 4 (Upper Bound).

Fix any $\mathcal{I}$ satisfying 1, $C\subseteq[n]$ with $|C|=c$ respecting
Restriction 2.1, and any
$\boldsymbol{\tilde{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}$. For all
$z\in(0,1/n]$, there exists
$\boldsymbol{\pi}\in\Pi(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$ such
that

$\min(\boldsymbol{\pi})\in\Omega(z)\qquad\text{and}\qquad\max(\boldsymbol{\pi})\in
O(\max\\{cz,1/(n_{min}(\mathcal{I})-c)\\}).$

###### Proof Sketch.

The full proof is intricate and requires significant notation, so we defer it
to Section B.5 and sketch it here. Fix any pair of instances
$\mathcal{I},\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$ with
$C,\tilde{\boldsymbol{w}}$ as specified in the statement. At a high level, we
will construct a panel distribution $\tilde{\mathbf{d}}$ in instance
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$ starting from a “good” panel
distribution $\mathbf{d}$ in instance $\mathcal{I}$. In particular, we will
choose $\mathbf{d}$ with associated $\boldsymbol{\pi}$ such that
$\min(\boldsymbol{\pi})\in\Omega(1/n)$ and $\max(\boldsymbol{\pi})\in
O(1/n_{min})$. We know such a $\mathbf{d}$ to exist by the following lemma:

###### Lemma 0.

If $\mathcal{I}$ satisfies Assumption 1, then $\exists$
$\boldsymbol{\pi}\in\Pi(\mathcal{I})$ such that
$\boldsymbol{\pi}\in[\Omega(1/n),\ O(1/n_{min}(\mathcal{I}))]^{n}.$

###### Proof Sketch.

We prove this lemma in Section B.4, but the argument is simple: all agents $i$
must exist on some panel $K_{i}\in\mathcal{K}$, per 1. By defining
$\mathbf{d}$ to uniformly randomize over $K_{1}\dots K_{n}$, we guarantee all
agents at least probability $\pi_{i}\in\Omega(1/n)$. The maximum total
probability given to any vector group by $\mathbf{d}$ is trivially at most
$k$; spread over at least $n_{min}(\mathcal{I})$ agents, it follows that for
all agents, $\pi_{i}\leq k/n_{min}(\mathcal{I})\in O(1/n_{min}(\mathcal{I}))$.
∎

Now, we construct $\tilde{\mathbf{d}}$ from $\mathbf{d}$ as pictured in Figure
1 (with some nuances omitted). Let $\overline{C}\subseteq C$ with
$|\overline{C}|=\overline{c}$ be the set of agents who misreport a feature
vector not in the original pool (i.e.,
$\tilde{w}_{i}\notin\mathcal{W}_{\mathcal{I}}$). For every $i\in\overline{C}$,
identify a panel $\tilde{K}_{i}\in\tilde{\mathcal{K}}$ such that
$i\in\tilde{K}_{i}$ (these need not be unique). Beginning from $\mathbf{d}$,
we transfer $\overline{c}z$ total probability mass from $\mathbf{d}$ (in blue)
and spread it evenly over the new panels $\tilde{K}_{i}|i\in\overline{C}$ (in
red).

Figure 1.  The solid bars depict $\tilde{\mathbf{d}}$, the distribution we
will construct. Blue bars represent the probability mass placed on panels that
were already present in the support of $\mathbf{d}$, and red bars represent
the probability placed on panels newly constructed to contain agents reporting
vectors not present in the truthful pool.

From this construction results the following panel distribution:

$\displaystyle\tilde{\mathbf{d}}_{K}=\Big{\\{}\mathbf{d}_{K}(1-\overline{c}z)\
\text{ for all }K\in\mathcal{K},\qquad z\ \text{ for all
}\tilde{K}_{i}|i\in[n],\qquad 0\ \text{ else}\Big{\\}}.$

Let $\tilde{\boldsymbol{\pi}}$ be the probability allocation implied by
$\mathbf{d}$. First, those who reported a vector outside the original pool
exist only on the $\overline{c}\leq c$ red panels, so
$\tilde{\pi}_{i}\in[z,cz]$ for all $i\in\overline{C}$. Next, considering those
who reported (either truthfully or not) a vector in the original pool: since
any member of this group may be on all $\overline{c}$ red panels, we apply
Lemma 5 to get that
$\pi_{i}\leq\tilde{\pi}_{i}\leq\pi_{i}\,\frac{n_{w_{i}}}{n_{w_{i}}-c}+\overline{c}z\leq\pi_{i}\,\frac{n_{min}}{n_{min}-c}\in
O(1/(n_{min}(\mathcal{I})-c)+cz)$ for all $i\in[n]\setminus\overline{C}$
(here, the intermediate steps handle the case that the coalition leaves $i$’s
vector group, making it smaller and thereby raising its members’ probabilities
by a factor of at most $n_{min}/(n_{min}-c)$). On the lower end, we have that
$\tilde{\pi}_{i}\geq(1-cz)\pi_{i}\in\Omega(1/n)$, using that
$\pi_{i}\in\Omega(1/n)$ and $1-cz\geq 1/2\in\Theta(1)$ (since $z\leq 1/n$ and
$c\leq n_{min}\leq n/2$ per Section 2). We conclude that
$\tilde{\pi}_{i}\in[\Omega(1/n),O(1/(n_{min}(\mathcal{I})-c)+cz)]$ for all
$i\in[n]\setminus\overline{C}$. Taking the union of the two ranges we have
deduced (the first for $i\in\overline{C}$, the second for
$i\in[n]\setminus\overline{C}$), we conclude that
$\tilde{\boldsymbol{\pi}}\in[\Omega(z),O(\max\\{cz,1/(n_{min}(\mathcal{I})-c)\\})]^{n}$,
as needed. ∎

##  4\. Goldilocks1: Manipulation Robustness and Fairness

Having characterized the quality of solutions that must exist, we now prove
bounds on the extent to which Goldilocks1 recovers the best available
solutions — and what this means for our ideals. The bulk of this section is
dedicated to proving Theorem 1, our main result, which positively bounds
Goldilocks1’s manipulation robustness and fairness. We will then discuss the
optimality of Goldilocks1, and how Goldilocks1 theoretically compares to (1)
Goldilocksγ with a finer-tuned choice of $\gamma$, and (2) the previously-
studied algorithms Leximin, Nash, and Minimax.

###### Theorem 1 (Upper Bound).

Fix any $\mathcal{I}$ satisfying 1 with $n_{min}(\mathcal{I})>k$. Then, for
all $c\leq n_{min}(\mathcal{I})-k$,

$\displaystyle\text{{{manip}}}_{\text{int}}(\mathcal{I},\textsc{Goldilocks}_{1},c)$
$\displaystyle\in O(\max\\{\nicefrac{{\sqrt{c}}}{{n}},\
\nicefrac{{1}}{{n_{min}(\mathcal{I})-c}}\\}),$
$\displaystyle\text{{{manip}}}_{\text{ext}}(\mathcal{I},\textsc{Goldilocks}_{1},c)$
$\displaystyle\in O(\nicefrac{{1}}{{n_{min}}}),$
$\displaystyle\text{{{manip}}}_{\text{comp}}(\mathcal{I},\textsc{Goldilocks}_{1},c)$
$\displaystyle\in
O(c\cdot\text{{{manip}}}_{\text{int}}(\mathcal{I},\textsc{Goldilocks}_{1},c))+\max_{(f,v)\in
FV}(u_{f,v}-\ell_{f,v}),$ $\displaystyle\text{{{manip-
fairness}}}(\mathcal{I},\textsc{Goldilocks}_{1},c)$
$\displaystyle\in\Omega(\min\left\\{\nicefrac{{1}}{{n\sqrt{c}}},\
\nicefrac{{(n_{min}-c)}}{{n^{2}}}\right\\}).$

###### Proof.

Fix any $\mathcal{I}$ and $C$ satisfying the requirements of the statement,
and fix any
$\boldsymbol{\tilde{w}}\in\boldsymbol{\mathcal{W}}_{\mathcal{I},C}$. Let
$\boldsymbol{\pi}^{*}=\boldsymbol{\pi}^{\textsc{Goldilocks}}(\mathcal{I})$
denote the optimal probabilities given by $\textsc{Goldilocks}_{1}$ in
$\mathcal{I}$, and likewise let
$\tilde{\boldsymbol{\pi}}^{*}=\boldsymbol{\pi}^{\textsc{Goldilocks}}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$.
The key steps of the proof are in bold.

Goldilocks minimizes multiplicative deviation from $k/n$. We represent the
minimum achievable multiplicative deviation from $k/n$ in $\mathcal{I}$ as
$\delta(\boldsymbol{\pi}):=\min_{\boldsymbol{\pi}\in\Pi(\mathcal{I})}\max\left\\{\frac{k/n}{\min(\boldsymbol{\pi})},\frac{\max(\boldsymbol{\pi})}{k/n}\right\\}.$
Then,777One may wonder why we do not just directly minimize
$\delta(\mathcal{I})$ to eliminate the 2-factor in Lemma 2. We study
Goldilocksγ because for practical reasons, we want an algorithm that continues
improving both the minimum and maximum as far as possible, rather than
stopping when the maximum multiplicative deviation from $k/n$ is reached.

###### Lemma 0.

For all $\mathcal{I}$,
$\boldsymbol{\pi}^{\textsc{Goldilocks}_{1}}(\mathcal{I})\in[k/n\cdot(2\delta(\mathcal{I}))^{-1},\
\ k/n\cdot 2\delta(\mathcal{I})]^{n}.$

###### Proof.

Fix any $\mathcal{I},\boldsymbol{\pi}\in\Pi(\mathcal{I})$ and let
$\boldsymbol{\pi}^{*}=\boldsymbol{\pi}^{\textsc{Goldilocks}_{1}}(\mathcal{I})$.
Then, by the optimality of $\boldsymbol{\pi}^{*}$,

$Goldilocks_{1}(\boldsymbol{\pi}^{*})\leq\textit{Goldilocks}_{1}(\boldsymbol{\pi})=\frac{\max(\boldsymbol{\pi})}{k/n}+\frac{k/n}{\min(\boldsymbol{\pi})}\leq
2\delta(\boldsymbol{\pi}).$

We apply this bound to bound each term of
Goldilocks${}_{1}(\boldsymbol{\pi}^{*})$ separately to conclude:

$\displaystyle\max(\boldsymbol{\pi}^{*})/(k/n)\leq 2\delta(\boldsymbol{\pi})$
$\displaystyle\iff\max(\boldsymbol{\pi}^{*})\leq k/n\cdot
2\delta(\boldsymbol{\pi})$ $\displaystyle(k/n)/\min(\boldsymbol{\pi}^{*})\leq
2\delta(\boldsymbol{\pi})$ $\displaystyle\iff\min(\boldsymbol{\pi}^{*})\geq
k/n\cdot(2\delta(\boldsymbol{\pi}))^{-1}.\qed$

$\delta(\mathcal{I})$ and
$\delta(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$ are bounded. First
considering $\mathcal{I}$, we know that there exists
$\boldsymbol{\pi}\in\Pi(\mathcal{I})$ such that $\max(\boldsymbol{\pi})\in
O(1/(n_{min}))$ and $\min(\boldsymbol{\pi})\in\Omega(1/n)$ (Lemma 5). It
follows that

(1) $\delta(\mathcal{I})\leq\max\left\\{\frac{k/n}{\Omega(1/n)},\
\frac{O(1/n_{min})}{k/n}\right\\}\in
O\left(\max\left\\{1,\frac{n}{n_{min}}\right\\}\right)=O\left(\frac{n}{n_{min}}\right).$

Next considering $\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$, we know that
for all $z\in(0,1/n]$, there exists
$\boldsymbol{\pi}\in\Pi(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$ such
that $\max(\boldsymbol{\pi})\in O(\max\\{cz,1/(n_{min}-c)\\})$ and
$\min(\boldsymbol{\pi})\in\Omega(z)$ (Theorem 4). We elect to apply this bound
with $z=1/(n\sqrt{c})$. Conceptually, we choose this $z$ because this is a
trade-off that Goldilocks1 is particularly well-suited to recover: Goldilocks1
penalizes deviations above and below $k/n$ equally, and this choice of $z$
correspondingly positions the requisite multiplicative probability gap of $c$
symmetrically over $k/n$ (i.e., $z=1/(n\sqrt{c})$ and $cz=\sqrt{c}/n$). It
follows that

(2)
$\delta(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\leq\max\left\\{\frac{k/n}{\Omega(1/(n\sqrt{c}))},\
\frac{O(\max\\{\sqrt{c}/n,\ 1/(n_{min}-c)\\})}{k/n}\right\\}\in
O\left(\max\left\\{\sqrt{c},\frac{n}{n_{min}-c}\right\\}\right).$

Maximum and minimum probabilities given by Goldilocks1 are bounded. Combining
Lemma 2 and Equations 1 and 2, we conclude that

$\boldsymbol{\pi}^{*}\in\left[\Omega\left(\frac{n_{min}}{n^{2}}\right),\
O\left(\frac{1}{n_{min}}\right)\right]^{n},\quad\tilde{\boldsymbol{\pi}}^{*}\in\left[\Omega\left(\min\left\\{\frac{1}{n\sqrt{c}},\
\frac{n_{min}-c}{n^{2}}\right\\}\right),\
O\left(\max\left\\{\frac{\sqrt{c}}{n},\
\frac{1}{n_{min}-c}\right\\}\right)\right]^{n}.$

Concluding the proof. The bounded probabilities above imply an upper bound on
the largest possible gain in probability by any agent:

$\text{{{manip}}}_{int}(\mathcal{I},\textsc{Goldilocks}_{1},c)\leq\max_{i\in[n]}(\tilde{\pi}_{i}^{*}-\pi_{i}^{*})\in
O\left(\max\left\\{\sqrt{c}/n,\ 1/(n_{min}-c)\right\\}\right).$

They also imply a bound on the largest possible loss in probability for any
agent:

$\text{{{manip}}}_{\text{ext}}(\mathcal{I},\textsc{Goldilocks}_{1},c)\leq\max_{i\in[n]}(\pi^{*}_{i}-\tilde{\pi}^{*}_{i})\in
O(1/n_{min}).$

Analyzing $\textsf{manip}_{comp}$ requires a little more care, because if the
quotas are not perfectly tight (e.g., if some group $f,v$ is permitted to
receive some range of seats $u_{f,v}-\ell_{f,v}>0$), manipulators can gain
seats for this group not just by misreporting value $v$ for $f$, but also by
ensuring that all panels in the support of the distribution give this group
$u_{f,v}$ seats instead of $\ell_{f,v}$. To make this formal, let
$\tilde{f}:[n]\to V_{f}$ map each agent $i$ to their reported value for
feature $f$. In the argument below, for each $(f,v)\in FV$, we divide the
quantity we want to bound into two, where the first represents the probability
garnered among agents who honestly report value $v$ for feature $f$, and the
second is the probability garnered among agents who do not report value $v$
for feature $f$ in the post-manipulation pool, but truly possess that feature.
Then, $\textsf{manip}_{comp}(\mathcal{I},\textsc{Goldilocks}_{1},c)$ is equal
to

$\displaystyle\max_{(f,v)\in
FV}\sum_{i:f(i)=v}(\tilde{\pi}^{*}_{i}-\pi_{i}^{*})$
$\displaystyle=\max_{(f,v)\in
FV}\sum_{i:f(i)=v\land\tilde{f}(i)=v}(\tilde{\pi}^{*}_{i}-\pi_{i}^{*})\ \
+\sum_{i:f(i)=v\land\tilde{f}(i)\neq v}(\tilde{\pi}^{*}_{i}-\pi_{i}^{*})$
$\displaystyle\leq\max_{(f,v)\in
FV}u_{f,v}-\ell_{f,v}+|\\{i|f(i)=v\land\tilde{f}(i)\neq
v\\}|\cdot\max_{i\in[n]}(\tilde{\pi}^{*}_{i}-\pi_{i}^{*})$
$\displaystyle\leq\max_{(f,v)\in
FV}u_{f,v}-\ell_{f,v}+O(c\cdot\text{{{manip}}}_{int}(\mathcal{I},\textsc{Goldilocks}_{1},c)).$

$\text{ Finally,}\ \ \text{{{manip-
fairness}}}(\mathcal{I},\textsc{Goldilocks}_{1},c)\geq\min_{i\in[n]}\tilde{\pi}_{i}^{*}\in\Omega\left(\min\left\\{1/(n\sqrt{c}),\
(n_{min}-c)/n^{2}\right\\}\right).\qed$

###  4.1. On the Optimality of Goldilocks

When considering the optimality of Goldilocks, we will primarily consider
manipint and manip-fairness. We comment on the tightness and practicality of
our other upper bounds in Section C.1. We first extend our impossibility on
controlling high and low probabilities (Theorem 3) to prove a corresponding
impossibility on the ability to simultaneously guarantee fairness and
manipulation robustness. This theorem is proven with almost an identical
construction to the proof of Theorem 3, with a slightly more complicated
coalition structure. We defer the proof to Section C.2.

###### Theorem 3 (Lower Bound).

Fix any algorithm A, any even $k\in\\{6,\dots,n_{min}-5\\}$,
$n_{min}\in\\{k+5,\dots,\lfloor n/k\rfloor\\}$ and
$c\in\\{5,\dots,n_{min}-k\\}$. There exists $\mathcal{I}$ with
$k,n_{min}(\mathcal{I})=n_{min}$ satisfying Assumption 1 such that for all
$z\in(0,1/n]$,

$\textsf{manip-
fairness}(\mathcal{I},\textsc{A},c)\in\Omega(z)\implies\textsf{manip}_{int}(\mathcal{I},\textsc{A},c)\in\Omega(\max\\{cz,1/(n_{min}-c)\\})$.

Observe that Goldilocks1 almost achieves the optimal trade-off at
$z=1/(n\sqrt{c})$: our bound on manipint in Theorem 1 matches that in Theorem
3, and our bound on manip-fairness in Theorem 1 matches Theorem 3 under the
condition that $n_{min},n_{min}-c\in\Omega(n)$. In fact, this special case
where Goldilocks1 is optimal is not entirely unnatural: it holds in
expectation in the real-world panel selection process, and thus should hold by
concentration for sufficiently large $n$.888Were $n$ to be increased in
practice, it would be done by increasing the number of letters sent out in
stage 1. Because these letters are sent out uniformly at random, all vector
groups present in the population would in expectation compose a constant
fraction of the pool. This guarantees that $n_{min}\in\Omega(n)$; it is a tiny
leap to strengthen Equation Restriction 2.1 such that
$c\leq(1-\epsilon)n_{min}-k$ for any constant $\epsilon>0$, in which case
$n_{min}-c\in\Omega(n)$ as well.

###### Observation 1.

For all $\mathcal{I},c$ such that
$n_{min}(\mathcal{I}),n_{min}(\mathcal{I})-c\in\Omega(n)$, Goldilocks1 is
optimal $z=1/(n\sqrt{c})$ (i.e., guarantees manipint and manip-fairness
matching Theorem 3 at this $z$ in $\mathcal{I}$).

The fact that Goldilocks1 is near-optimal for generic $c$ (and optimal when
$n_{min}$ is large) may seem surprising, because the algorithm has no
knowledge of $c$ with which to tune $\gamma$. This achievement is a
consequence of the fact that when Problem 2 is the main barrier to good
solutions (e.g., when $n_{min}$ is large), it is always possible to place the
$c$-dependent fundamental trade-off between maximum and minimum probabilities
symmetrically over $k/n$ (Theorem 4). Goldilocks1 will do so, thus achieving
an optimal trade-off. If Problem 1 is instead the main barrier to good
solutions (e.g., when $n_{min}$ is small), then the minimal achievable
deviations above and below $k/n$ are asymmetric, with the above deviation
being larger. Here, Goldilocks1 achieves the optimal maximum probability but
is not guaranteed to recover the best possible minimum probability due to the
asymmetry. This is the sense in which Goldilocks1 is tailored to Problem 2, as
discussed in Section 3.1.

Nonetheless, one may wonder if there exists a setting of $\gamma$ such that
Goldilocksγ can perfectly recover our bound in Theorem 3 for generic
$z,n_{min},c$. If not, this would suggest some weakness in the functional form
of Goldilocksγ, and perhaps some other objective could perform better.
Fortunately, we find that there does exist such a $\gamma$. We defer the proof
to Section C.3.

###### Proposition 0.

Fix any $\mathcal{I}$ satisfying 1 with $n_{min}(\mathcal{I})>k$, $c\leq
n_{min}(\mathcal{I})-k$, and $z\in(0,1/n]$. Let
$\gamma^{*}=z\cdot\max\\{1/(n_{min}-c),cz\\}\cdot(n/k)^{2}$. Then,

$\displaystyle\textsf{manip-
fairness}(\mathcal{I},\textsc{Goldilocks}_{\gamma^{*}},c)$
$\displaystyle\in\Omega(z)\quad\text{and}$
$\displaystyle\textsf{manip}_{int}(\mathcal{I},\textsc{Goldilocks}_{\gamma^{*}},c)$
$\displaystyle\in O(\max\\{cz,1/(n_{min}-c)\\}).$

Of course, the catch with this setting of $\gamma=\gamma^{*}$ is that it
depends on $c$, which is unknown in practice. While one may be tempted to
pursue more sophisticated, instance-dependent settings of $\gamma$, it will
turn out that $\gamma=1$ is already practically good enough: in Section 6, we
will find that Goldilocks1 has near-instance-optimal performance across
several real-world datasets. It will also significantly empirically outperform
all previously-studied algorithms.

###  4.2. Comparison to Existing Algorithms

Before empirically comparing Goldilocks1 to previously-studied algorithms
Minimax, Leximin, and Nash, we establish these algorithms’ theoretical
separation within our model (Propositions 6 and 5).999One may wonder why we do
not also compare to the linear analog of Goldilocksγ,
$\max(\boldsymbol{\pi})-\gamma\min(\boldsymbol{\pi})$. We prove a lower bound
on this objective in Section C.6. At a high level, this objective is limited
because it does not penalize low probabilities steeply enough relative to high
ones; Goldilocksγ has a steeper gradient, allowing it to reach better trade-
offs. We defer the proofs of these results to Sections C.4 and C.5, as they
are technically involved but conceptually only mildly generalize results
proven in (Flanigan et al., 2024).

First, it is easy to see that Minimax makes a highly undesirable trade-off,
giving no guarantees on fairness even when $n_{min}$ is large and there is no
manipulation:

###### Proposition 0.

There exists $\mathcal{I}$ with $n_{min}(\mathcal{I})\in\Omega(n)$ satisfying
Assumption 1 such that

$\text{{{fairness}}}(\mathcal{I},\textsc{Minimax})=0.$

In contrast, Leximin and Nash are not as obviously poor, but strike a
different trade-off than Goldilocks1: both algorithms prioritize essentially
only low probabilities, roughly akin to selecting $z\in\Theta(1/n)$ in Theorem
4 instead of $z\in\Theta(1/(\sqrt{c}n))$, as does Goldilocks1:

###### Proposition 0.

Fix any even $k\in\\{6,\dots,n_{min}-5\\}$, $n_{min}\in\\{k+5,\dots,\lfloor
n/k\rfloor\\}$ and $c\in\\{6,\dots,n_{min}-k\\}$. There exists $\mathcal{I}$
with $k,n_{min}(\mathcal{I})=n_{min}$ satisfying Assumption 1 such that

$\text{{{manip}}}_{int}(\mathcal{I},\textsc{Leximin},c),\ \
\text{{{manip}}}_{int}(\mathcal{I},\textsc{Nash},c)\ \in\
\Omega(\max\\{c/n,1/(n_{min}-c)\\}).$

To motivate our comparison of this bound with our upper bound on
$\textsf{manip}_{int}(\mathcal{I},\textsc{Goldilocks}_{1},c)$ in Theorem 1, we
note that one of the simplest ways to improve manipulation robustness in
practice is to increase the pool size $n$. It is therefore desirable for an
algorithm’s manipulation robustness to decline quickly in $n$. This is
precisely where Leximin / Nash and Goldilocks1 differ: unless $n_{min}$ is
prohibitively small (in which case both algorithms are subject to Problem 1),
the manipulation robustness of Leximin and Nash declines at a rate of $c/n$
while Goldilocks1 achieves $\sqrt{c}/n$. This may seem like a small
difference, but suppose manipulators make up a constant fraction of the pool
(i.e., $c\in\Theta(n)$). Then, $c/n\in\Theta(1)$ and Leximin and Nash have
arbitrarily poor manipulation robustness, even in the best case where $n$ and
$n_{min}$ are large. In contrast, for any $c$, Goldilocks1’s manipulation
robustness must decline in $n$ at a rate of $O(\sqrt{c}/n)\in O(1/\sqrt{n})$.

##  5\. Goldilocks1: Manipulation Robustness, Fairness, and Transparency

Finally, we extend our bounds from Theorem 1 to the transparent extension of
Goldilocks1, defined as $\mathcal{R}_{m}\circ$Goldilocks1 for some
$\mathcal{R}_{m}$. To do so, we will use the following key lemma from previous
work, which shows that there exists an $\mathcal{R}_{m}$ that can round any
panel distribution to an $m$-uniform lottery while changing all agents’
selection probabilities to only a bounded degree:

###### Lemma 0 (Thms 3.2 and 3.3, (Flanigan et al., 2021b)).

For all $\mathcal{I}$ and $m\in\mathbb{Z}^{+}$, there exists an
$\mathcal{R}_{m}$ such that for all $\mathbf{d}$ with corresponding
$\boldsymbol{\pi}$, it holds for
$\mathcal{R}_{m}(\mathbf{d})=\overline{\mathbf{d}}$ with corresponding
$\overline{\boldsymbol{\pi}}$ that

$\|\boldsymbol{\pi}-\overline{\boldsymbol{\pi}}\|_{\infty}\in
O\left(\min\left\\{k,\sqrt{|\mathcal{W}_{\mathcal{I}}|\log(|\mathcal{W}_{\mathcal{I}}|)}\right\\}/m\right).$

When applying this bound to our setting, we run into a problem: by Theorem 3,
the minimum probability may be dropping at a rate of $1/n\sqrt{c}$, which can
be as low as order $1/n\sqrt{n}$. In contrast, the above bound does not shrink
in $n$, so as $n$ grows (which is beneficial for manipulation robustness), the
upper bound above will exceed the minimum probability in the pre-rounded
instance, resulting in a fairness guarantee of 0. We solidify this concern by
proving a lower bound showing that rounding the Goldilocks-optimal solution
can indeed decrease the minimum probability by up to $\sqrt{k}/m$ (Proposition
1, Section D.1).

To avoid this issue, we need $m$ to grow at a rate of $\Omega(n\sqrt{n})$.
Fortunately, in practice it is much easier to scale up $m$ than $n$: scaling
up $n$ by a factor of 10 requires sending out 10 times as many letters, while
multiplying $m$ by 10 just requires adding another lottery bin (so panels are
numbered 0000 - 9999 instead of 000 - 999). We thus assume that $m\geq
n\sqrt{n}$.

We must deal with one more wrinkle: after manipulation, the number of unique
feature vectors in the pool may grow from $|\mathcal{W}_{\mathcal{I}}|$ to at
most $|\mathcal{W}_{\mathcal{I}}+c|$. Combining this observation, Lemma 1, and
Theorem 1, we conclude that there exists an $\mathcal{R}_{m}$ such that a
transparent algorithm $\mathcal{R}_{m}\circ\textsc{Goldilocks}_{1}$ achieves
the following simultaneous fairness and manipulation robustness guarantees.
Here, we use the shorthand
$\triangle(\mathcal{I}):=\min\\{k,\sqrt{|\mathcal{W}_{\mathcal{I}}+c|\,\log(|\mathcal{W}_{\mathcal{I}}+c|)}\\}/m$
(as in Lemma 1).

###### Theorem 2 (Upper Bound).

Fix any $m\geq n\sqrt{n}$ and $\mathcal{I}$ satisfying 1 with
$n_{min}(\mathcal{I})>k$. Then, there exists an $\mathcal{R}_{m}$ such that
for all $c\leq n_{min}(\mathcal{I})-k$,

$\displaystyle\text{{{manip}}}_{int}$
$\displaystyle(\mathcal{I},\mathcal{R}_{m}\circ\textsc{Goldilocks}_{1},c)\in
O\left(\text{{{manip}}}_{int}(\mathcal{I},\textsc{Goldilocks}_{1},c)+\triangle(\mathcal{I})\right),$
$\displaystyle\text{{{manip}}}_{ext}$
$\displaystyle(\mathcal{I},\mathcal{R}_{m}\circ\textsc{Goldilocks}_{1},c)\in
O\left(\text{{{manip}}}_{ext}(\mathcal{I},\textsc{Goldilocks}_{1},c)+\triangle(\mathcal{I})\right),$
$\displaystyle\text{{{manip}}}_{comp}$
$\displaystyle(\mathcal{I},\mathcal{R}_{m}\circ\textsc{Goldilocks}_{1},c)\in
O\left(\text{{{manip}}}_{comp}(\mathcal{I},\textsc{Goldilocks}_{1},c)+c\,\triangle(\mathcal{I})\right),$
manip-fairness
$\displaystyle(\mathcal{I},\mathcal{R}_{m}\circ\textsc{Goldilocks}_{1},c)\in\Omega\left(\text{{{manip-
fairness}}}(\mathcal{I},\textsc{Goldilocks}_{1},c)-\triangle(\mathcal{I})\right).$

##  6\. Empirical Evaluation

Instances. We analyze 9 instances of real-world panel selection data
identified only by number (their sources are anonymized). The relevant
properties of these instances are in Section E.2.

Algorithms. We evaluate four algorithms implementing Flanigan et al. (2021a)’s
maximally fair algorithmic framework: Leximin, Nash, Minimax, and
Goldilocks1.101010One might wonder if an instance-specific setting of $\gamma$
might perform better than $\gamma=1$. We evaluate two natural such definitions
of $\gamma$, but find that they make little difference to the performance of
Goldilocksγ (see Section E.1, Table 2). For our most computationally-intensive
experiments, we replace Leximin with Maximin, as it runs much faster on large
instances but behaves similarly with respect to the properties we aim to
test.111111Because Leximin/ Maximin and Minimax are optimizing such low
dimensional features of $\boldsymbol{\pi}$, one may wonder if tie-breaking may
improve these algorithms (e.g., fix the minimum probability achieved by the
Maximin-optimal solution, and then minimize the maximum probability). As shown
in Table 2, we find that this helps somewhat in some instances, but
Goldilocks1 still substantially dominates, suggesting that Goldilocks1 it is
finding a non-trivially good trade-off. Thus, for consistency with past work
and real-world implementations, our main results do not implement tie-
breaking. We also analyze the selection algorithm Legacy, which is a greedy
heuristic that was used widely in practice, and serves here as a benchmark
representing greedy algorithms that remain in use (see Section E.3 for
details). In some analyses, we consider only a key subset of these algorithms:
$\textsc{Minimax},\textsc{Leximin}$, and $\textsc{Goldilocks}_{1}$. Section
E.4 describes our implementation of Flanigan et al. (2021a)’s framework.

###  6.1. Maximum and Minimum Probabilities

We first compare algorithms’ ability to simultaneously control the maximum and
minimum probability. In Table 1, for each algorithm A and instance
$\mathcal{I}$, we report how closely the maximum and minimum probability given
by A approximate the optimal minimum probability (given by Maximin) and
optimal maximum probability (given by Minimax). Formally, table entries are
$\left(\min(\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I}))\,/\,\min(\boldsymbol{\pi}^{\textsc{Maximin}}(\mathcal{I})),\
\max(\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I}))\,/\,\max(\boldsymbol{\pi}^{\textsc{Minimax}}(\mathcal{I}))\right)$.

Equality Notions
---
$\mathcal{I}$ | Legacy | Minimax | Maximin | Leximin | Nash | Goldilocks1
1 | (0.0, 1.14) | (0.0, 1.0) | (1.0, 2.0) | (1.0, 2.0) | (0.62, 2.0) | (0.72, 1.1)
2 | (0.03, 1.01) | (0.0, 1.0) | (1.0, 1.33) | (1.0, 1.33) | (0.67, 1.33) | (0.9, 1.0)
3 | (0.0, 1.0) | (0.0, 1.0) | (1.0, 1.0) | (1.0, 1.0) | (0.61, 1.0) | (1.0, 1.0)
4 | (0.01, 1.0) | (0.0, 1.0) | (1.0, 1.0) | (1.0, 1.0) | (0.61, 1.0) | (1.0, 1.0)
5 | (0.0, 1.02) | (0.0, 1.0) | (1.0, 1.17) | (1.0, 1.17) | (0.57, 1.17) | (0.95, 1.0)
6 | (0.66, 1.11) | (0.25, 1.0) | (1.0, 1.5) | (1.0, 1.11) | (0.9, 1.08) | (1.0, 1.09)
7 | (0.0, 2.18) | (0.0, 1.0) | (1.0, 3.5) | (1.0, 3.5) | (0.46, 3.5) | (0.7, 1.38)
8 | (0.0, 1.0) | (0.0, 1.0) | (1.0, 1.0) | (0.98, 1.0) | (0.78, 1.0) | (1.0, 1.0)
9 | (0.0, 1.0) | (0.0, 1.0) | (1.0, 1.0) | (1.0, 1.0) | (0.45, 1.0) | (1.0, 1.0)
Table 1. Approximations to the optimal minimum, maximum probabilities across
algorithms, instances. In instance 8, Leximin is slightly worse than Maximin
due to numeric convergence errors in the solver.

What we see is already encouraging: in 7 out of 9 instances,
$\textsc{Goldilocks}_{1}$ achieves within 10% of the optimal maximum and
minimum probabilities. This is striking, because it was not even clear a
priori that this would be possible for any algorithm. In contrast, we see that
Legacy and Minimax perform poorly on low probabilities, Maximin/Leximin
perform poorly on high probabilities, and Nash performs somewhat poorly on
both. However, these results do not paint a complete picture: in instances 3,
4, 8, and 9, all algorithms achieve the optimal maximum probability simply
because the quotas require an agent to receive probability 1. Thus, to fully
compare the performance of these algorithms, we must examine their performance
on less constrained — but still realistic — instances. We therefore study
these algorithms’ maximum and minimum probabilities as we successively drop
features in decreasing order of their selection bias, as in Figure 1c of
(Flanigan et al., 2024). Details on feature dropping and results for omitted
instances are in Section E.5.

Figure 2. The solid, dashed lines respectively represent maximum, minimum
probabilities per algorithm. The shaded region lies between the optimal
maximum probability and optimal minimum probability, establishing the region
where no algorithm’s extremal probabilities can exist.

Figure 2 shows something striking: $\textsc{Goldilocks}_{1}$ hugs the gray
region almost perfectly above and below, thus maintaining near optimality as
features are dropped. This is in contrast to Leximin and Minimax, which
respectively continue to perform poorly on high and low probabilities, even as
the instance is loosened and better probabilities are possible. Together,
these results show that controlling high and low probabilities simultaneously
is generally possible to a great extent, and all previously explored
algorithms were leaving a lot on the table with respect to this goal.

###  6.2. Fairness, Manipulation Robustness, and Transparency

Fairness. While the above results already show the performance of all
algorithms on Maximin fairness, there are other normatively justified notions
of fairness. In Figure 3, we additionally evaluate fairness according to the
Gini Coefficient, defined as
$\text{{Gini}}(\boldsymbol{\pi}):=\frac{\sum_{i,j\in[n]}|\pi_{i}-\pi_{j}|}{2\sum_{i,j\in[n]}\pi_{i}\pi_{j}}.$
Note that a smaller Gini Coefficient reflects greater fairness, as Gini
measures inequality.

Figure 3 shows similar algorithmic behavior across instances: Legacy and
Minimax — which we expect to be very unfair — tend to have high inequality per
Gini. In contrast, $\textsc{Goldilocks}_{1}$ and Leximin perform far better.
Unsurprisingly, Leximin is slightly better, as it prioritizes fairness alone.

Figure 3. Gini coefficient across algorithms and instances. Lower Gini
Coefficient means greater fairness.

Manipulation Robustness. In accordance with previous work, we evaluate
manipulation robustness by measuring the maximum probability gainable by any
single, weakened manipulator. This manipulator uses the strategy Most
Underrepresented (MU), meaning they report the value of each feature that is
most disproportionately underrepresented in the pool (as studied in Flanigan
et al. (2024)). We evaluate how this probability changes as $n$ grows, which
we simulate by simply duplicating the pool. Details on these experiments are
found in Section E.6.

In Figure 4, we see that in instances 1 and 2, $\textsc{Goldilocks}_{1}$ is
far less manipulable than Maximin; in instance 3, we know the quotas require
some agents to receive probability 1. However, we see that as the pool is
duplicated, $\textsc{Goldilocks}_{1}$ makes use of this and the manipulation
drops; in contrast, across instances, Maximin remains just as manipulable.
From Figures 4 and 3, we conclude that $\textsc{Goldilocks}_{1}$ achieves
meaningful gains in manipulation robustness over Leximin — the practical
state-of-the-art — without any meaningful cost to fairness, as desired.

Figure 4. The maximum amount of probability any single MU manipulator can
gain, for 1 and 2 pool copies.

Transparency. Finally, we evaluate the extent to which we can round
$\textsc{Goldilocks}_{1}$-optimal panel distributions to $m$-uniform lotteries
without losing too much on high or low probabilities. In this analysis, we use
$m=1000$. Although this is lower than $n\sqrt{n}$ as our theory dictates, we
will find that this practicable number of panels is sufficient for good
performance.

We use Pipage rounding (Gandhi et al., 2006), a simple randomized dependent
rounding procedure. Although this algorithm does not come with any formal
guarantees on how much its rounded distribution will change agents’ selection
probabilities, Pipage is fast; already implemented in practice for the
purposes of transparent sortition (Sortition-Foundation, 2024); and has the
added advantage that, over the randomness of the rounding and sampling, it
perfectly preserves the selection probabilities, thereby exactly maintaining
our guarantees in Theorem 1 end-to-end. Details on our rounding algorithm and
experimental methods are in Section E.7.

Figure 5 shows good news: Pipage is reliably leaving
$\textsc{Goldilocks}_{1}$’s optimal selection probabilities essentially
unchanged. This is great news, because it means that we can have the best of
both worlds: we can achieve a high-quality uniform lottery while preserving
our fairness and manipulation robustness guarantees from Theorem 1 exactly,
end-to-end.

Figure 5. Deviations from $\textsc{Goldilocks}_{1}$-optimal selection
probability assignments by Pipage. The values for Pipage correspond to
averages of minimum, maximum probability per run over 1000 runs. Error bars
are plotted to indicate standard deviation, but they are so small that they
are not visible. Gray boxes extend vertically from the minimum (resp. maximum)
probability given by $\textsc{Goldilocks}_{1}$ to the theoretical bound given
by Lemma 1. Optimal minimum, maximum probabilities per instance are shown for
reference.

##  7\. Discussion

Stepping back from our worst-case model, we reflect on what manipulation is
likely to look like in practice. Based on anecdotes from sortition
practitioners, people who misreport their features usually appear to do so
with the intent to either increase their own probability
($\textsf{manip}_{int}$) or misappropriate seats from other groups
($\textsf{manip}_{comp}$). People tend to employ similar strategies,
misreporting belonging to identity groups that are more marginalized. This
usually amounts to joining groups that are underrepresented in the pool (as in
the strategy $MU$ in Section 6). Such misreports occur especially for
identities that are difficult to verify or challenge. Finally, it appears that
people tend to manipulate as individuals rather than as part of collusion
networks (though if sortition becomes more politically mainstream, this may
change).

These anecdotes motivate the pursuit of stronger bounds on
$\textsf{manip}_{int}$ and $\textsf{manip}_{comp}$. In the likely event that
better worst-case guarantees are impossible, one could pursue instance-wise
bounds. This direction would be of particular interest, as it might reveal new
conceptual barriers to good solutions beyond Problems 1 and 2. Another
approach would be to prove bounds in terms of instance parameters that
interpolate between the worst case and more realistic cases. For example,
since it is unlikely that all $c$ manipulators would act in concert, one could
pursue bounds assuming that at while there may be $c$ manipulators, they
collude in groups of size $s\leq c$. Such $s$-dependent bounds would reveal
any gaps between the power of manipulators acting in concert versus
independently. As another example, since manipulators often misreport
uncheckable features, one could pursue bounds parameterized by the instance
and which features are uncheckable. This approach might reveal, on an
instance-wise basis, which features are “safer” to protect with quotas.

###### Acknowledgements.

We thank Chara Podimata for helpful technical conversations, Ariel Procaccia
for computational resources, and the organizations who provided data (the
Sortition Foundation, the Center for Blue Democracy, Healthy Democracy, MASS
LBP, Of by For, and New Democracy). For funding, we thank the ETH Excellence
Scholarship Opportunity Programme (CB), the Fannie and John Hertz Foundation
(BF), and the NSF GRFP (BF).

## References

  * (1)
  * Beck and Fiala (1981) József Beck and Tibor Fiala. 1981.  “Integer-making” theorems.  _Discrete Applied Mathematics_ 3, 1 (1981), 1–8.
  * Benadè et al. (2019) Gerdus Benadè, Paul Gölz, and Ariel D Procaccia. 2019.  No stratification without representation. In _Proceedings of the 2019 ACM Conference on Economics and Computation_. 281–314.
  * Bradley et al. (1977) Stephen P Bradley, Arnoldo C Hax, and Thomas L Magnanti. 1977.  Applied mathematical programming.  _(No Title)_ (1977).
  * Bürgerrat (2023) Bürgerrat. 2023.  French citizens’ assembly supports assisted dying.  Available at https://www.buergerrat.de/en/news/french-citizens-assembly-supports-assisted-dying/ (2024/02/11).
  * Ebadian et al. (2022) Soroush Ebadian, Gregory Kehne, Evi Micha, Ariel D Procaccia, and Nisarg Shah. 2022.  Is Sortition Both Representative and Fair?  _Advances in Neural Information Processing Systems_ 35 (2022).
  * Ebadian and Micha (2023) Soroush Ebadian and Evi Micha. 2023.  Boosting Sortition via Proportional Representation.  Manuscript.
  * Flanigan et al. (2021a) Bailey Flanigan, Paul Gölz, Anupam Gupta, Brett Hennig, and Ariel D Procaccia. 2021a.  Fair algorithms for selecting citizens’ assemblies.  _Nature_ 596, 7873 (2021), 548–552.
  * Flanigan et al. (2021b) Bailey Flanigan, Gregory Kehne, and Ariel D Procaccia. 2021b.  Fair sortition made transparent.  _Advances in Neural Information Processing Systems_ 34 (2021), 25720–25731.
  * Flanigan et al. (2024) Bailey Flanigan, Jennifer Liang, Ariel D Procaccia, and Sven Wang. 2024.  Manipulation-Robust Selection of Citizens’ Assemblies. In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * Gandhi et al. (2006) Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. 2006.  Dependent rounding and its applications to approximation algorithms.  _Journal of the ACM (JACM)_ 53, 3 (2006), 324–360.
  * Gasiorowska (2023) Adela Gasiorowska. 2023.  Sortition and its Principles: Evaluation of the Selection Processes of Citizens’ Assemblies.  _Journal of Deliberative Democracy_ 19, 1 (2023).
  * Giraudet et al. (2022) Louis-Gaëtan Giraudet, Bénédicte Apouey, Hazem Arab, Simon Baeckelandt, Philippe Begout, Nicolas Berghmans, Nathalie Blanc, Jean-Yves Boulin, Eric Buge, Dimitri Courant, et al. 2022\.  “Co-construction” in deliberative democracy: lessons from the French Citizens’ Convention for Climate.  _Humanities and Social Sciences Communications_ 9, 1 (2022), 1–16.
  * gov.scot (2021) gov.scot. 2021.  Scotland’s Climate Assembly - recommendations for action: SG response.  Available at https://www.gov.scot/publications/scottish-government-response-scotlands-climate-assembly-recommendations-action/ (2024/02/11).
  * OIPD (2024) OIPD. 2024.  The Ostbelgien Model: a long-term Citizens’ Council combined with short-term Citizens’ Assemblies.  Available at https://oidp.net/en/practice.php?id=1237 (2024/02/11).
  * Sortition-Foundation (2024) Sortition-Foundation. 2024.  Stratification App.  https://github.com/sortitionfoundation/stratification-app.

##  Appendix A Supplemental Materials for Section 2

###  A.1. Proofs of Convexity, Conditional Equitability, and Anonymity

Below, we show that all of our stated equality objectives in Section 2 are
convex and satisfy conditional equitability and anonymity.

###### Proposition 0.

$Maximin,Minimax,Nash,$ and $Goldilocks_{\gamma}$ are all convex.

###### Proof.

The convexity of $Maximin$ and $Minimax$ follows immediately from their
definition: $\min$ is concave, so $-\min$ is convex, and $\max$ is a convex
function. Geometric mean is known to be concave, and as we define the $Nash$
objective to be the negative geometric mean, it is convex. Finally for
$Goldilocks_{\gamma}$, we can rewrite the second term as
$\frac{\gamma\max(1/\boldsymbol{\pi})}{n/k}$.
$1/\boldsymbol{\boldsymbol{\pi}}$ is convex as all entries of
$\boldsymbol{\pi}$ are nonnegative, and $\max$ is convex and increasing. Hence
the composition of these two functions is convex. Therefore,
$Goldilocks_{\gamma}$ is the sum of two convex functions, and is itself
convex. ∎

###### Proposition 0.

$Maximin,Minimax,Nash$ and $Goldilocks_{\gamma}$ are all conditionally
equitable.

###### Proof.

We will simply lower bound each objective function for any
$\boldsymbol{\pi}\in\Pi(\mathcal{I})$ and then show that $k/n\mathbf{1}^{n}$
achieves this bound. This will imply that
$k/n\mathbf{1}^{n}\in\Pi^{\mathcal{E}}(\mathcal{I})$. Fix any solution
$\pi\in\Pi(\mathcal{I})$. We know that $\max(\pi)\geq k/n$ and $\min(\pi)\leq
k/n$— otherwise $\sum_{i\in[n]}\pi_{i}\neq k$. Hence, for any feasible
solution:

$Maximin(\boldsymbol{\pi})\geq-k/n\qquad Minimax(\boldsymbol{\pi})\geq
k/n\qquad Goldilocks_{\gamma}(\boldsymbol{\pi})\geq n/k\cdot
k/n+\frac{\gamma}{n/k\cdot k/n}=1+\gamma$

Each of these lower bounds are realized by the solution $k/n\mathbf{1}$. For
$Nash$ we use the AM-GM inequality as follows:
$Nash(\boldsymbol{\pi})=-\left(\Pi_{i\in[n]}\pi_{i}\right)^{1/n}\geq\frac{-1}{n}\sum_{i\in[n]}\pi_{i}=\frac{-k}{n}$.
Again, this lower bound is realized by the solution $k/n\mathbf{1}$. ∎

We transfer the following claim about anonymity from Flanigan et al. (2021b)
as it is relevant to the structure of our final proposition proof.

###### Claim 1 ((Flanigan et al., 2021b) Claim B.6).

For any instance $\mathcal{I}$ and any realizable $\boldsymbol{\pi}$, let
$\boldsymbol{\pi^{\prime}}$ be the “anonymized” marginals obtained by setting
$\pi^{\prime}_{i}$ to the average $\boldsymbol{\pi_{j}}$ across all $j$ such
that $w_{j}=w_{i}$. Then $\boldsymbol{\pi^{\prime}}$ is realizable as well.

###### Proposition 0 (Adapted from (Flanigan et al., 2021b) Claim B.6).

$Maximin,Minimax,$ $Nash,\text{ and }Goldilocks_{\gamma}$ are all anonymous.

###### Proof.

Fix some instance $\mathcal{I}$, and
$\mathcal{E}\in\\{Maximin,Minimax,Nash,Linear_{\gamma},\text{ and
}Goldilocks_{\gamma}\\}$. By Assumption 1, we have that $\mathcal{I}$ is
feasible (all agents existing on a valid panel implies the existence of valid
panels and thus instance feasibility) – hence $\Pi^{\mathcal{E}}(\mathcal{I})$
is nonempty. Now we will use a similar proof as to that of 1, but will pay
attention to the impact of incrementally anonymizing the panel distribution on
the equality objective.

Assume for sake of contradiction that there is no anonymous $\boldsymbol{\pi}$
such that $\boldsymbol{\pi}\in\Pi^{\mathcal{E}}(\mathcal{I})$. Let
$\boldsymbol{\pi}$ be the most anonymized optimal vector of marginals, and
$\boldsymbol{d}$ be the corresponding panel distribution inducing it.
Formally:

$\boldsymbol{\pi}=\arg\min_{\boldsymbol{\pi}\in\Pi^{\mathcal{E}}(\mathcal{I})}\max_{w\in\mathcal{W}_{N}}\left(\max_{i\in[n]\colon
w_{i}=w}\pi_{i}-\min_{i\in[n]\colon w_{i}=w}\pi_{i}\right)$

There must be a finite number of pairs of marginals that are maximizing this
gap. We argue that we can equalize these pairs one-by-one without affecting
other marginals, while never increasing $\mathcal{E}$. Let $i,j\in[n]$ be such
that $w_{i}=w_{j}$ and they have the maximum gap between any marginals of the
same feature-vector in $\boldsymbol{\pi}$. Without loss of generality, assume
$\pi_{i}>\pi_{j}$. We construct a new panel distribution $\mathbf{d}^{\prime}$
as follows: $\mathbf{d}^{\prime}$ is identical to $\mathbf{d}$ except that it
swaps $i$ for $j$ and vice versa on all panels. Then define
$\mathbf{d}^{\prime\prime}=(\mathbf{d}+\mathbf{d}^{\prime})/2$. Let
$\boldsymbol{\pi^{\prime\prime}}$ be the marginals resulting from
$\boldsymbol{d^{\prime\prime}}$. We have that
$\pi^{\prime\prime}_{i}=\pi^{\prime\prime}_{j}$ and all other marginals remain
the same. Now we consider how our equality objective, $\mathcal{E}$ might be
impacted.

Notice that
$\min(\boldsymbol{\pi})\leq\pi_{j}<\pi^{\prime\prime}_{j}=\pi^{\prime\prime}_{i}<\pi_{i}\leq\max(\boldsymbol{\pi})$.
Therefore, as all other marginals remain unchanged, we have that
$\min(\boldsymbol{\pi})\leq\min(\boldsymbol{\pi^{\prime\prime}})$ and
$\max(\boldsymbol{\pi})\geq\max(\boldsymbol{\pi^{\prime\prime}})$. Therefore:

$\displaystyle Maximin(\boldsymbol{\pi^{\prime\prime}})$
$\displaystyle=-\min(\boldsymbol{\pi^{\prime\prime}})\leq-\min(\boldsymbol{\pi})\leq
Maximin(\boldsymbol{\pi})$ $\displaystyle
Minimax(\boldsymbol{\pi^{\prime\prime}})$
$\displaystyle=\max(\boldsymbol{\pi^{\prime\prime}})\leq\max(\boldsymbol{\pi})\leq
Minimax(\boldsymbol{\pi})$ $\displaystyle
Goldilocks_{\gamma}(\boldsymbol{\pi^{\prime\prime}})$
$\displaystyle=n/k\max(\boldsymbol{\pi^{\prime\prime}})-\gamma\cdot\frac{1}{n/k\min(\boldsymbol{\pi^{\prime\prime}})}\leq
n/k\max(\boldsymbol{\pi})-\gamma\cdot\frac{1}{n/k\min(\boldsymbol{\pi})}\leq
Goldilocks_{\gamma}(\boldsymbol{\pi})$

Finally, we just consider the case of $Nash$:

$\displaystyle Nash(\boldsymbol{\pi^{\prime\prime}})$
$\displaystyle=-\left(\Pi_{a\in[n]}\pi^{\prime\prime}_{a}\right)^{1/n}=-\left(\Pi_{a\in[n]}\pi_{a}\right)^{1/n}\cdot\left(\frac{\pi^{\prime\prime}_{i}\pi^{\prime\prime}_{j}}{\pi_{i}\pi_{j}}\right)^{1/n}$

We have that
$\pi^{\prime\prime}_{i}\pi^{\prime\prime}_{j}=\left(\frac{\pi_{i}+\pi_{j}}{2}\right)^{2}=\frac{\pi_{i}^{2}+2\pi_{i}\pi_{j}+\pi_{j}^{2}}{4}$.
We know that $(\pi_{i}-\pi_{j})^{2}\geq 0$ which implies that
$\pi_{i}^{2}+\pi_{j}^{2}\geq 2\pi_{i}\pi_{j}$. So this gives us that
$\pi^{\prime\prime}_{i}\pi^{\prime\prime}_{j}\geq\frac{4\pi_{i}\pi_{j}}{4}=\pi_{i}\pi_{j}$.
Returning to our analysis of $Nash$, we see that we are multiplying the
negative geometric mean of $\boldsymbol{\pi}$ by a value greater than or equal
to 1. So we have that
$Nash(\boldsymbol{\pi}^{\prime\prime})\leq-\left(\Pi_{a\in[n]}\pi_{a}\right)^{1/n}\leq
Nash(\boldsymbol{\pi})$. ∎

Then we have shown that for all equality objectives we are considering,
$\mathcal{E}(\boldsymbol{\pi}^{\prime\prime})\leq\mathcal{E}(\boldsymbol{\pi})$.
Therefore, after repeating this adjustment for all of the finitely many pairs
enforcing this maximum gap, we will have arrived at a more anonymized vector
of marginals that has objective value at most $\boldsymbol{\pi}$. This is a
contradiction to $\boldsymbol{\pi}$ being the most anonymized vector of
marginals in $\Pi^{\mathcal{E}}(\mathcal{I})$. Therefore, we have arrived at a
contradiction and can conclude that there exists an anonymous
$\boldsymbol{\pi}\in\Pi^{\mathcal{E}}(\mathcal{I})$.

###  A.2. Proof of Necessity of 1

###### Proposition 0.

If $\mathcal{I}$ is such that $EX(\mathcal{I})\neq\emptyset$ (satisfying
Assumption 1), then for all algorithms A, fairness$(\textsc{A},\mathcal{I})=0$
and manip-fairness$(\textsc{A},\mathcal{I},c)=0$ for all $c\in[0,n-1]$.

###### Proof.

Fix $\mathcal{I}=([n],\boldsymbol{w},k,\boldsymbol{\ell,u})$ such that
$EX(\mathcal{I})\neq\emptyset$. Then there exists some $i\in[n]$ such that
$i\not\in K$ for any $K\in\mathcal{K}$. Therefore, for any panel distribution
$\mathbf{d}\in\Delta(\mathcal{K})$, we have that
$\boldsymbol{\pi}(\mathbf{d})_{i}=0$, because $i$ does not appear on any panel
in the support of $\mathbf{d}$. As this is true for every possible panel
distribution, we have that $\textsf{fairness}(\mathcal{I},\textsc{A})=0$ for
any algorithm A. Note that manip-
fairness$(\textsc{A},\mathcal{I},c)\leq\textsf{fairness}(\mathcal{I},\textsc{A})$
for any $c\in[0,n-1]$ because there is always the possible scenario that none
of the coalition members misreport their vectors, and then
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}=\mathcal{I}$. Therefore, we have
that manip-fairness$(\textsc{A},\mathcal{I},c)\leq 0$ and is non-negative by
definition, so manip-fairness$(\textsc{A},\mathcal{I},c)=0$. ∎

###### Proposition 0.

Given a truthful instance $\mathcal{I}$ that satisfies Assumption 1,
Restriction 2.1 is nearly necessary to ensure that no non-coalition members
are structurally excluded in $\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$.
That is, $|C|$ must be at most $n_{min}-k+1$.

###### Proof.

Consider the instance $\mathcal{I}$ in which there is one binary feature and
quotas require that there are $k-1$ 1s for this feature on the panel. Let the
pool be evenly divided between those with value 1 and those with 0
($n_{0}=n_{1}=n/2$). Note that the pool satisfies Assumption 1: there is one
valid panel composition in which there are $k-1$ members with value 1 and $1$
member with value 0. Therefore, there are no structurally excluded agents in
the truthful pool. All members of the pool initially have feature-vector 1,
but a coalition $C$ of size $>n_{min}-k+1$ misreports their feature-vector as
0 in $\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$. As
$n_{min}(\mathcal{I})=n/2$, we have that the coalition has size $>n/2-k+1$,
and there are strictly fewer than $k-1$ remaining members with vector 1.
Therefore, there is no longer any valid panel remaining, so
$EX(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\cap([n]\setminus
C)\neq\emptyset$.

∎

##  Appendix B Supplemental Materials for Section 3

###  B.1. Analysis for Example 2

###### Proposition 0.

In the instance in Example 2, $\textsf{p}_{01}=\textsf{p}_{10}(n/2-1)$.

###### Proof.

Consider any valid panel $K\in\mathcal{K}$ for the instance $\mathcal{I}$.
Note that $K$ must have the same number of agents of type 01 and type 10 in
order to maintain equality of the total number of 0/1 values for each feature.
For a given vector $w\in\mathcal{W}$, we can write
$\textsf{p}_{w}(\boldsymbol{\pi})=\frac{1}{n_{w}}\sum_{i\in[n]\colon
w_{i}=w}\boldsymbol{\pi}_{i}=\frac{1}{n_{w}}\sum_{i\in[n]\colon
w_{i}=w}\sum_{K\in\mathcal{K}\colon i\in K}d_{K}$, as this is just looking at
the vector-indexed probability as the average of marginals of agents with that
probability vector. Rewriting, we get that
$\textsf{p}_{w}(\boldsymbol{\pi})=\frac{1}{n_{w}}\sum_{K\in\mathcal{K}}|\\{i\in
K:w_{i}=w\\}|\cdot d_{K}$. Plugging in for Example 2 gives that
$\textsf{p}_{01}=\frac{1}{1}\sum_{K\in\mathcal{K}}|\\{i\in K:w_{i}=01\\}|\cdot
d_{K}=(n/2-1)\cdot\frac{1}{n/2-1}\sum_{K\in\mathcal{K}}|\\{i\in
K:w_{i}=10\\}|\cdot d_{K}=(n/2-1)\textsf{p}_{10}$, where we use that $|\\{i\in
K:w_{i}=01\\}|=|\\{i\in K:w_{i}=10\\}|$ for all $K\in\mathcal{K}$. ∎

###  B.2. Proof of Theorem 3

###### Proof.

Fix $k,n_{min},c$ in the ranges specified in the statement. Our truthful
instance $\mathcal{I}=([n],\boldsymbol{w},k,\boldsymbol{\ell,u})$ has three
binary features $f_{1},f_{2},f_{3}$ and
$\mathcal{W}_{\mathcal{I}}=\\{000,110,111\\}$. Let the pool composition be

$n_{000}=n_{110}=(n-n_{min})/2$, $n_{111}=n_{min}$,

Let the quotas require perfect balance on the first two features:
$\boldsymbol{\ell}_{f_{1},0}=\boldsymbol{\ell}_{f_{1},1}=\boldsymbol{u}_{f_{1},0}=\boldsymbol{u}_{f_{1},1}=k/2$
and the same holds for $f_{2}$. On the third feature, let
$\boldsymbol{\ell}_{f_{3},0}=\boldsymbol{u}_{f_{3},0}=k-2$ while
$\boldsymbol{\ell}_{f_{3},1}=\boldsymbol{u}_{f_{3},1}=2$.

Fix any $C$ be of size $c$ and defined to contain $c$ agents who all have the
same truthful vector, $111$. To construct $\boldsymbol{\tilde{w}}$, let there
be two unique coalition members $i,j\in C$ that report different vectors from
the rest of the coalition: agent $i$ reports $\tilde{w}_{i}=111$ (truthfully),
and agent $j$ misreports $\tilde{w}_{j}=010$. All remaining agents $q\in
C\setminus\\{i,j\\}$ misreport $\tilde{w}_{q}=100$. Let
$\tilde{n}_{w}:=|\\{i\in[n]|\tilde{w}_{i}=w\\}$ represent the number of agents
in the manipulated pool with each vector $w\in\mathcal{W}$. Then, our
manipulated pool composition is as follows:

$\tilde{n}_{000}=\tilde{n}_{110}=(n-n_{min})/2,\qquad\tilde{n}_{111}=n_{min}-c+1,\qquad\tilde{n}_{100}=c-2,\qquad\tilde{n}_{010}=1.$

Let $\tilde{K}$ denote the set of valid panels in instance
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$. Observe that $\tilde{K}$
contains exactly two valid panel types (where both can be realized so long as
$k\geq 6$):

  * •

Type 1 contains 2 agents with vector $111$, $k/2-1$ agents with vector $000$,
and $k/2-1$ agents with vector $110$.

  * •

Type 2 contains 2 agents with vector $111$, $1$ agent with vector $010$, $1$
agent with vector $100$, $k/2-2$ agents with vectors $000$, and $k/2-2$ agents
with vector $110$.

Now, fix some $\mathbf{d}\in\Delta(\tilde{\mathcal{K}})$ with associated
probability allocation
$\boldsymbol{\pi}\in\Pi(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$ and
vector-indexed probabilities p. First, because all valid panels contain
exactly 2 agents with vector $111$, it must be that
$\textsf{p}_{111}=2/(n_{min}-c+1)$. Now deriving the other vector-indexed
probabilities, let $d_{1},d_{2}$ be the probabilities placed by $\mathbf{d}$
on panels of types 1 and 2, respectively. By definition of the panel types,

(3)
$\displaystyle\textsf{p}_{000}=\textsf{p}_{110}=d_{1}\frac{k/2-1}{(n-n_{min})/2}+d_{2}\frac{k/2-2}{(n-n_{min})/2},\qquad\textsf{p}_{100}=d_{2}\frac{1}{c-2},\qquad\textsf{p}_{010}=d_{2}.$

Noting that $d_{1}=(1-d_{2})$ and simplifying, we get that

(4)
$\displaystyle\textsf{p}_{000}=\textsf{p}_{110}=\frac{k/2-1-d_{2}}{(n-n_{min})/2},\quad\textsf{p}_{100}=d_{2}\frac{1}{c-2},\quad\textsf{p}_{010}=d_{2},\quad\textsf{p}_{111}=\frac{2}{n_{min}-c+1}.$

It follows that $\textsf{p}_{010}=(c-2)\textsf{p}_{110}$. To conclude the
proof, note that if $\min(\tilde{\boldsymbol{\pi}})\geq z$ and consequently
$\textsf{p}_{010}\geq z$, then
$\max(\tilde{\boldsymbol{\pi}})\geq(c-2)\textsf{p}_{010}\geq(c-2)z$. Given
also the value of p111, we conclude that $\min(\tilde{\boldsymbol{\pi}})\geq
z\implies\max(\tilde{\boldsymbol{\pi}})\geq\max\\{2/(n_{min}-c+1),(c-2)z\\})$,
as needed. ∎

###  B.3. Notation and preliminaries for proofs of Lemma 5 and Theorem 4

In this proof, we will work exclusively with feature-vector indexed objects,
which treat individuals with the same feature vector as interchangeable (this
is without loss of generality because, by Proposition 3, all objectives we
consider are anonymous). To begin, we will define these objects, which
collapse all individuals of the same feature vector.

Pool and panel compositions: For panel $K$, we let its panel composition
$\textsf{K}(K)\in[0,1]^{|\mathcal{W}|}$ describe the frequencies of each
feature vector on a panel, with $w$-th entry

$\textsf{K}_{w}(K)=\frac{|\\{i:i\in K\land w_{i}=w\\}|}{|K|}\ \ \text{and}\ \
\textsf{K}(K):=(\textsf{K}_{w}(K)|w\in\mathcal{W}).$

We say that K contains vector $w$ iff $\textsf{K}_{w}>0$.

We define a pool composition $\textsf{N}(N)\in[0,1]^{|\mathcal{W}|}$
analogously, so the pool composition of $N$ is given by

$\textsf{N}(N):=(\textsf{N}_{w}(N)|w\in\mathcal{W})\ \ \text{where}\ \
\textsf{N}_{w}(N)=\frac{|\\{i:i\in N\land w_{i}=w\\}|}{|N|}.$

When $N$ or $K$ is clear from context, or when referring to an arbitrary pool
or panel composition, we will simply use K or N respectively.

Let the set of valid panel compositions be

$\mathfrak{K}(\mathcal{K}):=\\{\textsf{K}(K)|K\in\mathcal{K}\\}.$

When $\mathcal{K}$ is clear, we will shorten this to $\mathfrak{K}$.

Then, a panel composition distribution is then any distribution over the set
of valid panel compositions; that is, $\textsf{d}\in\Delta(\mathfrak{K})$.

Vector-indexed total probabilities: Finally, for a given panel composition
distribution d we define the total probabilities given to each vector
$\textsf{t}(\textsf{d})\in[0,k]^{|\mathcal{W}|}$ as

$\textsf{t}_{w}(\textsf{d}):=\sum_{\textsf{K}\in\mathfrak{K}}\textsf{d}_{\textsf{K}}\cdot
k\cdot\textsf{K}_{w}\qquad\text{and}\qquad\textsf{t}(\textsf{d})=(\textsf{t}_{w}(\textsf{d})|w\in\mathcal{W}).$

Notice that we can just as easily define these totals for p as
$\textsf{t}_{w}(\textsf{p})=N_{w}\cdot\textsf{p}_{w}$ — abusing notation, we
will allow this.

Before proceeding, we prove the following two lemmas, which show how to
reconstruct a panel distribution from a panel composition distribution while
preserving the vector-indexed total probabilities and vice versa.

###### Lemma 0.

Fix a panel composition distribution d. We will now show how to construct a
corresponding panel distribution $\mathbf{d}$ such that
$\boldsymbol{\pi}(\mathbf{d})$ is anonymous with

$\pi_{i}(\mathbf{d})=\frac{\textsf{t}_{w}(\textsf{d})}{N_{w}}\quad\text{for
all }i:w_{i}=w,\text{ all }w\in\mathcal{W}.$

###### Proof.

Fix d. We will construct $\mathbf{d}$ via the following algorithm.

Initialize $\mathbf{d}\leftarrow\mathbf{0}^{|\mathcal{K}|}$.

For all panel compositions $\textsf{K}\in\mathfrak{K}$ such that
$\textsf{d}_{\textsf{K}}>0$, do the following:

> Let $W_{\textsf{K}}:=\\{w:\textsf{K}_{w}>0\\}$ be the set of all feature
> vectors contained by K. Then, let $L$ be the least common multiple of
> $N_{w}|w\in W_{\textsf{K}}$, i.e., the number of people in the pool with
> each such vector $w$. Now create $L$ panels $K_{1}^{(\textsf{K})}\dots
> K_{L}^{(\textsf{K})}$, where all these panels contain $k\cdot\textsf{K}_{w}$
> seats reserved for people of vector $w$, for each $w\in W_{\textsf{K}}$.
> Populate the seats reserved for vector $w$ on each panel with individuals
> with vector $w$ round-robin style until all panels of individuals are
> constructed. Because $L$ is a multiple of $N_{w}$ for all $w$, each $i$ with
> vector $w$ will be placed on the same number of panels, and will be placed
> on a total of $L\cdot k\cdot\textsf{K}_{w}/N_{w}$ panels. Also, note that
> because K was a valid panel composition, $K_{1}^{(\textsf{K})}\dots
> K_{L}^{(\textsf{K})}$ must be valid panels.
>
> Now, for each panel $K_{j}\in\\{K_{1}^{(\textsf{K})}\dots
> K_{L}^{(\textsf{K})}\\}$, $d_{K_{j}^{(\textsf{K})}}\leftarrow
> d_{K_{j}^{(\textsf{K})}}+\textsf{d}_{\textsf{K}}/L$.

Now, it just remains to prove that for all $i$ with $w_{i}=w$, we have that
$\pi_{i}(\mathbf{d})=t_{w}(\textsf{d})/N_{w}$, for all $w\in\mathcal{W}$. Fix
such a $w$ and corresponding $i$ with $w_{i}$. Then, based on the algorithm
above,

$\pi_{i}(\mathbf{d})=\sum_{\textsf{K}:\textsf{d}_{\textsf{K}}>0}L\cdot
k\cdot\textsf{K}_{w}/N_{w}\cdot\mathsf{d}_{\textsf{K}}/L=\sum_{\textsf{K}\in\mathfrak{K}}k\cdot\textsf{K}_{w}\cdot\mathsf{d}_{\textsf{K}}/N_{w}=\frac{\textsf{t}_{w}(\textsf{d})}{N_{w}}.\qed$

###### Lemma 0.

Given a panel distribution $\mathbf{d}$, we will show how to construct a
corresponding panel composition distribution d such that

$\textsf{t}_{w}(\textsf{d})=\sum_{i\in[n]\colon
w_{i}=w}\pi_{i}(\mathbf{d})\quad\text{for all }w\in\mathcal{W}.$

###### Proof.

Fix our panel distribution $\mathbf{d}$. We will essentially just abstract it
into a panel composition distribution. Initialize
$\textsf{d}\leftarrow\mathbf{0}^{|\mathfrak{K}|}$.

For all panels $K\in\mathcal{K}$ such that $\mathbf{d}_{K}>0$, update d as
follows:
$\textsf{d}_{\textsf{K}(K)}\leftarrow\textsf{d}_{\textsf{K}(K)}+\mathbf{d}_{K}$.
This is clearly a valid distribution because all entries are non-negative and
sum to 1 because we simply distribute the probability mass of $\mathbf{d}$
across panel compositions.

Fix some $w\in\mathcal{W}$. Based on the algorithm above, we have that:

$\displaystyle t_{w}(\mathsf{d})$
$\displaystyle=\sum_{\textsf{K}\in\mathfrak{K}}\textsf{d}_{\textsf{K}}\cdot
k\cdot\textsf{K}_{w}=\sum_{\textsf{K}\in\mathfrak{K}}\sum_{K\in\mathcal{K}\colon\textsf{K}(K)=\textsf{K}}\mathbf{d}_{K}\cdot
k\cdot\textsf{K}_{w}=\sum_{K\in\mathcal{K}}\mathbf{d}_{K}\cdot|\\{i\colon i\in
K\land w_{i}=w\\}|$ $\displaystyle=\sum_{K\in\mathcal{K}}\sum_{i\colon i\in
K\land w_{i}=w}\mathbf{d}_{K}=\sum_{i\in[n]\colon
w_{i}=w}\sum_{K\in\mathcal{K}\colon i\in K}\mathbf{d}_{K}=\sum_{i\in[n]\colon
w_{i}=w}\pi_{i}(\mathbf{d})$

∎

###  B.4. Proof of Lemma 5

###### Proof.

Fix an instance $\mathcal{I}$ satisfying 1. We will construct $\mathbf{d}$ by
constructing a panel composition distribution d, and then transforming it into
a panel distribution via Lemma 2. By 1, for each
$w\in\mathcal{W}_{\mathcal{I}}$ there must exist some panel composition
$\textsf{K}\in\mathfrak{K}$ such that $\textsf{K}_{w}>0$. Let
$\textsf{K}^{(w)}$ be the associated panel for each vector
$w\in\mathcal{W}_{\mathcal{I}}$ (these panel compositions need not be unique).
Then, define $h(\textsf{K}):=\sum_{w:\textsf{K}^{(w)}=\textsf{K}}n_{w}$ as the
number of agents in the pool whose “associated” panel composition is K. Now,
define our panel composition distribution such that

$\textsf{d}_{\textsf{K}}=\begin{cases}h(\textsf{K})/n\qquad&\text{for all
}\textsf{K}\in\bigcup_{w\in\mathcal{W}_{\mathcal{I}}}\textsf{K}^{(w)}\\\
0&\text{else}.\end{cases}$

First, note that this is a valid distribution: its probabilities are trivially
non-negative, and

$\sum_{\textsf{K}\in\bigcup_{w\in\mathcal{W}_{\mathcal{I}}}\textsf{K}^{(w)}}h(\textsf{K})/n=\sum_{\textsf{K}\in\bigcup_{w\in\mathcal{W}_{\mathcal{I}}}\textsf{K}^{(w)}}\sum_{w:\textsf{K}^{(w)}=\textsf{K}}n_{w}/n=\sum_{w\in\mathcal{W}_{\mathcal{I}}}n_{w}/n=1.$

By the above, for all feature vectors in the pool
$w\in\mathcal{W}_{\mathcal{I}}$, the total probability given to that vector
group is bounded as

$n_{w}/n\leq h(\textsf{K}^{(w)})\leq t_{w}(\textsf{d})\leq k.$

Finally, we apply Lemma 2 to transform d into our panel distribution
$\mathbf{d}$ such that $\pi_{i}(\mathbf{d})=t_{w}(\textsf{d})/n_{w}$; it
follows that for this $\mathbf{d}$,

$1/n\leq\pi_{i}(\mathbf{d})\leq k/n_{min}(\mathcal{I})\in
O(1/n_{min}(\mathcal{I}))\qquad\text{for all }i\in[n],$

as needed. ∎

###  B.5. Proof of Theorem 4

###### Proof.

Fix $\mathcal{I},C,\boldsymbol{\tilde{w}}$ as specified in the statement. By
the assumption that $c$ respects Restriction 2.1, we know that
$|C|=c\leq\max\\{n_{min}(\mathcal{I})-k,0\\}$. If $c=0$ based on this
restriction, then the claim is trivially true due to Lemma 5. Thus, we
henceforth assume that $\mathcal{I}$ is such that $c>0$.

Let $\mathcal{K}$ be the set of valid panels in $\mathcal{I}$ and
$\tilde{\mathcal{K}}$ be the set of valid panels in
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$; likewise, let $\mathfrak{K}$ be
the set of valid panel compositions in $\mathcal{I}$, and let
$\tilde{\mathfrak{K}}$ be the set of valid panel compositions in
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$. Finally, fix any $z\in(0,1/n]$.

Approach. Fix the panel distribution $\mathbf{d}\in\Delta(\mathcal{K})$ that
implies selection probability assignment $\boldsymbol{\pi}\in\Pi(\mathcal{I})$
giving all agents selection probability in
$[\Omega(1/n),O(1/n_{min}(\mathcal{I}))]$, which we know to exist by Lemma 5.
Our approach will be to construct a panel distribution
$\tilde{\mathbf{d}}\in\Delta(\mathcal{\tilde{K}})$ from our original panel
distribution $\mathbf{d}$ with the desired properties. We will do this
construction in panel composition space. We begin with Claim 1, which
characterizes the space of valid panel compositions in instance $\mathcal{I}$
versus $\tilde{\mathcal{I}}$.

Claim 1: $\mathfrak{K}\subseteq\tilde{\mathfrak{K}}$ (the set of valid
compositions only grows after $C$ misreports).

Proof of Claim 1. Recall that $\mathcal{W}_{\mathcal{I}}$ describes the unique
feature vectors in the pool in $\mathcal{I}$. By Restriction 2.1, we have that
$c\leq n_{min}(\mathcal{I})-k\leq n_{w}(\mathcal{I})-k$ for all
$w\in\mathcal{W}_{\mathcal{I}}$. This implies that
$n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\geq
n_{w}(\mathcal{I})-c\geq k$ for each $w\in\mathcal{W}_{\mathcal{I}}$. In other
words, there are at least $k$ agents $i$ such that $\tilde{w}_{i}=w$ for all
vectors present in the original instance, meaning that

$\textsf{K}\in\mathfrak{K}\implies\textsf{K}\in\tilde{\mathfrak{K}}.$

(End proof of Claim 1).

While the set of feasible panel compositions could not have shrunk due to $C$
misreporting, it could certainly have grown, as members of $C$ may have
reported vectors not present in $N$. We now partition $C$ into three mutually
exclusive and exhaustive subsets:

  * •

$C_{1}\subseteq C$ contains all $i$ whose feature vector
$\tilde{w}_{i}\notin\mathcal{W}_{\mathcal{I}}$ and is not contained on any
panel composition in $\tilde{\mathfrak{K}}$.

  * •

$C_{2}\subseteq C$ contains all $i$ whose feature vector
$\tilde{w}_{i}\notin\mathcal{W}_{\mathcal{I}}$ (and therefore is not contained
on any panel composition $\textsf{K}\in\mathfrak{K}$), but is contained on
some panel composition
$\textsf{K}\in\tilde{\mathfrak{K}}\setminus\mathfrak{K}$

  * •

$[n]\setminus C_{1}\setminus C_{2}$, which contains only agents with vectors
that were originally present in the original instance (i.e., appeared in
$\boldsymbol{w}$), since
$\mathcal{W}_{\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}}=\mathcal{W}_{\mathcal{I}}\cup\mathcal{W}_{C_{1}}\cup
W_{C_{2}}$ and all sets on the right-hand side are mutually exclusive.

Handling $\boldsymbol{C_{1}}$. By our handling of structural exclusion in
Section 2.2, we know that when given instance
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$, the selection algorithm will
ignore agents in $C_{1}$, meaning that our effective pool size in
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$ is $n-|C_{1}|$. Observe that it
is still the case that $n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\geq
k$ for all $w\in\mathcal{W}_{\mathcal{I}}$ as before, because the number of
agents $i$ with any $\tilde{w}_{i}\in\mathcal{W}_{\mathcal{I}}$ is unaffected
by dropping agents from the manipulated pool with
$\tilde{w}_{i}\notin\mathcal{W}_{\mathcal{I}}$.

Construction of valid panels / panel compositions containing new vectors. For
each $i\in C_{2}$, identify a panel $K^{(i)}\in\tilde{\mathcal{K}}$ such that
$i\in K^{(i)}$ (these panels needs not be unique). Let $Z$ represent the
maximum total number seats reserved for any single vector across all these
panels (counting duplicates with their multiplicity):

$Z:=\max_{w\in W_{\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}}}\ \sum_{i\in
C_{2}}k\cdot\textsf{K}_{w}(K^{(i)}).$

Note that $Z\geq 1$, because each agent $i\in C_{2}$ is given at least one
seat on one panel $K^{(i)}$. Also note that $Z\leq k|C_{2}|$, as we sum over
$|C_{2}|$ panels that can allot at most $k$ seats to any vector.

Now, let $g\colon\bigcup_{i\in
C_{2}}\\{\textsf{K}\left(K^{(i)}\right)\\}\rightarrow\mathbb{N}$ map any given
panel composition we have identified above to the number of agents in $C_{2}$
whose chosen panel has that composition. Formally, it is defined as
$g(\textsf{K})=|\\{i\in C_{2}\colon\textsf{K}(K^{(i)})=\textsf{K}\\}|$. Note
that grouping common panel compositions across the $K^{(i)}$ forms a partition
of $|C_{2}|$ (in which agents with common panel composition are grouped
together). Because $g(\textsf{K})$ represents the number of agents in the
coalition with associated panel composition K, it follows that

$\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\\{\textsf{K}(K^{(i)})\\}}g(\textsf{K})=|C_{2}|\qquad\text{and}\qquad
g(\textsf{K})\leq|C_{2}|\ \ \text{for all }\textsf{K}.$

We have that $Z\geq g(\textsf{K})$ for all K because if there are
$g(\textsf{K})$ many copies of the same panel composition in the
representative panels then there are at least $g(\textsf{K})$ seats reserved
for any given vector on this panel composition.

Construction of $\tilde{\textsf{d}}$. Let d be the panel composition
distribution corresponding to $\mathbf{d}$, transformed via Lemma 3. We will
now construct a new panel composition distribution $\tilde{\textsf{d}}$ from
d. In this construction, we will add our newly feasible panel compositions
constructed above to the support and redistribute some probability mass over
them. Define panel composition distribution $\tilde{\textsf{d}}$ as follows:

$\tilde{\textsf{d}}_{\textsf{K}}:=\begin{cases}\textsf{d}_{\textsf{K}}\cdot\left(1-|C_{2}|z\right)&\text{if
}\textsf{K}\in\mathfrak{K}\\\ z\,g(\textsf{K})&\text{if
}\textsf{K}\in\bigcup_{i\in C_{2}}\\{\textsf{K}(K^{(i)})\\}\\\
0&\text{else}\end{cases}\qquad\text{for all
}\textsf{K}\in\tilde{\mathfrak{K}}.$

Claim 2: $\tilde{\textsf{d}}$ is a well-defined distribution.

Proof of Claim 2. First, note that for every
$\textsf{K}\in\tilde{\mathfrak{K}}$, $\tilde{\textsf{d}}_{\textsf{K}}$ is set
to a single value. This is because the cases are by definition mutually
exclusive: if $\textsf{K}\in\mathfrak{K}$, it cannot be among the panels
compositions $\textsf{K}(K^{(i)})\colon i\in C_{2}$ by definition. Now, we
argue that all entries are in $[0,1]$. First, using that
$g(\textsf{K})\leq|C_{2}|\leq n_{min}$ and $z\leq 1/n$,

$\displaystyle 0\leq z\,g(\textsf{K})\leq z|C_{2}|\leq zn_{min}\leq
n_{min}/n\leq 1.$

Again using that $|C_{2}|\leq c\leq n_{min}$ and $z\leq 1/n$,

$\displaystyle
1\geq\textsf{d}_{\textsf{K}}\geq\textsf{d}_{\textsf{K}}(1-z|C_{2}|)\geq\textsf{d}_{\textsf{K}}(1-zc)\geq\textsf{d}_{\textsf{K}}(1-n_{min}/n)\geq
0.$

Finally, all probabilities in this distribution sum to 1:

$\displaystyle\sum_{\textsf{K}\in\tilde{\mathfrak{K}}}\tilde{\textsf{d}}_{\textsf{K}}$
$\displaystyle=\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\textsf{K}(K^{(i)})}z\,g(\textsf{K})+\sum_{\textsf{K}\in\tilde{\mathfrak{K}}\setminus\bigcup_{i\in
C_{2}}\textsf{K}(K^{(i)})}\textsf{d}_{\textsf{K}}\cdot\left(1-z|C_{2}|\right)$
$\displaystyle=z\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\textsf{K}(K^{(i)})}g(\textsf{K})+\left(1-z|C_{2}|\right)\sum_{\textsf{K}\in\tilde{\mathfrak{K}}\setminus\bigcup_{i\in
C_{2}}\textsf{K}(K^{(i)})}\textsf{d}_{\textsf{K}}$
$\displaystyle=z|C_{2}|+\left(1-z|C_{2}|\right)\cdot 1$ $\displaystyle=1$

(End proof of Claim 2).

Bounding $\textsf{t}_{w}(\tilde{\textsf{d}})$ for all
$w\in\mathcal{W}_{C_{2}}$. We begin by looking at $w\in\mathcal{W}_{C_{2}}$.
We first make some observations about the $g(\textsf{K})$, and in particular
their relationship to sets of agents:

  1. (1)

$n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\leq\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\\{\textsf{K}(K^{(i)})\\}\land\textsf{K}_{w}>0}g(\textsf{K})$ for all
$w\in\mathcal{W}_{C_{2}}$. To see this, note that we can partition agents in
$C_{2}$ according to the panel composition of $K^{(i)}$, the panel we
identified to include them. $g(\textsf{K})$ is then exactly the number of
agents who chose K. Adding up over all panel compositions including vector $w$
will necessarily add 1 per person with vector $w$, since for each such person
there is at least one panel composition containing them whose composition
group they belong to.

  2. (2)

By definition of $g(\textsf{K})$, $g(\textsf{K})z=\sum_{i\in
C_{2}:\textsf{K}(K^{(i)})=\textsf{K}}z$.

Now, we lower bound $t_{w}(\tilde{\textsf{d}})$ for all
$w\in\mathcal{W}_{C_{2}}$. The first inequality comes from applying
observation (1) above, noting that when $\textsf{K}_{w}>0$,
$k\textsf{K}_{w}\geq 1$. The final step uses that $Z\leq k|C_{2}|\leq kc$.

$\displaystyle t_{w}(\tilde{\textsf{d}})$
$\displaystyle=\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\\{\textsf{K}(K^{(i)})\\}}z\,g(\textsf{K})\cdot k\cdot\textsf{K}_{w}\geq
z\,n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\qquad\text{for all
}w\in\mathcal{W}_{C_{2}}.$

Now, to upper bound $\textsf{t}_{w}(\tilde{\textsf{d}})$ for all
$w\in\mathcal{W}_{C_{2}}$, we apply observation (2) above.

$\displaystyle t_{w}(\tilde{\textsf{d}})=\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\\{\textsf{K}(K^{(i)})\\}}z\,g(\textsf{K})\cdot k\cdot\textsf{K}_{w}$
$\displaystyle=z\sum_{\textsf{K}\in\bigcup_{i\in
C_{2}}\\{\textsf{K}(K^{(i)})\\}}\sum_{i\in
C_{2}:\textsf{K}(K^{(i)})=\textsf{K}}k\cdot\textsf{K}_{w}$ We can condense the
sums: the first is over all panel compositions, and the second is over all
$i\in C_{2}$ whose $K^{(i)}$ fits that composition; therefore, this is just
$\displaystyle=z\sum_{i\in C_{2}}k\cdot\textsf{K}_{w}(K^{(i)})$ This sum is by
definition at most $Z$: $\displaystyle\leq zZ$ And finally using that $Z\leq
kc$, $\displaystyle\leq zkc.$

We conclude that for all $w\in\mathcal{W}_{C_{2}}$,

(5)
$\textsf{t}_{w}(\tilde{\textsf{d}})\in\left[zn_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}),\
zkc\right].$

Bounding $\textsf{t}_{w}(\tilde{\textsf{d}})$ for all
$w\in\mathcal{W}_{\mathcal{I}}$. Now, we deduce the following bounds on
$\textsf{t}_{w}(\tilde{\textsf{d}})$ for all $w\in\mathcal{W}_{\mathcal{I}}$.
The lower bound corresponds to the case where $w$ occurs on no panel
compositions in
$\bigcup_{\tilde{w}\in\mathcal{W}_{C_{2}}}\\{\textsf{K}^{(\tilde{w})}\\}$.
Beforehand, recall our assumption that $|\mathcal{W}_{\mathcal{I}}|\geq 2$,
which implies directly that $n_{min}(\mathcal{I})\leq n/2$. Then, using that
$z\in(0,1/n]$ and $c\leq n_{min}\leq n/2$,

(6)
$\textsf{t}_{w}(\tilde{\textsf{d}})\geq(1-|C_{2}|z)\,\textsf{t}_{w}(\textsf{d})\geq(1-n_{min}/n)\,\textsf{t}_{w}(\textsf{d})\geq\textsf{t}_{w}(\textsf{d})/2\geq
n_{w}(\mathcal{I})/(2n)\geq
n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})/(4n).$

Up to the final two steps, we deduce that the total probability given to group
$w$ does not decrease in order from d to $\tilde{\textsf{d}}$. In the
penultimate step, we apply a lower bound on $\textsf{t}_{w}(\textsf{d})$ that
comes from the fact that by Lemma 5, all agents received probability at least
$1/n$ from d, which means that $\textsf{t}_{w}(\textsf{d})\geq
n_{w}(\mathcal{I})/n$. In the last step, we use that
$n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\leq
n_{w}(\mathcal{I})+c\leq 2n_{w}(\mathcal{I})$. The upper bound corresponds to
the case where this vector occurs on all panel compositions to the maximum
possible extent as captured in $Z$. Using that $t_{w}(\textsf{d})\leq k$,
$g(\textsf{K})\leq Z$, and $Z\leq ck$,

$\displaystyle\textsf{t}_{w}(\tilde{\textsf{d}})\leq
t_{w}(\textsf{d})+zg(\textsf{K})n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\leq\textsf{t}_{w}(\textsf{d})+zZ\,n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\leq
k+zck\,n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}).$

We conclude that

(7)
$\textsf{t}_{w}(\tilde{\textsf{d}})\in\left[n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})/(4n),k+kzcn_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\right]\qquad\text{for
all }w\in\mathcal{W}_{\mathcal{I}}.$

Transforming $\tilde{\textsf{d}}$ into our final panel distribution
$\tilde{\mathbf{d}}$. Now, we apply Lemma 2 to transform our panel composition
distribution $\tilde{\textsf{d}}$ into a corresponding panel distribution
$\tilde{\mathbf{d}}$. This lemma shows that for the $\tilde{\boldsymbol{\pi}}$
implied by $\tilde{\mathbf{d}}$, it holds that

$\tilde{\pi}_{i}=\frac{\textsf{t}_{w}(\tilde{\textsf{d}})}{n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})}\qquad\text{for
all }i\in[n]:\tilde{w}_{i}=w,\text{all }w\in\mathcal{W}.$

First, combining Equation 5 and that
$n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\geq 1$ for all $w\in
C_{2}$, we get that

$\displaystyle\tilde{\pi}_{i}$
$\displaystyle\in\left[z,kzc\right]\subseteq[\Omega(z),O(cz)]\qquad$ for all
$i:\tilde{w}_{i}\in\mathcal{W}_{C_{2}}$. Likewise, combining Equation 7 and
that $n_{w}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})\geq
n_{w}(\mathcal{I})-c\geq n_{min}-c$ for all $w\in\mathcal{W}_{\mathcal{I}}$,
$\displaystyle\tilde{\pi}_{i}$ $\displaystyle\in\left[\frac{1}{4n},\
\frac{k}{n_{min}-c}+kzc\right]\subseteq\left[\Omega(1/n),\max\\{cz,1/(n_{min}-c)\\}\right]\qquad$
$\displaystyle\text{for all }i:\tilde{w}_{i}\in\mathcal{W}_{\mathcal{I}}.$

Taking the union of both these ranges to bound the probabilities of all
agents, we conclude the result:

$\tilde{\boldsymbol{\pi}}\in\left[\Omega\left(z\right),O\left(\max\\{cz,1/(n_{min}-c)\\}\right)\right]^{n}.\qed$

##  Appendix C Supplemental Materials for Section 4

###  C.1. Comments on Theorem 1 upper bounds on manipext and manipcomp

First, our upper bound on manipext appears to be tight. To see this, suppose
our truthful instance is the instance in Example 1. Let there be some
coalition $C$ of size $c\in\kappa n_{min}$ for some constant $\kappa>0$ (which
is entirely possible under Restriction 2.1). Suppose every coalition member
has truthful vector $0$ but misreports vector $1$, thereby joining the
smallest group. They have then multiplied the group size by $(1+\kappa)$,
thereby decreasing their members’ probabilities from $1/n_{min}$ to
$1/(n_{min}\cdot(1+\kappa))$ — an additive decrease of the order $1/n_{min}$.

Moving onto manipcomp, one may notice something concerning about our upper
bound: if $c\in\Omega(n^{2/3})$, this bound is constant and could be as large
as $k$, even regardless of $n_{min}$. Conceivably, then, a coalition could
misappropriate the entire panel. We now unpack when this may or may not be of
practical concern.

First, it in fact may be that in practice, the number of agents willing to
misreport grows as $\Omega(n^{2/3})$. It would actually make sense if the
number of manipulators grew linearly in $n$, as this should be true in
expectation: if there is a constant fraction of the population willing to
manipulate, they should compose that same constant fraction of the pool in
expectation. While there may be many manipulators, it seems unlikely that such
a large number of agents would collude — a key feature of our lower bounds
when Problem 2 is the main issue. An approach to pursuing bounds that account
for this overly pessimistic aspect of our model is discussed in Section 7.

Importantly, however, when $n_{min}$ is small and thus Problem 1 is the main
issue, our upper bound’s dependence on $1/n_{min}$ may actually be somewhat
tight, even when $c$ is small and agents do not collude. To see this, consider
again the instance in Example 1; if $c$ agents misreport as discussed above
(which they could easily do independently, as this is just an example of the
manipulation heuristic MU from Section 6), all those agents will then receive
selection probability $1/(n_{min}+c)$, and garner $c/(n_{min}+c)$ total
expected seats originally allocated for agents with the vector 1. This
negative finding is consistent with a theme of the paper: when $n_{min}$ is
small, there is little any algorithm can do about manipulation in the worst
case.

###  C.2. Proof of Theorem 3

###### Proof.

Fix $k,n_{min},c$ in the ranges specified in the statement. Consider the same
truthful instance $\mathcal{I}$ as in the proof of Theorem 3 (Section B.2). We
will construct the coalition almost identically — indeed, it will result in
almost an identical manipulated instance
$\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}}$ except for a net shift of two
agents — but agents will move in slightly different ways in order to maximize
the manipulators’ gains in probability.

Let $C$ be defined to contain $c-2$ agents who have the truthful vector $111$,
an agent $i\in C$ with vector $000$, and an agent $i^{\prime}\in C$ with
vector $110$. To construct $\boldsymbol{\tilde{w}}$, let $\tilde{w}_{i}=111$,
$\tilde{w}_{i^{\prime}}=010$. Now, for two agents $j,j^{\prime}\in C$ such
that $w_{j}=w_{j^{\prime}}=111$, let $\tilde{w}_{j}=000$ and
$\tilde{w}_{j^{\prime}}=110$. Let all remaining agents $q\in
C\setminus\\{i,i^{\prime},j,j^{\prime}\\}$ misreport $\tilde{w}_{q}=100$. The
manipulated pool is almost exactly as it was in the proof of Theorem 3, except
that there are two more agents with 111 and two fewer agents with 100, where

$\tilde{n}_{000}=\tilde{n}_{110}=(n-n_{min})/2,\qquad\tilde{n}_{111}=n_{min}-c+3,\qquad\tilde{n}_{100}=c-4,\qquad\tilde{n}_{010}=1.$

Then, starting from where that proof left off but accounting for our slight
shifts in population, fix any
$\tilde{\boldsymbol{\pi}}\in\Pi(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$;
assuming $\tilde{\boldsymbol{\pi}}$ is anonymous, by Equation 4, we know that
it must imply vector-indexed selection probabilities as follows (defining
$d_{1},d_{2}$ the same way as in the proof of Section B.2):

$\displaystyle\textsf{p}_{000}=\textsf{p}_{110}=\frac{k/2-1-d_{2}}{(n-n_{min})/2},\quad\textsf{p}_{100}=d_{2}\frac{1}{c-4},\quad\textsf{p}_{010}=d_{2},\quad\textsf{p}_{111}=\frac{2}{n_{min}-c+3}.$

To lower-bound how much is gained by the manipulation constructed here, we
must upper bound the probability received by manipulators received in the
original instance $\mathcal{I}$. We will study two manipulators in particular,
$i$ and $i^{\prime}$, because they have misreported the most lucrative
vectors. By the above probabilities, they receive the following probabilities
post-manipulation:

$\tilde{\pi}_{i}=\textsf{p}_{111}=2/(n_{min}-c+3)\qquad\text{and}\qquad\tilde{\pi}_{i^{\prime}}=\textsf{p}_{010}=d_{2}.$

Next, we upper bound $i,i^{\prime}$’s probabilities in $\mathcal{I}$. Fix any
$\boldsymbol{\pi}\in\Pi(\mathcal{I})$. Observe that both $i,i^{\prime}$ belong
to the vector groups $000$ or $110$, both of which are of size
$(n-n_{min})/2$. These groups can be given at most $k/2-1$ seats on any valid
panel, meaning that

$\pi_{i}\leq 2(k/2-1)/(n-n_{min})\qquad\text{and}\qquad\pi_{i^{\prime}}\leq
2(k/2-1)/(n-n_{min}).$

Now, to conclude the proof, fix any $z\in(0,1/n]$, and fix any algorithm A
such that manip-fairness$(\mathcal{I},\textsc{A},c)\in\Omega(z)$. Note that we
have argued so far about generic $\boldsymbol{\pi}\in\Pi(\mathcal{I})$ and
$\tilde{\boldsymbol{\pi}}\in\Pi(\mathcal{I})$ so when we now set
$\boldsymbol{\pi}=\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I})$ and
$\tilde{\boldsymbol{\pi}}=\boldsymbol{\pi}^{\textsc{A}}(\mathcal{I}^{\to_{C}\boldsymbol{\tilde{w}}})$,
all claims above apply to these particular probability allocations.

We deduce that $\textsf{manip-
fairness}(\mathcal{I},\textsc{A},c)\in\Omega(z)\implies\min(\tilde{\boldsymbol{\pi}})\in\Omega(z)\implies\textsf{p}_{100}=d_{2}/(c-4)\in\Omega(z)\iff
d_{2}\in\Omega(cz).$ If $d_{2}\in\Omega(cz)$, then $i$ has gained probability

(8)
$\tilde{\pi}_{i}-\pi_{i}=2/(n_{min}-c+3)-(k-2)/(n-n_{min})\in\Omega\left(1/(n_{min}-c)\right).$

where the difference is non-negative given that $k\geq 2$ and $n_{min}\leq
n/k$ as is by construction. Similarly $i^{\prime}$ has gained

(9)
$\tilde{\pi}_{i^{\prime}}-\pi_{i^{\prime}}=\max\\{0,d_{2}-(k-2)/(n-n_{min})\\}\in\Omega(cz).$

We simplify this term to $\Omega(cz)$ because if $d_{2}\in o(k/n)$ or