#  Fundamental Limits of Throughput and Availability:
Applications to prophet inequalities & transaction fee mechanism design

Aadityan Ganesh  Jason Hartline  Atanu R Sinha  Matthew vonAllmen

###### Abstract

This paper studies the fundamental limits of availability and throughput for
independent and heterogeneous demands of a limited resource. Availability is
the probability that the demands are below the capacity of the resource.
Throughput is the expected fraction of the resource that is utilized by the
demands. We offer a concentration inequality generator that gives lower bounds
on feasible availability and throughput pairs with a given capacity and
independent but not necessarily identical distributions of up-to-unit demands.
We show that availability and throughput cannot both be poor. These bounds are
analogous to tail inequalities on sums of independent random variables, but
hold throughout the support of the demand distribution. This analysis gives
analytically tractable bounds supporting the unit-demand characterization of
[17] and generalizes to up-to-unit demands. Our bounds also provide an
approach towards improved multi-unit prophet inequalities [5]. They have
applications to transaction fee mechanism design (for blockchains) where high
availability limits the probability of profitable user-miner coalitions [18].

##  1 Introduction

Consider the following Soup Kitchen Problem:

> A soup kitchen produces $\kappa$ units of soup, and serves diners with
> independent but not necessarily identically distributed demands of at most
> one unit. An auditor needs to ensure that the soup kitchen is performing
> well. Two key performance metrics are availability $\alpha$ and throughput
> $\tau$. Availability is the probability the kitchen does not run out of
> soup. Throughput is the expected fraction of soup produced that is consumed.
> The auditor’s problem is to catch an underperforming soup kitchen by
> establishing a lower bound on feasible availability and throughput pairs.

We define the performant set of availability-throughput pairs $(\alpha,\tau)$
for supply $\kappa$ as a subset of $[0,1]^{2}$ for which there exist
independent distributions for the diners’ demands $D_{i}\in[0,1]$ with sum
$D=\sum_{i=1}^{n}D_{i}$ that induce at most availability and throughput of
$(\alpha,\tau)$, i.e., an availability of $\alpha\geq\mathbb{P}(D<\kappa)$ and
a throughput of $\tau\geq\mathbb{E}[\min(D/\kappa,1)]$. The auditor seeks to
find as tight a bound as possible on performant $(\alpha,\tau)$ pairs so that
underperforming pairs are not mistaken for performant pairs. An illustration
of how tighter bounds permit the auditor to identify underperforming soup
kitchens is provided in Figure 1.

Figure 1: The solid blue line represents the true bound on performant
(availability, throughput) pairs, while the dashed green line is a lower bound
known to the auditor. The soup kitchen achieving $(\alpha_{3},\tau_{3})$ above
the solid blue line performs well, and the soup kitchens achieving
$(\alpha_{1},\tau_{1})$ and $(\alpha_{2},\tau_{2})$ below the solid blue line
are underperforming. However, the auditor can only detect that
$(\alpha_{1},\tau_{1})$ is underperforming, since it does not know the true
location of the solid blue line.

Both throughput and availability are important. If a soup kitchen has low
throughput, much of the soup produced each day goes to waste. However, if it
has low availability, prospective diners have good reason to think that the
kitchen will not have any soup to serve them, and so cannot reliably visit the
kitchen and expect to be served.

This paper provides a method for generating novel concentration inequalities
to relate availability and throughput. These concentration inequalities are
applicable in a wide variety of domains, and improve upon similar
concentration inequalities, such as the Chernoff bound, in ways that are
required for a good approximate solution to the soup kitchen problem. Unlike
most concentration inequalities, which can only bound the probability that a
random variable falls in a region above its mean, the concentration
inequalities provided in this paper can bound the probability that a random
variable falls in any upward-closed region. In this sense, the concentration
inequalities we provide move beyond ?tail bounds? and can instead bound a
larger class of regions than the tail of a distribution.

A mechanism designer that can fine-tune either the availability or the
throughput can use these bounds to establish worst-case values for whichever
parameter they do not fine-tune. When demands come from price-sensitive
agents, the designer can increase the price to increase throughput and
decrease availability, while decreasing the price does the opposite.
Furthermore, since the bounds improve as the size of the soup supply $\kappa$
increases, a designer that increases their supply while targeting a specific
availability can increase the value of their worst-case throughput.
Alternatively, a designer that increases their supply while targeting a
specific throughput can increase the value of their worst-case availability.
This allows them to identify the minimal amount of soup $\kappa$ which permits
them to meet their desired values for availability and throughput.

The fact that posted prices can be used to pick a particular point on the
tradeoff curve between availability and throughput is particularly useful for
prophet inequalities. The conventional way to prove multi-unit prophet
inequalities is to demonstrate the existence of a price that achieves a point
on the the tradeoff curve which maximizes the posted-price mechanism’s worst-
case expected welfare. Better bounds on the worst-case throughput in terms of
the availability, or better bounds on the worst-case availability in terms of
the throughput, translate into better bounds on expected welfare.

### Results

Our primary theorem is a concentration inequality generator. Given a function
$f$ that satisfies certain criteria, it constructs a concentration inequality
that is either stronger or weaker (and more or less tractable) depending on
the function $f$ selected.

######  Theorem LABEL:main_theorem.

Let supply $\kappa\geq 0$, and let $D_{1},...,D_{n}\in[0,1]$ be independent
random demands whose sum $D=\sum_{i=1}^{n}D_{i}$ has throughput
$\tau=\mathbb{E}[\min(D/\kappa,1)]$ and availability
$\alpha=\mathbb{P}(D<\kappa)$. For any weakly convex and weakly positive
function $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ that is strictly increasing
at $\kappa$, the probability that $D$ is at least $\kappa$ is bounded above by
the expectation of $f$ evaluated on on a binomially distributed random
variable with mean equal to the absolute throughput $\kappa\tau$, normalized
by $f$ evaluated at the supply $\kappa$. I.e., for
$X\sim\text{Binomial}(n,\kappa\tau/n)$,

$\displaystyle 1-\alpha\leq\frac{\mathbb{E}[f(X)]}{f(\kappa)}\text{.}$

Note that, unlike Chernoff bounds, the mean of the demand distribution
$\mathbb{E}[D]$ does not appear in concentration inequalities generated by
LABEL:main_theorem. The only quantities relating to the demand $D$ which
appear are the availability and the throughput. Furthermore, observe that
LABEL:main_theorem permits the selection of thresholds $\kappa$ which are less
than the mean of the demand $D$, whereas Chernoff bounds do not. Thresholds
$\kappa$ below $\mathbb{E}[D]$ permit concentration inequalities generated by
LABEL:main_theorem to bound the probability of non-tail regions of the demand
$D$.

To prove LABEL:main_theorem, we first establish that the expected value of a
convex non-negative function of demand is non-decreasing as we go from general
up-to-unit demand to asymmetric unit-demand to binomial (symmetric unit-
demand) to Poisson demand (an infinite number of unit demands)111This last
inequality between binomial demand and Poisson demand is eventually used to
show that the formula in LABEL:main_theorem is weakest when the number of
demands $n\to\infty$.. Next we show that the probability of the demand
exceeding the threshold $\kappa$ can be bounded by the expected value of a
non-negative convex function $f$ of a binomial distribution with the same
expectation as $D$, normalized by the value of the function on the expected
overdemand, i.e. $f(\mathbb{E}[D\mid D\geq\kappa])$. Finally, we show that
this bound still holds when all instances of the expected overdemand
$\mathbb{E}[D\mid D\geq\kappa]$ are lowered to the threshold $\kappa$,
producing the formula for LABEL:main_theorem.

A simple argument then shows that the tightest bound for LABEL:main_theorem
comes from a weakly convex function that is zero up to a point and then
linear, i.e., $f(x)=\max(x-\beta,0)$ for some constant $\beta$. In machine
learning this is referred to as a ReLU function. It is the case that non-ReLU
bounds, though less tight than ReLU bounds, may still be desirable due to
their comparative tractability. We prove several bounds, each produced from a
different function $f$, and compare them to the optimal ReLU bound, showing
how different bounds trade off tractability against strength.

Lastly, we apply one of these bounds to the setting of multi-unit prophet
inequalities with up-to-unit demands. Conventionally, multi-unit prophet
inequalities have attempted to showcase the existence of posted prices that
produce good expected welfare relative to the optimal allocation, which
requires selecting posted prices that sacrifice availability for throughput.
The literature on multi-unit prophet inequalities has not explored what occurs
when availability is its own independent concern for the mechanism designer,
and we show in LABEL:invertible_near_chernoff_bound that one of the bounds
generated by LABEL:main_theorem can be used to illustrate a tractable yet
strong bound on the tradeoff between stronger prophet inequalities and
availability.

### Characterization of Throughput versus Availability

A consequence of the analysis of multi-unit prophet inequalities in [17] is a
simple (but analytically intractable) characterization of the limits of
throughput and availability for unit demands, i.e., when each individual
demand $D_{i}$ is in $\\{0,1\\}$, showing that for any given availability
$\alpha$ the worst-case/smallest throughput $\tau$ occurs when the total
demand $D$ is Poisson-distributed. Therefore, there does not exist any
feasible $(\alpha,\tau)$ pairs below the curve drawn out by assuming $D$ is
Poisson distributed and varying the Poisson parameter $\mathbb{E}[D]$ from
$\mathbb{E}[D]=0$, where $(\alpha,\tau)=(1,0)$, to $\mathbb{E}[D]\to\infty$,
where $(\alpha,\tau)=(0,1)$. Poisson distributions for $D$ with a mean between
these two extremes will trade off between different intermediate values for
throughput and availability.

As mentioned, exact analysis of Poisson tail probabilities are not
analytically tractable; that is, given any particular availability, there is
no closed form for the corresponding throughput of a Poisson distribution. Our
analysis provides concentration inequalities that do give a closed form for
worst-case throughput in terms of availability. In addition, our bounds are
not restricted to the unit demand setting of multi-unit prophet inequalities.
They also hold in a more general setting with up-to-unit demands, i.e. where
each $D_{i}$ can take on values in the unit interval $[0,1]$. In the setting
with up-to-unit demand diners, a simple characterization of the solution to
the soup kitchen problem is not known. We conjecture that the worst-case
distribution in the up-to-unit-demand setting is also Poisson:

######  Conjecture.

For independently distributed up-to-unit demands with availability and
throughput $(\alpha,\tau)$ for a given supply, there is a Poisson distribution
for total demand with availability and throughput at most $(\alpha,\tau)$.

Throughout this paper we will use availability-throughput pairs corresponding
to Poisson distributions as a benchmark to compare against our concentration
inequalities.

### Applications

The analysis presented of the soup kitchen problem is applicable in several
economic and computational settings.

Consider airline ticket sales, where a clear tradeoff exists between
throughput and availability [4, 8]. Airlines intentionally overbook tickets
for seats on a flight knowing that some customers will cancel or not show up
[2]. When more passengers show up than there are seats, an airline must engage
in ?bumping,? whereby some passengers are removed from the flight, either by
way of offering them a voucher for a new flight or rescheduling them for a new
one later that day. An airline that tried to set its availability $\alpha=1$
will never overbook, but will waste most of the seats on a flight by
frequently leaving them empty, exemplified by a low throughput value.
Conversely, an airline that aggressively overbooks will achieve a high
throughput, but will need to bump passengers so frequently that airline
tickets are no longer seen as a reliable indicator for a passenger that they
will be boarding a flight at the time printed upon their ticket. Balancing
these two quantities is an important tradeoff for the airline to make, and
they can control where they fall along the tradeoff curve by changing the
degree of overbooking in which they engage.

Analogous tradeoffs occur commonly in cloud computing [6, 9] with high fixed
cost of compute and storage, and heterogeneity in demand from users. An
exemplar is that of major enterprises renting costly GPUs from cloud providers
to provision dedicated GPUs to internal users or products [10]. Consider a
contract where the enterprise rents a fixed supply of GPUs from a provider,
and then in turn provisions them out to its employees on demand. Employees’
requests for GPUs arrive in sequence and different requests have different
values in terms of productivity for the enterprise. The enterprise would like
to maximize its throughput, since it still has to pay for each of the GPUs
regardless of whether an employee makes use of them. At the same time, the
enterprise also desires high availability. If employees request GPUs and the
enterprise consistently cannot fulfil those requests because it has exhausted
its supply, it is unproductive for the enterprise. An enterprise can control
where it falls on the availability-throughput tradeoff curve by making GPUs
easier or harder for employees to acquire. Additionally, rather than trading
off between availability and throughput, the enterprise can potentially
increase both metrics by increasing the supply of GPUs $\kappa$, which
improves the entire availability-throughput tradeoff curve. Since it is costly
to rent GPUs from a cloud provider, an enterprise may wish to select a minimal
supply $\kappa$ that still permits it to meet its desired availability and
throughput values.

Another application arises from designing transaction fee mechanisms for
blockchains. A block can accommodate up to $\kappa$ units of data. The block
proposer packs the block with transactions performed by users. Different
transactions require different quantities of data [7], and typically the total
demand is more than the space available on the block. In the event this
occurs, a transaction fee mechanism is deployed to determine which
transactions are included in the block. A central question explored in the
literature is to design a mechanism that satisfies strategy-proofness for
users and block proposers, while also deterring collusion between block
proposers and users [12, 18]. Ethereum, for instance, runs a posted-price
mechanism that burns all the payments collected from users [12, 14]. Whenever
the demand at the base price set by the protocol is less than the capacity of
the block, the mechanism satisfies all the required properties. On the other
hand, when demand exceeds the block capacity, space in the block is allocated
through an emergency mechanism, which is a first-price auction in Ethereum’s
case. First-price auctions are not strategy-proof for users, while switching
to a second-price auction introduces strategic deviations for block proposers.
[18] show, under some natural assumptions, that there cannot exist a mechanism
that guarantees strategy-proofness and collusion resistance for all parties
simultaneously. One remedy would be to instead guarantee strategy-proofness
and collusion resistance with high probability [[, cf.]]GH-03. High
availability corresponds to a lower probability of these periods of over-
demand, thereby mitigating the need to run the ?undesirable? emergency
auction, while a larger throughput corresponds to efficient space utilization
in the block. The base price can be adjusted to trade off availability (and
the strategy-proofness that comes with it) and throughput (and the efficiency
that comes with it).

### Related Work

[5] apply a prophet inequality to posted-price mechanisms that ration a supply
of $\kappa$ units of an item among $n$ agents with independent but not
identically distributed values for those items. They showcase an upper bound
of $1+\sqrt{\nicefrac{{8\ln(\kappa)}}{{\kappa}}}$ and a lower bound of
$1+\sqrt{\nicefrac{{1}}{{512\kappa}}}$ on the approximation ratio for expected
welfare achieved by a posted-price mechanism compared to a prophet’s optimal
allocation. Their setting assumes binary demand; either agents purchase a
single unit of the item, or do not purchase at all. Additionally, the upper
and lower bounds derived are only valid for high values of $\kappa$. [19]
confirm the asymptotic optimality of the former bound, showing that the
fraction of the expected welfare achieved by a posted-price mechanism compared
to a prophet is $1-\Theta(\sqrt{\log(\kappa)/\kappa})$.

[17] analyze the same setting and conclude that the worst-case distribution of
demand is Poisson, where there are infinitely many agents who all purchase
with the same infinitesimally small probability. This result enables numerical
calculation of the worst case approximation factor, specifically in the small
$\kappa$ case. Though it is not the main focus of their paper, their analysis
that Poisson demand is the worst case for welfare also demonstrates, for our
paper, that Poisson demand produces the worst case throughput for any given
availability when individuals have unit demands.

Our main theoretical contribution, the development of tail bounds superior to
the Chernoff bound, also applies to the special case of individuals with unit
demands. This is useful because the tradeoff curve between availability and
throughput of the worst-case Poisson demand distribution is not analytically
tractable. In contrast, several of the bounds we develop have a closed form.

##  2 The Soup Kitchen Problem

###  2.1 Model

The soup kitchen produces $\kappa$ units of soup. The kitchen serves $n$
diners with independent but not necessarily identically distributed demands.
Let diner $i$’s demand be $D_{i}\in[0,1]$ and $D=\sum_{i=1}^{n}D_{i}$ be the
total demand. The availability $\alpha=\mathbb{P}(D<\kappa)$ of the kitchen is
the probability that the total demand can be served without running out of
soup. Throughput $\tau=\mathbb{E}[\min(D/\kappa,1)]$ is the expected fraction
of the produced soup that is consumed. Additionally, we will sometimes refer
to the quantity $\kappa\tau=\mathbb{E}[\min(D,\kappa)]$ as the absolute
throughput, i.e., the expected total units of soup consumed. The goal is to
generate concentration bounds on pairs of availability and throughput
$(\alpha,\tau)$ that preclude the possibility of any pair below the bound
being realized by independent diner demands.

###  2.2 Limits of Throughput and Availability

The following high-level sequence of results culminates in our main theorem.

######  Theorem 1.

numerator_inequality Let $D_{1},...,D_{n}\in[0,1]$ be independent random
demands with sum $D=\sum_{i=1}^{n}D_{i}$ and collective mean
$\mu=\mathbb{E}[D]$. Then, for any weakly convex function
$f:\mathbb{R}_{+}\rightarrow\mathbb{R}$, the expectation of $f(D)$ is
maximized when $D$ is binomially distributed, and is further bounded above
when $D$ is Poisson distributed with the same mean. I.e., for
$X\sim\text{Binomial}(n,\mu/n)$ and $Y\sim\text{Poisson}(\mu)$,

$\displaystyle\mathbb{E}[f(D)]\leq\mathbb{E}[f(X)]\leq\mathbb{E}[f(Y)]\text{.}$

######  Theorem 2.

Let supply $\kappa\geq 0$, and let $D_{1},...,D_{n}\in[0,1]$ be independent
random demands whose sum $D=\sum_{i=1}^{n}D_{i}$ has collective mean
$\mu=\mathbb{E}[D]$ and availability $\alpha=\mathbb{P}(D<\kappa)$. Then, for
any weakly convex and weakly positive function
$f:\mathbb{R}_{+}\rightarrow\mathbb{R}$, the probability $D$ is at least
$\kappa$ is bounded above by the expectation of $f$ evaluated on a binomially
distributed random variable with the same mean as $D$, normalized by $f$
evaluated at the conditional mean of $D$ given that it is at least as large as
$\kappa$. I.e., for $X\sim\text{Binomial}(n,\mu/n)$,

$\displaystyle 1-\alpha\leq\frac{\mathbb{E}[f(X)]}{f(\mathbb{E}[D\mid
D\geq\kappa])}\text{.}$

######  Theorem 3.

main_theorem Let supply $\kappa\geq 0$, and let $D_{1},...,D_{n}\in[0,1]$ be
independent random demands whose sum $D=\sum_{i=1}^{n}D_{i}$ has throughput
$\tau=\mathbb{E}[\min(D/\kappa,1)]$ and availability
$\alpha=\mathbb{P}(D<\kappa)$. For any weakly convex and weakly positive
function $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ that is strictly increasing
at $\kappa$, the probability that $D$ is at least $\kappa$ is bounded above by
the expectation of $f$ evaluated on on a binomially distributed random
variable with mean equal to the absolute throughput $\kappa\tau$, normalized
by $f$ evaluated at the supply $\kappa$. I.e., for
$X\sim\text{Binomial}(n,\kappa\tau/n)$,

$\displaystyle 1-\alpha\leq\frac{\mathbb{E}[f(X)]}{f(\kappa)}\text{.}$

Some functions $f$ in the above theorem will produce stronger bounds, while
others will produce weaker bounds. The following lemma can be used to narrow
the search space for functions $f$ that produce strong bounds:

######  Lemma 1.

Let $f:\mathbb{R}\rightarrow\mathbb{R}$ be weakly convex and weakly positive.
Then, for any random variable $D$ and for any threshold $\kappa\geq 0$ such
that $f$ is increasing past $\kappa$, there exists a scaled ReLU function
whose expectation is at least as small as the expectation of $f(D)$ normalized
by $f(\kappa)$. More formally, we have

$\displaystyle\frac{\mathbb{E}[\max(D-\beta,0)]}{\max(\kappa-\beta,0)}\leq\frac{\mathbb{E}[f(D)]}{f(\kappa)}$

for $\beta\equiv\kappa-\frac{f(\kappa)}{f^{\prime}(\kappa^{+})}$, where we
define the subderivative
$f^{\prime}\left(\kappa^{+}\right)\equiv\lim_{z\downarrow\kappa}\frac{f(z)-f(\kappa)}{z-\kappa}$.

###### Proof.

Observe that $x\mapsto\frac{\max(x-\beta,0)}{\max(\kappa-\beta,0)}$ is the
scaled ReLU function which is tangent to $f(x)/f(\kappa)$ at $\kappa$. Note
that this scaled ReLU is equal to $f(x)/f(\kappa)$ at $\kappa$ and weakly
smaller than $f(x)/f(\kappa)$ elsewhere. See Figure 2 for an illustration. ∎

Figure 2: The solid red line is an example $\frac{f(x)}{f(\kappa)}$, and the
dotted blue line is $\frac{\max(x-\beta,0)}{\max(\kappa-\beta,0)}$.

###  2.3 Analysis of Throughput and Availability

This section sketches the proofs of LABEL:numerator_inequality, Theorem 2, and
LABEL:main_theorem. Full proofs can be found in the appendix.

One way to conceptualize LABEL:numerator_inequality is that it demonstrates a
set of upper bounds on $\mathbb{E}[f(D)]$ that are tight when

  1. 1.

$D_{1},...,D_{n}\in[0,1]$ place all their probability mass on $\\{0,1\\}$,

  2. 2.

$D_{1},...,D_{n}$ all allocate the same amount of probability mass to $0$ and
to $1$, and

  3. 3.

the number $n$ is sent to infinity.

To prove LABEL:numerator_inequality, we first show the following lemma:

######  Lemma 2.

sum_of_bernoullis Let $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ be a weakly
convex function, and let $D_{1},...,D_{n}\in[0,1]$ be independent random
variables. Additionally, let $Z_{1},...,Z_{n}$ be independently distributed
Bernoulli random variables such that $\mathbb{E}[Z_{i}]=\mathbb{E}[D_{i}]$.
Then, for all weakly positive translations $L\geq 0$,

$\displaystyle\mathbb{E}[f(L+D)]\leq\mathbb{E}[f(L+Z)]$

where $D=\sum_{i=1}^{n}D_{i}$ and $Z=\sum_{i=1}^{n}Z_{i}$.

When $L$ is set equal to $0$ in LABEL:sum_of_bernoullis, it shows that the
expectation of $f(D)$ is maximized when all $D_{i}$s are Bernoulli distributed
random variables. However, to show LABEL:numerator_inequality, we must show
that it is further maximized when all such Bernoulli random variables are
identically distributed, i.e. have the same mean. We demonstrate this in
LABEL:iid_is_worst.

######  Lemma 3.

iid_is_worst Let $f:\mathbb{R}_{+}\rightarrow\mathbb{R}$ be a weakly convex
function, and let $D_{1},...,D_{n}\in\\{0,1\\}$ be independently distributed
Bernoulli random variables with means $\mu_{i}=\mathbb{E}[D_{i}]$. Denote
their sums $D=\sum_{i=1}^{n}D_{i}$ and $\mu=\sum_{i=1}^{n}\mu_{i}$. Then,

$\displaystyle\mathbb{E}[f(D)]\leq\mathbb{E}[f(X)]$

for $X\sim\text{Binomial}(n,\mu/n)$. This inequality is tight when
$D_{1},...,D_{n}$ are identically distributed, meaning $D\sim X$.

A proof of LABEL:iid_is_worst can also be found in other works [1, 16], and
can be naturally extended to show that $\mathbb{E}[f(X)]$ is maximized as the
number of demands $n\to\infty$, i.e. as the binomial $X$ approaches a Poisson
$Y$ with mean $\mathbb{E}[Y]=\mathbb{E}[X]$. The fact that
$\mathbb{E}[f(X)]\leq\mathbb{E}[f(Y)]$ is used to conclude
LABEL:numerator_inequality. Furthermore, observe that
$\mathbb{E}[f(X)]\leq\mathbb{E}[f(Y)]$ additionally implies that the bound in
LABEL:main_theorem is weakest when $n\to\infty$.

The proof Theorem 2 from LABEL:numerator_inequality is relatively
straightforward. It follows a similar structure to Markov’s inequality on the
random variable $f(D)$.

###### Proof of Theorem 2.

From the law of total expectation, we have

$\displaystyle\mathbb{E}[f(D)]=\mathbb{E}[f(D)\,\mathds{1}(D<\kappa)]+\mathbb{E}[f(D)\mid
D\geq\kappa]\mathbb{P}(D\geq\kappa)\text{.}$

Since $f$ is weakly positive, $\mathbb{E}[f(D)\,\mathds{1}(D<\kappa)]\geq 0$.
Furthermore, since $f$ is weakly convex, $\mathbb{E}[f(D)\mid D\geq\kappa]\geq
f(\mathbb{E}[D\mid D\geq\kappa])$. Thus,

$\displaystyle f(\mathbb{E}[D\mid
D\geq\kappa])\,\mathbb{P}(D\geq\kappa)\leq\mathbb{E}[f(D)]\text{.}$

Next, from LABEL:numerator_inequality, we have
$\mathbb{E}[f(D)]\leq\mathbb{E}[f(X)]$. Therefore,

$\displaystyle f(\mathbb{E}[D\mid
D\geq\kappa])\,\mathbb{P}(D\geq\kappa)\leq\mathbb{E}[f(X)]\text{.}$

Dividing both sides by $f(\mathbb{E}[D\mid D\geq\kappa])\geq 0$, we obtain as
desired:

$\displaystyle\mathbb{P}(D\geq\kappa)$
$\displaystyle\leq\frac{\mathbb{E}[f(X)]}{f(\mathbb{E}[D\mid
D\geq\kappa])}\text{.}\qed$

Observe that the most notable difference between Theorem 2 and Markov’s
inequality is that the denominator on the right-hand side is
$f(\mathbb{E}[D\mid D\geq\kappa])$, not $f(\kappa)$.

Proving LABEL:main_theorem from Theorem 2 is quite involved.

###### Proof sketch of LABEL:main_theorem.

We select the ReLU mapping $f(x)=\max(x-\beta,0)$ for a value of
$\beta\leq\kappa$, and obtain

$\displaystyle\mathbb{P}(D\geq\kappa)\leq\frac{\mathbb{E}[\max(X-\beta,0)]}{\max(\mathbb{E}[D\mid
D\geq\kappa]-\beta,0)}$

from Theorem 2, with $X\sim\text{Binomial}(n,\mu/n)$. Observe that since
expectations with respect to a binomial distribution have a closed form, the
right-hand side can be written as a function of two parameters,
$\mu^{\uparrow}\triangleq\mathbb{E}[D\mid D\geq\kappa]$ and
$\mu^{\downarrow}\triangleq\mathbb{E}[D\mathds{1}(D<\kappa)]$, as follows:

$\displaystyle\frac{\mathbb{E}[\max(X-\beta,0)]}{\max(\mathbb{E}[D\mid
D\geq\kappa]-\beta,0)}=\frac{\sum_{i=0}^{n}\max(i-\beta,0)\frac{n!}{i!(n-i)!}\left(\frac{\mu^{\uparrow}\mathbb{P}(D\geq\kappa)+\mu^{\downarrow}}{n}\right)^{i}\left(1-\frac{\mu^{\uparrow}\mathbb{P}(D\geq\kappa)+\mu^{\downarrow}}{n}\right)^{n-i}}{\max(\mu^{\uparrow}-\beta,0)}$

In the case where $\beta<0$, we show directly that the right-hand side is
decreasing in $\mu^{\uparrow}$, and move $\mu^{\uparrow}\to\kappa$. In the
more complicated case where $\beta\geq 0$, we adjust the parameters of the
right-hand side in two steps:

  1. 1.

Move along a path of pairs $(\mu^{\uparrow},\mu^{\downarrow})$ that keeps the
right-hand side constant, and such that the end of the path is the point
$(\kappa,t)$ for some $t$ below the original $\mu^{\downarrow}$.

  2. 2.

Adjust $t$ upwards to the original $\mu^{\downarrow}$, and show that this only
increases the right-hand side.

Therefore, the final value of the right-hand side should be at least
$\mathbb{P}(D\geq\kappa)$. See Figure 3 for an illustration.

Figure 3: Step 1 moves between different $(\mu^{\uparrow},\mu^{\downarrow})$
pairs. At all points along this path in step 1, the RHS stays constant and
thus above $\mathbb{P}(D\geq\kappa)$. Then, since the RHS is increasing along
the $\mu^{\downarrow}$ axis, moving from $b$ to $c$ in step 2 raises the RHS
even further above $\mathbb{P}(D\geq\kappa)$.

The resulting formula for the right-hand side is equal to the formula for the
expectation of a binomial distribution with mean
$\kappa\mathbb{P}(D\geq\kappa)+\mu^{\downarrow}=\kappa\tau$, divided by the
value $\max(\kappa-\beta,0)$. A straightforward application of Lemma 1
completes the theorem, showing that this ReLU bound can be weakened to
$f(X)/f(\kappa)$ for $X\sim\text{Binomial}(n,\kappa\tau/n)$. ∎

Observe that the ReLU function described in Lemma 1 is weakly convex, weakly
positive, and is strictly increasing past $\kappa$. It thus satisfies all the
requirements for making a concentration inequality using LABEL:main_theorem,
and we can conclude that for any concentration inequality made using
LABEL:main_theorem, there exists a ReLU function that produces a concentration
inequality at least as strong. This means that in order to find the functions
$f$ for use with LABEL:main_theorem that produce the strongest concentration
inequalities, it suffices to search solely among the class of ReLU functions.

##  3 Multi-Unit Posted-Price Mechanisms

In this section we apply our analysis of throughput and availability to
deriving prophet inequalities for posted-price mechanisms. Typically, prophet
inequalities are concerned with showcasing the existence of a price that
obtains good worst-case expected welfare. However, a price that obtains good
worst-case expected welfare can potentially result in low availability. We
examine what occurs when the mechanism designer cares about both availability
and expected welfare, converting the availability-throughput tradeoff curves
from the soup kitchen problem into availability-welfare tradeoff curves along
which a mechanism designer can select their preferred location.

###  3.1 Model

Consider running a posted-price mechanism to sell $K\in\mathbb{R}_{+}$ units
of a divisible good to $n$ agents. Agents purchase up to a unit of the good
and agent $i$’s value for receiving $x$ units of good is given by the value
function $v_{i}(x)$, $v_{i}:[0,1]\xrightarrow{}\mathbb{R}$, drawn from some
distribution $F_{i}$ over value functions. All distributions $F_{i}$ are
independent and we assume $v_{i}(0)=0$.

Agents have quasi-linear utility from purchasing $x$ units of good at price
$p$ per-unit good, i.e, agent $i$ gets a utility

$\displaystyle u_{i}(x)=v_{i}(x)-px\text{.}$

Thus, if $S_{i}$ units of the good are left unsold when the agent interacts
with the mechanism, the agent purchases
$B_{i}=\operatorname*{arg\,max}_{x\in[0,\min\\{1,S_{i}\\}]}\\{v_{i}(x)-px\\}$
to maximize its utility. We make a mild assumption on the valuation function
$v_{i}$ that for any quantity of residual supply $S_{i}$, there is a maximizer
$B_{i}$ that optimizes agent $i$’s utility (if this is not unique, the agent
can mix between buying any of these quantities). Observe that the class of all
weakly concave functions is contained in the class of functions satisfying the
above assumption.

Let $D_{i}=\operatorname*{arg\,max}_{x\in[0,1]}\\{v_{i}(x)-px\\}$ be agent
$i$’s desired quantity of goods assuming no supply constraints, and let
$D=\sum_{i=1}^{n}D_{i}$ be the total quantity of goods demanded by the agents.

The agents’ arrival order is determined adversarially as follows:

  1. 1.

Agents realize their value functions $(v_{1},\dots,v_{n})$.

  2. 2.

An adversary determines the order in which the agents interact with the online
mechanism fully knowing agents’ value functions so as to minimize the welfare
of the mechanism.

  3. 3.

Agents interact with the mechanism in the order determined by the adversary,
purchasing $B_{i}$ units of the good so as to optimize their utility.

The mechanism designer cares about selecting a price $p$, not only to achieve
an allocation with high expected welfare, but to make sure the mechanism can
reliably serve agents. We define

$\displaystyle\delta\triangleq\mathbb{P}\left(\bigcup_{i=1}^{n}\\{D-D_{i}>K-1\\}\right)$

as the probability that there exists some agent who, if placed at the
worst/latest possible location in the arrival order, would be denied the
option to purchase up to $1$ unit of the good.

$1-\delta$ is closely related to the concept of availability $\alpha$
introduced in the soup kitchen problem. A low $\delta$ means that shoppers can
be confident that the posted-price mechanism will have enough of the good to
serve them, no matter what they choose to buy. Observe also that if we define
the supply threshold $\kappa=K-1$ and the availability of the mechanism as
$\alpha=\mathbb{P}(D<\kappa)$, then the availability is a lower bound on
$1-\delta$. We will therefore term $\delta$ the ?real unavailability? and $K$
the ?real supply? when needed to differentiate from our use of unavailability
$1-\alpha$ and supply $\kappa$ from the soup kitchen problem, though we will
refer to both by the same term outside such cases.

Let $p(\delta)$ be the price such that, with probability $1-\delta$, every
agent is able to choose its desired quantity irrespective of its position in
the queue. Note that $p(\delta)$ is independent of the order in which agents
interact with the mechanism. We trace out a lower bound on the expected
welfare APX of the posted-price mechanism at price $p(\delta)$, against that
of the optimal offline mechanism OPT, as a function of $\delta$.

###  3.2 Results

We produce a prophet inequality which demonstrates the tradeoff between
$\delta$ and expected welfare.

######  Proposition 4.

welfare_bound In a multi-unit posted-price mechanism with up-to-unit demand
buyers, where
$\delta\triangleq\mathbb{P}\left(\bigcup_{i=1}^{n}\\{D-D_{i}>K-1\\}\right)$ is
the probability that any agent, if prioritized last by the mechanism, does not
have the option to buy $1$ unit of the good, then

$\displaystyle\frac{\text{APX}}{\text{OPT}}\geq\min\left(\frac{K-1}{K}\mathbb{E}\left[\min\left(\frac{D}{K-1},1\right)\right],1-\delta\right)\text{.}$

For the purposes of bounding the welfare approximation ratio achieved by a
posted-price mechanism in LABEL:welfare_bound, we have the particular goal of
finding a tail bound that is tractably invertible–that is, since the
throughput $\tau=\mathbb{E}\left[\min\left(\frac{D}{K-1},1\right)\right]$
shows up as a direct term in our bound on the approximation ratio, we need to
find a lower bound on $\tau$ in terms of the unavailability $\delta$ rather
than an upper bound on unavailability $\delta$ in terms of throughput $\tau$.
This bound can be directly inserted into our lower bound on
$\text{APX}/\text{OPT}$. For tractability purposes, this ?inverse tail bound?
should be writable in terms of elementary functions, while also remaining
close to tight. As described in the previous section, to match the notation of
LABEL:main_theorem, which we will be using to construct these invertible tail
bounds, we will define $\kappa=K-1$.

One such bound can be achieved by selecting $f(x)=\exp(\lambda x)-1$ and
selecting the parameter $\lambda$ to make the bound as tight as possible. We
present this bound in the following theorem:

######  Theorem 5.

invertible_near_chernoff_bound Let $D_{1},...,D_{n}\in[0,1]$ be independent
random variables with sum $D=\sum_{i=1}^{n}D_{i}$ and let supply threshold
$\kappa\geq 0$. For
$\delta\triangleq\mathbb{P}\left(\bigcup_{i=1}^{n}\\{D-D_{i}>\kappa\\}\right)$,
we then have the following bound on throughput
$\tau\triangleq\mathbb{E}[\min(D/\kappa,1)]$:

$\displaystyle\tau\geq\frac{\frac{1}{\kappa}\ln\left(\exp\left(\kappa\sqrt{1-\exp\left(\frac{1}{\kappa}\ln(\delta)\right)}\right)+(1-\delta)\right)}{\exp\left(\sqrt{1-\exp\left(\frac{1}{\kappa}\ln(\delta)\right)}-\frac{1}{\kappa}\ln(\delta)\right)-1}$

The proof of LABEL:invertible_near_chernoff_bound in the appendix is similar
to the construction of a conventional Chernoff bound, though with some key
differences.

We can insert the bound in LABEL:invertible_near_chernoff_bound directly into
our inequality on $\frac{\text{APX}}{\text{OPT}}$ from LABEL:welfare_bound.
Note that LABEL:main_theorem also permits us to explore superior bounds on
$\tau$ using ReLU functions that, though less tractable, are significantly
tighter. Additionally, we can use LABEL:main_theorem with the same proof
techniques as the conventional Chernoff bound. To understand the looseness of
our tractable bound in LABEL:invertible_near_chernoff_bound, we compare it to
these other two bounds in Figure 4 and Figure 5.

Figure 4: Graph of minimum throughput $\tau=\mathbb{E}[\min(D/\kappa,1)]$ as a
function of availability $\alpha=\mathbb{P}(D<\kappa)$ when $\kappa=100$.
Dashed orange line is produced when $f$ is a near-optimal ReLU function, the
red line is produced when $f(x)=\exp(\lambda x)-1$ for a carefully chosen
$\lambda$, and the dotted green line is the conventional Chernoff-style bound.
Compare to solid blue line, which represents the true $(\alpha,\tau)$ pairs
for a Poisson distribution. Figure 5: Zoomed in version of Figure 4 on the
point (availability, throughput) = (1, 0), with $\kappa=5$. Observe that all
bounds save for the dotted green conventional Chernoff-style bound very
steeply approach (1, 0) as $\mathbb{P}(D<\kappa)\to 1$, whereas the Chernoff-
style bound becomes negative.

The first of our plotted bounds is the one from
LABEL:invertible_near_chernoff_bound, which is displayed as the red line in
Figure 4. We begin by comparing it to a second bound, which is constructed
using steps identical to those used to construct the traditional Chernoff
bound; we select $f(x)=\exp(\lambda x)$, carefully select a value of
$\lambda>0$ equal to

$\displaystyle\lambda=\ln(1/\tau)$

to make the bound as strong as possible, and then weaken the result via a Padé
approximation. The result is a bound with the same functional form as the
traditional Chernoff, but with the mean of the distribution $\mathbb{E}[D]$
replaced by the smaller quantity $\kappa\tau\leq\mathbb{E}[D]$, where
$\kappa\tau$ is the absolute throughput:

$\displaystyle
1-\alpha=\mathbb{P}(D\geq\kappa)\leq\exp\left(-\frac{\frac{1}{2}\left(\kappa-(\kappa\tau)\right)^{2}}{(\kappa\tau)+\frac{1}{3}\left(\kappa-(\kappa\tau)\right)}\right)$

Inverting this bound produces

$\displaystyle\tau\geq
1+\frac{2}{3}\frac{1}{\kappa}\ln\left(\frac{1}{1-\alpha}\right)-\sqrt{\left(\frac{2}{3}\frac{1}{\kappa}\ln\left(\frac{1}{1-\alpha}\right)\right)^{2}+2\frac{1}{\kappa}\ln\left(\frac{1}{1-\alpha}\right)}\text{,}$

which we plot as the dotted green line in Figure 4.

Our first bound has a major advantage over the traditional Chernoff-style
bound: Observe how in Figure 5, which is very zoomed in, that the traditional
Chernoff-style bound produces a negative lower bound on throughput $\tau$ for
very high availability $\mathbb{P}(D<\kappa)\approx 1$. While Chernoff bounds
are very effective in the asymptotic case where the threshold
$\kappa\to\infty$, they fall short at bounding very low tail probabilities for
fixed $\kappa$. A failure to bound low tail probabilities is an especially big
issue when $\kappa$ is very low, where the range of tail probabilities with a
negative lower bound on the throughput $\tau$ can be quite large. It is also a
problem for analyzing posted-price mechanisms designed to have very low
probabilities of running out of supplies, since it means the traditional
Chernoff bound provides no welfare guarantees as availability
$\mathbb{P}(D<\kappa)\to 1$.

We compare both of these bounds to a third bound, which is constructed with an
optimal ReLU function $x\mapsto\max(x-\beta,0)$ that we can use with
LABEL:main_theorem. The value of $\beta$ is adaptively selected, based on the
desired value of $\mathbb{P}(D\geq\kappa)$, to make the bound

$\displaystyle\mathbb{P}(D\geq\kappa)\leq\frac{\mathbb{E}[\max(Y-\beta,0)]}{\max(\kappa-\beta,0)}$

as strong as possible for $Y\sim\text{Poisson}(\kappa\tau)$. We display the
bound thus obtained as a dashed orange line in Figure 4, to showcase how much
lower the welfare guarantees of a posted-price mechanism become when using a
non-ReLU function $f$.

Lastly, all three of these bounds are compared to the true availability-
throughput pairs of Poisson distributions. This is the solid blue line in
Figure 4. Since the three bounds are lower bounds on throughput $\tau$ in
terms of availability $\alpha$, it is clear that the actual throughput $\tau$
of a Poisson distribution for any fixed $\alpha$ should be higher than these
lower bounds. Thus, this solid blue line should be seen as a benchmark to
compare against our three lower bounds on the throughput $\tau$; the smaller
the gap between the true throughput $\tau$ of a Poisson distribution and a
given lower bound on $\tau$, the better. Our goal is to minimize this gap as
much as possible while keeping our bounds analytically tractable. As one can
see, our optimal ReLU bound (the dashed orange line) minimizes this gap the
most, but is quite intractable. The other two bounds perform worse, but are
far more tractable. Thus, there is a clear tradeoff between tractability and
strength of our three bounds.

(a) Welfare bounds given the same parameters as Figure 4, which has supply
$K=101$.

(b) Welfare bounds in a low-supply setting, with supply $K=10$.

Figure 6: Plugging the same bounds on $\tau$ as in Figure 4 into our lower
bound on $\frac{\text{APX}}{\text{OPT}}$. The black horizontal line is the
$\Big{(}1+\sqrt{\frac{8\ln(K)}{K}}\Big{)}^{-1}$ lower bound on
$\frac{\text{APX}}{\text{OPT}}$ obtained by [5]. Note that this welfare bound
is achieved by a particular $\delta$ value, and we have drawn it as a
horizontal black line to better illustrate for which values of $\delta$ our
own bounds produce stronger or weaker welfare guarantees.

Recall that by defining our supply threshold $\kappa=K-1$, each of the bounds
on throughput $\tau=\mathbb{E}[\min(D/\kappa,1)]$ (and the curve corresponding
to the Poisson distribution) can be inserted into our welfare bound

$\displaystyle\frac{\text{APX}}{\text{OPT}}$
$\displaystyle\geq\min\left(\frac{K-1}{K}\mathbb{E}\left[\min\left(\frac{D}{K-1},1\right)\right],1-\delta\right)$
$\displaystyle=\min\left(\frac{K-1}{K}\tau,1-\delta\right)$

from LABEL:welfare_bound to obtain the tradeoff curves displayed in Figure 6.
Any particular unavailability $\delta$ produces a different lower bound on
$\frac{\text{APX}}{\text{OPT}}$, and the solid blue Poisson curve is an upper
bound on any such approximation ratio. Thus, the true tradeoff curve must lie
between the strongest of our lower bounds and the Poisson curve. We plot these
tradeoffs for both a high supply environment (Figure 6(a)) and a low supply
environment (Figure 6(b)) to give a visualization of the changes that occur as
the parameter $K$ varies.

As can be seen, there is a minor plateau around the peak of the welfare curves
$\frac{K-1}{K}\tau\approx 1-\delta$, where there is a minimal penalty to the
lower bound on $\frac{\text{APX}}{\text{OPT}}$ for decreasing unavailability
$\delta$, followed by a sharp dropoff that occurs as the unavailability
$\delta$ moves far below the welfare-optimal level. The slope of the plateau
depends on which of the bounds is used, increasing as the bounds become
stronger and move toward the Poisson curve. Furthermore, the slope of the
plateau becomes smaller as we move toward high-supply environments. This
suggests that a mechanism designer who is willing to sacrifice some of the
welfare guarantee of a posted-price mechanism in exchange for lowering
unavailability $\delta$ can do so at a very favorable tradeoff rate.

There are also implications for mechanism designers unconcerned with
minimizing unavailability $\delta$, and only concerned with maximizing the
worst-case welfare guarantee. The black line in Figure 6(a) and Figure 6(b) is
the $\frac{\text{OPT}}{\text{APX}}\leq 1+\sqrt{\frac{8\ln(K)}{K}}$ bound
obtained by [5], which is intended to be used in a unit-demand setting with
asymptotically high values of the real supply $K$. There is a gap between the
best lower bounds obtained on $\frac{\text{APX}}{\text{OPT}}$ via
LABEL:main_theorem at the welfare-optimal selection of unavailability $\delta$
and this black line, which suggests that the constants involved for the
$1+\sqrt{\frac{8\ln(K)}{K}}$ bound can be significantly improved at these
lower values of supply $K$. Therefore, posted-price mechanisms can provide
much stronger welfare guarantees at non-asymptotically large $K$ than the
bounds from [5] permit.

##  4 Transaction fee mechanism design

We take a closer look at the application of our results to designing
transaction fee mechanisms, which are used in blockchain technology to
allocate limited space on a block.

As discussed in the introduction, space in a block is considered a valuable
resource since each block can accommodate only so many units of data (or gas,
in the case of Ethereum). A transaction fee mechanism is deployed to decide
the inclusion of transactions in a block. Ethereum, for instance, runs a
posted-price mechanism that burns all the payments collected from users [12].
Conditioned on demand at the price being smaller than capacity of the block,
the posted-price mechanism is strategy-proof for users and block proposers,
while also deterring collusion between users and block proposers. However,
when demand exceeds capacity, an emergency mechanism is deployed wherein the
three incentive properties satisfied by the posted-price mechanism cannot all
be satisfied simultaneously. The first price auction used by Ethereum as the
emergency mechanism is not strategy-proof for users. Therefore, having a high
availability is desirable since it corresponds to not needing to frequently
deploy the emergency mechanism. However, high availability trades off against
throughput, which corresponds to an efficient utilization of the valuable
block space.

Controlling for availability directly is challenging since whether the demand
exceeds the capacity of a block is binary; either the demand exceeds capacity,
or it does not. Instead, price-posting heuristics use throughput as an easily
measurable lever to indirectly ensure high availability. Ethereum’s heuristic
increases (decreases) the price if the ex-post throughput of the previous
block was more (less) than half. Improved methods for managing this tradeoff
have been proposed [[, e.g.]]FMPS-21.

Our analysis of the shape of the tradeoff curve suggests one such method:
targeting a higher average throughput of recent blocks than Ethereum’s current
throughput target of $1/2$. Our analysis of multi-unit posted-price mechanisms
indicates that this would result in superior worst-case expected welfare,
while retaining acceptably high availability222In practice, the likely effects
on availability are less clear. In Ethereum, the emergency auction is
triggered in around 20% of blocks [15], corresponding to 80% availability.
This is lower than what our tradeoff curves would permit if throughput were
fixed to $1/2$, and suggests that Ethereum’s price adjustment to maintain its
$1/2$ throughput target is not fast enough. When the price lags behind its
ideal level, blocks may achieve a throughput either far above or below the
$1/2$ target, and it is the average availability between these two cases which
produces the 80% figure.. Consider that the block space in Ethereum is
restricted to $30$ million units of gas, while $750,000$ is a conservative
upper bound on the maximum gas requested by any single transaction. For the
above numbers, the effective supply $\kappa$ is at least $40$. Figure 7 plots
the availability vs throughput tradeoff for $\kappa=40$, using an optimal ReLU
bound from LABEL:main_theorem. Targeting a throughput of $60\%$, for instance,
guarantees an availability of at least $99.66\%$ which translates to requiring
the emergency auction approximately once every $300$ blocks. By
LABEL:welfare_bound, a throughput of $60\%$ would also guarantee approximately
$60\%$ of the optimal welfare.

Figure 7: The optimal ReLU bound from LABEL:main_theorem when $\kappa=40$,
illustrating the tradeoff curve between guarantees on throughput and
availability for Ethereum. Throughput can be set to $60\%$ while maintaining a
$99.66\%$ availability.

##  5 Conclusions and future work

For posted-price mechanisms, we are able to significantly improve upon the
lower bounds on expected welfare provided by a conventional Chernoff bound.
Our bounds on throughput in terms of availability also improve on the
analytical tractability of those provided by [17] without significantly
sacrificing strength, and can be applied to settings with up-to-unit-demand
agents.

We are able to show that the unavailability $\delta$ can be made much smaller
than its usual value in prophet inequalities, with only a minor penalty to
expected welfare. As can be seen from Figure 4 and Figure 6, several of our
derived lower bounds on throughput $\tau$ are nearly flat as a function of
$\delta$ near the peak of the welfare curve. A nearly flat curve suggests that
prices intentionally selected to be higher than their welfare-optimal value
can significantly decrease unavailability $\delta$ with only a minor impact on
throughput $\tau$, and thus only a minor impact on expected welfare. A
mechanism designer has good reason to make $\delta$ as small as possible, and
so may wish to take advantage of this favorable tradeoff.

The bounds we derive can almost certainly be made tighter, and this is an
important area for future work. [17] are able to demonstrate that Poisson-
distributed demand produces the worst ratio of expected welfare achieved by a
posted-price mechanism compared to a prophet in a unit-demand setting. In
comparison, as can be seen from Figure 4, the throughput $\tau$ corresponding
to a true Poisson distribution for any given availability $\alpha$ is above
the strongest lower bounds on $\tau$ available from LABEL:main_theorem, via
selecting an optimal ReLU function. The tradeoff curve for Poisson
distributions would need to be identical to the strongest bound from
LABEL:main_theorem for the proof techniques demonstrated in this paper to
extend the results of [17] that Poisson demand is worst-case from the unit-
demand setting to the up-to-unit-demand setting. Future work should seek to
close the gap between the two tradeoff curves.

Another area for future work is to refine our availability-throughput bounds
to better capture salient features of the demand distribution in Ethereum
blocks. The concentration inequalities presented in this paper assume only
that individual demands are independent and up-to-unit, and if stronger
assumptions can be made on the individual demands’ distributions, stronger
concentration inequalities could be developed. For example, in Ethereum it is
known that the gas requested by many transactions falls below their maximum
possible value. Our analysis used a conservative upper bound on the gas
requested by any single transaction of $750,000$. However, a standard transfer
between two Ethereum wallets requires $21,000$ units of gas, which is an order
of magnitude smaller. Since the variability in the gas requested by each
transaction is high, the ?effective supply? of $\kappa=40$ that we selected is
an underestimate; most blocks typically accommodate over $100$ transactions. A
more refined analysis that takes into account these empirical facts could
demonstrate an improved tradeoff between throughput and availability, by
restricting attention to more realistic demand distributions rather than the
worst-case demand distributions examined in this paper.

## References

  * [1] Wassily Hoeffding  “On the distribution of the number of successes in independent trials”  In _The Annals of Mathematical Statistics_ JSTOR, 1956, pp. 713–721
  * [2] Yoshinori Suzuki  “An empirical analysis of the optimal overbooking policies for US major airlines”  In _Transportation Research Part E: Logistics and Transportation Review_ 38.2 Elsevier, 2002, pp. 135–149
  * [3] Andrew V Goldberg and Jason D Hartline  “Envy-free auctions for digital goods”  In _Proceedings of the 4th ACM conference on Electronic commerce_ , 2003, pp. 29–35
  * [4] Dimitris Bertsimas and Sanne De Boer  “Simulation-based booking limits for airline revenue management”  In _Operations Research_ 53.1 INFORMS, 2005, pp. 90–106
  * [5] Mohammad Taghi Hajiaghayi, Robert Kleinberg and Tuomas Sandholm  “Automated online mechanism design and prophet inequalities”  In _AAAI_ 7, 2007, pp. 58–65
  * [6] Gunho Lee and Randy H Katz  “Heterogeneity-Aware Resource Allocation and Scheduling in the Cloud”  In _3rd USENIX Workshop on Hot Topics in Cloud Computing (HotCloud 11)_ , 2011
  * [7] Vitalik Buterin  “A next-generation smart contract and decentralized application platform”  In _white paper_ 3.37, 2014, pp. 2–1
  * [8] E Boyd  “The future of pricing: How airline ticket pricing has inspired a revolution”  Springer, 2016
  * [9] Qiumin Lu et al.  “Fairness-efficiency allocation of CPU-GPU heterogeneous resources”  In _IEEE Transactions on Services Computing_ 12.3 IEEE, 2016, pp. 474–488
  * [10] Myeongjae Jeon et al.  “Multi-tenant GPU clusters for deep learning workloads: Analysis and implications”  In _Technical report, Microsoft Research_ , 2018
  * [11] Biel Roig-Solvas and Mario Sznaier  “Euclidean Distance Bounds for LMI Analytic Centers using a Novel Bound on the Lambert Function”  In _arXiv preprint arXiv:2004.01115_ , 2020
  * [12] Tim Roughgarden  “Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559”  In _arXiv preprint arXiv:2012.00854_ , 2020
  * [13] Matheus VX Ferreira, Daniel J Moroz, David C Parkes and Mitchell Stern  “Dynamic posted-price mechanisms for the blockchain transaction-fee market”  In _Proceedings of the 3rd ACM Conference on Advances in Financial Technologies_ , 2021, pp. 86–99
  * [14] Tim Roughgarden  “Transaction fee mechanism design”  In _ACM SIGecom Exchanges_ 19.1 ACM New York, NY, USA, 2021, pp. 52–55
  * [15] Yulin Liu et al.  “Empirical analysis of eip-1559: Transaction fees, waiting times, and consensus security”  In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_ , 2022, pp. 2099–2113
  * [16] Nick Arnosti and Will Ma  “Tight guarantees for static threshold policies in the prophet secretary problem”  In _Operations research_ 71.5 INFORMS, 2023, pp. 1777–1788
  * [17] Shuchi Chawla, Nikhil Devanur and Thodoris Lykouris  “Static pricing for multi-unit prophet inequalities”  In _Operations Research_ INFORMS, 2023
  * [18] Hao Chung and Elaine Shi  “Foundations of transaction fee mechanism design”  In _Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2023, pp. 3856–3899  SIAM
  * [19] Jiashuo Jiang, Will Ma and Jiawei Zhang  “Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities”  In _Proceedings of the 24th ACM Conference on Economics and Computation_ , EC ’23  , London, United Kingdom,: Association for Computing Machinery, 2023, pp. 909  DOI: 10.1145/3580507.3597734