# Lotteries for Shared Experiences

May 2022

Nick Arnosti  University of MinnesotaMinneapolisMNUS<EMAIL_ADDRESS>and
Carlos Bonet  Columbia UniversityNew YorkNYUS<EMAIL_ADDRESS>
###### Abstract.

We study a setting where tickets for an experience are allocated by lottery.
Each agent belongs to a group, and a group is successful if and only if its
members receive enough tickets for everyone. A lottery is efficient if it
maximizes the number of agents in successful groups, and fair if it gives
every group the same chance of success. We study the efficiency and fairness
of existing approaches, and propose practical alternatives.

If agents must identify the members of their group, a natural solution is the
Group Lottery, which orders groups uniformly at random and processes them
sequentially. We provide tight bounds on the inefficiency and unfairness of
this mechanism, and describe modifications that obtain a fairer allocation.

If agents may request multiple tickets without identifying members of their
group, the most common mechanism is the Individual Lottery, which orders
agents uniformly at random and awards each their request until no tickets
remain. Because each member of a group may apply for (and win) tickets, this
approach can yield arbitrarily unfair and inefficient outcomes. As an
alternative, we propose the Weighted Individual Lottery, in which the
processing order is biased against agents with large requests. Although it is
still possible to have multiple winners in a group, this simple modification
makes this event much less likely. As a result, the Weighted Individual
Lottery is approximately fair and approximately efficient, and similar to the
Group Lottery when there are many more agents than tickets.

††conference: ; ;

##  1\. Introduction

###  1.1. Motivation

Although matching models often assume that agents care only about their own
allocation, there are many scenarios where people also care about the
allocation received by their friends or family members. For example, couples
entering residency may wish to be matched to programs in the same region,
siblings may wish to attend the same school, and friends may want to share a
hiking trip. Practitioners often employ ad-hoc solutions in an effort to
accommodate these preferences.

This paper studies a special case of this problem, in which there are multiple
copies of a homogeneous good. Each agent belongs to a group, and is successful
if and only if members of her group receive enough copies for everyone in the
group. Examples of such settings include:

  * •

American Diversity Visa Lottery. Each year 55,000 visas are awarded to
citizens of eligible countries. Applicants are selected by lottery.
Recognizing that families want to stay together, the state department grants
visas to eligible family members of selected applicants.111Details of the 2022
Diversity Immigrant Visa Program are available at
https://travel.state.gov/content/dam/visas/Diversity-Visa/DV-Instructions-
Translations/DV-2022-Instructions-Translations/DV-2022-Instructions-and-
FAQs_English.pdf.

  * •

Big Sur Marathon. Many popular marathons limit the number of entrants and use
a lottery to select applicants. The Big Sur Marathon uses several lotteries
for different populations (i.e. locals, first-timers, and returning runners
from previous years). One of these is a “Groups and Couples” lottery which “is
open for groups of from 2-15 individuals, each of whom want to run the Big Sur
Marathon but only if everyone in the group is chosen.” In 2020, 702 tickets
were claimed by 236 successful groups selected from 1296 applicants. 222More
information about the 2020 Big Sur Marathon Drawing is available at
https://www.bigsurmarathon.org/random-drawing-results-for-the-2020-big-sur-
marathon/

  * •

Hiking Permits on Recreation.gov. Many parks use a permit system to limit the
number of hikers on popular trails. For example, the permits to hike Half Dome
in Yosemite National Park are awarded through a pre-season lottery, as well as
daily lotteries.333More information available at
https://www.nps.gov/yose/planyourvisit/hdpermits.htm To enable applicants to
hike with friends and family, each applicant is allowed to apply for up to six
permits.

  * •

Discounted Broadway Tickets. Many popular Broadway shows hold lotteries for
discounted tickets. While some people may be happy going to a Broadway show
alone, most prefer to share the experience with others. Recognizing this fact,
theaters typically allow each applicant to request up to two tickets. On the
morning of the show, winners are selected and given the opportunity to
purchase the number of tickets that they requested.

Inspired by the last application, in the rest of the paper we will refer to a
copy of the homogeneous good as a ‘ticket’.

The settings above present several challenges. First and foremost, the
designer must prevent individuals from submitting multiple applications. In
high-stakes environments such as the diversity visa lottery, this can be
accomplished by asking applicants to provide government identification as part
of their application. In applications with lower stakes, this is frequently
accomplished by tying each application to an e-mail address, phone number, or
social media account. The effectiveness of this approach will vary across
settings. If the designer is concerned that individuals may be submitting
multiple applications, then this concern should be addressed before anything
else. In this paper, we assume that the designer has a way to identify each
individual, and verify that nobody has submitted duplicate applications.

A second challenge is that designers do not know who belongs to each group.
One solution is to ask applicants to identify members of their group in
advance. While this is done for the diversity visa lottery and for affordable
housing lotteries, it can be quite cumbersome. It requires additional effort
from applicants, which may be wasted if their applications are not selected.
In addition, to ensure that applicants do not submit false names, when
awarding tickets the designer must verify that the identity of each recipient
matches the information on the application form. Perhaps for these reasons,
many designers opt for a simpler interface which allows applicants to specify
how many tickets they wish to receive, but does not ask them to name who these
tickets are for.

Motivated by these observations, we study two types of mechanisms: “direct”
mechanisms which ask applicants to identify members of their group, and
mechanisms which only ask each applicant to specify a number of tickets
requested. In the former case, the most natural approach is to place groups in
a uniformly random order, and sequentially allocate tickets until no more
remain. This procedure, which we refer to as the Group Lottery, is used, for
example, to allocate affordable housing in New York City. In the latter case,
an analogous procedure is often used: applicants are processed in a uniformly
random order, with each applicant given the number of tickets that they
requested until no tickets remain. We call this mechanism the Individual
Lottery, and variants of it are used in all of the applications listed
above.444 Recreation.gov goes into great detail about the algorithm used to
generate a uniform random order of applicants
(https://www.recreation.gov/lottery/how-they-work), while the FAQ for the
Diversity Visa Lottery notes, “a married couple may each submit a DV Lottery
application and if either is selected, the other would also be entitled to a
permanent resident card” (https://www.dv-lottery.us/faq/).

###  1.2. Concerns with existing approaches

Although the Individual Lottery and the Group Lottery seem natural and are
used in practice, they each have flaws. In the Individual Lottery, each member
of a group can submit a separate application. This is arguably arguably
unfair, as members of large groups might have a much higher chance of success
than individual applicants. In addition, the Individual Lottery may be
inefficient. One reason for this is that there is no penalty for submitting a
large request, so some individuals may ask for more tickets than their group
needs.555Applicants are very aware of this. One of the authors received an
e-mail from the organizer of a Half Dome trip who noted, “It costs nothing
extra to apply for 6 spots. If you do win, you might as well win big!”
Meanwhile, a guide about the lottery for the Broadway show Hamilton advises,
“You can enter the lottery for either one or two seats. Always enter it for
two. A friend you bring to Hamilton will be a friend for life”
(https://www.timeout.com/newyork/theater/hamilton-lottery). Even if this does
not occur, multiple members of a group might apply and win tickets, resulting
in some of these tickets going to waste.

Anecdotally, we see strong evidence of groups with multiple winners in the Big
Sur Marathon lottery. Although the information page suggests that “a single,
designated group leader enters the drawing on behalf of the group,” in 2019,
the lottery winners included two teams titled “Taylor’s” (with leaders Molly
Taylor and Amber Taylor, respectively), as well as a team titled “What the
Hill?” and another titled “What the Hill?!”666More information about the
drawing can be found at
https://web.archive.org/web/20200407192601/https://www.bigsurmarathon.org/drawing-
info/. The list of groups awarded in 2019 is available at
http://www.bigsurmarathon.org/wp-content/uploads/2018/07/Group-Winners-for-
Website.pdf. These examples suggest that groups are (rationally) not abiding
by the recommendation that only one member enter the lottery, and that some
groups are receiving more tickets than needed.

The instruction that only one member of each group should apply to the Big Sur
Marathon lottery suggests that the organizers intended to implement a Group
Lottery. Although the Group Lottery overcomes some of the issues described
above, it is also not perfectly fair nor perfectly efficient. This is because
when only a few tickets remain, (i) small groups still have a chance of
success while large groups do not, and (ii) these tickets may be wasted if the
next group to be processed is large. Because these issues arise only at the
end of the allocation process, one might hope that the resulting allocation
will not be too unfair or inefficient.

Our first contribution is to quantify the unfairness and inefficiency of these
mechanisms. While the fairness and efficiency of the Individual Lottery suffer
when everyone from a group applies, how bad can the problem be? And is the
intuition that the Group Lottery is approximately fair and efficient correct?
Our answers to these questions are “very bad”, and “yes,” respectively.
Although neither mechanism is perfectly fair or efficient, there is a large
qualitative and quantitative difference between them. Our second contribution
is to identify modifications to each algorithm which use the same user
interfaces but offer improved fairness and/or efficiency. We elaborate on
these contributions below.

###  1.3. Overview of Model and Results

We consider a model with $k$ identical tickets. The set of agents is
partitioned into a set of groups, and agents have dichotomous preferences: an
agent is successful if and only if members of her group receive enough tickets
for everyone in the group. We treat the group structure as private
information, unknown to the designer. Because there are only $k$ tickets,
there can be at most $k$ successful agents. We define the efficiency of a
lottery allocation to be the expected number of successful agents, divided by
$k$. If this is at least $\beta$, then the allocation is $\beta$-efficient. A
lottery allocation is fair if each agent has the same success probability, and
$\beta$-fair if for any pair of agents, the ratio of their success
probabilities is at least $\beta$.

Given these definitions, we seek lottery allocations that are both
approximately efficient and approximately fair. Although this may be
unattainable if groups are large, in many cases group sizes are much smaller
than the total number of tickets. We define a family of instances
characterized by two parameters, $\kappa$ and $\alpha$. The parameter $\kappa$
bounds the ratio of group size to total number of tickets, while $\alpha$
bounds the supply-demand ratio. For any $\kappa$ and $\alpha$, we provide
worst-case performance guarantees in terms of efficiency and fairness.

We first consider a scenario where applicants can identify each member of
their group. Here, the mechanism typically used is the Group Lottery. We show
in Proposition 2 that this mechanism incentivizes agents to truthfully report
their groups. Moreover, Theorem 3 establishes that the Group Lottery is
$(1-\kappa)$-efficient and $(1-2\kappa)$-fair. It is not perfectly efficient,
as tickets might be wasted if the size of the group being processed exceeds
the number of remaining tickets. It is not perfectly fair, since once only a
few tickets remain, a large group can no longer be successful, but a small
group can. Proposition 3 shows that this guarantee is tight.

Could there be a mechanism with stronger performance guarantees than the Group
Lottery? Proposition 6 establishes the limits of what can be achieved.
Specifically, it says that there always exists an allocation $\pi$ that is
$(1-\kappa)$-efficient and fair, but for any $\epsilon>0$, there are examples
where any allocation that is $(1-\kappa+\epsilon)$-efficient is not even
$\epsilon$-fair. To show the existence of the random allocation $\pi$, we use
a generalization of the Birkhoff-von Neumann theorem proved by Nguyen et al.
(2016). By awarding groups according to the allocation $\pi$, we can obtain a
mechanism that attains the best possible performance guarantees. Therefore,
the $2\kappa$ loss in fairness in the Group Lottery can be thought of as the
“cost” of using a simple procedure that orders groups uniformly, rather than
employing a Birkhoff-von Neumann decomposition to generate the allocation
$\pi$.

In many applications, developing an interface that allows applicants to list
their group members may be too cumbersome. This motivates the study of a
second scenario, where applicants are only allowed to specify the number of
tickets they need. The natural mechanism in this setting is the Individual
Lottery. Unfortunately, Theorem 10 establishes that the Individual Lottery may
lead to arbitrarily inefficient and unfair outcomes. It is perhaps not
surprising that the Individual Lottery will be inefficient if agents request
more tickets than needed, or if each agent has a large chance of success.
However, we show that the waste due to over-allocation may be severe even if
all agents request only their group size and demand far exceeds supply.
Furthermore, because the probability of success will be roughly proportional
to group size, small groups are at a significant disadvantage.

Can we achieve approximate efficiency and fairness without asking applicants
to identify each member of their group? We show that this is possible with a
minor modification to the Individual Lottery which gives applicants with
larger requests a lower chance of being allocated. This eliminates the
incentive to inflate demand, and reduces the possibility of multiple winners
from the same group. To make the allocation fair, we choose a particular
method for biasing the lottery against large requests: sequentially select
individuals with probability inversely proportional to their request. We call
this approach the Weighted Individual Lottery. In the Weighted Individual
Lottery, a group of four individuals who each request four tickets has the
same chance of being drawn next as a group of two individuals who each request
two tickets. As a result, outcomes are similar to the Group Lottery. We prove
that the Weighted Individual Lottery is ($1-\kappa-\alpha/2$)-efficient and
($1-2\kappa-\alpha/2$)-fair (in fact, Theorem 16 establishes slightly stronger
guarantees). Notice that these guarantees coincide with those of the Group
Lottery when demand far exceeds supply ($\alpha$ is close to $0$).

Our main results are summarized in Table 1. Our conclusion is that the
Individual Lottery can be arbitrarily unfair and inefficient. These
deficiencies can be mostly eliminated by using a Group Lottery. Perhaps more
surprisingly, approximate efficiency and fairness can also be achieved while
maintaining the Individual Lottery interface, by suitably biasing the lottery
against agents with large requests.

Mechanism | Action Set | Efficiency | Fairness
---|---|---|---
Benchmark |  | $1-\kappa$ | 1
Group Lottery | $2^{\mathcal{N}}$ | $1-\kappa$ | $1-2\kappa$
Individual Lottery | $\\{1,2,\ldots,k\\}$ | 0 | 0
Weighted Individual Lottery | $\\{1,2,\ldots,k\\}$ | $1-\kappa-\alpha/2$ | $1-2\kappa-\alpha/2$
Table 1. Summary of main results: worst-case guarantees for the efficiency and
fairness of instances in $I(\kappa,\alpha)$. These guarantees are established
in Theorems 3, 10 and 16. Meanwhile, Proposition 6 establishes that the best
one can hope for is a mechanism that is $(1-\kappa)$ efficient and $1$-fair.

##  2\. Related work

Our high-level goal of allocating objects efficiently, subject to fairness and
incentive compatibility constraints, is shared by numerous papers. The
definitions of efficiency, fairness, and incentive compatibility differ
significantly across settings, and below, we focus on papers that are closely
related to our own.

If the group structure is known to the designer, then our problem simplifies
to allocating copies of a homogeneous item to groups with multi-unit demand.
This problem has received significant attention. Benassy (1982) introduces the
uniform allocation rule, in which each group requests a number of copies, and
receives the minimum of its request and a quantity $q$, which is chosen so
that every copy is allocated. Sprumont (1991) and Ching (1992) show that when
preferences are single-peaked, this is the unique rule that is Pareto
efficient, envy-free, and incentive compatible. Ehlers and Klaus (2003) extend
this characterization to randomized allocation mechanisms. Cachon and
Lariviere (1999) consider the uniform allocation rule in a setting where
groups have decreasing marginal returns from additional items.

In contrast to these papers, we assume that groups have dichotomous
preferences, with no value for receiving only a fraction of their request. As
a result, uniform allocation would be extremely inefficient. Instead, we
propose the Group Lottery, which resembles the “lexicographic” allocation rule
from Cachon and Lariviere (1999). Dichotomous preferences have also been used
to model preferences in kidney exchange (Roth et al., 2005), two-sided
matching markets (Bogomolnaia and Moulin, 2004), and collective choice
problems (Bogomolnaia et al., 2005).

The all-or-nothing nature of preferences means that our work is related to the
“fair knapsack” problem introduced by Patel et al. (2020), where a planner
must choose a subset of groups to allocate, subject to a resource constraint.
Groups are placed into categories, and the number of successful groups from
each category must fall into specified ranges. Their model is fairly general,
and if groups are categorized by size, then ranges can be chosen to make their
fairness notion similar to ours. However, they do not quantify the cost of
imposing fairness constraints. By contrast, we show that in our setting,
fairness can be imposed with little or no cost to efficiency. Furthermore,
approximate efficiency and fairness can be achieved in our setting using
mechanisms that are much simpler than their dynamic-programming based
algorithms.

Closer to our work is that of Nguyen et al. (2016). They consider a setting in
which each group has complex preferences over bundles of heterogeneous items,
but only wants a small fraction of the total number of items. They find
approximately efficient and fair allocations using a generalization of the
Birkhoff-von Neumann theorem. Although their notion of fairness is different
from ours, we use their results to prove Proposition 6. However, our papers
have different goals: their work identifies near-optimal but complex
allocation rules, while we study the performance of simple mechanisms deployed
in practice, and close variants of these mechanisms.

An important difference between all of the aforementioned papers and our own
is that we assume that the group structure is unknown to the designer. In
theory, this can be solved by asking agents to identify the members of their
group (as in the Group Lottery), but in many contexts this may be impractical.
Hence, much of our analysis considers a scenario where agents are asked to
report only a single integer (interpreted as the size of their group). We show
what can be achieved is this setting, through our analysis of the Individual
Lottery and Weighted Individual Lottery. We are unaware of any prior work with
related results.

We close by highlighting two papers with results that are used in our
analysis. Serfling (1974) introduces the martingale when sampling without
replacement from a finite population. This martingale is key in the proof of
Proposition 5, which establishes bounds on the expected hitting time for the
sample sum. This, in turn, is used to establish our fairness result for the
Group Lottery. Johnson et al. (2005) state a simple bound on the probability
that a Poisson random variable deviates from its expectation at least by a
given number. We use this result in our analysis of the Weighted Individual
Lottery, where we use a Poisson random variable to bound the probability that
a group has at least $r$ members awarded.

##  3\. The model

###  3.1. Agents, Outcomes, Utilities

A designer must allocate $k\in\mathbb{N}$ indivisible identical tickets to a
set of agents $\mathcal{N}=\\{1,...,n\\}$. A _feasible allocation_ is
represented by $x\in\\{0,1,...,k\\}^{n}$ satisfying
$\sum_{i\in\mathcal{N}}x_{i}\leq k$, where $x_{i}$ indicates the number of
tickets that agent $i$ receives. We let $\mathcal{X}$ be the set of all
feasible allocations.

A lottery allocation is a probability distribution $\pi$ over $\mathcal{X}$,
with $\pi_{x}$ denoting the probability of allocation $x$. Let
$\Delta(\mathcal{X})$ be the set of all lottery allocations.

The set $\mathcal{N}$ is partitioned into groups according to $\mathcal{G}$:
that is, each $G\in\mathcal{G}$ is a subset of $\mathcal{N}$,
$\cup_{G\in\mathcal{G}}G=\mathcal{N}$, and for each
$G,G^{\prime}\in\mathcal{G}$ either $G=G^{\prime}$ or $G\cap
G^{\prime}=\emptyset$. Given agent $i\in\mathcal{N}$, we let
$G_{i}\in\mathcal{G}$ be the group containing $i$. Agents are successful if
and only if the total number of tickets allocated to the members of their
group is at least its cardinality. Formally, each $i\in\mathcal{N}$ is endowed
with a utility function $u_{i}:\mathcal{X}\to\\{0,1\\}$ given by

(1) $u_{i}(x)=\mathbf{1}\left\\{\sum_{j\in G_{i}}x_{j}\geq|G_{i}|\right\\}.$

We say that agent $i$ is successful under allocation $x$ if $u_{i}(x)=1$.

In a slight abuse of notation, we denote the expected utility of agent
$i\in\mathcal{N}$ under the lottery allocation $\pi$ by

(2) $u_{i}(\pi)=\sum_{x\in\mathcal{X}}\pi_{x}u_{i}(x).$

###  3.2. Performance Criteria

We define the expected utilization of a lottery allocation $\pi$ to be

(3) $U(\pi)=\frac{1}{k}\sum_{i\in\mathcal{N}}u_{i}(\pi).$

###### Definition 0 (Efficiency).

A lottery allocation $\pi$ is efficient if $U(\pi)=1.$ It is $\beta$-efficient
if $U(\pi)\geq\beta$.

###### Definition 0 (Fairness).

A lottery allocation $\pi$ is fair if for every $i,i^{\prime}\in\mathcal{N},$
$u_{i}(\pi)=u_{i^{\prime}}(\pi)$. It is $\beta$-fair if for every
$i,i^{\prime}\in\mathcal{N}$, $u_{i}(\pi)\geq\beta u_{i^{\prime}}(\pi)$.

#### Alternative Definitions of Fairness.

With dichotomous preferences, our notion of efficiency seems quite natural.
Our fairness definition states that agents in groups of different sizes should
have similar expected utilities. There are other notions of fairness that one
might consider. Two that arise in other contexts are equal treatment of equals
and envy-free. Below we present the natural analog of these in our setting,
and discuss their relation to our definition.

###### Definition 0.

Lottery allocation $\pi$ satisfies equal treatment of equals if for every pair
of agents $i,j$ such that $|G_{i}|=|G_{j}|$, we have $u_{i}(\pi)=u_{j}(\pi)$.

This is clearly weaker than our fairness definition, and is an easy property
to satisfy. In particular, the group request outcomes of the three mechanisms
we study all satisfy equal treatment of equals.

To define envy-freeness, we introduce additional notation. For any
$x\in\mathcal{X}$, we let $N_{G}(x)$ be the number of tickets allocated to
members of $G$. For any $\pi\in\Delta(\mathcal{X})$, let $N_{G}(\pi)$ be a
random variable representing this number. Let $u_{G}(N)=\mathbb{P}(N\geq|G|)$
be the expected utility of $G$ when the number of tickets received by members
of $G$ is equal to $N$.

###### Definition 0.

Lottery allocation $\pi$ is group envy-free if no group envies the allocation
of another: $u_{G}(N_{G}(\pi))\geq u_{G}(N_{G^{\prime}}(\pi))$ for all
$G,G^{\prime}\in\mathcal{G}$.

This notion is neither stronger nor weaker than our fairness definition. To
see this, suppose that there is a group of size $1$ and another of size $2$.
The group of size $1$ gets one ticket with probability $\epsilon$, and
otherwise gets zero tickets. The group of size $2$ gets two tickets with
probability $\epsilon$ and otherwise gets one ticket. This is fair (according
to our definition) but not even approximately group envy-free. Conversely, if
both groups get one ticket with probability $\epsilon$ and zero tickets
otherwise, then the allocation is group envy-free but not fair.

However, the conclusions we draw would also hold for this new fairness notion.
The group request outcome of the Individual Lottery may not be even
approximately group envy-free. The group request outcome of the Group Lottery
is group envy-free. The group request outcome of the Weighted Individual
Lottery is approximately group envy-free, with the same approximation factor
as in Theorem 16.

###  3.3. Actions and Equilibria

The designer can identify each agent (and therefore prevent agents from
applying multiple times), but does not know the group structure a priori.
Therefore, the designer must deploy a mechanism that asks individual agents to
take actions. When studying incentives induced by a mechanism, however, we
assume that members of a group can coordinate their actions.

Formally an anonymous mechanism consists of an action set $A$ and an
allocation function $\pi:A^{\mathcal{N}}\rightarrow\Delta(\mathcal{X})$, which
specifies a lottery allocation $\pi({\bf a})$ for each possible action profile
${\bf a}\in A^{\mathcal{N}}$.

###### Definition 0.

The actions ${\bf a}_{G_{i}}\in A^{G_{i}}$ are dominant for group $G_{i}$ if
for any actions ${\bf a}_{-G_{i}}\in A^{\mathcal{N}\backslash G_{i}}$,

(4) ${\bf a}_{G_{i}}\in\arg\max_{{\bf a}^{\prime}_{G_{i}}\in
A^{G_{i}}}u_{i}(\pi({\bf a}^{\prime}_{G_{i}},{\bf a}_{-G_{i}})).$

The action profile ${\bf a}\in A^{\mathcal{N}}$ is a dominant strategy
equilibrium if for each group $G\in\mathcal{G}$, actions ${\bf a}_{G}$ are
dominant for $G$.

Note that although actions are taken by individual agents, our definition of
dominant strategies allows all group members to simultaneously modify their
actions. We believe that this reasonably captures many settings, where group
members can coordinate but the mechanism designer has no way to identify
groups a priori.

##  4\. Results

In general, it might not be feasible to achieve approximate efficiency, even
if the group structure is known. Finding an efficient allocation involves
solving a knapsack problem where each item represents a group, and the
knapsack’s capacity is the total number of tickets. If it is not possible to
select a set of groups whose sizes sum up to the number of tickets, then some
tickets will always be wasted. This issue can be particularly severe if
groups’ sizes are large relative to the total number of tickets. Therefore,
one important statistic will be the ratio of the maximum group size to the
total number of tickets.

Additionally, one concern with the Individual Lottery is that tickets might be
wasted if groups have multiple winners. Intuitively, this is more likely when
the number of tickets is close to the number of agents. Therefore, a second
important statistic will be the ratio of tickets to agents.

These thoughts motivate us to define a family of instances characterized by
two parameters: $I(\kappa,\alpha)$. The parameter $\kappa$ captures the
significance of the “knapsack” structure, and $\alpha$ captures the
“abundance” of the good. For any $\kappa,\alpha\in(0,1)$, define the family of
instances

(5)
$I(\kappa,\alpha)=\left\\{(n,k,\mathcal{G}):\frac{\max_{G\in\mathcal{G}}|G|-1}{k}\leq\kappa,\frac{k}{n}\leq\alpha\right\\}.$

Therefore, when analyzing a mechanism we study the worst-case efficiency and
fairness guarantees in terms of $\kappa$ and $\alpha$. Ideally, we might hope
for a solution that is both approximately fair and approximately efficient.
Theorem 3 shows that this is achieved by the Group Lottery, which asks agents
to reveal their groups. By contrast, Theorem 10 establishes that the
Individual Lottery may lead to arbitrarily inefficient and unfair outcomes.
Finally, Theorem 16 establishes that the Weighted Individual Lottery is
approximately fair and approximately efficient, and similar to the Group
Lottery when there are many more agents than tickets ($\alpha$ is small).

###  4.1. Group Lottery

In this section, we present the Group Lottery ($GL$) and show that it is
approximately fair and approximately efficient. In this mechanism, each agent
is asked to report a subset of agents, interpreted as their group. We say that
a group $S\subseteq\mathcal{N}$ is valid if all its members declared the group
$S$. Valid groups are placed in a uniformly random order and processed
sequentially (agents that are not part of a valid group will not receive
tickets). When a group is processed, if enough tickets remain then every
member of the group is given one ticket. Otherwise, members of the group
receive no tickets and the lottery ends.777There is a natural variant of this
mechanism which skips over large groups when few tickets remain, and gives
these tickets to the next group whose request can be accommodated. This
variant may be arbitrarily unfair, as can be seen by considering an example
with an odd number of tickets, one individual applicant, and many couples.
Then the individual applicant is always successful, while the success rate of
couples can be made arbitrarily small by increasing the number of couples.

We now introduce notation that allows us to study this mechanism. For any
finite set $E$, we let $\mathcal{S}_{E}$ be the set of finite sequences of
elements of $E$, and let $\mathcal{O}_{E}$ be the set of sequences such that
each element of $E$ appears exactly once. We refer to an element
$\sigma\in\mathcal{O}_{E}$ as an order over $E$, with $\sigma_{t}\in E$ and
$\sigma_{[t]}=\bigcup_{t^{\prime}\leq t}\sigma_{t^{\prime}}$ denoting the
subset of $E$ that appears in the first $t$ positions of $\sigma$.

Next we provide a formal description of the mechanism. The action set is the
power set of $\mathcal{N}$. Given an action profile ${\bf a}$, we call a set
of agents $S\subseteq\mathcal{N}$ a valid group if for every agent $i\in S$ we
have that $a_{i}=S$. We define a function $\tau$ that will let us to
characterize the number of valid groups that obtain their full request. Fix a
finite set $E$ and a size function $|\cdot|:E\rightarrow\mathbb{N}$. For any
$c\in\mathbb{N}$ and $\sigma\in\mathcal{S}_{E}$ satisfying
$\sum_{t}|\sigma_{t}|\geq c$, define

(6)
$\tau(c,{\sigma})=\min\left\\{T\in\mathbb{N}:\sum_{t=1}^{T}|{\sigma}_{t}|\geq
c\right\\}.$

Fix an arbitrary action profile ${\bf a}$ and let $V$ be the resulting set of
valid groups. For any order ${\sigma}\in\mathcal{O}_{V}$, we let
$\tau=\tau(k+1,{\sigma})$ be as in (6) where the size of each valid group is
its cardinality. Then the number of valid groups that are processed and obtain
their full request is $\tau-1$. We define

(7) $x^{GL}_{i}({\bf
a},\sigma)=\sum_{j=1}^{\tau-1}\mathbf{1}\left\\{i\in\sigma_{j}\right\\}.$

For any $x^{\prime}\in\mathcal{X}$, the allocation function of the Group
Lottery is

$\pi^{GL}_{x^{\prime}}({\bf
a})=\sum_{{\sigma}\in\mathcal{O}_{V}}\mathbf{1}\left\\{x^{\prime}=x^{GL}({\bf
a},{\sigma})\right\\}\frac{1}{|V|!}.$

####  4.1.1. Incentives.

In every mechanism that we study, there is one strategy that intuitively
corresponds to truthful behavior. We refer to this as the _group request
strategy_. In the Group Lottery, this is the strategy in which each agent
declares the members his or her group.

###### Definition 0.

In the Group Lottery, group $G\in\mathcal{G}$ follows the group request
strategy if $a_{i}=G$ for all $i\in G$.

###### Proposition 0.

In the Group Lottery, the group request strategy is the only dominant
strategy.

The intuition behind Proposition 2 is as follows. Potential deviations for
group $G$ include splitting into two or more groups, or naming somebody
outside of the group as a member. We argue that in both cases the group
request is weakly better. First, neither approach will decrease the number of
other valid groups. Second, if there are at least $|G|$ tickets remaining and
a valid group containing a member of $G$ is processed, then under the group
request $G$ gets a payoff of 1. This might not be true under the alternatives
strategies.

In light of Proposition 2, we will assume that groups follow the group request
strategy when analyzing the performance of the Group Lottery.

####  4.1.2. Performance.

We next argue that the Group Lottery is approximately fair and approximately
efficient. Of course, the Group Lottery is not perfectly efficient, as it
solves a packing problem greedily, resulting in an allocation that does not
maximize utilization. Similarly, it is not perfectly fair, as once there are
only a few tickets left, small groups still have a chance of being allocated
but large groups do not. Thus, in the Group Lottery smaller groups are always
weakly better than larger groups. This is formally stated in Lemma 2 located
in Appendix A.

###### Theorem 3 (“GL is Good”).

Fix $\kappa,\alpha\in(0,1)$. For every instance in $I(\kappa,\alpha)$, the
group request equilibrium outcome of the Group Lottery is
$(1-\kappa)$-efficient and $(1-2\kappa)$-fair.

In Proposition 3 (located in Appendix A), we construct instances where the
fairness of the Group Lottery is arbitrarily close to the guarantee provided
in Theorem 3. These instances are fairly natural: groups all have size one or
two, and the total number of tickets is odd. These conditions are met by the
Hamilton Lottery, which we discuss in Section 5.

####  4.1.3. Proof Sketch of Theorem 3.

The efficiency guarantee is based on the fact that for any order over groups,
the number of tickets wasted can be at most $\max_{G}|G|-1$. Therefore, the
tight lower bound on efficiency of the group lottery is
$1-\frac{\max_{G}|G|-1}{k}\geq 1-\kappa$.

We now turn to the the fairness guarantee. We will show that for any pair of
agent $i,j$,

(8) $\frac{u_{i}(\pi^{GL}({\bf a}))}{u_{j}(\pi^{GL}({\bf
a}))}\geq(1-2\kappa).$

Because all groups are following the group request strategy, the set of valid
groups is $\mathcal{G}$. Fix an arbitrary agent $i$. We construct a uniform
random order over $\mathcal{G}$ using Algorithm 2: first generate a uniform
random order ${\Sigma}^{-i}$ over $\mathcal{G}\setminus G_{i}$, and then
extend it to $\mathcal{G}$ by uniformly inserting $G_{i}$ in ${\Sigma}^{-i}$.
Moreover, if groups in $\mathcal{G}\setminus G_{i}$ are processed according
${\Sigma}^{-i}$, then $\tau(k-|G_{i}|+1,{\Sigma}^{-i})$ represents the last
step in which at least $|G_{i}|$ tickets remains available. Therefore, if
$G_{i}$ is inserted in the first $\tau(k-|G_{i}|+1,{\Sigma}^{-i})$ positions
it will get a payoff of $1$. This is formalized in the next lemma.

###### Lemma 0.

For any instance in $I(\kappa,\alpha)$ and any agent $i$, if we let ${\bf a}$
be the group request strategy under the Group Lottery and ${\Sigma}^{-i}$ be a
uniform order over $\mathcal{G}\setminus G_{i}$, then

(9) $u_{i}(\pi^{GL}({\bf
a}))=\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{m}\leq\frac{k}{n}\left(1+\kappa\right),$

where $\tau(k-|G_{i}|+1,{\Sigma}^{-i})$ is as in (6) using the cardinality of
each group as the size function.

Lemma 2 in Appendix A states that if two groups are selecting the group
request strategy under the Group Lottery, then the utility of the smaller
group will be at least the utility of the larger group. Therefore, we assume
without loss of generality that $|G_{i}|\geq|G_{j}|$. From Lemma 4, it follows
that

(10) $\displaystyle\frac{u_{i}(\pi^{GL}({\bf a}))}{u_{j}(\pi^{GL}({\bf a}))}$
$\displaystyle=\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-j})]}\geq\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-i})]}.$

To complete the proof, we express the denominator on the right hand side as
the sum of the numerator and the difference

$\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-i})]-\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})],$

which reflects the advantage of the small group $G_{j}$. We bound this ratio
by taking a lower bound on the numerator
$\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]$ and an upper bound on the
difference
$\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-i})]-\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]$.
Both bounds follow from the lemma below.

###### Proposition 0.

Given a sequence of numbers $\\{a_{1},\ldots,a_{n}\\}$ such that $a_{t}\geq
1$, define $\mu=\sum_{i}a_{i}/n$ and $\bar{a}=\max a_{i}$. Let ${\sigma}$ be
an order over $\\{1,\ldots,n\\}$. For $k\in\\{1,\ldots,\sum_{i}a_{i}\\}$, we
let $\tau=\tau(k,{\sigma})$ be as in (6) where the size of $i$ is $a_{i}$,
that is, $|{\sigma}_{t}|=a_{{\sigma}_{t}}$. If ${\Sigma}$ is a uniform random
order of $\\{1,\ldots,n\\}$, then

(11)
$1+\frac{k-\bar{a}}{\mu}\leq\mathbb{E}[\tau(k,{\Sigma})]\leq\frac{k+\bar{a}-1}{\mu}.$

Furthermore, if $k,k^{\prime}\in\mathbb{N}$ are such that
$k+k^{\prime}\leq\sum_{i}a_{i}$ then

(12)
$\mathbb{E}[\tau(k^{\prime},{\Sigma})]+\mathbb{E}[\tau(k,{\Sigma})]\geq\mathbb{E}[\tau(k^{\prime}+k,{\Sigma})].$

Equation (11) establishes that the expected time to reach $k$ is approximately
$k$ divided by the average size $\mu$, while (12) establishes that hitting
times are sub-additive. Both results are well known when the values
$a_{{\Sigma}_{t}}$ are sampled with replacement from
$\\{a_{1},\ldots,a_{n}\\}$. Proposition 5 establishes the corresponding
results when values are sampled without replacement. The proof of (11) employs
a martingale presented in Serfling (1974), while the proof of (12) uses a
clever coupling argument.888We thank Matt Weinberg for suggesting the
appropriate coupling. Although both statements are intuitive, we have not seen
them proven elsewhere, and we view Proposition 5 as a statement whose
importance extends beyond the setting in which we deploy it.

####  4.1.4. A Fair Group Lottery.

Theorem 3 establishes that the Group Lottery has strong performance
guarantees. However, this mechanism is not perfectly fair, as small groups
have an advantage over large groups, nor perfectly efficient, as the last few
tickets might be wasted. It is natural to ask whether there exists a mechanism
that overcomes these issues. Proposition 6 shows that the best we can hope for
is a mechanism that is $(1-\kappa)$-efficient and fair. We then describe a
fairer version of the Group Lottery which attains these performance
guarantees. We conclude with a discussion of advantages and disadvantages of
this fair Group Lottery.

###### Proposition 0.

  1. (1)

Fix $\kappa,\alpha\in(0,1)$. For every instance in $I(\kappa,\alpha)$, there
exist a random allocation that is $(1-\kappa)$-efficient and fair.

  2. (2)

For any $\epsilon>0$, there exists $\kappa,\alpha\in(0,1)$ and an instance in
$I(\kappa,\alpha)$ such that no random allocation is
$(1-\kappa+\epsilon)$-efficient and $\epsilon$-fair.

The first statement follows from a result in Nguyen et al. (2016), which
implies that any utility vector such that (i) the sum of all agents’ utilities
is at most $k-\max_{G\in\mathcal{G}}|G|+1$, and (ii) members of the same group
have identical utility, can be induced by a lottery over feasible allocations.
To prove the second part of Proposition 6, we construct an instance where a
particular group must be awarded in order to avoid wasting a fraction $\kappa$
of the tickets. Therefore, to improve beyond $(1-\kappa)$-efficiency it is
necessary to allocate that group more frequently. The complete proof of
Proposition 6 is located in Appendix A.3.

Proposition 6 establishes that the best guarantee we can hope for is a
mechanism that is $(1-\kappa)$-efficient and fair. In fact, this can be
achieved by first asking agents to identify their groups (as in the Group
Lottery), and then allocating according to the random allocation referred to
in the first part of Proposition 6. When using this mechanism, it is dominant
for a group to truthfully report its members, as long as it can not influence
the total number of tickets awarded. In the following discussion, we refer to
this mechanism as the _Fair Group Lottery_.

To conclude this section, we discuss the trade-offs between the Fair Group
Lottery and the Group Lottery. In light of its stronger performance
guarantees, one might conclude that the Fair Group Lottery is superior.
However, we think that there are several practical reasons to favor the
standard Group Lottery. First, the computation of the Fair Group Lottery
outcome is not trivial: Nguyen et al. (2016) give two procedures, one which
they acknowledge might be “impractical for large markets,” and the other which
returns only an approximately fair allocation. By contrast, the Group Lottery
is simple to implement in code, and can even be run physically by writing
applicants’ names on ping-pong balls or slips of paper. In some settings, a
physical implementation that allows applicants to witness the process may
increase their level of trust in the system. Even when implemented digitally,
the ability to explain the procedure to applicants may provide similar
benefits.

A final benefit of the Group Lottery is that it provides natural robustness.
Although we assume that the number of tickets is known in advance and that all
successful applicants claim their tickets, either assumption may fail to hold
in practice. When using the Group Lottery, if additional tickets become
available after the initial allocation, they can be allocated by continuing
down the list of groups. This intuitive policy preserves the fairness and
efficiency guarantees from Theorem 3. By contrast, if tickets allocated by the
Fair Group Lottery go unclaimed, there is no obvious “next group” to offer
them to, and any approach will likely violate the efficiency and fairness
guarantees that this mechanism purports to provide.

For these reasons, we see the Group Lottery as a good practical solution in
most cases: the $2\kappa$ loss of fairness identified in Theorem 3 seems a
modest price to pay for the benefits outlined above. There is a loose analogy
to be drawn between the Fair Group Lottery and the Vickrey auction: although
the Vickrey auction is purportedly optimal, practical considerations outside
of the standard model prevent it from being widely deployed (Ausubel et al.,
2006). Similarly, a Fair Group Lottery is only likely to be used in settings
satisfying several specific criteria: the institution running the lottery is
both sophisticated and trusted, fairness is a primary concern, and applicants
are unlikely to renege.

###  4.2. Individual Lottery

As noted in the introduction, asking for (and verifying) the identity of each
participant may prove cumbersome. In this section we consider the widely-used
Individual Lottery, in which the action set is $A=\\{1,\ldots,k\\}$.999In
practice, agents are often limited to asking for $\ell<k$ tickets. We refer to
this mechanism as the Individual Lottery with limit $\ell$, and discuss it
briefly at the end of the section. Appendix B provides a complete analysis of
this mechanism, and demonstrates that like the Individual Lottery without a
limit, it can be arbitrarily unfair and inefficient. Agents are placed in a
uniformly random order and processed sequentially. Each agent is given a
number of tickets equal to the minimum of their request and the number of
remaining tickets.101010As for the Group Lottery, one might imagine using a
variant in which agents whose request exceeds the number of remaining tickets
are skipped. The negative results in Theorem 10 would still hold when using
this variant.

More formally, given an action profile ${\bf a}\in A^{\mathcal{N}}$ and an
order over agents $\sigma\in\mathcal{O}_{\mathcal{N}}$, we let $x^{IL}({\bf
a},\sigma)\in\mathcal{X}$ be the feasible allocation generated by the
Individual Lottery:

(13) $x^{IL}_{\sigma_{t}}({\bf
a},\sigma)=\min\left\\{a_{\sigma_{t}},\max\left\\{k-\sum_{i\in\sigma_{[t-1]}}a_{i},0\right\\}\right\\},$

for $t\in\\{1,\ldots,n\\}$. For any $x^{\prime}\in\mathcal{X}$, the allocation
function of the Individual Lottery is

$\pi^{IL}_{x^{\prime}}({\bf
a})=\frac{1}{n!}\sum_{{\sigma}\in\mathcal{O}_{\mathcal{N}}}\mathbf{1}\left\\{x^{\prime}=x^{IL}({\bf
a},{\sigma})\right\\}.$

####  4.2.1. Incentives.

As in the Group Lottery, we refer to the strategy that correspond to truthful
behavior as the group request strategy. In the Individual Lottery, this is the
strategy in which each agent declares his or her group size.

###### Definition 0.

In the Individual Lottery, we say that group $G$ follows the group request
strategy if $a_{i}=|G|$ for all $i\in G$.

Our next result establishes that because agents’ request do not affect the
order in which they are processed, each agent should request at least his or
her group size.

###### Proposition 0.

In the Individual Lottery, the set of actions ${\bf a}_{G}$ is dominant for
group $G$ if and only if $a_{i}\geq|G|$ for all $i\in G$.

####  4.2.2. Performance.

Proposition 8 states that it is a dominant strategy to follow the group
request strategy, but that there are other dominant strategies in which agents
inflate their demand (select $a_{i}>|G_{i}|$).111111Our model assumes that
agents are indifferent between all allocations that allow all members of their
group to receive a ticket. While we believe this to be a reasonable
approximation, in practice, groups might follow the group request strategy if
each ticket has a cost, or inflate their demand if tickets can be resold on a
secondary market. Our next result implies that the group request equilibrium
Pareto dominates any other dominant strategy equilibrium.

###### Proposition 0.

Let $i$ be any agent, fix any ${\bf
a}_{-i}\in\\{1,2,\ldots,k\\}^{\mathcal{N}\backslash\\{i\\}}$, and let
$a_{i}^{\prime}>a_{i}\geq|G_{i}|$. Then for every agent $j\in\mathcal{N}$,

$u_{j}(\pi^{IL}(a_{i},{\bf a}_{-i}))\geq u_{j}(\pi^{IL}(a_{i}^{\prime},{\bf
a}_{-i})).$

Even when agents request only the number of tickets needed by their group, the
outcome will be inefficient if there are multiple winners from the same group.
One might expect that this is unlikely if the supply/demand ratio $\alpha$ is
small. However, Theorem 10 show that even in this case, the individual lottery
can be arbitrarily unfair and inefficient.

###### Theorem 10 (“IL is Bad”).

For any $\alpha,\kappa,\epsilon\in(0,1)$, there exists an instance in
$I(\kappa,\alpha)$ such that any dominant strategy equilibrium outcome of the
Individual Lottery is not $\epsilon-$efficient nor $\epsilon-$fair.

####  4.2.3. Proof Sketch of Theorem 10.

We will construct an instance in $I(\kappa,\alpha)$, where the outcome of the
Individual Lottery is arbitrarily unfair and arbitrarily inefficient. In this
instance, there are $n$ agents and $k=\alpha n$ tickets. Furthemore, agents
are divided into one large group of size $n^{3/4}$ and $n-n^{3/4}$ groups of
size one. If $n$ is large enough, then this instance is in $I(\kappa,\alpha)$
and the following two things happen simultaneously:

  1. (1)

The size of the large group $n^{3/4}$ is small relative to the number of
tickets $k=\alpha n$.

  2. (2)

The fraction of tickets allocated to small groups is insignificant.

Hence, the resulting allocation is unfair as the large group has an advantage
over small groups, and inefficient as a vanishing fraction of the agents get
most of the tickets.

Formally, let agents $i,j$ be such that $|G_{i}|=1$ and $|G_{j}|=n^{3/4}$. We
will start by proving the efficiency guarantee. By Proposition 9 it follows
that the group request is the most efficient dominant action profile.
Therefore, we assume without loss of generality that this action profile is
being selected. The utilization of this system is

(14) $\frac{n^{3/4}u_{j}(\pi^{IL}({\bf
a}))}{k}+\frac{(n-n^{3/4})u_{i}(\pi^{IL}({\bf a}))}{k}.$

We now argue that both terms in (14) can be made arbitrarily small by making
$n$ sufficiently large. We begin by studying the first term in (14). Using the
fact that utilities are upper bounded by $1$, it follows that

$\frac{n^{3/4}u_{j}(\pi^{IL}({\bf
a}))}{k}\leq\frac{n^{3/4}}{k}=\frac{1}{\alpha n^{1/4}}.$

Hence, to ensure that $(1)$ holds it suffices to have $n$ growing to infinity.
We now analyze the second term in (14). Because the group request action
profile is being selected, this term is equal to the fraction of tickets
allocated to small groups.

Moreover, we show the following upper bound on utility of agent $i$:

(15) $u_{i}(\pi^{IL}({\bf
a}))\leq\frac{k}{(n^{3/4})^{2}}=\frac{\alpha}{n^{1/2}}.$

The intuition behind this bound is as follows. If we restrict our attention
only to agents in $G_{i}$ and $G_{j}$, then we know that $i$ will get a payoff
$0$ unless it is processed after at most $k/n^{3/4}-1$ members of $G_{j}$.
Because the order over agents is uniformly distributed, this event occurs with
probability

$\frac{k/n^{3/4}}{n^{3/4}+1}\leq\frac{k}{(n^{3/4})^{2}}.$

From the first inequality in (15), it follows that

$\frac{(n-n^{3/4})u_{i}(\pi^{IL}({\bf
a}))}{k}\leq\frac{n}{n^{3/2}}\leq\frac{1}{n^{1/2}}.$

Notice that the right hand side goes to $0$ as $n$ grows, so $(2)$ holds.

We now turn to the fairness guarantee. To this end, we use a trivial upper
bound on the utility of agent $j$, based on the fact that the first agent to
be processed always obtains a payoff of $1$. Thus,

(16) $u_{j}(\pi^{IL}({\bf a}))\geq\frac{n^{3/4}}{n}=n^{-1/4}.$

Note that this lower bound is attained when all agents in small groups request
$k$ tickets. Combining the bound above and the second inequality in (15), we
obtain

(17) $\frac{u_{i}(\pi^{IL}({\bf a}))}{u_{j}(\pi^{IL}({\bf
a}))}\leq\frac{\alpha n^{1/4}}{n^{1/2}}.$

We conclude noting that the right side goes to $0$ as $n$ grows. The full
proof of Theorem 10 is located in Appendix B.

####  4.2.4. Limiting the Number of Tickets Requested.

In many applications, a variant of the Individual Lottery is used where a
limit is imposed on the number of tickets an agent can request. For example,
in the Hamilton Lottery agents can request at most $2$ tickets, and in the Big
Sur Marathon groups can have at most 15 individuals. This motivates us to
study the Individual Lottery with limit $\ell$. Formally, the only difference
between this and the standard Individual Lottery is the action set, which is
$A=\\{1,\ldots,\ell\\}^{n}$, with the limit $\ell$ chosen by the designer.

The choice of limit must balance several risks. Imposing a limit of $\ell$
reduces the risk from inflated demand, but harms groups with more than $\ell$
members. The latter effect reduces fairness and may also reduce efficiency if
there are many large groups. In fact, we show in Proposition 11 that the
Individual Lottery with limit $\ell$ is still arbitrarily unfair and
arbitrarily inefficient in the worst case.

###### Proposition 0.

For any $\alpha,\kappa,\epsilon\in(0,1)$ and $\ell\in\mathbb{N}$, there exists
an instance in $I(\kappa,\alpha)$ such that, regardless the action profile
selected, the outcome of the Individual Lottery with limit $\ell$ is not
$\epsilon-$efficient nor $\epsilon-$fair.

The proof of Proposition 11 is in Appendix B. In the example considered in the
proof, problems stem from the fact that most groups have more than $\ell$
members. However, even if group sizes are upper bounded by $\ell$, the
Individual Lottery with limit $\ell$ still performs poorly in the worst case.
In particular, Propositions 2 and 3 show that, if no group have more than
$\ell$ members, every dominant strategy equilibrium outcome of the Individual
Lottery with limit $\ell$ is $1/\ell-$efficient and $1/\ell$-fair. Moreover,
these guarantees are tight in the worst case. We give a complete analysis of
this variant of the Individual Lottery in Appendix B.

###  4.3. Weighted Individual Lottery

The example presented in Theorem 10 is an extreme case that we shouldn’t see
too often in practice. However, it illustrates the major issues of the
Individual Lottery. In this section, we show that minor modifications to the
Individual Lottery can yield strong performance guarantees even in these
extreme cases.

We study the Weighted Individual Lottery ($IW$), whose only departure from the
Individual Lottery is the order in which agents are placed. Instead of using a
uniform random order, the Weighted Individual Lottery uses a random order
biased against agents with large requests. Theorem 16 shows that the Weighted
Individual Lottery is approximately fair and approximately efficient, and
similar to the Group Lottery when there are many more agents than tickets.

Formally, each agent selects an action in $\\{1,....,k\\}$. For each
${\sigma}\in\mathcal{O}_{\mathcal{N}}$, we let random order over agents
${\Sigma}$ be such that

(18) $\mathbb{P}({\Sigma}={\sigma}|{\bf
a})=\prod_{t=1}^{n}\frac{1/a_{{\sigma}_{t}}}{\sum\limits_{i\in
N\backslash{\sigma}_{[t-1]}}1/a_{{\sigma}_{i}}}.$

There are several ways to generate ${\Sigma}$. This order can be thought of as
the result of sequentially sampling agents without replacement, with
probability inversely proportional to the number of tickets that they request.
One property that motivates the study of the Weighted Individual Lottery is
that when agents declare their group size, every group that has not been drawn
is equally likely to be draw next.

Let ${\Sigma}\in\mathcal{O}_{\mathcal{N}}$ be distributed according to (18).
For any $x^{\prime}\in\mathcal{X}$, the allocation function of the Weighted
Individual Lottery is

$\pi^{IW}_{x^{\prime}}({\bf
a})=\sum_{{\sigma}\in\mathcal{O}_{\mathcal{N}}}\mathbf{1}\left\\{x^{\prime}=x^{IL}({\bf
a},{\sigma})\right\\}\mathbb{P}({\Sigma}={\sigma}),$

with $x^{IL}$ defined as in (13).

We define group request strategy as in Definition 7: each agent $i$ requests
$|G_{i}|$ tickets.

####  4.3.1. Incentives.

In this section, we will see that under the Weighted Individual Lottery, there
are instances where no strategy is dominant for every group. However, we will
argue that if demand significantly exceeds supply, then it is reasonable to
assume that groups will select the group request strategy.

We start by showing in Proposition 12, that for groups of size three or less
the group request is the only dominant strategy.

###### Proposition 0.

In the Weighted Individual Lottery, if $G\in\mathcal{G}$ is such that $|G|\leq
3$, then the group request is the only dominant strategy for $G$.

The following example shows that for groups of more than three agents,
deviating from the group request is potentially profitable.

###### Example 0.

Consider an instance with $n$ agents and $n-1$ tickets. We divide the agents
into one group of size $4$ and $n-4$ groups of a single agent. If $n\geq 17$,
then the optimal strategy for the large group will depend on the action
profile selected by the small groups. In particular, if the small groups are
following the group request strategy, then members of the larger group benefit
from each requesting $2$ tickets instead of $4$. The analysis of this example
is located in Appendix C.

In the example above, when $n\leq 16$, it is actually optimal for the large
group to play the group request. Thus, this deviation is only profitable when
$n\geq 17$, and the group success probability is bigger than $92\%$. In
general, when agents request fewer tickets than their group size, their chance
of being selected increases, but now multiple agents from the group must be
drawn in order to achieve success. This should be profitable only if the
chance of each agent being drawn is high.

We formalize this intuition in Conjecture 14. Roughly speaking, we conjecture
that in scenarios where the success probability of a group is below
$1-1/e\approx 63\%$, the group request strategy maximizes its conditional
expected utility. Proposition 15 lends additional support to the conjecture.
This proposition establishes that our conjecture holds when restricted to a
broad set of strategies. In order to present our conjecture, we need first to
introduce some definitions.

In what follows, we fix an arbitrary group $G$. Given any action profile ${\bf
a}$, we generate an order over agents ${\Sigma}$ using the following
algorithm:

  1. (1)

Draw $\\{X_{i}\\}_{i\in\mathcal{N}}$ as i.i.d. exponentials, with
$\mathbb{P}(X_{i}>t)=e^{-t}$ for $t\geq 0$.

  2. (2)

Place agents in increasing order of $a_{i}X_{i}$: that is, output $\Sigma$
such that

$a_{\Sigma_{1}}X_{\Sigma_{1}}<\cdots<a_{\Sigma_{n}}X_{\Sigma_{n}}.$

ALGORITHM 1

From Proposition 1 in Appendix C, it follows that ${\Sigma}$ is distributed
according to (18) conditional on ${\bf a}$. We will refer to $a_{i}X_{i}$ as
the score obtained by agent $i$. Note that a lower score is better as it
increases the chances of getting awarded.

The usual way to study the incentives of group $G$, is to find a strategy that
maximizes its utility given the actions of other agents. Here, we will assume
that $G$ has an additional information: the scores of other agents. Thus, we
study the problem faced by $G$ of maximizing its success probability given
actions and scores of everyone else. This problem seems to be high-dimensional
and very complex, however, we will show that all the information relevant for
$G$ can be captured by a sufficient statistic $T$. Define,

(19) $T=\inf\left\\{t\in\mathbb{R}:\sum_{j\not\in
G}a_{j}\mathbf{1}\left\\{a_{j}X_{j}<t\right\\}>k-|G|\right\\}.$

We show in Lemma 2 located in Appendix C, that $G$ gets a utility of $1$ if
and only if the sum of the requests of its members whose score is lower than
$T$ is at least $|G|$. Therefore, we can formulate the problem faced by $G$ as
follows:

(20) $\begin{array}[]{rlll}\max&\mathbb{P}(\sum_{i\in
G}a_{i}\mathbf{1}\left\\{a_{i}X_{i}<T\right\\}\geq|G|)\\\ \text{\rm subject
to}&a_{i}\in\\{1,\ldots,k\\}\quad\forall i\in G.\end{array}$

Notice that under the group request strategy, the objective value in (20)
evaluates to

(21) $1-e^{-T}.$

This follows because $G$ will get a payoff of $1$ if and only if at least one
of its members has a score lower than $T$, that is, $\min_{i\in
G}\\{a_{i}X_{i}\\}<T$. Moreover, using that $\sum_{i\in G}1/a_{i}=1$, and by
the well-known properties of the minimum of exponential random variables, we
have that $\min_{i\in G}\\{a_{i}X_{i}\\}\sim Exp(1)$.

Definitions out of the way, we can present our conjecture and the proposition
supporting it.

###### Conjecture 0.

If $T\leq 1$, then no other strategy yields a higher objective value in (20)
than the group request.

From equation (21), we see that the utility yield by the group request is an
increasing function of $T$. Therefore, we can think of $T$ as an indicator of
how competitive the market is. Thus, the interpretations of Conjecture 14 is
that if the market is moderately competitive ($G$ has success probability
below $1-1/e\approx 63\%$), then the group request is optimal. While we
haven’t proved the conjecture, we do have a proof that it holds for a broad
subset of strategies. For $r\in\\{0,\ldots,|G|-1\\}$, we define
$\mathcal{B}_{r}\subseteq A_{G}$ to be the set of strategies for which the sum
of any $r$ requests is less than $|G|$, while the sum of any $r+1$ requests is
greater than or equal to $|G|$. Let

(22) $\mathcal{B}=\bigcup_{r=0}^{|G|-1}\mathcal{B}_{r}.$

###### Proposition 0.

If $T\leq 1$, then no other strategy in $\mathcal{B}$ yields a higher
objective value in (20) than the group request.

Note that $\mathcal{B}$ is rich enough such that for any group of size greater
than $3$, it contains a strategy that is better than the group request for $T$
large enough.

###### Proof sketch of Proposition 15.

In this proof, we will say that an agent is awarded if and only if it has a
score lower than $T$.

From (21), it suffices to show that under any strategy in $\mathcal{B}_{r}$,
the objective value in (20) is at most $1-e^{-T}$. We start by studying a
relaxation of the problem defined in (20). In this relaxation, the number of
times an agent $i$ is awarded follows a Poisson distribution with rate
$T/a_{i}$, and the total number of times $G$ is awarded follows a Poisson
distribution with rate $\sum_{i\in G}T/a_{i}$. Note that if the set of
feasible strategies is $\mathcal{B}_{r}$, then by Lemma 2 in Appendix C it
follows that $G$ needs to be awarded at least $r+1$ times. Finally, using a
Poisson tail bound, we show that this event happens with probability at most
$1-e^{-T}$. This bound can only be applied if the expected number of times $G$
is awarded is at most $r+1$. This follows because $T\leq 1$ and Lemma 3 in
Appendix C, which establishes that for any ${\bf
a}_{G}^{\prime}\in\mathcal{B}_{r},~{}\sum_{i\in G}1/a^{\prime}_{i}\leq r+1$. ∎

####  4.3.2. Performance.

We now study the performance of the Weighted Individual Lottery, under the
assumption that groups are selecting the group request strategy. We think that
this assumption is reasonable for two reasons: (i) for groups of size at most
three, the group request is the only dominant strategy, and (ii) for larger
groups, we conjecture that in scenarios where its success probability is
moderate (at most $63\%$), the group request strategy is optimal. The main
result of this section is Theorem 16, which establishes that the Weighted
Individual Lottery is approximately efficient and fair.

To state these guarantees, we define for any $x>0$,

(23) $g(x)=\frac{1-e^{-x}}{x}.$

###### Theorem 16.

Fix $\kappa,\alpha\in(0,1)$. For every instance in $I(\kappa,\alpha)$, the
group request outcome of the Weighted Individual Lottery is
$(1-\kappa)g(\alpha)$-efficient and $(1-2\kappa)g(\alpha)$-fair.

These guarantees resemble the ones offered for the Group lottery. Recall that
Theorem 3 establishes that the Group Lottery is $(1-\kappa)$-efficient and
$(1-2\kappa)$-fair. It is not perfectly efficient, as the last tickets might
be wasted. Similarly, it is not perfectly fair, as once there are only a few
tickets left, small groups still have a chance of being allocated but large
groups do not. These issues persist under the Weighted Individual Lottery. In
addition, the Weighted Individual Lottery has the additional concern that
multiple member of a group may be selected. This explains the multiplicative
factor of $g(\alpha)$ in the theorem statement. Because $g(\alpha)\geq
1-\alpha/2$, when $\alpha$ is close to $0$ the guarantees for the Group
Lottery and the Weighted Individual Lottery coincide. Although it is intuitive
that a small supply-demand ratio implies a small chance of having groups with
multiple winners, the previous section shows that this may not be the case
under the standard Individual Lottery.

####  4.3.3. Proof Sketch of Theorem 16.

In order to prove the efficiency and fairness guarantees, we first introduce a
new mechanism: the Group Lottery with Replacement (GR). This is a variant of
the Group Lottery in which valid groups can be processed more than once.
Formally, the set of actions, the set of valid groups $V$, the group request
strategy and the allocation rule $x^{GL}$ are defined exactly as in the Group
Lottery. However, the allocation function $\pi^{GR}$ is different, in
particular, this mechanism process valid groups according to a sequence of $k$
elements $\Sigma\in\mathcal{S}_{V}$ , where $\Sigma_{t}$ is independently and
uniformly sampled with replacement from $V$. Hence, for any
$x^{\prime}\in\mathcal{X}$, the allocation function of the Group Lottery is

$\pi^{GR}_{x^{\prime}}({\bf
a})=\sum_{{\sigma}\in\mathcal{O}_{V}}\mathbf{1}\left\\{x^{\prime}=x^{GL}({\bf
a},{\sigma})\right\\}\mathbb{P}(\Sigma={\sigma}),$

with $x^{GL}$ defined as in (7). Having defined this new mechanism, we now
present a lemma that will be key in proving both guarantees. This lemma
establishes a dominance relation between the Weighted Individual Lottery, the
Group Lottery and the Group Lottery with Replacement, when the group request
action profile is being selected. As we will see, every agent prefers the
Group Lottery to the Weighted Individual Lottery, and the Weighted Individual
Lottery to the Group Lottery with Replacement.

###### Lemma 0.

For any instance and any agent $i\in\mathcal{N}$, if ${\bf a}$ denote the
corresponding group request action profile for each mechanism below, then

(24) $u_{i}(\pi^{GR}({\bf a}))\leq u_{i}(\pi^{IW}({\bf a}))\leq
u_{i}(\pi^{GL}({\bf a})).$

The key idea to prove Lemma 17 is that the order or sequence used in each of
these mechanism can be generated based on a random sequence of agents
$\Sigma^{\prime}$. Roughly speaking, each order or sequence is generated from
$\Sigma^{\prime}$ as follows:

  * •

Group Lottery with replacement: replace every agent by its group.

  * •

Weighted Individual Lottery: remove every agent that has already appeared in a
previous position.

  * •

Group Lottery: replace every agent by its group, and then remove every group
that has already appeared in a previous position.

Note that because in each mechanism the group request strategy is being
selected, whenever a group or agent is being processed, it is given a number
of tickets equal to the minimum of its group size and the number of remaining
tickets.

This implies that, under the Group Lottery with Replacement, a group could be
given more tickets than needed because one of its members appeared more than
once in the first positions of $\Sigma^{\prime}$. This situation is avoided in
the Weighted Individual Lottery, hence, making all agents weakly better.
Similarly, under the Weighted Individual Lottery, a group could be given more
tickets than needed because its members appeared more than once in the first
positions of $\Sigma^{\prime}$. This situation is avoided in the Group
Lottery, hence, making all agents weakly better. The full proof is located in
Appendix C.2.2.

We now turn to the efficiency guarantee. From Lemma 17, it follows that for
any instance the utilization under the Weighted Individual Lottery is at least
the utilization under the Group Request with Replacement. Therefore, it
suffices to show that for any instance in $I(\kappa,\alpha)$, the Group
Lottery with Replacement is $(1-\kappa)g(\alpha)$-efficient. To this end, we
present in Lemma 18 a lower bound on the utility of any agent under the Group
Lottery with Replacement.

###### Lemma 0.

For any instance in $I(\kappa,\alpha)$ and any agent $i$, if we let ${\bf a}$
be the group request under the Group Lottery with Replacement, then

(25) $u_{i}(\pi^{GR}({\bf a}))\geq\frac{k}{n}(1-\kappa)g(\alpha).$

The proof of Lemma 18 is in Appendix C.2.3. This lemma immediately give us the
desired lower bound on the utilization of the Group Lottery with replacement.

We now show the fairness guarantee. From Lemma 17, we have that for any
instance and any pair of agents $i,j$,

(26) $\frac{u_{i}(\pi^{IW}({\bf a}))}{u_{j}(\pi^{IW}({\bf
a}))}\geq\frac{u_{i}(\pi^{GR}({\bf a}))}{u_{j}(\pi^{GL}({\bf a}))}.$

Hence, it suffices to show that the ratio on the right hand side is at least
$(1-2\kappa)g(\alpha)$. In Lemma 4 we proved an upper bound on the utility of
an agent under the Group Lottery. Meanwhile, in Lemma 18 we established a
lower bound on the utility of an agent under the Group Lottery with
Replacement. Combining equation (26), Lemma 4 and Lemma 18 yields our fairness
factor of $(1-2\kappa)g(\alpha)$.

##  5\. Discussion

We consider a setting where groups of people wish to share an experience that
is being allocated by lottery. We study the efficiency and fairness of simple
mechanisms in two scenarios: one where agents identify the members of their
group, and one where they simply request a number of tickets. In the former
case, the Group Lottery is $(1-\kappa)$-efficient and $(1-2\kappa)$-fair.
However, its natural and widespread counterpart, the Individual Lottery,
suffers from deficiencies that can cause it to be arbitrarily inefficient and
unfair. As an alternative, we propose the Weighted Individual Lottery. This
mechanism uses the same user interface as the Individual Lottery, and Theorem
16 establishes that it is $(1-\kappa)g(\alpha)$-efficient and
$(1-2\kappa)g(\alpha)$-fair.

Although our bounds are based on worst-case scenarios, they can be combined
with publicly available data to provide meaningful guarantees. In 2016 the
Hamilton Lottery received approximately $n=10,000$ applications daily for
$k=21$ tickets, with a max group size of $s=2$.121212Source:
https://www.bustle.com/articles/165707-the-odds-of-winning-the-hamilton-
lottery-are-too-depressing-for-words. Hence, in this case $\kappa\leq.05$ and
$g(\alpha)\geq.99$. Therefore, by Theorem 3, the Group Lottery outcome is at
least $95\%$ efficient and $90\%$ fair. Furthermore, Theorem 16 gives nearly
identical guarantees for the Weighted Individual Lottery. Meanwhile, the 2020
Big Sur Marathon Groups and Couples lottery received $1296$ applications for
$k=702$ tickets, with a maximum group size of $15$.131313Source:
https://www.bigsurmarathon.org/random-drawing-results-for-the-2020-big-sur-
marathon/. This yields $\kappa=14/702\approx.02$, so Theorem 3 implies $98\%$
efficiency and $96\%$ fairness for the Group Lottery. Determining $\alpha$ is
tricker, as we do not observe the total number of agents $n$. Using the very
conservative lower bound $n\geq 1296$ (based on the assumption that every
member of every group submitted a separate application) yields
$g(\alpha)\geq.77$. Thus, Theorem 16 implies $76\%$ efficiency and $74\%$
fairness for the Weighted Individual Lottery. Its true performance would
likely be much better, but accurate estimates would rely on understanding how
many groups are currently submitting multiple applications.

Our analysis makes the strong assumption of dichotomous preferences. In
practice, the world is more complicated: groups may benefit from extra tickets
that can be sold or given to friends, and groups that don’t receive enough
tickets for everyone may choose to split up and have a subset attend the
event. Despite these considerations, we believe that dichotomous preferences
capture the first-order considerations in several markets while maintaining
tractability. The mechanisms we have proposed, while imperfect, are practical
and offer improvements over the Individual Lottery (which is often the status
quo). Furthermore, we conjecture that the efficiency and fairness of the Group
Lottery would continue to hold in a model where the utility of members of
group $G$ is a more general function of the number of tickets received by $G$,
so long as this function is convex and increasing on $\\{1,2,\ldots,|G|\\}$,
and non-increasing thereafter.

One exciting direction for future work is to adapt these mechanisms to
settings with heterogeneous goods. For example, while the daily lottery for
Half Dome allocates homogeneous permits using the Individual Lottery, the pre-
season lottery allocates 225 permits for each day. Before the hiking season,
each applicant enters a number of permits requested (up to a maximum of six),
as well as a ranked list of dates that would be feasible. Applicants are then
placed in a uniformly random order, and sequentially allocated their most
preferred feasible date. This is the natural extension of the Individual
Lottery to a setting with with heterogeneous goods, and has many of the same
limitations discussed in this paper. It would be interesting to study the
performance of (generalizations of) the Group Lottery and Weighted Individual
Lottery in this setting.

## References

  * (1)
  * Ausubel et al. (2006) Lawrence M Ausubel, Paul Milgrom, et al. 2006\.  The lovely but lonely Vickrey auction.  _Combinatorial auctions_ 17 (2006), 22–26.
  * Benassy (1982) Jean Pascal Benassy. 1982\.  _The economics of market disequilibrium_.  New York: Academic Press.
  * Bogomolnaia and Moulin (2004) Anna Bogomolnaia and Hervé Moulin. 2004.  Random matching under dichotomous preferences.  _Econometrica_ 72, 1 (2004), 257–279.
  * Bogomolnaia et al. (2005) Anna Bogomolnaia, Hervé Moulin, Richard Stong, et al. 2005\.  Collective choice under dichotomous preferences.  _Journal of Economic Theory_ 122, 2 (2005), 165–184.
  * Cachon and Lariviere (1999) Gérard P Cachon and Martin A Lariviere. 1999.  Capacity choice and allocation: Strategic behavior and supply chain performance.  _Management science_ 45, 8 (1999), 1091–1108.
  * Ching (1992) Stephen Ching. 1992\.  A simple characterization of the uniform rule.  _Economics letters_ 40, 1 (1992), 57–60.
  * Ehlers and Klaus (2003) Lars Ehlers and Bettina Klaus. 2003.  Probabilistic assignments of identical indivisible objects and uniform probabilistic rules.  _Review of Economic Design_ 8, 3 (2003), 249–268.
  * Johnson et al. (2005) Norman L Johnson, Adrienne W Kemp, and Samuel Kotz. 2005\.  _Univariate discrete distributions_. Vol. 444.  John Wiley & Sons.
  * Nguyen et al. (2016) Thành Nguyen, Ahmad Peivandi, and Rakesh Vohra. 2016\.  Assignment problems with complementarities.  _Journal of Economic Theory_ 165 (2016), 209–241.
  * Patel et al. (2020) Deval Patel, Arindam Khan, and Anand Louis. 2020.  Group Fairness for Knapsack Problems.  _arXiv preprint arXiv:2006.07832_ (2020).
  * Roth et al. (2005) Alvin E Roth, Tayfun Sönmez, and M Utku Ünver. 2005\.  Pairwise kidney exchange.  _Journal of Economic theory_ 125, 2 (2005), 151–188.
  * Serfling (1974) Robert J Serfling. 1974\.  Probability inequalities for the sum in sampling without replacement.  _The Annals of Statistics_ (1974), 39–48.
  * Sprumont (1991) Yves Sprumont. 1991\.  The division problem with single-peaked preferences: a characterization of the uniform allocation rule.  _Econometrica_ 59 (1991), 509–519.

##  Appendix A Group Lottery

Input: A finite set $E$

Output: A random order ${\Sigma}\in\mathcal{O}_{E}$

Choose $S\subset E$. Generate

  1. i.

a uniform random order ${\Sigma}^{S}\in\mathcal{O}_{S}$,

  2. ii.

a uniform random order ${\Sigma}^{-}\in\mathcal{O}_{E\backslash S}$.

  3. iii.

a uniform random subset $P\subset\\{1,\ldots,|E|\\}$ with $|P|=|S|$.

Generate ${\Sigma}$ from ${\Sigma}^{S},{\Sigma}^{-},P$ placing elements of $S$
in positions $P$, maintaining the order of elements of $S$ as given by
${\Sigma}^{S}$ and the order of elements of $E\backslash S$ as given by
${\Sigma}^{-}$.

ALGORITHM 2

###### Lemma 0.

For any finite set $E$, Algorithm 2 generates a uniform random order
${\Sigma}\in\mathcal{O}_{E}$: for each order ${\sigma}\in\mathcal{O}_{E},$
$P({\Sigma}={\sigma})=1/|E|!$.

###### Proof of Lemma 1.

Fix an order ${\sigma}\in\mathcal{O}_{E}$. Let ${\sigma}_{S}$ and
${\sigma}_{-S}$ be the restriction of ${\sigma}$ to $S$ and $E\setminus S$,
respectively. For any $i\in E$, we let $p_{i}$ be the position of $i$ in
${\sigma}$, that is, ${\sigma}_{p_{i}}=i$. We define $P_{S}=\cup_{i\in
S}\\{p_{i}\\}$. In order to end with the order ${\sigma}$, it must be that:

  * •

The order ${\Sigma}$ generated in step i. is equal to ${\sigma}_{S}$, which
occurs with probability $\mathbb{P}({\Sigma}={\sigma}_{S})=1/|S|!$.

  * •

The order ${\Sigma}^{-}$ generated in step ii. is equal to ${\sigma}_{-S}$,
which occurs with probability
$\mathbb{P}({\Sigma}^{-}={\sigma}_{-S})=1/(|\mathbb{E}|-|S|)!$.

  * •

The random subset $P$ generated in step iii. is equal to $P_{S}$, which occurs
with probability $\mathbb{P}(P=P_{S})=\prod_{j=0}^{|S|-1}(|S|-j)/(|E|-j)$.

Hence, the probability that the algorithm generates the order ${\sigma}$ is

$\frac{1}{|S|!}\frac{1}{E-|S|!}\prod_{j=0}^{|S|-1}\frac{|S|-j}{|E|-j}=\frac{1}{|E|!}.$

∎

###  A.1. Incentives

###### Proof of Proposition 2.

Fix an arbitrary agent $i\in\mathcal{N}$. Let ${\bf a}$ be an action profile
such that ${\bf a}_{G_{i}}$ is the group request strategy and ${\bf
a}_{-G_{i}}$ is arbitrary. Let ${\bf a}^{\prime}$ denote an alternative
strategy profile in which $a^{\prime}_{j}=a_{j}$ for $j\not\in G_{i}$. Let $V$
be the set of valid groups according to ${\bf a}$, $V^{\prime}$ the set of
valid groups according to ${\bf a}^{\prime}$, and $V^{-}$ be the set of valid
groups not containing any members of $G_{i}$:

$\displaystyle V\,\,$ $\displaystyle=\\{S\subset\mathcal{N}:a_{j}=S~{}\forall
j\in S\\}.$ $\displaystyle V^{\prime}$
$\displaystyle=\\{S\subset\mathcal{N}:a^{\prime}_{j}=S~{}\forall j\in S\\}$
$\displaystyle V^{-}$ $\displaystyle=\\{S\subset\mathcal{N}\setminus
G_{j}:a_{j}=S~{}\forall j\in S\\}.$

Note that $V^{-}\subseteq V\cap V^{\prime}$, and that agents in $G_{i}$ do not
influence $V^{-}$. We generate uniform random orders ${\Sigma}$ and
${\Sigma}^{\prime}$ over $V$ and $V^{\prime}$ (respectively) using Algorithm
2: we first generate a uniform random order ${\Sigma}^{-}$ over $V^{-}$, and
then extend this to obtain ${\Sigma}$ and ${\Sigma}^{\prime}$. We will prove
that for any realization of ${\Sigma}^{-}$,

(27) $\mathbb{E}[u_{i}(x^{GL}({\bf
a},{\Sigma}))|{\Sigma}^{-}]\geq\mathbb{E}[u_{i}(x^{GL}({\bf
a}^{\prime},{\Sigma}^{\prime}))|{\Sigma}^{-}].$

Because agents in $G_{i}$ cannot influence ${\Sigma}^{-}$, it follows
immediately that the unconditional expected utility of agent $i$ is also
higher under the group request strategy.

If $\sum_{S\in V^{-}}|S|\leq k-|G_{i}|$, then the group request strategy
guarantees that all members of $G_{i}$ will receive a ticket, so there is
nothing to prove. Otherwise, let

$\tau({\Sigma}^{-})=\tau(k-|G_{i}|+1,{\Sigma}^{-}),$

be as defined in (6) where the size function is the cardinality of the valid
group declared by the agent, that is, $|{\sigma}_{t}|=|a_{{\sigma}_{t}}|$.
Intuitively, $\tau$ is the first point at which the number of remaining
tickets would be less than $|G_{i}|$, when processing valid groups in $V^{-}$
according to order ${\Sigma}^{-}$.

Because agents in $G_{i}$ follow the group request strategy under ${\bf a}$,
we have $V=V^{-}\cup G_{i}$. Members of $G_{i}$ get a payoff of 1 if and only
if $G_{i}$ is in the first $\tau(\Sigma^{-})$ positions of $\Sigma$.
Therefore,

(28) $\mathbb{E}[u_{i}(x^{GL}({\bf
a},\Sigma))|\Sigma^{-}]=\frac{\tau(\Sigma^{-})}{1+|V^{-}|}.$

We now turn to the action profile ${\bf a}^{\prime}$. Because the Group
Lottery gives at most one ticket to each agent, $i$ gets a payoff of 1 if and
only if all members of $G_{i}$ receive a ticket. This is not possible unless
(i) every agent in $G_{i}$ is included in a valid group in $V^{\prime}$, and
(ii) in the order $\Sigma^{\prime}$, all valid groups in $V^{\prime}\backslash
V^{-}$ appear before group $S=\Sigma^{-}_{\tau(\Sigma^{-})}$. According to the
algorithm, the conditional probability of (ii) given $\Sigma^{-}$ is at most

$\frac{\tau(\Sigma^{-})}{2+|V^{-}|}\frac{\tau(\Sigma^{-})-1}{1+|V^{-}|},$

which is smaller than the right side of (28), implying that group $G_{i}$ has
not benefited from its deviation.

Next, we show that any other strategy is not dominant. Let $j\not\in G_{i}$
and $\tilde{\bf a}$ denote an action profile such that $j\in\tilde{a}_{i}$,
$i\not\in\tilde{a}_{j}$ and the remaining actions $\tilde{\bf a}_{-\\{i,j\\}}$
are arbitrary. Under $\tilde{\bf a}$ agent $i$ is not in a valid group then it
is not award and group $G_{i}$ get a payoff of 0. This is strictly less than
the payoff under a group request, which is greater than the probability of
$G_{i}$ being the first group to be processed. Therefore, we can restrict to
strategies $\hat{\bf a}$ where $\hat{a}_{i^{\prime}}\subset G_{i}$ for any
$i^{\prime}\in G_{i}$. Furthermore, $G_{i}$ will have a positive expected
payoff only if under $\hat{\bf a}$ its members are divided into two or more
valid groups. Let actions $\hat{\bf a}_{-G_{i}}$ be such that
$\hat{a}_{j}=\mathcal{N}\setminus G_{i}$ for any $j\in\mathcal{N}\setminus
G_{i}$, and $\hat{V}$ be the set of valid groups according to $\hat{a}$,

$\hat{V}\,\,=\\{S\subset\mathcal{N}:\hat{a}_{j}=S~{}\forall j\in S\\}.$

Observe that $|\hat{V}|\geq 3$. By assumption $n>k$, so $G_{i}$ will get a
payoff of 1 if and only if valid group $\mathcal{N}\setminus G_{i}$ is the
last valid group to be processed. This event occurs with probability

$\frac{(|\hat{V}|-1)!}{|\hat{V}|!}=\frac{1}{|\hat{V}|}.$

This is strictly smaller than $1/2$ the expected utility when $G_{i}$ select a
group request. ∎

###  A.2. Performance

###### Lemma 0.

Fix any instance and any pair of agents $i,j\in\mathcal{N}$. Let ${\bf a}$ be
an action profile under the Group Lottery such that $G_{i}$ and $G_{j}$ select
the group request strategy. If $|G_{i}|\geq|G_{j}|$, then

(29) $u_{i}(\pi^{GL}({\bf a}))\leq u_{j}(\pi^{GL}({\bf a})).$

###### Proof of Lemma 2.

Let $V$ be the set of valid groups given ${\bf a}$. Observe that by assumption
$G_{i},G_{j}\in V$. We define $S_{i},S_{j}$ to be the set of orders over $V$
that guarantee a payoff of $1$ to group $G_{i}$ and $G_{j}$, respectively. It
suffices to show that

$|S_{j}|\geq|S_{i}|.$

To prove this, we will construct an injective map $f:S_{i}\to S_{j}$. We let
$f$ be the map that only swap the positions of $G_{i}$ and $G_{j}$, keeping
all the remaining positions unchanged. Clearly $f$ is injective. Thus, all
that remains to show is that for any ${\sigma}\in S_{i}$, $f({\sigma})\in
S_{j}$. Fix ${\sigma}\in S_{i}$. If ${\sigma}\in S_{j}$, then there are enough
tickets to satisfy both groups and $f({\sigma})\in S_{i}\cap S_{j}\subseteq
S_{j}$. If ${\sigma}\not\in S_{j}$, then then the number of tickets remaining
before $G_{j}$ is processed under $f({\sigma})$ is the same as the number of
tickets remaining before $G_{i}$ is processed under ${\sigma}$. Because
${\sigma}\in S_{i}$, this number is at least $|G_{i}|$ which by assumption is
at least $|G_{j}|$, so $f({\sigma})\in S_{j}$. ∎

###### Fact 1.

For any $a,b,c\in\mathbb{R}$ such that $a\leq b$ and $c\geq 0$, then

(30) $\frac{a}{b}\leq\frac{a+c}{b+c}.$

###### Proof of Proposition 5.

First, we will prove the right inequality of (11). If
$k\geq\sum_{i}a_{i}-\bar{a}+1$, then our upper bound is at least $n$ and
immediately holds. Hence, without loss of generality we can assume
$k\leq\sum_{i}a_{i}-\bar{a}$. We let $S_{t}=S_{t}({\Sigma})$ be the sum of the
first $t$ numbers according to ${\Sigma}$, that is,

(31) $S_{t}=\sum_{i=1}^{t}a_{{\Sigma}_{i}}.$

We define

(32) $Z_{t}^{*}=\frac{S_{t}-t\mu}{n-t}.$

As mentioned in Serfling (1974), the sequence $Z^{*}_{1},\ldots,Z^{*}_{n-1}$
is a forward martingale. Furthermore, $k\leq\sum_{i}a_{i}-\bar{a}$ implies
$\mathbb{P}(\tau\leq n-1)=1$ so $\tau$ is bounded and $Z^{*}_{\tau}$ is well
defined. Hence, we can apply Doob’s optional stopping theorem to obtain

(33)
$\mathbb{E}\left[\frac{S_{\tau}-\tau\mu}{n-\tau}\right]=\mathbb{E}[Z^{*}_{\tau}]=\mathbb{E}[Z^{*}_{1}]=0.$

From the definition of $\tau$, we get

(34)
$\mathbb{E}\left[\frac{S_{\tau}}{n-\tau}\right]\leq(k+\bar{a}-1)\mathbb{E}\left[\frac{1}{n-\tau}\right].$

We claim that

(35)
$\mathbb{E}[\tau]\mathbb{E}\left[\frac{1}{n-\tau}\right]\leq\mathbb{E}\left[\frac{\tau}{n-\tau}\right].$

For any $x<n$, define

$f(x)=\left(x-\mathbb{E}[\tau]\right)\left(\frac{1}{n-x}-\frac{1}{n-\mathbb{E}\left[\tau\right]}\right).$

Note that $f(x)\geq 0$ for all $x$, so $\mathbb{E}[f(\tau)]\geq 0$. Thus,

$0\leq\mathbb{E}[f(\tau)]=\mathbb{E}\left[(\tau-\mathbb{E}\left[\tau\right])\left(\frac{1}{n-\tau}-\frac{1}{n-\mathbb{E}\left[\tau\right]}\right)\right]=\mathbb{E}\left[\frac{\tau-\mathbb{E}\left[\tau\right]}{n-\tau}\right].$

Combining equations (33), (34) and (35) yields our desired result.

Now, we prove the left inequality of (11). If $k\leq\bar{a}$, then our lower
bound is at most $1$ and immediately holds, then without loss of generality we
can assume $k\geq\bar{a}+1$. To construct ${\Sigma}$ we will generate a random
order ${\Sigma}^{\prime}$ and iterate through it backwards, that is,
${\Sigma}_{t}={\Sigma}^{\prime}_{n-t+1}$ for $t=1,\ldots,n$. We claim that for
every ${\Sigma}$,

(36) $\tau(k,\Sigma)+\tau(\sum_{i}a_{i}-k+1,\Sigma^{\prime})=n+1.$

It suffices to show that

(37)
$\displaystyle\sum_{t=1}^{\tau(\sum_{i}a_{i}-k+1,\Sigma^{\prime})}a_{{\Sigma}^{\prime}_{t}}$
$\displaystyle=\sum_{t=\tau(k,\Sigma)}^{n}a_{{\Sigma}_{t}}.$

From the definition of $\tau$, we have that

$\sum_{t=\tau(k,\Sigma)+1}^{n}a_{{\Sigma}_{t}}=\sum_{i=1}a_{i}-\sum_{t=1}^{\tau(k,\Sigma)}a_{{\Sigma}_{t}}\leq\sum_{i=1}a_{i}-k.$

Similarly,

$\sum_{t=\tau(k,\Sigma)}^{n}a_{{\Sigma}_{t}}=\sum_{i=1}a_{i}-\sum_{t=1}^{\tau(k,\Sigma)-1}a_{{\Sigma}_{t}}\geq\sum_{i=1}a_{i}-k+1.$

Applying the upper bound in (11) to (36) immediately implies

$\mathbb{E}[\tau(k,\Sigma)]=n+1-\mathbb{E}[\tau(\sum_{i}a_{i}-k+1,\Sigma^{\prime})]\geq
n+1-\frac{\sum_{i}a_{i}-k+\bar{a}}{\mu}=1+\frac{k-\bar{a}}{\mu}.$

We now turn to equation (12). For any order $\sigma$, we define $h({\sigma})$
to be the order that: (i) is identical to ${\sigma}$ from position
$\tau(k+k^{\prime},{\sigma})$ until the end, and (ii) flip the ordering of all
elements from position $1$ to $\tau(k+k^{\prime},{\sigma})-1$. More precisely,

(38) $h({\sigma})_{t}=\begin{cases}{\sigma}_{t}&\text{if
}t\geq\tau(k+k^{\prime},{\sigma}),\\\
{\sigma}_{\tau(k+k^{\prime},{\sigma})-t}&\text{if
}t<\tau(k+k^{\prime},{\sigma}).\end{cases}$

We claim that

$\tau(k+k^{\prime},{\sigma})=\tau(k+k^{\prime},h({\sigma})).$

This implies that $h(h({\sigma})))={\sigma}$, which further implies that $h$
is a bijective map. This follows from 2 observations: (i) the elements in the
first $\tau(k+k^{\prime},{\sigma})-1$ positions are the same in both orders,
and do not sum to $k+k^{\prime}$. Additionally, (ii) the agents in the first
$\tau(k+k^{\prime},{\sigma})$ positions are also the same in both orders, and
they do sum to $k+k^{\prime}$.

We will show that for any ${\sigma}\in\mathcal{O}_{[n]}$,

(39)
$\tau(k,{\sigma})+\tau(k^{\prime},h({\sigma}))\geq\tau(k+k^{\prime},{\sigma}).$

This implies our result as

$\displaystyle\mathbb{E}[\tau(k,{\Sigma})+\tau(k^{\prime},h({\Sigma}))]$
$\displaystyle=\frac{1}{n!}\left(\sum_{{\sigma}\in\mathcal{O}_{[n]}}\tau(k,{\sigma})+\tau(k^{\prime},{\sigma})\right)$
$\displaystyle=\frac{1}{n!}\left(\sum_{{\sigma}\in\mathcal{O}_{[n]}}\tau(k,{\sigma})+\tau(k^{\prime},h({\sigma}))\right)$
$\displaystyle\geq\frac{1}{n!}\left(\sum_{{\sigma}\in\mathcal{O}_{[n]}}\tau(k+k^{\prime},{\sigma})\right)$
$\displaystyle=\mathbb{E}[\tau(k+k^{\prime},{\Sigma})].$

The second equality follows as $h$ is a bijective map, and the inequality
follows from (39). Thus all that remains is to show (39). From the definition
of $\tau$, we have

$\displaystyle\sum_{t=1}^{\tau(k,{\sigma})}a_{{\sigma}_{t}}$
$\displaystyle\geq k,$
$\displaystyle\sum_{t=1}^{\tau(k+k^{\prime},{\sigma})-1}a_{{\sigma}_{t}}$
$\displaystyle<k+k^{\prime}.$

Implying that

(40)
$\sum_{t=\tau(k,{\sigma})+1}^{\tau(k+k^{\prime},{\sigma})-1}a_{{\sigma}_{t}}<k^{\prime}.$

Moreover, from the definition of $h$ in (38) it follows that

(41)
$\\{h({\sigma})_{1},\ldots,h({\sigma})_{\tau(k+k^{\prime},{\sigma})-\tau(k,{\sigma})-1}\\}=\\{{\sigma}_{\tau(k+k^{\prime},{\sigma})-1},\ldots,{\sigma}_{\tau(k,{\sigma})+1}\\}.$

Combining (40) and (41) yields

$\sum_{t=1}^{\tau(k+k^{\prime},{\sigma})-\tau(k,{\sigma})-1}a_{h({\sigma})_{t}}<k^{\prime}.$

This implies (39) as by definition $\tau$ is integral and

$\tau(k^{\prime},h({\sigma}))>\tau(k+k^{\prime},{\sigma})-\tau(k,{\sigma})-1.$

∎

###### Proof of Lemma 4.

Because all groups are playing the group request, the set of valid groups is
$\mathcal{G}$. In what follows we fix an arbitrary agent $i\in\mathcal{N}$. We
construct a random order ${\Sigma}$ over $\mathcal{G}$ using Algorithm 2: we
generate an order ${\Sigma}^{-i}$ over $\mathcal{G}\setminus G_{i}$ and then
extend it to $\mathcal{G}$. By Lemma 1, the resulting order ${\Sigma}$ is
uniformly distributed. We let $\tau^{-i}=\tau(k-|G_{i}|+1,{\Sigma}^{-i})$ be
the number of positions in ${\Sigma}$ that ensure $G_{i}$ a payoff of 1 given
${\Sigma}^{-i}$. Note that $\tau^{-i}$ is well defined as $k<n$ implies
$k-|G_{i}|+1\leq n-|G_{i}|=\sum_{t}|{\Sigma}^{-i}_{t}|$. Moreover, if $G_{i}$
is in the first $\tau^{-i}$ positions of ${\Sigma}$, then it gets a payoff of
1 as the number of remaining tickets before it is processed is at least

$k-\sum_{t=1}^{\tau^{-i}-1}|{\Sigma}^{-i}_{t}|\geq k-(k-|G_{i}|)=|G_{i}|.$

On the other hand, if $G_{i}$ is in the last $m-\tau^{-i}$ positions of
${\Sigma}$, then it gets a payoff of $0$ because the number of remaining
tickets when $G_{i}$ is processed is at most

$k-\sum_{t=1}^{\tau^{-i}}|{\Sigma}^{-i}_{t}|\leq k-(k-|G_{i}|+1)=|G_{i}|-1.$

Therefore,

(42) $u_{i}(x^{GL}({\bf a},{\Sigma}))=\mathbb{E}[\mathbb{E}[u_{i}(x^{GL}({\bf
a},{\Sigma}))|{\Sigma}^{-i}]]=\frac{\mathbb{E}[\tau^{-i}]}{m}.$

By Proposition 5 equation (11), we have

(43)
$\displaystyle\mathbb{E}[\tau^{-i}]\leq\frac{k-G_{i}+\max_{G}|G|}{(n-|G_{i}|)/(m-1)}.$

This and equation (42) yields

(44) $\displaystyle u_{i}(\pi^{GL}({\bf
a}))\leq\left(\frac{k-G_{i}+\max_{G}|G|}{n-|G_{i}|}\right)\left(\frac{m-1}{m}\right).$

Because there is a group of size $|G_{i}|$ and the remaining $n-|G_{i}|$
agents can be in at most $n-|G_{i}|$ groups of size $1$, we have

(45) $m\leq n-|G_{i}|+1.$

This implies

(46) $\frac{m-1}{m}\leq\frac{n-|G_{i}|}{n-|G_{i}|+1}.$

From (44) and (46) it follows that

(47) $u_{i}(\pi^{GL}({\bf a}))\leq\frac{k-G_{i}+\max_{G}|G|}{n-|G_{i}|+1}.$

Applying Fact 1 with $a=k+\max_{G}|G|-|G_{i}|$, $b=n+1-|G_{i}|$ and
$c=|G_{i}|-1$, we get

(48)
$\frac{k+\max_{G}|G|-|G_{i}|}{n-|G_{i}|+1}\leq\frac{k+\max_{G}|G|-1}{n}\leq\frac{k}{n}\left(1+\kappa\right).$

Note that to apply Fact 1 we need $a\leq b$, we can assume this without loss
of generality. Otherwise, $a>b$ or equivalently

(49) $k+\max_{G}|G|>n+1.$

We claim that if the inequality above holds then
$\frac{k}{n}\left(1+\kappa\right)>1$, hence, our bound is vacuous. This can be
seen by noting that

(50) $1+\kappa\geq\frac{k+\max_{G}|G|-1}{k}>\frac{n}{k}.$

The last inequality follows by (49). ∎

###### Proof of Theorem 3.

Fix $\alpha,\kappa\in(0,1)$ and an arbitrary instance in $I(\kappa,\alpha)$.
In what follows, we let ${\bf a}$ denote the group request action profile
under the Group Lottery. We define $s$ to be the maximum group size, that is,
$s=\max_{G\in\mathcal{G}}|G|$.

We begin with the efficiency guarantee. For any order
${\sigma}\in\mathcal{O}_{\mathcal{G}}$,

(51) $U(x^{GL}({\bf a},{\sigma}))\geq 1-\frac{s-1}{k}\geq 1-\kappa,$

where the second inequality follows as our instance is in $I(\kappa,\alpha)$.
This is fairly trivial: if we let

$\tau({\sigma})=\tau(k+1,{\sigma}),$

be as defined in (6) where the size of a group is its number of elements. Then
$U(x^{GL}({\bf a},{\sigma}))$ is exactly
$\frac{1}{k}\sum_{j=1}^{\tau({\sigma},k+1)-1}|{\sigma}_{j}|$, which is at
least $\frac{1}{k}(k-(s-1))$, because adding one more group (of size at most
$s$) brings the sum above $k$. From (51), it immediately follows that if
${\Sigma}$ is a random order on $\mathcal{G}$, then

$\mathbb{E}[U(x^{GL}({\bf a},{\Sigma}))]\geq 1-\kappa.$

We now show that in this setting the outcome is $(1-2\kappa)$-fair. Our goal
is to show that for any pair of agents $i,j\in\mathcal{N}$,

(52) $\frac{u_{i}(\pi^{GL}({\bf a}))}{u_{j}(\pi^{GL}({\bf a}))}\geq
1-2\kappa.$

By Lemma 2, we can assume without loss of generality that

(53) $\displaystyle|G_{i}|$ $\displaystyle=\max_{G\in\mathcal{G}}|G|\text{ and
}|G_{j}|=\min_{G\in\mathcal{G}}|G|.$

We let $\mu^{-i}$ be the average group size in $\mathcal{G}\setminus G_{i}$,
more precisely,

(54) $\mu^{-i}=\frac{n-|G_{i}|}{m-1}.$

We claim that

(55) $\displaystyle\frac{u_{i}(\pi^{GL}({\bf a}))}{u_{j}(\pi^{GL}({\bf a}))}$
$\displaystyle\geq\frac{k-2|G_{i}|+1+\mu^{-i}}{k-|G_{j}|+\mu^{-i}}.$

This implies our result as

$\frac{k-2|G_{i}|+1+\mu^{-i}}{k-|G_{j}|+\mu^{-i}}\geq\frac{k-2|G_{i}|+1+|G_{j}|}{k}\geq
1-\frac{2(|G_{i}|-1)}{k}\geq 1-2\kappa.$

In the first inequality, we apply Fact 1 with $a=k-2|G_{i}|+1+|G_{j}|$, $b=k$
and $c=\mu^{-i}-|G_{j}|$. The last inequality follows from the definition of
$I(\kappa,\alpha)$ in (5). Remember that for any instance in
$I(\kappa,\alpha)$, we have

$\frac{|G_{i}|-1}{k}=\frac{\max_{G\in\mathcal{G}}|G|-1}{k}\leq\kappa.$

We now turn to the proof of equation (55). Let ${\Sigma}^{-i}$ be a uniform
order on $\mathcal{G}\setminus G_{i}$. Applying Lemma 4 to agents $i,j$, it
follows that

(56) $\frac{u_{i}(x^{GL}({\bf a},{\Sigma}))}{u_{j}(x^{GL}({\bf
a},{\Sigma}))}=\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-j})]}.$

By Proposition 5 equation (12), we have

(57)
$\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-j})]\leq\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-j})]+\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-j})].$

We claim that for any constant $c\in\mathbb{N}$, such that $c\leq
n-|G_{i}|=\sum_{t}|{\Sigma}^{-i}_{t}|$,

(58) $\mathbb{E}[\tau(c,{\Sigma}^{-j})]\leq\mathbb{E}[\tau(c,{\Sigma}^{-i})].$

We now show (58). We generate ${\Sigma}^{-i}$ using ${\Sigma}^{-j}$ in the
following way:

${\Sigma}^{-i}_{t}({\Sigma}^{-j})=\begin{cases}{\Sigma}^{-j}_{t}&\text{if
}{\Sigma}^{-j}_{t}\neq G_{i},\\\ G_{j}&\text{otherwise}.\end{cases}$

Note that by construction for any ${\Sigma}^{-j}$,
$\tau(c,{\Sigma}^{-i}({\Sigma}^{-j}))\geq\tau(c,{\Sigma}^{-j})$. This
establishes (58). Applying (58) twice we get

(59)
$\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-j})]+\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-j})]\leq\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]+\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-i})].$

Then by (57) and (59),

(60)
$\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{j}|+1,{\Sigma}^{-j})]}\geq\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]+\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-i})]}.$

By Proposition 5 equation (11), we have

(61) $\displaystyle\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]$
$\displaystyle\geq\frac{k-2|G_{i}|+1+\mu^{-i}}{\mu^{-i}},$ (62)
$\displaystyle\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-i})]$
$\displaystyle\leq\frac{2|G_{i}|-|G_{j}|-1}{\mu^{-i}}.$

From (61) and (62), we have

$\displaystyle\frac{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]}{\mathbb{E}[\tau(k-|G_{i}|+1,{\Sigma}^{-i})]+\mathbb{E}[\tau(|G_{i}|-|G_{j}|,{\Sigma}^{-i})]}$
$\displaystyle\geq\frac{k-2|G_{i}|+1+\mu^{-i}}{k-2|G_{i}|+1+\mu^{-i}+2|G_{i}|-|G_{j}|-1}$
$\displaystyle=\frac{k-2|G_{i}|+1+\mu^{-i}}{k-|G_{j}|+\mu^{-i}}.$

∎

####  A.2.1. Tightness

###### Proposition 0.

For any $\epsilon>0$ and $\alpha\in(0,1)$, there exists $\kappa\in(0,1)$ and
an instance in $I(\kappa,\alpha)$ such that the group request equilibrium
outcome of the Group Lottery is not $1-(2-\epsilon)\kappa$ fair.

###### Proof of Proposition 3.

We consider an instances in which there is one “single person” (group of size
one), and the remaining groups are “couples” (groups of size two). Fix
$r\in\mathbb{N}$ such that

(63) $\frac{1}{r}<\epsilon,$

and set $k=2r-1$ and $\kappa=1/k$. Let $m$ be the total number of groups, and
note that for all sufficiently large $m$, the instance will be in
$I(\kappa,\alpha)$.

The single person is successful if among the first $r$ groups (which occurs
with probability $\frac{r}{m}$), while each couple is successful if among the
first $r-1$ couples (which occurs with probability $\frac{r-1}{m-1}$). Thus,
as $m\rightarrow\infty$, the ratio of the utility each couple to the utility
of the single person converges to

$\frac{r-1}{r}<1-\frac{2-\epsilon}{2r-1}=1-(2-\epsilon)\kappa,$

where the first equality follows from (63). ∎

###  A.3. Proof of Proposition 6

We divide the proof into two parts: Lemma 4 establishes that for any instance
in $I(\kappa,\alpha)$, there exists a random allocation that is
$(1-\kappa)$-efficient and fair. Lemma 5 shows that improving beyond
$(1-\kappa)$-efficiency may require abandoning even approximate fairness.

###### Lemma 0.

Fix $\kappa,\alpha\in(0,1)$. For every instance in $I(\kappa,\alpha)$, there
exist a random allocation that is $(1-\kappa)$-efficient and fair.

###### Proof of Lemma 4.

We claim that there exists of a random allocation $\pi^{*}$ such that for
every agent $i\in\mathcal{N}$,

(64) $u_{i}(\pi^{*})=u^{*}=\frac{k-\max_{G\in\mathcal{G}}|G|+1}{n}.$

It immediately follows that $\pi^{*}$ is fair as the utility of every agent is
equal to $u^{*}$. Moreover, the utilization in this system is

$U(\pi^{*})=\frac{nu^{*}}{k}=1-\frac{\max_{G}|G|-1}{k}\geq 1-\kappa.$

The inequality follows because our instance is in $I(\kappa,\alpha)$.

All that remains is to prove our claim. To this end, we will apply Theorem 2.1
in Nguyen et al. (2016) which establishes that any utility vector such that
(i) the sum of all agents’ utilities is at most
$k-\max_{G\in\mathcal{G}}|G|+1$, and (ii) members of each group receive the
same utility, can be induced by a lottery over feasible allocations. Before
formally presenting this result some definitions are needed.

A group allocation is represented by $x\in\\{0,\ldots,k\\}^{m}$ satisfying
$\sum_{G\in\mathcal{G}}x_{G}\leq k$, where $x_{G}$ represents the number of
tickers assigned to group $G$. For simplicity, we restrict to allocations such
that for every group $G$, $x_{G}\in\\{0,|G|\\}$. Notice that a group $G$ is
successful if and only if $x_{G}=|G|$. A random group allocation correspond to
a distribution $\pi$ over the set of group allocations. A group utility vector
$u\in[0,1]^{m}$ associates to each group $G$ a utility $u_{G}$.

Theorem 2.1 in Nguyen et al. (2016) establishes that if a group utility vector
$u^{\prime}$ satisfies

(65) $\sum_{G\in\mathcal{G}}|G|u^{\prime}_{G}\leq
k-\max_{G\in\mathcal{G}}|G|+1,$

then it can be induced by a random group allocation, that is, there exists a
random allocation $\pi$ such that

$u_{i}(\pi)=u^{\prime}_{G}\text{ for every }G\in\mathcal{G},i\in G.$

Observe that the expected number of tickets awarded to each group is equal to
the sum of the utilities of its members. Therefore, condition (65) can be
interpreted as an upper bound on the total expected number of tickets awarded,
which depends on the maximum number of tickets demanded by a single group.

Hence, the existence of a random allocation $\pi^{*}$ that yields (64) follows
by letting $\hat{u}$ be the utility vector that gives each group a utility of
$u^{*}$. Note that $\hat{u}$ satisfies condition (65) as

$\sum_{i\in\mathcal{N}}\hat{u}_{i}=nu^{*}=k-\max_{G\in\mathcal{G}}|G|+1.$

∎

###### Lemma 0.

For any $\epsilon>0$, there exists $\alpha,\kappa\in(0,1)$ and an instance in
$I(\kappa,\alpha)$ such that no random allocation is $\epsilon$-fair and
$(1-\kappa+\epsilon)$-efficient.

###### Proof of Lemma 5.

Fix $\epsilon>0$ and let $m,s,r\in\mathbb{N}$. We consider an instance with
$k=rs-1$ tickets, one group of size $s-1$ and $m-1$ groups of size $s$. Let
$i$ be a member of the group of size $s-1$. Let $\pi$ be any random
allocation. Because at most $r-1$ of the large groups can be satisfied in any
deterministic allocation, we have that

(66) $s(m-1)\min_{j\not\in G_{i}}\\{u_{j}(\pi)\\}\leq\sum_{j\not\in
G_{i}}u_{j}(\pi)\leq s(r-1).$

If the allocation is $\epsilon$-fair, then it must be the case that

(67) $\epsilon u_{i}(\pi)\leq\min_{j\not\in
G_{i}}\\{u_{j}(\pi)\\}\leq\frac{r-1}{m-1},$

where the right inequality follows from (66).

Observe that if $G_{i}$ is successful then there will be no tickets wasted;
otherwise, there will be $s-1$ tickets wasted. Hence, the utilization under
$\pi$ is

(68) $1-\left(1-u_{i}(\pi)\right)\frac{s-1}{k}\leq
1-\left(1-\frac{r-1}{\epsilon(m-1)}\right)\frac{s-1}{k}.$

If we choose $r,m$ such that $(r-1)/(m-1)<\epsilon^{2}k/(s-1)$, and define
$\kappa=(s-1)/k$ and $\alpha=k/n$, then our instance is in $I(\kappa,\alpha)$,
and (68) implies that utilization is strictly smaller than
$1-\kappa+\epsilon$. ∎

##  Appendix B Individual Lottery

###  B.1. Incentives

###### Proof of Proposition 8.

This is a direct consequence of Proposition 1. Notice that for any given
instance with $k$ tickets, the Individual Lottery is equivalent to the
Individual Lottery with limit $\ell=k$. Therefore, $r=\lceil|G|/k\rceil=1$ and
our result follows. ∎

###### Proof of Proposition 9.

Consider any agent $i$. We let ${\bf a}_{-i}\in A_{-i}$ be an arbitrary set of
actions and $a_{i}^{\prime}>a_{i}\geq|G_{i}|.$ We begin by showing that for
any order over agents ${\sigma}$, the conditional expected utility of $i$ is
the same under both strategies. We consider two possible cases. First, the
number of tickets remaining before agent $i$ is processed is $a_{i}$ or less.
Then, under both strategies the allocation of every agent is the same and the
payoff of $G_{i}$ coincide. Second, the number of tickets remaining before
agent $i$ is processed is greater than $a_{i}$. Then, under both strategies
agent $i$ obtains at least $|G_{i}|$ tickets and the group gets a payoff of
$1$.

Now, we will show that the utility of every group $G\neq G_{i}$ is weakly
better under $a_{i}$. It suffices to show that for any order
$\sigma\in\mathcal{O}_{N}$,

(69) $x^{IL}_{j}((a_{i},{\bf a}_{-i}),\sigma)\geq
x^{IL}_{j}((a_{i}^{\prime},{\bf a}_{-i}),\sigma)~{}\text{for every agent
}j\neq i.$

Because this holds for any order ${\sigma}$, and the random order over agents
used in the Individual Lottery is uniformly distributed, this implies our
result. Let $T=T(\sigma)$ be the position of agent $i$ in ${\sigma}$, that is,
$T=\\{t\in\\{1,\ldots,n\\}:\sigma_{t}=i\\}$. The allocation of agents
$\sigma_{1},\ldots,\sigma_{T-1}$ is not affected by the action of $i$, then
(69) holds. A smaller request can only lead to a smaller allocation, hence the
allocation of agent $i$ is weakly smaller under $a_{i}$. Therefore, the
allocation of agents $\sigma_{T+1},\ldots,\sigma_{n}$ is weakly greater under
$a_{i}$ as the only difference is due to agent $i$. ∎

###  B.2. Performance

###### Proof of Theorem 10.

Consider an instance with $n=rs$ agents divided into one large group of size
$s$ and $s(r-1)$ small groups of size one. Besides, the number of tickets is
$k=\lfloor\alpha r\rfloor s$. Observe that for any $s,r\in\mathbb{N}$,

$\frac{k}{n}=\frac{\lfloor\alpha r\rfloor s}{rs}\leq\alpha.$

Thus, if $(s-1)/k\leq\kappa$ then this instance will be in $I(\kappa,\alpha)$.
We claim that a sufficient condition for this is

(70) $r\geq\frac{\kappa+1}{\alpha\kappa}.$

This can be seen as

$\frac{s-1}{k}=\frac{s-1}{\lfloor\alpha r\rfloor s}\leq\frac{1}{\alpha
r-1}\leq\kappa.$

In the first inequality we use that for any $x$, $\lfloor x\rfloor\geq x-1$
and $(s-1)/s\leq 1$. The last inequality follows from (70). For ease of
exposition, in the proof sketch of Theorem 10 we consider $n$ agents, a large
group of size $s=n^{3/4}$ and $k=\alpha n$ tickets.

Let agents $i,j$ be such that $|G_{i}|=1$ and $|G_{j}|=s$. We claim that for
any dominant strategy equilibrium ${\bf a}$,

(71) $u_{i}(\pi^{IL}({\bf a}))\leq\frac{k}{s^{2}}\leq\frac{\alpha r}{s}.$

This bound is key to prove both guarantees. We start by proving the efficiency
result. The expected utilization in this system is:

$\displaystyle\frac{1}{k}\sum_{i^{\prime}\in\mathcal{N}}u_{i^{\prime}}(\pi^{IL}({\bf
a}))$ $\displaystyle=\frac{s}{k}\left((r-1)u_{i}(\pi^{IL}({\bf
a}))+u_{j}(\pi^{IL}({\bf a})\right)$
$\displaystyle\leq\frac{r-1}{s}+\frac{s}{k}$
$\displaystyle=\frac{r-1}{s}+\frac{1}{\lfloor\alpha r\rfloor}.$

In the inequality we use that $u_{j}(\pi^{IL}({\bf a}))\leq 1$ and the first
inequality in (71). Hence, if we choose $s=s(r)$ such that $r/s(r)\to 0$ as
$r$ grows, then the right side goes to $0$ as we take the limit.

We now turn to the fairness guarantee. Because the first agent to be processed
always get a payoff of $1$, we get that

$u_{j}(\pi^{IL}({\bf a}))\geq\frac{s}{n}=\frac{1}{r}.$

Note that this lower bound is independent of $s$, and is tight when all agents
in small groups request $k$ tickets.

Using this and the second inequality in (71), we obtain

$\frac{u_{i}(\pi^{IL}({\bf a}))}{u_{j}(\pi^{IL}({\bf a}))}\leq\frac{\alpha
r^{2}}{s}.$

Therefore, if we choose $s=s(r)$ such that $r^{2}/s(r)\to 0$ as $r$ grows,
then again the right side goes to $0$ as we take the limit.

All that remains is to prove (71). We let ${\Sigma}$ be a random order over
agents. To generate ${\Sigma}$ we use Algorithm 2 from Lemma 1: set
$S=G_{i}\cup G_{j}$, and independently generate (i) a uniform random order
${\Sigma}^{S}$ over $S$, (ii) a uniform random order ${\Sigma}^{-}$ over
$\mathcal{N}\setminus S$, and (iii) uniform random positions
$P\subseteq\\{1,\ldots,|\mathcal{N}|\\}$ where agents in $S$ will be placed.
By Lemma 1, the resulting order ${\Sigma}$ is uniformly distributed. Note that
$i$ will get a payoff 0 unless it appears in the first $k/s$ positions of
${\Sigma}^{S}$. Because ${\Sigma}^{S}$ is uniformly distributed this event
occurs with probability

$\frac{k/s}{s+1}\leq\frac{k}{s^{2}}.$

This implies (71) and concludes our proof. ∎

###  B.3. Extension

###### Proposition 0.

In the Individual Lottery with limit $\ell$, the set of actions ${\bf a}_{G}$
is dominant for group $G$ if and only if $\sum_{i\in S}a_{i}\geq|G|$ for all
$S\subseteq G$ such that $|S|=\lceil|G|/\ell\rceil$.

###### Proof of Proposition 1.

Fix an arbitrary agent $i$. Let ${\bf a}_{-G_{i}}\in A_{-G_{i}}$ be an
arbitrary action profile for agents not in $G_{i}$. We let
$r=\lceil|G_{i}|/\ell\rceil$ be the minimum number of members of $G_{i}$ that
must be awarded in the Individual Lottery with limit $\ell$ in order for
$G_{i}$ to get a payoff of $1$. Let ${\bf a}_{G_{i}}\in A_{G_{i}}$ be any
action profile such that $\sum_{j\in S}a_{j}\geq|G_{i}|$ for all $S\subseteq
G_{i}$ such that $|S|=r$.

First, we show that for any order $\sigma\in\mathcal{O}_{\mathcal{N}}$ the
utility of agent $i$ is maximized under ${\bf a}_{G_{i}}$, that is,

(72) $u_{i}(x^{IL}(({\bf a}_{G_{i}},{\bf a}_{-{G_{i}}}),\sigma))\geq
u_{i}(x^{IL}(({\bf a}^{\prime}_{G_{i}},{\bf a}_{-G_{i}}),\sigma)),\text{ for
every }{\bf a}^{\prime}_{G_{i}}\in A_{G_{i}}.$

Because this holds for any order $\sigma$, the expected utility of group
$G_{i}$ will also be maximized by ${\bf a}_{G_{i}}$. Let $T=T(\sigma)$ be the
position of the $r^{th}$ member of $G_{i}$ under $\sigma$:

$T(\sigma)=\min\\{t\in\\{1,\ldots,n\\}:\left|\sigma_{[t]}\cap
G_{i}\right|=r\\}.$

If $\sum_{j\in\sigma_{[T]}\setminus G_{i}}a_{j}>k-|G_{i}|$, then for any
action profile selected by group $G_{i}$ its payoff is 0.

If $\sum_{j\in\sigma_{[T]}\setminus G_{i}}a_{j}\leq k-|G_{i}|$, then under
action profile ${\bf a}_{G_{i}}$ group $G_{i}$ receives a payoff of 1.

Hence, ${\bf a}_{G_{i}}$ maximizes the payoff of agent $i$ for each $\sigma$.

Second, let $\hat{\bf a}_{G_{i}}$ be such that $\sum_{j\in
S}\hat{a}_{j}<|G_{i}|$ for some $S\subseteq G_{i}$ with $|S|=r$. We will show
that there exists an order $\hat{\sigma}\in\mathcal{O}_{\mathcal{N}}$ such
that

$1=u_{i}(x^{IL}(({\bf a}_{G_{i}},{\bf
a}_{-G_{i}}),\hat{\sigma}))>u_{i}(x^{IL}((\hat{\bf a}_{G_{i}},{\bf
a}_{-G_{i}}),\hat{\sigma}))=0.$

This combined with (72) implies that $\hat{\bf a}_{G_{i}}$ is dominated by
${\bf a}_{G_{i}}$. We construct $\hat{\sigma}$ in the following way:

  * •

Agents in $S$ are arbitrary placed in the first $r$ positions of
$\hat{\sigma}$.

  * •

Agents in $\mathcal{N}\setminus G_{i}$ are arbitrary placed in positions
$r+1,\ldots,r+n-|G_{i}|$ of $\hat{\sigma}$.

  * •

Agents in $G_{i}\setminus S$ are arbitrary placed in the last $|G_{i}|-r$
positions of $\hat{\sigma}$.

We begin by proving that if ${\bf a}_{G_{i}}$ is selected then $G_{i}$
received at least $|G_{i}|$ tickets, implying that $u_{i}(x^{IL}(({\bf
a}_{G_{i}},{\bf a}_{-G_{i}}),\hat{\sigma}))=1$. To see this note that the
number of tickets received by $G_{i}$ is

$\sum_{j\in G}x^{IL}_{j}(({\bf a}_{G_{i}},{\bf
a}_{-G_{i}}),\hat{\sigma})\geq\sum_{j\in S}x^{IL}_{j}(({\bf a}_{G_{i}},{\bf
a}_{-G_{i}}),\hat{\sigma})\geq\min\\{k,\sum_{j\in S}a_{j}\\}\geq|G_{i}|.$

The last inequality follows as $k\geq|G_{i}|$ and $\sum_{j\in
S}a_{j}\geq|G_{i}|$. On the other hand, we show that when $\hat{\bf
a}_{G_{i}}$ is selected then $G_{i}$ received strictly less than $|G_{i}|$
tickets and $u_{i}(x^{IL}((\hat{\bf a}_{G_{i}},{\bf
a}_{-G_{i}}),\hat{\sigma}))=0$. For the sake of contradiction, suppose that
$|G_{i}|$ received at least $|G_{i}|$ tickets, then

$\sum_{j\in\mathcal{N}}x^{IL}_{j}(({\bf a}_{G_{i}},\hat{\bf
a}_{-G_{i}}),\hat{\sigma})=\sum_{j\in G_{i}}x^{IL}_{j}(({\bf
a}_{G_{i}},\hat{\bf a}_{-G_{i}}),\hat{\sigma})+\sum_{j\in\mathcal{N}\setminus
G_{i}}x^{IL}_{j}(({\bf a}_{G_{i}},\hat{\bf
a}_{-G_{i}}),\hat{\sigma})\geq|G_{i}|+\sum_{j\in\mathcal{N}\setminus
G_{i}}1=n.$

A contradiction, as $k<n$. Note that $G_{i}$ will get $|G_{i}|$ or more
tickets only if agent in position $r+n-|G_{i}|+1$ is awarded, this implies
that all agents in the first $r+n-|G_{i}|$ must also be awarded. ∎

###### Proof of Proposition 11.

Consider a sequence of instances with $n\rightarrow\infty$ and a constant $k$
number of tickets. In each instance, there is one group of size $1$ and the
remaining groups have size $\ell+1$. We let $i$ be such that $|G_{i}|=1$ and
$j$ be such that $|G_{j}|=\ell+1$. We let ${\Sigma}$ be a uniform order over
agents.

First, note that regardless of the action profile ${\bf a}$, $i$ gets utility
$1$ if among the first $\lceil k/\ell\rceil$ agents in ${\Sigma}$, and gets
utility $0$ if after the first $k$ agents. Because ${\Sigma}$ is drawn
uniformly at random from $\mathcal{O}_{\mathcal{N}}$, we have

(73) $\frac{\lceil k/\ell\rceil}{n}\leq u_{i}(\pi^{IL}({\bf
a}))\leq\frac{k}{n}.$

Second, because $\ell<|G_{j}|$, at least two agents from group $G_{j}$ must be
awarded in order for the group to get utility $1$. Furthermore, any agent not
among the first $k$ will certainly not receive any tickets. Therefore, group
$G_{j}$ gets utility $1$ only if some pair of agents from $G_{j}$ are both
among the first $k$ agents. For any pair of agents, the chance that both are
among the first $k$ agents is $\binom{n-2}{k-2}/\binom{n}{k}$. Applying a
union bound, we see that

(74) $u_{j}(\pi^{IL}({\bf
a}))\leq\frac{\binom{n-2}{k-2}\binom{\ell+1}{2}}{\binom{n}{k}}=\frac{k(k-1)}{n(n-1)}\binom{\ell+1}{2}.$

Combining the upper bounds derived in (73) and (74), we bound the overall
efficiency as follow

$\displaystyle\frac{1}{k}\sum_{i^{\prime}\in\mathcal{N}}u_{i^{\prime}}(\pi^{IL}({\bf
a}))$
$\displaystyle\leq\frac{1}{k}\left(\frac{k}{n}+(n-1)\frac{k(k-1)}{n(n-1)}\binom{\ell+1}{2}\right)=\frac{2+(k-1)(\ell+1)\ell}{2n},$

which approaches zero as $n$ grows.

Furthermore, (73) and (74) imply that

$\frac{u_{j}(\pi^{IL}({\bf a}))}{u_{i}(\pi^{IL}({\bf
a}))}\leq\frac{\frac{k(k-1)}{n(n-1)}\binom{\ell+1}{2}}{\frac{\lceil
k/\ell\rceil}{n}}=\frac{k(k-1)}{\lceil k/\ell\rceil(n-1)}\binom{\ell+1}{2},$

which also approaches zero as $n$ grows. ∎

###### Proposition 0.

For any $\ell\in\mathbb{N}$ and any instance such
$\max_{G\in\mathcal{G}}|G|\leq\ell$, every dominant strategy equilibrium
outcome of the Individual Lottery with limit $\ell$ is $1/\ell-$efficient.

###### Proof of Proposition 2.

We let ${\Sigma}$ be a uniform order over agents. We claim that if ${\bf
a}_{G_{i}}$ is dominant for $G_{i}$, then

(75) $\mathbb{E}[u_{i}(x^{IL}({\bf a},\Sigma))]\geq\frac{k}{\ell n}.$

From this, it follows that if ${\bf a}$ is such that all agents follow a
dominant strategy, then

$\mathbb{E}[U(x^{IL}({\bf
a},\Sigma))]=\frac{1}{k}\sum_{i\in\mathcal{N}}\mathbb{E}[u_{i}(x^{IL}({\bf
a},\Sigma))]\geq\frac{1}{\ell}.$

We now prove (75). If $|G_{i}|=1$, then no matter the reports of others, $i$
succeeds if in the first $\lceil k/\ell\rceil$ positions, which occurs with
probability $\frac{\lceil k/\ell\rceil}{n}\geq\frac{k}{\ell n}$.

Otherwise, because $\max_{G\in\mathcal{G}}|G|\leq\ell$ and agents in $G_{i}$
follow a dominant strategy, $i$ succeeds if any agent from $G_{i}$ is in the
first $\lfloor k/\ell\rfloor$ positions.

If $k/\ell<2$, then this occurs with probability
$\frac{|G_{i}|}{n}\geq\frac{k}{\ell n}$. Thus, we turn to the case with
$\min(|G_{i}|,k/\ell)\geq 2$. Fix two agents in $G_{i}$. The chance that at
least one of them is in the first $\lfloor k/\ell\rfloor$ positions is

$\displaystyle\frac{2\lfloor k/\ell\rfloor}{n}-\frac{\binom{n-2}{\lfloor
k/\ell\rfloor-2}}{\binom{n}{\lfloor k/\ell\rfloor}}$
$\displaystyle\geq\frac{2\lfloor k/\ell\rfloor}{n}-\left(\frac{\lfloor
k/\ell\rfloor}{n}\right)^{2}$
$\displaystyle\geq\frac{k/\ell-1}{n}+\frac{\lfloor
k/\ell\rfloor}{n}-\left(\frac{\lfloor k/\ell\rfloor}{n}\right)^{2}$
$\displaystyle=\frac{k}{\ell n}-\frac{1}{n}+\frac{\lfloor
k/\ell\rfloor}{n}\left(1-\frac{\lfloor k/\ell\rfloor}{n}\right).$

All that remains is to establish that

$\frac{\lfloor k/\ell\rfloor}{n}\left(1-\frac{\lfloor
k/\ell\rfloor}{n}\right)\geq\frac{1}{n}.$

This holds because $\lfloor k/\ell\rfloor\geq 2$ by assumption, and
$1-\frac{\lfloor k/\ell\rfloor}{n}\geq 1-1/\ell\geq 1/2$. ∎

###### Proposition 0.

For any $\ell\in\mathbb{N}$ and any instance such that
$\max_{G\in\mathcal{G}}|G|\leq\ell$, every dominant strategy equilibrium
outcome of the Individual Lottery with limit $\ell$ is $1/\ell-$fair.

###### Proof of Proposition 3.

We construct a random order over agents ${\Sigma}$ using Algorithm 2: set
$S=G_{i}\cup G_{j}$, and independently generate (i) a uniform random order
${\Sigma}^{S}$ over $S$, (ii) a uniform random order ${\Sigma}^{-}$ over
$\mathcal{N}\setminus S$, and (iii) uniform random positions
$P\subseteq\\{1,\ldots,|\mathcal{N}|\\}$ where agents in $S$ will be placed.
By Lemma 1, the resulting order ${\Sigma}$ is uniformly distributed.

Without loss of generality, we assume

(76) $\ell\geq|G_{i}|\geq|G_{j}|.$

We let

(77) $\displaystyle\tau_{i}({\Sigma}^{-})$
$\displaystyle=\tau(k-|G_{i}|+1,{\Sigma}^{-}),$ (78)
$\displaystyle\tau_{j}({\Sigma}^{-})$
$\displaystyle=\tau(k-|G_{j}|+1,{\Sigma}^{-})-\tau(k-|G_{i}|+1,{\Sigma}^{-}),$

be as defined in (6) where the size of each agent is its request, that is,
$|{\sigma}_{t}|=a_{{\sigma}_{t}}$. Note that by definition,

(79) $1\leq\tau_{i}({\Sigma}^{-}),\hskip 14.45377pt\text{ and }\hskip
14.45377pt\tau_{j}({\Sigma}^{-})\leq|G_{i}|-|G_{j}|.$

In addition, for $s\in\\{1,\ldots,|S|\\}$ let $T_{s}(P)$ be the $s^{th}$
smallest value in $P$, so $T_{1}(P)$ denotes the first position of ${\Sigma}$
containing a member of $G_{i}\cup G_{j}$. Note that

$\mathbb{P}(T_{1}(P)=t)=\left(\frac{|G_{i}|+|G_{j}|}{n}\right)\frac{\binom{n-t}{|G_{i}|+|G_{j}|-1}}{\binom{n-1}{|G_{i}|+|G_{j}|-1}},$

which is decreasing in $t$. From this, it follows that for any ${\Sigma}^{-}$,

(80)
$\frac{\mathbb{P}(T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})}{\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})}\leq\frac{\tau_{i}+\tau_{j}}{\tau_{i}}\leq
1+|G_{i}|-|G_{j}|,$

where the second inequality comes from (79). Our final definition is to let

(81) $A_{i}=\\{{\Sigma}^{S}_{1}\in G_{i}\\},\hskip
36.135ptA_{j}=\\{{\Sigma}_{1}^{S}\in G_{j}\\},$

and note that

(82) $\mathbb{P}(A_{i})=\frac{|G_{i}|}{|G_{i}|+|G_{j}|}=1-\mathbb{P}(A_{j}).$

Definitions out of the way, we proceed with the proof. Note that

$\frac{u_{j}(\pi^{IL}({\bf a}))}{u_{i}(\pi^{IL}({\bf
a}))}=\frac{\mathbb{E}[\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]]}{\mathbb{E}[\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]]}\leq\max_{{\sigma}^{-}}\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}={\sigma}^{-}]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}={\sigma}^{-}]}.$

Therefore, to establish $1/\ell$ fairness, it suffices to show that for every
${\Sigma}^{-}$,

(83) $\frac{1}{\ell}\leq\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}\leq\ell.$

We claim that

(84)
$\mathbb{P}(A_{i})\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})\leq\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]\leq\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-}).$

The left inequality follows because whenever $T_{1}\leq\tau_{i}$ and a member
of $G_{i}$ comes before all members of $G_{j}$, group $G_{i}$ gets a payoff of
$1$. The right inequality follows because the definition of $\tau_{i}$ ensures
that $G_{i}$ can get a payoff of one only if a member of $G_{i}$ is in the
first $\tau_{i}$ positions of ${\Sigma}$. By analogous reasoning, we have

(85)
$\mathbb{P}(A_{j})\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})\leq\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]\leq\mathbb{P}(T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})-\mathbb{P}(A_{i})\mathbb{P}(\tau_{i}<T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-}),$

where the right inequality follows because in order for group $G_{j}$ to get
utility one, we must have $T_{1}\leq\tau_{i}+\tau_{j}$, and if
$T_{1}\in(\tau_{i},\tau_{i}+\tau_{j}]$, then a member of $G_{j}$ must appear
before all members of $G_{i}$.

We now prove the upper-bound in (83). Combining (84) and (85), we see that

$\displaystyle\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}$
$\displaystyle\leq\frac{\mathbb{P}(T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})-\mathbb{P}(A_{i})\mathbb{P}(\tau_{i}<T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})}{\mathbb{P}(A_{i})\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})}$
$\displaystyle=\frac{\mathbb{P}(T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})(1-\mathbb{P}(A_{i}))+\mathbb{P}(A_{i})\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})}{\mathbb{P}(A_{i})\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})}$
$\displaystyle=\frac{|G_{j}|}{|G_{i}|}\frac{\mathbb{P}(T_{1}\leq\tau_{i}+\tau_{j}|{\Sigma}^{-})}{\mathbb{P}(T_{1}\leq\tau_{i}|{\Sigma}^{-})}+1$
$\displaystyle\leq\frac{|G_{j}|-|G_{j}|^{2}}{|G_{i}|}+|G_{j}|+1$ (86)
$\displaystyle\leq\ell.$

The second inequality uses (80). The final inequality follows because if
$|G_{j}|=\ell$, then $|G_{i}|=\ell$ by (76), and thus the expression is equal
to $2$;141414We assume $\ell\geq 2$ because if $\ell=1$ and all groups have
size one, the individual lottery simply selects $k$ agents uniformly at
random, and is perfectly fair. if $|G_{j}|<\ell$, then the expression is at
most $\ell$ because $\frac{|G_{j}|-|G_{j}|^{2}}{|G_{i}|}\leq 0$.

Meanwhile, (84) and (85) also imply that

(87) $\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}\geq\mathbb{P}(A_{j})=\frac{|G_{j}|}{|G_{i}|+|G_{j}|}.$

If $|G_{i}|<\ell$ or $|G_{j}|>1$, the ratio on the right is at least $1/\ell$,
and the proof is complete. Thus, all that remains is to show that the lower
bound in (83) holds when $|G_{i}|=\ell$ and $|G_{j}|=1$.

Our analysis will condition on both ${\Sigma}^{-}$ and $P$. We note that

$\mathbb{E}[u_{i}(x({\bf a},{\Sigma}))|{\Sigma}^{-},P]>0\Leftrightarrow
T_{1}(P)\leq\tau_{i}({\Sigma}^{-}).$

Therefore,

$\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-}]}=\frac{\mathbb{E}_{P}[\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]]}{\mathbb{E}_{P}[\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]]}\geq\min_{P:\,\,T_{1}(P)\leq\tau_{i}({\Sigma}^{-})}\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}.$

We will show that the quantity on the right is at least $1/\ell$. To do this,
we let

(88) $\tau_{ij}({\Sigma}^{-})=\tau(k-|G_{j}|-|G_{i}|+1,{\Sigma}^{-}),$

be as defined in (6) with size function $|{\sigma}_{t}|=a_{{\sigma}_{t}}$. If
$T_{2}(P)\leq\tau_{ij}({\Sigma}^{-})$, then because each agent requests at
most $\ell=|G_{i}|$ tickets, agent $j$ will receive utility of one if first or
second in ${\Sigma}^{S}$. Thus,

$\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}\geq\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]\geq\frac{2}{\ell+1}\geq\frac{1}{\ell}.$

Meanwhile, if $T_{2}(P)>\tau_{ij}({\Sigma}^{-})$, then each group gets utility
$1$ only if one of its members is first in ${\Sigma}^{S}$. In this case,

$\frac{\mathbb{E}[u_{j}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}{\mathbb{E}[u_{i}(x({\bf
a},{\Sigma}))|{\Sigma}^{-},P]}=\frac{\mathbb{P}(A_{j})}{\mathbb{P}(A_{i})}=\frac{1}{\ell}.$

∎

##  Appendix C Weighted Individual Lottery

###  C.1. Incentives

###### Proposition 0.

Algorithm 1 generates a random order ${\Sigma}\in\mathcal{O}_{\mathcal{N}}$
distributed according to (18) conditional on ${\bf a}$.

###### Proof of Proposition 1.

Fix any order ${\sigma}$ over $\mathcal{N}$. Let $Y_{j}=a_{j}X_{j}$. It
follows that $\mathbb{P}(Y_{j}>t)=e^{-t/a_{j}}$, so each $Y_{j}$ is
distributed as an exponential random variable with mean $a_{i}$. Moreover, the
$Y_{j}$ are independent. Let ${\Sigma}$ be the order generated by the
algorithm. We have that

$\mathbb{P}({\Sigma_{1}}=j)=\mathbb{P}(Y_{j}=\min_{i\in\mathcal{N}}Y_{i})=\frac{1/a_{j}}{\sum_{i\in\mathcal{N}}1/a_{i}},$

where the second equality follows from well-known properties of the minimum of
exponential random variables.151515See e.g.
https://en.wikipedia.org/wiki/Exponential_distribution. Furthermore, the
definition of $\Sigma$ and the memoryless property of exponential random
variables imply that for $t\in\\{1,\ldots,n\\}$ and $j\not\in\Sigma_{[t-1]}$,

$\mathbb{P}({\Sigma_{t}}=j|\Sigma_{[t-1]})=\mathbb{P}(Y_{j}=\min_{i\in\mathcal{N}\backslash\Sigma_{[t-1]}}Y_{i})=\frac{1/a_{j}}{\sum_{i\in\mathcal{N}\backslash\Sigma_{[t-1]}}1/a_{i}}.$

This implies that

$\Pr(\Sigma=\sigma)=\prod_{t=1}^{n}\mathbb{P}({\Sigma_{t}}=\sigma_{t}|\Sigma_{[t-1]}=\sigma_{[t-1]})=\prod_{t=1}^{n}\frac{1/a_{\sigma_{t}}}{\sum\limits_{i\in\mathcal{N}\backslash\sigma_{[t-1]}}1/a_{i}},$

as claimed. ∎

###### Proof of Proposition 12.

We start by proving that agents have no incentives to request more tickets
than their group size. Formally, if we let $i\in G$, $a_{i}=|G|$ and
$a^{\prime}_{i}>|G|$ then for every action profile ${\bf a}_{-i}\in A_{-i}$,

$u_{i}(\pi^{IW}(a_{i},{\bf a}_{-i}))\geq u_{i}(\pi^{IW}(a^{\prime}_{i},{\bf
a}_{-i})).$

This follows because the set of orders over agents in which $G$ get a payoff
of $1$ is the same under both strategies, and by reducing its request agent
$i$ improves her probability of being drawn early.

We now show that if group $G$ is such that $|G|\leq 3$, then selecting group
request ${\bf a}_{G}$ is dominant for $G$. Given an action profile ${\bf a}\in
A$, we generate a random order over agents ${\Sigma}$ using the Algorithm 1:
we draw iid exponential random variables $X_{i}$ for each agent $i$, and sort
agents in increasing order according to $a_{i}X_{i}$. From Proposition 1, it
follows that $\Sigma$ is distributed according to (18) conditional on ${\bf
a}$. Let $T$ be as in Definition (19), intuitively $T$ is the score threshold
that some members of $G$ must clear in order to ensure the group a payoff of
$1$. Furthermore, when $G$ is selecting the group request strategy, it will
get a payoff of $1$ if and only if at least one of its members has a score
lower than $T$, that is, $\min_{i\in G}\\{a_{i}X_{i}\\}<T$. Because
$\min_{i\in G}\\{a_{i}X_{i}\\}\sim Exp(1)$, it follows that for $i\in G$,

(89) $\mathbb{E}[u_{i}(\pi^{IW}({\bf a}_{G},{\bf
a}_{-G}))|T]=\mathbb{P}(\min_{i\in G}\\{a_{i}X_{i}\\}<T)=1-e^{-T}.$

Because $T$ is independent of the strategy followed by $G$, it suffices to
show that for any deviation ${\bf a}^{\prime}_{G}$ the conditional expected
utility of $G$ given $T$ is less than or equal the right side of (89).

We have already established that it is never beneficial for agents to request
more tickets than their group size. Hence, without loss of generality we
assume that each member of $G$ will request at most $|G|$ tickets.

If $|G|=1$, then the group request is the only feasible strategy so it is
dominant.

If $|G|=2$, then the only deviations we need to consider are ${\bf
a}^{\prime}_{G}=(1,2),(1,1)$. The first strategy is dominated by the group
request, because the allocation of the member requesting $1$ ticket is
irrelevant for the outcome of group $G$. Under the second strategy, $G$ gets a
payoff of $1$ if and only if both members have a score lower than $T$. In
particular, agent $i\in G$ must have a score lower than $T$. This happens with
probability

$\mathbb{P}(a_{i}^{\prime}X_{i}<T)=\mathbb{P}(X_{i}<T)=1-e^{-T}.$

Note that the quantity above coincides with (89), implying that the utility of
$G$ when selecting ${\bf a}^{\prime}_{G}=(1,1)$ is at most its utility under
the group request strategy.

If $|G|=3$, there are $27$ feasible strategies (26 deviations from the group
request), but by symmetry we only need to evaluate 9 of them:

${\bf
a}^{\prime}_{G}=(1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3).$

We argue now that the group request dominates all strategies above in which
there is at least one agent requesting $1$ ticket. Note that under any of
these strategies, $G$ will get a payoff of $1$ only if the remaining $2$
members are awarded two or more tickets. From the case $|G|=2$, we know that
the probability of this event is at most the right hand side of (89). This
implies that the group request strategy dominates all these deviations.

There are only 3 strategies remaining: ${\bf
a}^{\prime}_{G}=(3,3,2),(3,2,2),(2,2,2)$. The first strategy is dominated by
the group request, because the allocation of the member requesting $2$ tickets
is irrelevant for the outcome of group $G$. The second strategy is dominated
by $(3,2,1)$. This follows because the set of orders over agents in which $G$
get a payoff of $1$ is the same under both strategies, and by reducing its
request the last agent improves her probability of being drawn early. A
similar argument shows that the last strategy is dominated by $(1,2,2)$. ∎

###### Analysis of Example 13.

Let $i$ be a member of the large group. We let ${\bf a}=({\bf a}_{G_{i}},{\bf
a}_{-{G_{i}}})$ denote the group request action profile, and ${\bf
a}^{\prime}_{G_{i}}$ denote the strategy where all members of $G_{i}$ request
$2$ tickets. We will show that for $n\geq 17$,

$u_{i}(\pi^{IW}({\bf a}^{\prime}_{G_{i}},{\bf a}_{-{G_{i}}}))\geq
u_{i}(\pi^{IW}({\bf a}_{G_{i}},{\bf a}_{-{G_{i}}})).$

Let $m=n-3$ be the number of groups. We claim that

(90) $\displaystyle u_{i}(\pi^{IW}({\bf a}_{G_{i}},{\bf a}_{-{G_{i}}}))$
$\displaystyle=1-\frac{1}{m},$ (91) $\displaystyle u_{i}(\pi^{IW}({\bf
a}^{\prime}_{G_{i}},{\bf a}_{-{G_{i}}}))$