# Simple and Optimal Online Contention Resolution Schemes for $k$-Uniform
Matroids

Atanas Dinev
Massachusetts Institute of Technology, Cambridge MA, USA  S. Matthew Weinberg
Princeton University, Princeton, USA

###### Abstract

We provide a simple $(1-O(\frac{1}{\sqrt{k}}))$-selectable Online Contention
Resolution Scheme for $k$-uniform matroids against a fixed-order adversary. If
$A_{i}$ and $G_{i}$ denote the set of selected elements and the set of
realized active elements among the first $i$ (respectively), our algorithm
selects with probability $1-\frac{1}{\sqrt{k}}$ any active element $i$ such
that $|A_{i-1}|+1\leq(1-\frac{1}{\sqrt{k}})\cdot\mathbb{E}[|G_{i}|]+\sqrt{k}$.
This implies a $(1-O(\frac{1}{\sqrt{k}}))$ prophet inequality against fixed-
order adversaries for $k$-uniform matroids that is considerably simpler than
previous algorithms [Ala14, AKW14, JMZ22].

We also prove that no OCRS can be $(1-\Omega(\sqrt{\frac{\log
k}{k}}))$-selectable for $k$-uniform matroids against an almighty adversary.
This guarantee is matched by the (known) simple greedy algorithm that accepts
every active element with probability $1-\Theta(\sqrt{\frac{\log k}{k}})$
[HKS07].

##  1 Introduction

Background: OCRSs. Online contention resolution schemes (OCRS) are a broadly
applicable rounding technique for online selection problems [FSZ16]. These are
problems in which an algorithm makes irrevocable decisions for whether to
select elements arriving online, often subject to combinatorial constraints.
Offline, the algorithm knows a distribution over which elements will be
“active.” Online, elements are revealed to be active or inactive one at a
time, and the algorithm must immediately and irrevocably decide whether to
accept an active element (inactive elements must be rejected). There are
feasibility constraints $\mathscr{F}$ on which elements can be simultaneously
accepted. An OCRS for a class of instances is $c$-selectable if it guarantees
that every element is selected with probability at least $c$, conditioned on
being active. See Definition 2.1 for a formal definition.

Online contention resolution schemes have direct applications to prophet
inequalities [FSZ16]. In a prophet inequality, a gambler knows the
distribution of a sequence of independent random variables
$X_{1},\ldots,X_{n}$. Online, each random variable will be sampled one at a
time and revealed to the gambler, who immediately and irrevocably decides
whether to accept the element, subject to feasibility constraints
$\mathscr{F}$. The gambler’s goal is to maximize the expected sum of weights
of accepted elements, and a prophet inequality compares the ratio of the
gambler’s expected performance to that of a prophet (who knows all random
variables before making decisions). Seminal work of Krengel, Sucheston, and
Garling establishes a tight $1/2$-approximation for the single-choice prophet
inequality, and seminal work of Samuel-Cahn shows that the same result can be
achieved with an especially simple thresholding algorithm [KS78, Sam84].

In their work introducing OCRSs, Feldman, Svensson, and Zenklusen prove that a
$c$-selectable OCRS implies a $c$-approximation for the corresponding prophet
inequality [FSZ16]. In fact, a $c$-selectable OCRS provides a
$c$-approximation even to the ex ante relaxation, and Lee and Singla show that
OCRSs are _equivalent_ to ex ante prophet inequalities [LS18].

$k$-Uniform Matroids. $k$-uniform matroids are a canonical set of feasibility
constraints: any set of up to $k$ elements can be selected. Here, a
$(1-O(\sqrt{\frac{\log k}{k}}))$-approximate prophet inequality (whose
analysis implicitly extends to a $(1-O(\sqrt{\frac{\log k}{k}}))$-selectable
OCRS) is first developed in [HKS07]. [Ala14] later develops a
$(1-O(\frac{1}{\sqrt{k}}))$-approximation (which also implies a
$(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS), which is tight. [AKW14] further
shows how to achieve the same $(1-O(\frac{1}{\sqrt{k}}))$-approximation using
a single sample from each distribution (but their work does not imply any
OCRS). [JMZ22] tightens the analysis of [Ala14] to nail down exactly the
optimal achievable prophet inequality for all $k$ (and this same analysis
applies to the implied OCRS). We overview in Section 1.1 these results in more
detail, and in particular clarify against what kind of adversary (who selects
the order in which the elements are revealed) the guarantees hold.

While the optimal competitive ratio has been known for a decade, and recently
tightened to even nail down the precise constants, these algorithms are
significantly more complex than Samuel-Cahn’s elegant algorithm for the
single-choice prophet inequality. For example, [Ala14, JMZ22] both require to
solve and analyze a mathematical program in order to accept elements with
precisely the correct probability. The rehearsal algorithm of [AKW14] is
perhaps simpler, but still requires several lines of pseudocode, and some care
with minor details.

Main Result: A Simple, Optimal OCRS. Our main result is a significantly
simpler OCRS/prophet inequality for $k$-uniform matroids that still achieves
the optimal guarantee of $1-O(\frac{1}{\sqrt{k}})$. Of course, it is still not
nearly as simple as Samuel-Cahn’s single-choice prophet inequality, but a full
description fits in two sentences, and the complete analysis is just a few
pages.111The proof does require connecting our algorithm to a random walk, and
then analyzing properties of that random walk. But, the proof requires minimal
calculations. Our OCRS simply denotes by $A_{i}$ the set of elements it has
selected amongst the first $i$ and by $G_{i}$ the set of realized active
elements amongst the first $i$. Then, when processing element $i$, we select
$i$ with probability $1-\frac{1}{\sqrt{k}}$ if and only if $i$ is active and
$|A_{i-1}|+1\leq(1-\frac{1}{\sqrt{k}})\cdot\mathbb{E}[|G_{i}|]+\sqrt{k}$
(otherwise, we discard). Intuitively, our OCRS selects an element if, so far,
the number of selected elements does not exceed the expected number of active
elements by too much. To turn our OCRS into a prophet inequality, simply let
$T$ denote the unique value such that $\sum_{i}\Pr[X_{i}>T]=k$.222If the
distributions have point-masses, smooth them out by adding a uniformly random
draw from $[0,\varepsilon]$ for arbitrarily small $\varepsilon$. Then, declare
$X_{i}$ to be active if and only if $X_{i}>T$ and plug this into our OCRS.
Compared to prior optimal algroithms for the same setting, our algorithm has
the advantage that it is very simple to implement since it does not require
solving a complicated dynamic/linear program. (See Section 1.1) We state our
algorithm precisely, and prove that it is
$(1-O(\frac{1}{\sqrt{k}}))$-selectable against a fixed-order adversary in
Section 4.333A fixed-order adversary sets the order to reveal the elements
offline, and based only on the distributions.

An Impossibility for OCRS against almighty adversary. While the fixed-order
adversary is standard in the prophet inequality literature, it is also
important to explore the extent to which these same guarantees can hold
against an almighty adversary.444An almighty adversary sets the order to
reveal online, and with full knowledge of all random variables and all past
decisions of the algorithm. For example, the prophet inequality of [AKW14]
holds against an almighty adversary, but does not imply an OCRS. Our second
result shows that this is for good reason: no OCRS can guarantee a
selectability better than $1-\Omega(\sqrt{\frac{\log k}{k}})$ against an
almighty adversary. We state and prove this in Section 5.

###  1.1 Detailed Discussion of Related Work

As previously referenced, prior to our work it is already known that the
optimal selectability for OCRS and the optimal prophet inequality against a
fixed-order adversary is $1-\Theta(\frac{1}{\sqrt{k}})$ ([HKS07] proves the
impossibility, and [Ala14] designs the first algorithm matching it). [AKW14]
designs a prophet inequality that achieves the same
$(1-O(\frac{1}{\sqrt{k}}))$-approximation against an almighty adversary, but
this does not imply an OCRS. The analysis in [HKS07] implies an extremely
simple OCRS (accept every active element with probability
$1-\Theta(\sqrt{\frac{\log k}{k}})$) that is $(1-\Theta(\sqrt{\frac{\log
k}{k}}))$-selectable against an almighty adversary. We show that this is the
best possible guarantee (Theorem 5.1). Because we view our main result as a
simpler algorithm achieving (asymptotically) the same guarantees as prior
work, we now overview these works in greater detail.

The $\gamma$-Conservative magician in [Ala14]. As previously mentioned,
[Ala14] implies an optimal $(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS against
a fixed-order adversary. [Ala14, Definition 2] describes a
$\gamma$-Conservative Magician, which is an algorithm that adaptively computes
thresholds $\theta_{i}$ and accepts an active element on step $i$ if and only
if the number of selected elements (or broken wands in the terminology of
[Ala14]) $W_{i}$ in steps $1,\ldots,i-1$ is less than $\theta_{i}$. The
cumulative distribution function of $W_{i}$ is computed adaptively at every
step through dynamic programming equation. Once the CDF of $W_{i}$ has been
computed, $\theta_{i}$ is chosen so that the ex-ante probability that
$W_{i}\leq\theta_{i}$ is at least $\gamma$. [Ala14] shows that one can choose
$\gamma=1-\frac{1}{\sqrt{k+3}}$ and $\theta_{i}\leq k$ for all $i$, which
effectively guarantees an OCRS against a fixed-order adversary that is
$1-\frac{1}{\sqrt{k+3}}$-selectable [Ala14, Theorem 4]. In comparison to
[Ala14], our main result achieves the same asymptotic guarantee, but is
considerably simpler (in particular, the analysis requires minimal
calculations, and there is no dynamic program).

Characterization of the optimal OCRS and prophet inequality for $k$-uniform
matroids in [JMZ22]. [JMZ22] studies the optimal OCRS for $k$-uniform matroids
(i.e. with optimal selection probability $c$). They characterize the optimal
OCRS for $k$-uniform matroids as the solution to a linear program. Then, using
a differential equation, they show that this optimal solution corresponds to a
$\gamma^{*}_{k}$-Conservative magician, where
$\gamma^{*}_{k}>1-\frac{1}{\sqrt{k+3}}$. [JMZ22] extend their OCRS guarantees
against an online adversary 555An online adversary adaptively decides which
elements to reveal next, based on which elements were active. But the online
adversary does not know the status of the unrevealed elements (i.e. it has the
same information as the algorithm).

In comparison to [JMZ22], our main result achieves the same
$1-O(\frac{1}{\sqrt{k}})$ asymptotic guarantee against a fixed-order
adversary, but is, again, considerably simpler and does not require solving
any mathematical program. Although our analysis holds against the weaker
fixed-order adversary, this assumption is sufficient for many popular
applications of OCRS and prophet inequalities in online stochastic
optimization.

The Rehearsal algorithm in [AKW14]. As previously discussed, [AKW14] gives an
optimal $(1-O(\frac{1}{\sqrt{k}}))$-approximation prophet inequality against
an almighty adversary, and even when knowing only a single sample from each
distribution, using the rehearsal algorithm. Their rehearsal algorithm takes a
sample from each distribution, and stores the $k-2\sqrt{k}$ highest samples at
$T_{1},\ldots,T_{k-2\sqrt{k}}$, then repeats $T_{i}:=T_{k-2\sqrt{k}}$ for all
$i\in[k-2\sqrt{k},k]$. When processing the online element $X_{e}$, $e$ is
accepted if and only if there is an unfilled slot $i$ with $X_{e}>T_{i}$. If
$X_{e}$ is accepted, it fills the highest such slot (the slot with the highest
threshold).

Their analysis does not imply an OCRS (indeed, it is not even clear what it
would mean to set the thresholds $T_{i}$ in an OCRS). But, their analysis does
hold against an almighty adversary. In comparison, our prophet inequality is
simpler, and implies an OCRS. But, our algorithm requires some knowledge of
the distributions, rather than just a single sample.666Turning our OCRS into a
prophet inequality requires a value $T$ such that $\sum_{i}\Pr[X_{i}>T]\approx
k$, and an accurate estimate of $\sum_{j\leq i}\Pr[X_{j}>T]$ for all $i$.
Estimates up to an additive $\sqrt{k}$ with high probability suffice. This can
certainly be achieved with polynomially-many samples, but not a single sample.

Our analyses have similar flavors: both works connect our algorithms’
performance to a random walk. These random walks are quite different (for
example, the random walk in [AKW14] is correlated, and ours is not. Our random
walk has non-integral step sizes, while theirs does not), and are used to
analyze different algorithms. While there are some coincidental similarities
(for example, our Lemma A.2 is a generalization of their Lemma 10), the core
of our proof is simply connecting our algorithm to a random walk, whereas the
bulk of their proof is coping with the correlation in their random walk and
any associated calculations.

Other Related Work. There is substantial additional work on both prophet
inequalities and online contention resolution schemes, subject to various
other constraints [CHMS10, KW12, GHK+14, DK15, Rub16, RS17, DFKL17, AW18,
GW19, ANSS19, EFGT20, CDF+22, CCF+22, SSZ23, MMG23]. Aside from this, there is
not much technical overlap with this works (in particular, a substantial
fraction of these works consider richer feasibility constraints, and therefore
achieve constant-factor approximations rather than approximations approaching
$1$).

Other works have also considered a special class of static threshold policies
for $k$-unit prophet inequalities which set a single threshold and accept any
element that exceeds it subject to the feasibility constraint. [HKS07]
provides a prophet inequality with a static threshold which is a
$1-O(\sqrt{\frac{\log(k)}{k}})$ approximation. [CDL20] proposes a different
static threshold prophet inequality with the same
$1-O(\sqrt{\frac{\log(k)}{k}})$ asymptotic guarantee improving the
approximation for small $k$. [JMZ23] uses a mathematical programming approach
to show that the policy in [CDL20] is worst-case optimal within all static
threshold policies. In contrast to these works, we study the design and
limitations of the richer class of adaptive strategies for the more general
setting of OCRS.

In the context of _offline_ contention resolution schemes (introduced in
[CVZ14]), [KS23] shows a simple optimal contention resolution scheme for
$k$-uniform matroids, which is
$(1-\binom{n}{k}(1-\frac{k}{n})^{n+1-k}(\frac{k}{n})^{k})$-selectable. Their
method is not extendable to the online case because it requires knowing the
set of active elements $A$ in advance.

###  1.2 Roadmap

Section 2 follows with preliminaries and definitions. Section 3 is a warmup
that rules out optimal selectability via _extremely_ simple greedy algorithms.
Section 4 presents a complete proof of our new
$(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS. Section 5 contains a proof of the
$1-\Omega(\sqrt{\frac{\log(k)}{k}})$ upper bound on the probability of
selection of any OCRS against almighty adversaries. Section 6 concludes.

##  2 Preliminaries

###  2.1 Online contention resolution schemes

Online contention resolution schemes were first introduced by [FSZ16] as a
broadly applicable online rounding framework. Suppose we are given a finite
ground set of elements $N=\\{e_{1},\ldots,e_{n}\\}$. Consider a family of
feasible sets $\mathscr{F}\subset 2^{N}$ which is downwards-closed (that is,
if $I\in\mathscr{F}$ and $J\subseteq I$, then $J\in\mathscr{F}$). Let

$P_{\mathscr{F}}=\text{conv}(\mathbbm{1}_{I}|I\in\mathscr{F})\in[0,1]^{n}$

be the convex hull of all characteristic vectors in $\mathscr{F}$. We will
refer to $P_{\mathscr{F}}$ as the polytope corresponding to the family
$\mathscr{F}$.

######  Definition 2.1 (Online contention resolution scheme (OCRS))

Consider the following online selection setting. A point $x\in
P_{\mathscr{F}}$ is given and let $R(x)$ be a random subset of active
elements, where element $e_{i}$ is active with probability $x_{i}$. The
elements $e\in N$ reveal one by one whether they are active, i.e. $e\in R(x)$,
and the decision of the algorithm whether to select an active element is taken
irrevocably before the next element is revealed. An OCRS for $P_{\mathscr{F}}$
is an online algorithm that selects a subset $I\subseteq R(x)$ such that
$\mathbbm{1}_{I}\in P_{\mathscr{F}}$.

Many of the natural OCRS considered in [FSZ16] are also greedy.

######  Definition 2.2 (Greedy OCRS)

A greedy OCRS $\pi$ for $P_{\mathscr{F}}$ is an OCRS that for any $x\in
P_{\mathscr{F}}$, defines a downwards-closed subfamily of feasible sets
$\mathscr{F}_{x}\subseteq\mathscr{F}$ and an element $e$ is selected when it
arrives if, together with the already selected elements, the obtained set is
in $\mathscr{F}_{x}$

Our next goal is to define the notion of $c$-selectability, which is a notion
of performance of the OCRS. Intuitively, an OCRS is $c$-selectable if for any
element $e$ the probability that the OCRS selects $e$ given that it is active
is at least $c$, where we desire $c$ to be as large as possible. In order to
talk about $c$-selectability in a rigorous way, we need to specify the power
of the adversary that chooses the order of the elements revealed to the OCRS
in an online fashion (Definition 2.1). There are three main types of
adversaries considered in prior work, which we define below.

###### Definition 2.3

(Strength of adversary) In the setting of Definition 2.1, there is an
underlying adversary which can choose the order in which the elements are
revealed to the OCRS. We define three different types of adversaries:
(i) Offline/Fixed-Order adversary, which chooses the order of the elements
upfront before any are revealed. Such an adversary knows $x$ and the
distribution of $R(x)$, but not the realized active elements.
(ii) Online adversary, which adaptively chooses next element to reveal using
the same information available to the algorithm ($x$, the distribution of
$R(x)$, and which elements have been revealed, which were active, and which
were selected).
(iii) Almighty adversary, which knows upfront the outcomes of all random
events, which includes the realization of $R(x)$ and the outcome of the random
bits that the OCRS might query.

We are now ready to define the notion of $c$-selectability.

###### Definition 2.4

($c$-selectability) Let $c\in[0,1]$. An OCRS for $P$ is $c$-selectable against
an adversary $\mathscr{A}$ if for any $x\in P$ and $e\in N$, we have

$\Pr[e\text{ is selected by the OCRS against $\mathscr{A}$}|e\text{ is
active}]\geq c$

It is often true that a larger probability of selection $c$ can be achieved
when $x$ is supposed to be in a down-scaled version of $P$.

###### Definition 2.5

($(b,c)$-selectability). Let $b,c\in[0,1]$. An OCRS for $P$ is
$(b,c)$-selectable against an adversary $\mathscr{A}$ if for any $x\in b\cdot
P$ and $e\in N$, we have

$\Pr[e\text{ is selected by the OCRS against $\mathscr{A}$}|e\text{ is
active}]\geq c$

An important observation is that a $(b,c)$-selectable OCRS for $b\cdot P$
against $\mathscr{A}$ implies a $bc$-selectable OCRS for $P$ against
$\mathscr{A}$.

###### Observation 2.6

([FSZ16]) A $(b,c)$-selectable OCRS for $P$ implies a $bc$-selectable OCRS for
$P$.

The reduction in Observation 2.6 is as follows: The $bc$-selectable OCRS
essentially runs the given $(b,c)$-selectable OCRS while scaling down by $b$
each of the probabilities $x_{i}$ online (i.e. consider selecting an active
element independently with probability $b$). For more details see [FSZ16].

###### Remark 2.7

It is important to emphasize that a $c$-selectable ORCS for $P$ gives
selection guarantees on all $x\in P$, while a $(b,c)$-selectable OCRS for $P$
gives guarantees only when $x\in b\cdot P$ (i.e. a scaled-down version of
$P$).

###  2.2 OCRS and Prophet inequalities

As previously discussed, one of the many applications of OCRS is to the
prophet inequality problem. Here we define the general setting of the prophet
inequality problem. We begin with a setup for the environment.

General setting and prophet:  We are given a group set
$N=\\{e_{1},\ldots,e_{n}\\}$ and a downwards-closed family
$\mathscr{F}\subseteq 2^{N}$ of feasible subsets. Each of the elements $e_{i}$
is associated with a value $v_{i}$. A prophet is an offline algorithm, which
sees the vector $(v_{1},\ldots,v_{n})$ and outputs the feasible set
$\text{MAX}(v)=\text{argmax}_{I\in F}\sum_{i\in I}v_{i}$. We denote by
$\text{OPT}(v)=\sum_{i\in\text{MAX}(v)}v_{i}$ the weight of the maximum set.

###### Definition 2.8

(Prophet inequality) Suppose we are given a downwards-closed feasibility
constraint $\mathscr{F}\subseteq 2^{N}$. Suppose each element $e_{i}\in N$
takes value $v_{i}\in\mathbb{R}_{\geq 0}$ independently from some known
distribution $\mathscr{D}_{i}$. These values are presented one-by-one to an
online algorithm $\pi$ in an adversarial order (again specified as offline,
online, or almighty). On seeing a value the algorithm needs to immediately and
irrevocably decide whether to select the next element $e_{i}$, while always
maintaining that the set of selected elements so far is in $\mathscr{F}$.
Let’s denote the set of selected elements by $\pi$ as $A^{*}(v)$. We say that
$\pi$ induces a prophet inequality with competitive ratio $c$ for
$\mathscr{F}$ if

$\mathbb{E}_{v\sim\mathscr{D}}[\sum_{i\in A^{*}(v)}v_{i}]\geq
c\cdot\mathbb{E}_{v\sim\mathscr{D}}[\text{OPT}(v)]$

where $\mathscr{D}=\mathscr{D}_{1}\times\ldots\times\mathscr{D}_{n}$ is the
product of the independent distributions $\mathscr{D}_{i}$

As with OCRS, in order to talk about $\alpha$-approximation, we need to
specify the power of the adversary which specifies the order of the elements
revealed. Completely analogously to Definition 2.3, we could have offline,
online, and almighty adversaries.
[FSZ16] showed that a $c$-selectable OCRS against a particular adversary
$\mathscr{A}$ implies a $c$-approximation prophet inequality against an
adversary of the same strength.

###### Theorem 2.9

([FSZ16]) A $c$-selectable OCRS against (offline/online/almighty) adversary
implies the existence of a $c$-approximation prophet inequality algorithm.

In the classical prophet inequality formulation [KS78], the value of the
online algorithm $\pi$ is compared directly to the offline optimum. [LS18]
consider an ex-ante prophet inequality, where the value of $\pi$ is compared
to the optimal value of a convex relaxation, which upper bounds the offline
optimum. [LS18] show that this stronger notion of an ex-ante prophet
inequality is equivalent to an OCRS.

###  2.3 $k$-uniform matroids

In this section, we give a definition for $k$-uniform matroids, which is the
feasibility constraint that we will use throughout the paper. Given a ground
set $N=\\{e_{1},\ldots,e_{n}\\}$, the $k$-uniform matroid is the matroid
consisting of all subsets of $N$ of size at most $k$.

###### Definition 2.10

($k$-uniform matroid) The $k$-uniform matroid for $N$ is
$M_{k}=(N,\mathscr{F}_{k})$ , where

$\mathscr{F}_{k}=\\{S\subseteq N||S|\leq k\\}$

and the corresponding polytope of $\mathscr{F}_{k}$ is given by

$P_{k}=\\{x\in\mathbb{R}_{\geq 0}^{n}|\sum_{i=1}^{n}x_{i}\leq k\\}$

We remind the reader of prior work on OCRSs and prophet inequalities for
$k$-uniform matroids below.

######  Theorem 2.11 ([HKS07, Ala14, AKW14, JMZ22])

The following is known, prior to our work, on OCRSs and prophet inequalities
for $k$-uniform matroids:

  * •

Against a fixed-order/online adversary, the best prophet inequalities and
OCRSs for $\mathscr{F}_{k}$ achieve a guarantee of
$1-\Theta(\frac{1}{\sqrt{k}})$ (lower bound: [HKS07], algorithm: [Ala14,
JMZ22]).

  * •

Against an almighty adversary, the best prophet inequalities for
$\mathscr{F}_{k}$ achieve a guarantee of $1-\Theta(\frac{1}{\sqrt{k}})$ (lower
bound: [HKS07], algorithm: [AKW14]).

  * •

Against an almighty adversary, the best-known OCRS achieves a guarantee of
$1-\Theta(\sqrt{\frac{\log k}{k}})$ (implicit in [HKS07]).

##  3 Warmup: Naive approaches towards an OCRS

The goal of this section is to explore a few exceptionally simple algorithms
that one might try to use to construct an optimal OCRS for $k$-uniform
matroids. We will present results about whether optimal factors are possible
against adversaries of variable strengths. In particular, we will show that
one cannot achieve a $(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS by using a
very simple greedy algorithm or a tweaked variant of it utilizing a partition
matroid.

We first consider a naive greedy OCRS, which greedily selects active elements
until it has selected $k$ elements. Formally in the language of Definition
2.2, for this OCRS we have $\mathscr{F}=\\{S\subseteq N||S|=k\\}$ and
$\mathscr{F}_{x}=\mathscr{F}$ for all $x$. We quickly establish that the naive
greedy OCRS is not $(b,c)$-selectable even against an offline/fixed-order
adversary for any $b,c$ satisfying $bc=1-O(\frac{1}{\sqrt{k}})$. This would
rule out constructing exceptionally simple OCRS via Observation 2.6.

###### Theorem 3.1

There are no $b,c$, satisfying $bc=1-O(\frac{1}{\sqrt{k}})$, such that the
naive greedy OCRS is $(b,c)$-selectable against the offline adversary.

Proof. See Appendix A.1 for a proof.

Our second result is that even if we complicate the naive greedy OCRS slightly
it does not imply an optimal factor. Suppose instead of using the $k$-uniform
matroid, we use a partition matroid and the algorithm is to greedily select
active elements as long as the set of selected elements lies in the partition
matroid. Formally in the language of Definition 2.2, the feasibility family
$\mathscr{F}_{x}$ is given by a partition matroid (which could depend on $x$).
For a given $x$, the partition matroid is of the form
$\\{(n_{i},k_{i},S_{i})\\}_{i=1}^{s}$, where $\sum_{i=1}^{s}k_{i}=k$,
$\sum_{i=1}^{s}n_{i}=n$ and the sets $S_{i}$ are pairwise disjoint and satisfy
$\cup_{i=1}^{s}S_{i}=N$ and $|S_{i}|=n_{i}$. Here we can select at most
$k_{i}$ elements from $S_{i}$. We next prove that such scheme is not
$(b,c)$-selectable even against the offline adversary for any $b,c$ satisfying
$bc=1-O(\frac{1}{\sqrt{k}})$.

###### Theorem 3.2

There are no $b,c$, satisfying $bc=1-O(\frac{1}{\sqrt{k}})$, such that the
naive greedy OCRS with a partition matroid is $(b,c)$-selectable against the
offline adversary.

Proof. See Appendix A.1 for a proof.

###### Remark 3.3

Theorems 3.1 and 3.2 say that one cannot use the transformation in Observation
2.6 on a naive greedy OCRS to obtain a $(1-O(\frac{1}{\sqrt{k}}))$-selectable
OCRS. Thus ruling out some exceptionally simple ways to construct a
$(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS for $k$-uniform matroids.

###### Remark 3.4

Intuitively, the above variations of the naive greedy schemes fail to be
optimal because they tend to select too many elements early in the process in
comparison to the expected number of active elements so far. Thus, they are
likely to run out of space when they reach the last element. Our main
algorithm in Section 4 attempts to counter this.

We conclude by reminding the reader that the naive greedy OCRS is
$(b,c)$-selectable against the almighty adversary for some $b,c$ satisfying
$bc=1-O(\sqrt{\frac{\log(k)}{k}})$. The proof is implicit in the analysis of
the $(1-O(\sqrt{\frac{\log(k)}{k}}))$-approximate prophet inequality of
[HKS07].

######  Theorem 3.5 (Implicit in [HKS07])

The naive greedy OCRS is
$(1-\sqrt{\frac{2\log(k)}{k}},1-\frac{1}{k})$-selectable against the almighty
adversary. By the tranformation in Observation 2.6 this implies a
$(1-O(\sqrt{\frac{\log(k)}{k}}))$-selectable OCRS for $k$-uniform matroids.

Proof. We remind the reader of the simple proof in Appendix A.1.

##  4 A simple optimal OCRS for $k$-uniform matroids

The goal of this section is to give a new
$(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS against offline/fixed-order
adversaries. Because the adversary must commit to an ordering using just
knowledge of $x$, and the distribution of $R(x)$, we let
$e_{1},e_{2}\ldots,e_{n}$ refer to the elements that are revealed, in order.
Note that the events $e_{i}\in R(x)$ are independent. We will show that the
following algorithm is a $(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS for
$k$-uniform matroids.

OCRS($x$)

  1. 1.

Initialize the set of selected elements $A_{0}=\emptyset$.

  2. 2.

For $i=1,\ldots,n$ do:

    1. 2.a

If $e_{i}$ is active and $|A_{i-1}|+1\leq(1-\frac{1}{\sqrt{k}})(\sum_{j\leq
i}x_{j})+\sqrt{k}$, then select $e_{i}$ with probability
$(1-\frac{1}{\sqrt{k}})$ (i.e. $A_{i}=A_{i-1}\cup e_{i}$) and otherwise
discard it (i.e. $A_{i}=A_{i-1}$).

    2. 2.b

If $|A_{i-1}|+1>(1-\frac{1}{\sqrt{k}})(\sum_{j\leq i}x_{j})+\sqrt{k}$ or
$e_{i}$ is inactive, then discard $e_{i}$ (i.e. $A_{i}=A_{i-1}$).

Observe that OCRS is derived from an even simpler
$(1-\frac{1}{\sqrt{k}},1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS, by using the
reduction of Observation 2.6. We clearly state this simpler algorithm below
(we also state it parameterized by $d$, as our entire analysis follows for
general $d$, and then is optimized for $d:=\sqrt{k}$ at the very end).

Algorithm($d,x$)

  1. 1.

Initialize the set of selected elements $B_{0}=\emptyset$.

  2. 2.

For $i=1,\ldots,n$ do:

    1. 2.a

If $e_{i}$ is active and $|B_{i-1}|+1\leq\sum_{j\leq i}x_{j}+d$, then select
$e_{i}$, and otherwise discard it.

    2. 2.b

If $|B_{i-1}|+1>\sum_{j\leq i}x_{j}+d$ or $e_{i}$ is inactive, then discard
$e_{i}$.

###### Observation 4.1

If Algorithm($\sqrt{k},x$) is a
$(1-\frac{1}{\sqrt{k}},1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS for $P_{k}$,
then OCRS($x$) is a $(1-O(\frac{1}{\sqrt{k}}))$-selectable OCRS for $P_{k}$.

Proof. OCRS($x$) is exactly the result of applying the [FSZ16] reduction of
Observation 2.6 to Algorithm($\sqrt{k},x$), with $b=1-\frac{1}{\sqrt{k}}$ and
$c=$. Therefore, by Observation 2.6, OCRS($x$) is
$(1-\frac{1}{\sqrt{k}})\cdot(1-O(\frac{1}{\sqrt{k}}))$-selectable (i.e.
$(1-O(\frac{1}{\sqrt{k}}))$-selectable) whenever Algorithm($\sqrt{k},x$) is
$(1-\frac{1}{\sqrt{k}},1-O(\frac{1}{\sqrt{k}}))$-selectable.

In line with Remark 2.7, we emphasize that Algorithm($\sqrt{k},x$) operates in
a universe where the probabilities $x_{i}$ are scaled down by
$b=1-\frac{1}{\sqrt{k}}$, while OCRS($x$) operates with the original
probabilities $x_{i}$.

Our key proposition is that Algorithm($d$,$x$) is indeed sufficiently
selectable.

###### Proposition 4.2

Algorithm($d$,$x$) is $(1-\frac{d}{k},1-\frac{2}{d-1})$-selectable over
$P_{k}$. That is, for all $x\in(1-\frac{d}{k})\cdot P_{k}$, Algorithm($d$,$x$)
is $(1-\frac{2}{d-1})$-selectable.

The proof of Proposition 4.2 proceeds in two steps. The first (shorter) step
is to guarantee that Algorithm($d,x$) always selects at most $k$ elements. The
second is to show that every element is accepted with sufficient probability.

###### Observation 4.3

For all $x\in(1-\frac{d}{k})\cdot P_{k}$, Algorithm($d,x$) accepts at most $k$
elements.

Proof. Observe that, at all times, $|B_{i}|\leq\sum_{j\leq i}x_{j}+d$. As
$\sum_{j}x_{j}\leq k\cdot(1-\frac{d}{k})=k-d$, this implies that $|B_{n}|\leq
k$, and the algorithm accepts at most $k$ total elements.

We now proceed to prove that the algorithm is sufficiently selectable. For
this part of the analysis, it will be convenient to consider the process
$S_{i}:=|B_{i}|-\sum_{j\leq i}x_{j}$. Observe that $S_{i}$ has the following
dynamics. First, $S_{0}=0$. Further if $S_{i-1}+1-x_{i}\leq d$ (i.e. have
”space” to accept $e_{i}$), then

$S_{i}:=\begin{cases}S_{i-1}+1-x_{i}&\text{if $e_{i}$ is active (with
probability $x_{i}$)}\\\ S_{i-1}-x_{i}&\text{if $e_{i}$ is inactive (with
probability $1-x_{i}$)}\\\ \end{cases}$

and if $S_{i-1}+1-x_{i}>d$ (i.e. don’t have ”space” to accept $e_{i}$), then
$S_{i}=S_{i-1}-x_{i}$ regardless of whether $e_{i}$ is active (with
probability 1). Additionally, consider the process
$W_{i}=\sum_{j=1}^{i}X_{j}$, where

$X_{i}=\begin{cases}1-x_{i}&\text{if $e_{i}$ is active (with probability
$x_{i}$)}\\\ -x_{i}&\text{if $e_{i}$ is inactive (with probability
$1-x_{i}$)}\\\ \end{cases}$

Intuitively, $W_{i}$ tracks the number of active elements above expectation
(among the first $i$), and $S_{i}$ tracks the number of _selected_ elements
above the expected number of active elements (among the first $i$).

###### Lemma 4.4

$W_{i}-S_{i}$ is exactly equal to the number of active elements that are
discarded amongst the first $i$.

Proof. Let $G_{i}$ be the set of active elements in the first $i$ revealed
elements. Then, by definition $W_{i}=|G_{i}|-\sum_{j\leq i}x_{j}$. Thus,
$W_{i}-S_{i}=|G_{i}|-|B_{i}|$ and the conclusion follows because $|B_{i}|$ is
the number of active and selected elements in the first $i$ revealed ones.

By Lemma 4.4 it follows that the difference $W_{i}-S_{i}$ increases by one if
and only if $e_{i}$ is active and discarded, and stays the same otherwise. The
rest of the proof requires just two more natural steps. First, we characterize
which elements are active and discarded, just as a property of the random
process $W$. Second, we bound the probability of this occurring.

###### Lemma 4.5

Element $e_{i}$ is active and discarded by Algorithm($d,x$) if and only if
$\lceil W_{i}\rceil>d$ and $\lceil W_{i}\rceil>\lceil W_{j}\rceil$ for all
$j<i$. That is, $e_{i}$ is active and discarded by Algorithm($d,x$) if and
only if the random process $W$ reaches a new integral height for the first
time.

Proof. By Lemma 4.4 the difference $W_{i}-S_{i}$ increases by 1 when $e_{i}$
is active and discarded and stays the same otherwise. Therefore, the $n$-th
active and discarded elements is $e_{i}$, where $i$ is the smallest index such
that $W_{i}-S_{i}=n$. Let’s now fix an arbitrary $n\geq 1$. To prove the
lemma, it is enough to show that $i$ is the smallest index such that
$W_{i}-S_{i}=n$ if and only if $i$ is the smallest index such that $\lceil
W_{i}\rceil=d+n$.

We begin with the “only if” direction. Suppose $i_{n}$ is the smallest index
such that $W_{i_{n}}-S_{i_{n}}=n$. By Lemma 4.4, element $e_{i_{n}}$ is active
and discarded. Therefore, by the selection rule of Algorithm($d,x$) we get
that $S_{i_{n}-1}+1-x_{i_{n}}>d$ and therefore
$S_{i_{n}}=S_{i_{n}-1}-x_{i_{n}}$. This implies that $S_{i_{n}}>d-1$. We also
know that $S_{i_{n}}\leq d$ (because $S_{i}$ stores the difference between
$|B_{i}|$ and $\sum_{j\leq i}x_{i}$, which is hard-coded to be at most $d$).
Using these two inequalities along with our hypothesis that
$W_{i_{n}}-S_{i_{n}}=n$ we obtain:

$W_{i_{n}}=S_{i_{n}}+n\in(d+n-1,d+n],\text{ and therefore: }\lceil
W_{i_{n}}\rceil=d+n.$

Further, by definition of $i_{n}$ as the _first_ index such that
$W_{i}-S_{i}=n$, we know that for all $j<i_{n}$: $W_{j}\leq S_{j}+n-1$.
Moreover, we also know that $S_{j}\leq d$ for all $j$ (again, because $S_{j}$
stores the difference between $|B_{j}|$ and $\sum_{\ell\leq j}x_{\ell}$, which
is at most $d$). Therefore, $W_{j}\leq d+n-1$, and we conclude that $\lceil
W_{j}\rceil\leq d+n-1<\lceil W_{i_{n}}\rceil$ for all $j<i_{n}$. Therefore,
$i_{n}$ is the smallest index such that $\lceil W_{i_{n}}\rceil=d+n$. This
establishes that if $i_{n}$ is the smallest index such that
$W_{i_{n}}-S_{i_{n}}=n$, then $i_{n}$ is the smallest index such that $\lceil
W_{i_{n}}\rceil=d+n$.

Now we show the “if” direction. Suppose that $i_{n}$ is the smallest index
such that $\lceil W_{i_{n}}\rceil=d+n$. Since $W_{i_{n}}-S_{i_{n}}$ is an
integer, and because $S_{i_{n}}\leq d$, it must be the case that
$W_{i_{n}}-S_{i_{n}}\geq n$ . Let $i^{*}\leq i_{n}$ be the smallest index such
that $W_{i^{*}}-S_{i^{*}}=n$ (such $i^{*}$ exists because $W_{i}-S_{i}$ always
increases by 1 or stays the same, and because we have just shown that
$W_{i_{n}}-S_{i_{n}}=n$). By the “only if” proof above, $i^{*}$ is the
smallest index such that $\lceil W_{i^{*}}\rceil=d+n$, implying that in fact
$i^{*}=i_{n}$, as desired. This establishes that if $i_{n}$ is the smallest
index such that $\lceil W_{i_{n}}\rceil=d+n$, then $i_{n}$ is also the
smallest index such that $W_{i_{n}}-S_{i_{n}}=n$.

This completes the proof: the $n^{th}$ active element discarded by the
algorithm is the smallest index such that $W_{i}-S_{i}=n$. By the work above,
this is exactly the smallest index such that $\lceil W_{i}\rceil=n+d$.
Therefore, discarded elements are exactly those that reach a new integral
height for the first time.

Our remaining task is simply to upper bound the probability that $W_{i}$
reaches a new integral height, for all $i$.

###### Lemma 4.6

For each $m\in[1,n]$

$\Pr(\lceil W_{m}\rceil>d\text{ and }\lceil W_{m}\rceil>\lceil
W_{i}\rceil\text{ for $i<m$})\leq\frac{2x_{m}}{d-1}$

Proof. Fix $m\in[1,n]$. Consider the process $Q_{i}:=W_{m-i-1}-W_{m-1}$ for
$i=0,1,\ldots,m-1$. Intuitively, $\\{Q_{i}\\}_{i=0}^{m-1}$ is the “reversed”
process $W$ starting at time-step $m-1$. Note that $Q_{0}=0$ and
$Q_{m-1}=-W_{m-1}$. Observe also that

$Q_{i}-Q_{i-1}=W_{m-i-1}-W_{m-1}-(W_{m-i}-W_{m-1})=W_{m-i-1}-W_{m-i}=-X_{m-i}$

Note that since the adversary does not see which elements are active and has
to commit to their order a priori, we know that $X_{1},\ldots,X_{n}$ are
independent. We also note that

$\mathbb{E}[X_{i}]=x_{i}(1-x_{i})-x_{i}(1-x_{i})=0$

By combining the previous two facts, we obtain that $\\{Q_{i}\\}_{i=0}^{m-1}$
is a discrete martingale. Let’s denote its maximum by $M_{m-1}=\max_{1\leq
i\leq m-1}Q_{i}$. We will next show that if $\lceil W_{m}\rceil>d$ and $\lceil
W_{m}\rceil>\lceil W_{i}\rceil$ for $i<m$, then the following two events have
to hold:

  * •

$e_{m}$ is active.

  * •

$M_{m-1}<1$ and $Q_{m-1}\leq-(d-1)$. That is, the martingale $Q$ can never
reach a height of $1$, _and_ it must finish below $-(d-1)$.

Indeed, since $\lceil W_{m}\rceil>\lceil W_{m-1}\rceil$, then $e_{m}$ is
active. Also since $\lceil W_{m}\rceil>\lceil W_{i}\rceil$ for $i<m$, we know
that $W_{m}>W_{m-i-1}$ for all $i$. Combining this with the inequality
$W_{m}\leq W_{m-1}+1$, we obtain

$Q_{i}=W_{m-i-1}-W_{m-1}\leq W_{m-i-1}-W_{m}+1<1$

Thus, $Q_{i}<1$ for all $i\in[1,m-1]$ or equivalently $M_{m-1}<1$. The
condition $\lceil W_{m}\rceil>d$ implies that $W_{m}>d$. Using the last
inequality we obtain

$Q_{m-1}=-W_{m-1}\leq-W_{m}+1\leq-(d-1)$

Therefore, we obtained that $e_{m}$ is active, $M_{m-1}<1$ and
$Q_{m-1}\leq-(d-1)$ as desired.

Using the above property combined with the fact that the event whether $e_{m}$
is active is independent of the events $M_{m-1}<1$ and $Q_{m-1}\leq-(d-1)$
(because $M_{m-1}$ and $Q_{m-1}$ are determined entirely by the previous $m-1$
elements) we obtain that:

$\displaystyle\Pr(\lceil W_{m}\rceil>d\text{ and }\lceil W_{m}\rceil>\lceil
W_{i}\rceil\text{ for $i<m$})$ $\displaystyle\leq\Pr(\\{e_{m}\text{ is
active}\\}\cap\\{M_{m-1}<1\text{ and }Q_{m-1}\leq-(d-1)\\})$
$\displaystyle=\Pr(e_{m}\text{ is active})\cdot\Pr(M_{m-1}<1\text{ and
}Q_{m-1}\leq-(d-1))$ $\displaystyle=x_{m}\cdot\Pr(M_{m-1}<1\text{ and
}Q_{m-1}\leq-(d-1))$

So, the final step is to upper bound $\Pr(M_{m-1}<1\text{ and
}Q_{m-1}\leq-(d-1))$, which is just a claim about martingales that change by
at most $1$ in each step. Lemma A.2, which is a short application of the
Optional Stopping Theorem, applied for $a=1,b=-(d-1)<0$, and $K=1$ implies
that:

$\Pr(M_{m-1}<1\text{ and }Q_{m-1}\leq-(d-1))\leq\frac{2}{d-1}.$

Therefore,

$\Pr(\lceil W_{m}\rceil>\lceil W_{i}\rceil\text{ for $i<m$ and }\lceil
W_{m}\rceil>d)\leq\frac{2x_{m}}{d-1},$

which concludes the proof of the lemma.

This suffices to wrap up the proof of Proposition 4.2.

Proof of Proposition 4.2. We have that

$\displaystyle\Pr(e_{m}\text{ is selected}|e_{m}\text{ is active})$
$\displaystyle=1-\Pr(e_{m}\text{ is discarded}|e_{m}\text{ is active})$
$\displaystyle=1-\frac{\Pr(e_{m}\text{ is active and discarded
})}{\Pr(e_{m}\text{ is active})}$ $\displaystyle\geq
1-\frac{\frac{2x_{m}}{d-1}}{x_{m}}=1-\frac{2}{d-1}\text{ (by Lemma
\ref{prob_upper_bd}).}$

Setting $d=\sqrt{k}$ in Proposition 4.2 we get

###### Corollary 4.7

Algorithm($\sqrt{k},x$) is
$(1-\frac{1}{\sqrt{k}},1-\frac{2}{\sqrt{k}-1})$-selectable, and therefore
OCRS($x$) is $(1-O(\frac{1}{\sqrt{k}}))$-selectable.

###### Remark 4.8

An intuitive comparison with the extremely simple OCRS implied in [HKS07] is
the following. The OCRS from [HKS07] needs to ”scale” probabilities down with
$(1-\Theta(\sqrt{\frac{\log(k)}{k}}))$ in order to have a
$(1-\Theta(\sqrt{\frac{\log(k)}{k}}))$ chance of not running out of space. Our
result shows that if we adaptively select active elements whenever the number
of selected ones does not exceed the expected number by $d$, then we only need
to ”scale” down probabilities by $(1-\Theta(\frac{1}{\sqrt{k}}))$ to have a
$(1-\Theta(\frac{1}{\sqrt{k}}))$ chance of not running out of space.

###### Remark 4.9

Intuitively, an online adversary can potentially manipulate the algorithm by
revealing an element $e_{j}$ with a high with large (resp. small) $x_{j}$ when
the algorithm has selected many (resp. few) elements above the expectation. In
this scenario, the proof of Lemma 4.6 will not go through since the ”reversed”
process $Q_{i}$ could have correlated steps and will (in general) fail to be a
martingale.

##  5 Upper bound against almighty adversaries

Recall that [HKS07] implies that the naive greedy OCRS can be used to obtain a
$(1-O(\sqrt{\frac{\log(k)}{k}}))$-selectable OCRS against the almighty
adversary. (Theorem 3.5) We recall that the almighty adversary knows which
elements are active a priori and also knows everything about the OCRS
(Definition 2.3). In this section we show that, against the almighty
adversary, the probability of selection of any OCRS cannot be greater than
$(1-\Omega(\sqrt{\frac{\log(k)}{k}}))$. This implies that, against almighty
adversaries the factor of $(1-O(\sqrt{\frac{\log(k)}{k}}))$, achieved by the
naive greedy OCRS, is asymptotically optimal. In particular, our main goal in
this section is to prove the following theorem.

###### Theorem 5.1

Suppose that a $c$-selectable OCRS for the $k$-uniform matroid against the
almighty adversary exists. Then $c\leq 1-\Omega(\sqrt{\frac{\log(k)}{k}})$

In our proof of Theorem 5.1 we will only consider the instance $n=2k$ and
vector of probabilities $x_{i}=\frac{1}{2}$ for all $i\in[1,2k]$ (i.e. each
element is active with probability $\frac{1}{2}$). To execute the proof, we
will use the following strategy.

  * •

We will consider the following subclass of almighty adversaries. The adversary
knows which elements are active and everything about the OCRS. However, it
needs to:

    * –

commit to the order in which the elements will be revealed a priori

    * –

reveal all active elements before all inactive ones

This type of restriction will be convenient for the analysis. We will refer to
the class of such adversaries as $\mathscr{H}$.

  * •

Assuming the existence of a $c$-selectable OCRS $\pi$ against adversaries of
class $\mathscr{H}$, we show that there exists $c$-selectable OCRS $\pi^{s}$
against adversaries of class $\mathscr{H}$, which selects the $i$-th revealed
active element with probability independent of the identities of the first $i$
revealed elements. In other words, the probability that $\pi^{s}$ selects the
$i$-th revealed active element is a function $g(i)$ (which depends on $\pi$
but not on the identities of the first $i$ revealed elements). (Section 5.1)

  * •

By using the probability values $\\{g(i)\\}_{i=1}^{2k}$, we construct an
adversary in $\mathscr{H}$. Based on this adversary, we upper bound the
probability of selection $c$ by using the solution to a linear programming
relaxation. (Section 5.2)

Before we proceed with the proof we will fully describe a general model for
how an OCRS works. An arbitrary OCRS $\pi$ operates in the following way:
1. Before any elements are revealed $\pi$ can flip some random coins $coins_{1}$.
2. Once the first element $a_{1}$ is revealed (and whether it is active or not), $\pi$ can flip more random coins $coins^{\prime}_{1}$ and it makes a decision to select / discard $a_{1}$ with some probability based on $coins_{1}$, $coins^{\prime}_{1}$ and the identity of the element $a_{1}$. Let $b_{1}$ be the indicator random variable of the event that $a_{1}$ is selected.
3. Based on the history so far, i.e. $coins_{1},a_{1},coins^{\prime}_{1},b_{1}$, it flips more random coins $coins_{2}$ before the second element is revealed.
4. After the identity of the second element $a_{2}$ (and its activity) is revealed $\pi$ flips more coins $coins^{\prime}_{2}$ (based on the history so far), and makes a decision to select $a_{2}$ or not, which is recorded in an indicator variable $b_{2}$.
5. Let $B_{i}=(coins_{i},a_{i},coins^{\prime}_{i},b_{i})$ where $coins_{i}$ is the random coins $\pi$ flips right before seeing the $i$-the revealed element $a_{i}$, $coins^{\prime}_{i}$ is the random coins $\pi$ flips after seeing $a_{i}$, and $b_{i}$ is the indicator of the event that $\pi$ selects $a_{i}$.
6. In general, as a function of the history $\overline{B}_{i}=\\{B_{1},\ldots,B_{i}\\}$, $\pi$ flips random coins $coins_{i+1}$. Then the $(i+1)$-th element $a_{i+1}$ is revealed. Based on the history $\overline{B}_{i}\cup coins_{i+1}\cup a_{i+1}$, $\pi$ flips more random coins $coins^{\prime}_{i+1}$. Finally, based on the history $\overline{B}_{i}\cup coins_{i+1}\cup a_{i+1}\cup coins^{\prime}_{i+1}$, $\pi$ decides to select / discard $a_{i+1}$, which generates the indicator $b_{i+1}$.
7\.  The procedure described in 6. is repeated until the $n$-th element is
selected / discard.

###  5.1 Defining a symmetric OCRS

Suppose we have a $c$-selectable OCRS $\pi$. Our goal in this section will
first be to define what it means to “apply a permutation” to $\pi$. Then we
will define the “symmetric” OCRS $\pi^{s}$ in the following way:
1 Sample uniformly random permutation $\sigma$ of $N$.
2 Apply $\sigma$ to $\pi$.
We will then show that the probability that $\pi^{s}$ selects the $i$-th
active revealed element is independent on the identities of the first $i$
revealed elements.
We will first introduce some definitions. Given an OCRS $\pi$, and a
permutation $\sigma$ of the ground set $N$, we define $\pi_{\sigma}$ as the
OCRS which “treats” each element $a_{i}$ exactly like $\pi$ would “treat”
$\sigma^{-1}(a_{i})$. Formally we use the following definition.

###### Definition 5.2

Let $\pi$ be an OCRS and $\sigma$ a permutation of $N$. Define $\pi_{\sigma}$
as an OCRS which uses $\pi$ as a black-box in the following way:
1. Before any elements are revealed $\pi_{\sigma}$ queries $\pi$ to flip some random coins $coins_{1}$.
2. Once the first element $a_{1}$ is revealed (and whether it is active or not), $\pi_{\sigma}$ queries $\pi$ on $(coins_{1},\sigma^{-1}(a_{1}))$ to flip more random coins $coins^{\prime}_{1}$. Based on $(coins_{1},\sigma^{-1}(a_{1}),coins^{\prime}_{1})$, $\pi$ will make some decision to select / discard $\sigma^{-1}(a_{1})$ with some probability. Then $\pi_{\sigma}$ selects $a_{1}$ if and only if $\pi$ selects $\sigma^{-1}(a_{1})$. Let $b_{1}$ be the indicator random variable of the event that $a_{1}$ is selected by $\pi_{\sigma}$.
3. $\pi_{\sigma}$ queries $\pi$ on history $coins_{1},\sigma^{-1}(a_{1}),coins^{\prime}_{1},b_{1}$ to generate random coins $coins_{2}$ before the second element is revealed.
4. After the identity of the second element $a_{2}$ (and its activity) is revealed $\pi_{\sigma}$ queries $\pi$ on $coins_{1},$ $\sigma^{-1}$, $(a_{1}),coins^{\prime}_{1},b_{1},coins_{2},\sigma^{-1}(a_{2})$ to flip more random coins $coins^{\prime}_{2}$. Then it queries $\pi$ on $coins_{1},$ $\sigma^{-1}(a_{1}),$ $coins^{\prime}_{1},b_{1},coins_{2},\sigma^{-1}(a_{2}),coins^{\prime}_{2}$ whether to select / discard $\sigma^{-1}(a_{2})$, and $\pi_{\sigma}$ selects $a_{2}$ if and only if $\pi$ selects $\sigma^{-1}(a_{2})$.
5. Let $B_{i}=(coins_{i},a_{i},coins^{\prime}_{i},b_{i})$ where $coins_{i}$ is the random coins $\pi_{\sigma}$ flips by querying $\pi$ right before seeing the $i$-the revealed element $a_{i}$, $coins^{\prime}_{i}$ is the random coins $\pi_{\sigma}$ flips by querying $\pi$ after seeing $a_{i}$, and $b_{i}$ is the indicator of the event that $\pi_{\sigma}$ selects $a_{i}$.
6. In general, as a function of the history $\overline{B}_{i}=\\{B_{1},\ldots,B_{i}\\}$, $\pi_{\sigma}$ will query $\pi$ on $\overline{B^{\prime}}_{i}=\\{B^{\prime}_{1},\ldots,B^{\prime}_{i}\\}$, where $B^{\prime}_{i}=(coins_{i},\sigma^{-1}(a_{i}),coins^{\prime}_{i+1},b_{i})$ to flips random coins $coins_{i+1}$ before the $(i+1)$-th active element $a_{i+1}$ is revealed. Then it queries $\pi$ on $\overline{B^{\prime}}_{i}\cup coins_{i+1}\cup\sigma^{-1}(a_{i+1})$, to generate more random coins $coins^{\prime}_{i+1}$, and then it queries it again on $\overline{B^{\prime}}_{i}\cup coins_{i+1}\cup\sigma^{-1}(a_{i+1})\cup coins^{\prime}_{i+1}$ whether to select $a_{i+1}$ if and only if $\pi$ selects $\sigma^{-1}(a_{i+1})$. This generates an indicator $b_{i+1}$.
7\.  The procedure described in 6. is repeated until the $n$-th element is
selected / discarded.

Similarly to applying a permutation to an OCRS $\pi$, we can apply a
permutation to an adversary $\mathscr{A}$, resulting in an adversary
$\mathscr{A}_{\sigma}$. Intuitively, $\mathscr{A}_{\sigma}$ “treats” element
$a$ like $\mathscr{A}$ would treat $\sigma^{-1}(a)$. We give the following
formal definition. Recall that $\mathscr{H}$ is the class of adversaries
defined in the beginning of this section.

###### Definition 5.3

Let $\mathscr{A}\in\mathscr{H}$ be an adversary and $\sigma$ a permutation of
the ground set $N$. We define the adversary $\mathscr{A}_{\sigma}$ as
operating against an OCRS $\pi$ in the following way:
1\.  Given a set of active elements $A$, $\mathscr{A}_{\sigma}$ queries
$\mathscr{A}$ on a set of active elements $\sigma^{-1}(A)$ against the OCRS
$\pi_{\sigma^{-1}}$. Upon this query $\mathscr{A}$ returns an order in which
to reveal the elements from $N$.
2\.  Given this order, if $\mathscr{A}$ chose to reveal element $a$ in the
$i$-th position, $\mathscr{A}_{\sigma}$ reveals $\sigma(a)$ in the $i$-th
position.

###### Remark 5.4

It is easy to see that if $\mathscr{A}\in\mathscr{H}$, then
$\mathscr{A}_{\sigma}\in\mathscr{H}$.

We next show that the operation of applying a permutation to an OCRS or
adversary is invertible.

###### Proposition 5.5

For a given permutation $\sigma$, the maps $\pi\to\pi_{\sigma}$ and
$\mathscr{A}\to\mathscr{A}_{\sigma}$ are bijections, with inverses
$\pi\to\pi_{\sigma^{-1}}$ and $\mathscr{A}\to\mathscr{A}_{\sigma^{-1}}$
respectively.

Proof. See Appendix A.3 for a proof.

We will now need the following helpful lemma.

###### Lemma 5.6

Let $a\in N$ be an element and $A\subseteq N$ a subset of elements. Let
$\sigma$ be a permutation of $N$, $\pi$ an OCRS, and
$\mathscr{A}\in\mathscr{H}$ an adversary. Then

$\Pr(\pi\text{ selects $a$ against $\mathscr{A}$}|A\text{ are
active})=\Pr(\pi_{\sigma}\text{ selects $\sigma(a)$ against
$\mathscr{A}_{\sigma}$}|\sigma(A)\text{ are active})$

Proof. Consider the interaction between $\pi_{\sigma}$ and
$\mathscr{A}_{\sigma}$ on set of active elements $\sigma(A)$. By Definition
5.3 before the process begins $\mathscr{A}_{\sigma}$ queries $\mathscr{A}$ on
$\sigma^{-1}(\sigma(A))=A$ against OCRS $(\pi_{\sigma})_{\sigma^{-1}}=\pi$
(Proposition 5.5). Based on this if $\mathscr{A}$ chooses to first reveal the
active elements $A$ to $\pi$ in some order, $\mathscr{A}$ will reveal
$\sigma(A)$ to $\pi_{\sigma}$ in the same order (Definition 5.3). Thus, if we
now pair $\pi$ and $\pi_{\sigma}$ as in Definition 5.2, we know that in the
interaction when $\pi$ is given history $\overline{B}$ and $\pi_{\sigma}$ will
be given history $\overline{B^{\prime}}$, obtained from $\overline{B}$ by
replacing each element $b$ by $\sigma(b)$. Thus, by Definition 5.2 it follows
that $\pi_{\sigma}$ will select element $\sigma(a)$ if and only if $\pi$
selects element $a$. This finishes the proof.

We are now ready to show if $\pi$ is $c$-selectable against adversaries in
$\mathscr{H}$, then $\pi_{\sigma}$ is also $c$-selectable against adversaries
in $\mathscr{H}$.

###### Lemma 5.7

If $\pi$ is $c$-selectable against adversaries in $\mathscr{H}$, then
$\pi_{\sigma}$ is also $c$-selectable against adversaries in $\mathscr{H}$.

Proof. Let $\mathscr{A}\in\mathscr{H}$ be an adversary and $a\in N$ an
arbitrary element. We have that

$\displaystyle\Pr(\pi_{\sigma}\text{ selects $a$ against $\mathscr{A}$})=$
$\displaystyle=\sum_{A\subseteq N}\Pr(\pi_{\sigma}\text{ selects $a$ against
$\mathscr{A}$}|\text{$A$ are active})\Pr(\text{$A$ are active})$
$\displaystyle=\sum_{A\subseteq N}\Pr(\pi_{\sigma}\text{ selects $a$ against
$\mathscr{A}$}|\text{$A$ are active})\frac{1}{2^{2k}}$
$\displaystyle=\sum_{A\subseteq N}\Pr(\pi\text{ selects $\sigma^{-1}(a)$
against $\mathscr{A}_{\sigma^{-1}}$}|\text{$\sigma^{-1}(A)$ are
active})\frac{1}{2^{2k}}\text{ (Lemma \ref{parallel_permutation} and Prop.
\ref{prop_bijection})}$ $\displaystyle=\sum_{A\subseteq N}\Pr(\pi\text{
selects $\sigma^{-1}(a)$ against
$\mathscr{A}_{\sigma^{-1}}$}|\text{$\sigma^{-1}(A)$ are
active})\Pr(\text{$\sigma^{-1}(A)$ are active})\text{
($x_{i}=\frac{1}{2},\forall i$)}$ $\displaystyle=\Pr(\pi\text{ selects
$\sigma^{-1}(a)$ against $\mathscr{A}_{\sigma^{-1}}$})\geq\frac{c}{2}\text{
(by $c$-selectability of $\pi$})$

Thus,

$\Pr(\pi_{\sigma}\text{ selects $a$ against $\mathscr{A}$}|\text{ $a$ is
active})=\frac{\Pr(\pi_{\sigma}\text{ selects $a$ against
$\mathscr{A}$})}{\Pr(\text{$a$ is active})}\geq c$

since $\Pr(\text{$a$ is active})=\frac{1}{2}$.

###### Remark 5.8

Notice that in the proof of Lemma 5.7 it was crucial that $x_{i}=\frac{1}{2}$
for all $i$, which we used to claim $\Pr(\text{$A$ are
active})=\Pr(\text{$\sigma^{-1}(A)$ are active})=\frac{1}{2^{2k}}$.

Suppose we have a $c$-selectable OCRS $\pi$ against adversaries in
$\mathscr{H}$. We define the “symmetric” OCRS $\pi^{s}$ in the following way:
1. Sample a uniformly random permutation $\sigma$ of the ground set $N$.
2. Operate like $\pi_{\sigma}$
We will next show that $\pi^{s}$ is $c$-selectable against adversaries in
$\mathscr{H}$ and that it does not differentiate between identities of
different elements.

###### Lemma 5.9

The OCRS $\pi^{s}$ is $c$-selectable against adversaries in $\mathscr{H}$.

Proof. Let $\mathscr{A}\in\mathscr{H}$ be an adversary. Since $\mathscr{A}$
needs to decide on the order in which to reveal the elements before seeing
what permutation $\sigma$ is drawn in step 1., we know that the order of
elements revealed does not depend on $\sigma$. Thus, for an arbitrary element
$a$ we have that

$\displaystyle\Pr(\pi^{s}\text{ selects $a$ against $\mathscr{A}$})$
$\displaystyle=\sum_{\sigma}\Pr(\pi_{\sigma}\text{ selects $a$ against
$\mathscr{A}$})\frac{1}{n!}\geq\text{(by Lemma
\ref{permutation_ocrs_cselectable})}$
$\displaystyle\geq\sum_{\sigma}\frac{c}{2}\frac{1}{n!}=\frac{c}{2}$

as desired.

We will now state the key lemma for this Section. Namely, that $\pi^{s}$
selects the $i$-th revealed active element with probability independent of the
identities of the first $i$ revealed elements.

###### Lemma 5.10

Against adversaries in $\mathscr{H}$, the probability that $\pi^{s}$ selects
the $i$-th revealed element, conditioned on it being active, is given by a
function $g(i)$ that is independent of the identities of the first $i$
revealed elements and their order.

Proof. Consider any adversary $\mathscr{A}\in\mathscr{H}$. By definition
$\mathscr{A}$ decides on the order in which to reveals the elements apriori,
and reveals all active elements before all inactive ones. Suppose that the
first $i$ elements that $\mathscr{A}$ reveals are $a_{1},\ldots,a_{i}$ in that
order. To prove the lemma it is enough to show that

$\Pr(\pi^{s}\text{ selects $a_{i}$}|a_{1},\ldots,a_{i}\text{ are
revealed})=g(i)$

where $g$ is allowed to depend only on $\pi$. Note that the permutation
$\sigma$ drawn is independent of the order of the elements
$a_{1},\ldots,a_{i}$ by definition of $\mathscr{H}$. Thus, we have

$\displaystyle\Pr(\pi^{s}\text{ selects $a_{i}$}|a_{1},\ldots,a_{i}\text{ are
revealed})=$ $\displaystyle=\sum_{\sigma}\Pr(\pi_{\sigma}\text{ selects
$a_{i}$}|a_{1},\ldots,a_{i}\text{ are revealed})\Pr(\sigma\text{ is
drawn}|a_{1},\ldots,a_{i}\text{ are revealed})$
$\displaystyle=\sum_{\sigma}\Pr(\pi_{\sigma}\text{ selects
$a_{i}$}|a_{1},\ldots,a_{i}\text{ are revealed})\frac{1}{n!}$
$\displaystyle=\frac{1}{n!}\sum_{\sigma}\Pr(\pi_{\sigma}\text{ selects
$a_{i}$}|a_{1},\ldots,a_{i}\text{ are revealed})$
$\displaystyle=\frac{1}{n!}\sum_{\sigma}\sum_{B\subseteq\\{a_{1},\ldots,a_{i-1}\\}}\Pr(\pi_{\sigma}\text{
selects $a_{i}$}\text{ and }\pi_{\sigma}\text{ selected
$B$}|a_{1},\ldots,a_{i}\text{ are revealed})\text{ (Definition
\ref{permutation_ocrs_def})}$
$\displaystyle=\frac{1}{n!}\sum_{\sigma}\sum_{B\subseteq\\{a_{1},\ldots,a_{i-1}\\}}\Pr(\pi\text{
selects $\sigma^{-1}(a_{i})$}\text{ and }\pi\text{ selected
$\sigma^{-1}(B)$}|\sigma^{-1}(\\{a_{1},\ldots,a_{i}\\})\text{ revealed})\text{
($\Delta$)}$

In the second inequality we used the fact that the event that $\sigma$ is
drawn is independent of the decision of the adversary for which
$a_{1},\ldots,a_{i}$ to reveal. The key observation is that expression
$(\Delta)$ does not depend on the elements $a_{1},\ldots,a_{i}$ but only on
$i$. Notice that for fixed $A^{\prime},B^{\prime},a^{\prime}$, such that
$|A^{\prime}|=i$, $B^{\prime}\subset A^{\prime}$ and $a^{\prime}\in
A^{\prime}\setminus B^{\prime}$, there are exactly

$\binom{i-1}{|B^{\prime}|}(|B^{\prime}|)!(i-1-|B^{\prime}|)!(n-i)!$

terms in the sum ($\Delta$) of the form

$\Pr(\pi\text{ selects $a^{\prime}$}\text{ and }\pi\text{ selected
$B^{\prime}$}|A^{\prime}\text{ revealed})$

To see this consider the number of $(\sigma,B)$ which are solutions to

$\sigma^{-1}(a_{i})=a^{\prime},\sigma^{-1}(B)=B^{\prime},\sigma^{-1}(A)=A^{\prime}$

where $A=\\{a_{1},\ldots,a_{i}\\}$. There are $\binom{i-1}{|B^{\prime}|}$ ways
to choose $B$. Given $B$ there are $(|B^{\prime}|)!(i-1-|B^{\prime}|)!(n-i)!$
ways to choose $\sigma$ in order to send $a^{\prime}$ to $a_{i}$, $B^{\prime}$
to $B$, and $A^{\prime}$ to $A$. Therefore, $\Delta$ is equal to

$\sum_{|A^{\prime}|=i,B^{\prime}\subset A^{\prime},a^{\prime}\in
A^{\prime}\setminus B^{\prime}}\Pr(\pi\text{ selects $a^{\prime}$}\text{ and
}\pi\text{ selected $B^{\prime}$}|A^{\prime}\text{
revealed})\binom{i-1}{|B^{\prime}|}(|B^{\prime}|)!(i-1-|B^{\prime}|)!(n-i)!$

which only depends on $i$. Therefore, the probability that $\pi^{s}$ selects
the $i$-th revealed element given that it is active only depends on $i$ we
will denote it by $g(i)$.

###  5.2 Upper bound on the probability of selection

In this section we will present an adversary in the class $\mathscr{H}$ and
show how this adversary implies the upper bound of
$1-\Omega(\sqrt{\frac{\log(k)}{k}})$ on $c$. By Lemma 5.10 it follows that,
against adversaries in $\mathscr{H}$, the probability that $\pi^{s}$ selects
the $i$-th revealed active element is given by a function $g(i)$.
We now describe the adversary. We will only specify what the adversary does
when $e_{1}$ is active.

Adversary $\mathscr{A}^{*}$:
1\.  If there are $m$ active elements except for $e_{1}$, the adversary
computes $g(1),\ldots,g(m+1)$.
2\.  Before the process starts, the adversary finds
$j=\operatorname*{arg\,min}_{i\in[1,m+1]}g(i)$ and reveals element $e_{1}$ at
position $j$ and all other $m$ active elements on positions
$j^{\prime}\in[1,j-1]\cup[j+1,m+1]$ in arbitrary order.

It is not hard to see that the adversary $\mathscr{A}^{*}$ is in the class
$\mathscr{H}$ because it commits to the order apriori and reveals all active
elements before all inactive. We will next show the following lemma for the
probability that $\pi^{s}$ selects $e_{1}$ against the above adversary.

###### Lemma 5.11

Let $h(m+1)=\min_{i\in[1,m+1]}g(i)$ for $m\in[0,2k-1]$. Then

$\Pr(\pi^{s}\text{ selects $e_{1}$ against $\mathscr{A}^{*}$}|e_{1}\text{ is
active})=\sum_{i=1}^{2k}h(i)\frac{\binom{2k-1}{i-1}}{2^{2k-1}}$

Proof. Suppose $e_{1}$ is active. Notice that the number of active elements is
equal to $N+1$, where $N\sim Bin(2k-1,\frac{1}{2})$. By definition of
$\mathscr{A}^{*}$, when there are $m$ active elements (except for $e_{1}$),
the probability that $\pi^{s}$ selects $e_{1}$ is equal to $h(m+1)$.
Therefore, by the law of total probability, $\pi^{s}$ selects $e_{1}$ with
probability

$\displaystyle\Pr(\pi^{s}\text{ selects $e_{1}$ against
$\mathscr{A}^{*}$}|e_{1}\text{ is active})$
$\displaystyle=\sum_{i=1}^{2k}h(i)\Pr[N+1=i]$
$\displaystyle=\sum_{i=1}^{2k}h(i)\Pr[Bin(2k-1,\frac{1}{2})=i-1]$
$\displaystyle=\sum_{i=1}^{2k}h(i)\frac{\binom{2k-1}{i-1}}{2^{2k-1}}$

as desired.

We will next show a property on the values $\\{g(i)\\}_{i=1}^{2k}$ that will
be useful later.

###### Lemma 5.12

$\sum_{i=1}^{2k}g(i)\leq k$

Proof. Suppose that all $2k$ elements in $N$ are active. We know that any
adversary in $\mathscr{H}$ will choose an order for the elements to be
revealed before $\pi^{s}$ draws $\sigma$. In that case we know by Lemma 5.10
that $\pi^{s}$ will select the $i$-th revealed element with probability
$g(i)$. Let $I_{i}$ be the indicator random variable that $\pi^{s}$ selects
that $i$-th revealed element. Note that $E[I_{i}]=g(i)$. Since $\pi^{s}$ never
selects more than $k$ elements (Definition 2.1) we have that

$k\geq\mathbb{E}[\sum_{i=1}^{2k}I_{i}]=\sum_{i=1}^{2k}\mathbb{E}[I_{i}]=\sum_{i=1}^{2k}g(i)$

as desired.

As a last step towards Theorem 5.1, we consider a linear program relaxation
whose optimal objective upper bounds the probability of selection $c$ (Lemma
5.13), and characterize an optimal solution to the program (Lemma 5.14).
Finally, we show that the optimal objective of the linear program is at most
$1-\Omega(\sqrt{\frac{\log(k)}{k}})$ (Lemma 5.15).

###### Lemma 5.13

Let $c^{*}$ denote the optimal value of the following linear program

$\begin{array}[]{ll@{}ll}\text{maximize}&\displaystyle\sum\limits_{i=1}^{2k}f(i)\frac{\binom{2k-1}{i-1}}{2^{2k-1}}&\\\
\text{subject to}&\displaystyle\sum_{i=1}^{2k}f(i)\leq k\\\ &f(i)\geq
f(i+1)\text{ for }&i=1,\dots,2k-1\\\ &f(2k)\geq 0\\\ \end{array}$ (1)

Then if $\pi^{s}$ is $c$-selectable it holds that

$c\leq c^{*}$

Proof. We first claim that $\\{h(i)\\}_{i=1}^{2k}$ is a feasible assignment to
(1). Notice that by definition we have that $h(i)\leq g(i)$ for $i\in[1,2k]$.
Using this combined with Lemma 5.12 we obtain

$\sum_{i=1}^{2k}h(i)\leq\sum_{i=1}^{2k}g(i)\leq k$

Further, note that by definition we have that $h(i)\geq h(i+1)$ for
$i\in[1,2k-1]$ and clearly $h(2k)\geq 0$. Combining the aforementioned
observations we get that the vector $\\{h(i)\\}_{i=1}^{2k}$ is a feasible
assignment of (1). Therefore, by Lemma 5.11 we obtain that

$c^{*}\geq\sum_{i=1}^{2k}h(i)\frac{\binom{2k-1}{i-1}}{2^{2k-1}}=\Pr(\pi^{s}\text{
selects $e_{1}$ against $\mathscr{A}^{*}$}|e_{1}\text{ is active})$

By Lemma 5.9 we know that $\pi^{s}$ is $c$-selectable i.e.

$\Pr(\pi^{s}\text{ selects $e_{1}$ against $\mathscr{A}^{*}$}|e_{1}\text{ is
active})\geq c$

By combining the above two inequalities we obtain that

$c^{*}\geq c$

which finishes the proof.
We will next prove a claim for the optimal solution of the linear program (1).

###### Lemma 5.14

The optimal solution of (1) has the form $f(i)=x$ for $i=1\ldots,k+a$,
$f(k+a+1)=y$, and $f(i)=0$ for $i>k+a+1$ for some $x\geq y\geq 0$ and
$a\in[0,k]$.

Proof. First, note that the constraints of the linear program (1) define a
bounded convex polytope, so there exists a feasible assignment that achieves
the optimum of (1). Let $b_{i}=\frac{\binom{2k-1}{i-1}}{2^{2k-1}}$, we know
that $b_{i}<b_{i+1}$ for $i<k$, $b_{k}=b_{k+1}$, and $b_{i}>b_{i+1}$ for
$i>k$. Let $f^{*}$ be an optimal solution to (1). Suppose that
$f^{*}(i)>f^{*}(i+1)$ for some $i<k$. Then consider $f^{**}$ defined by
$f^{**}(j)=f^{*}(j)$ for $j\not\in\\{i,i+1\\}$, and
$f^{**}(i)=f^{**}(i+1)=\frac{f^{*}(i)+f^{*}(i+1)}{2}$. Note that $f^{**}$
still has decreasing non-negative entries and the sum of its entries is equal
to that of $f^{*}$ i.e. it is feasible. The difference between the objective
values of $f^{**}$ and $f^{*}$ is equal to

$\frac{f^{*}(i)+f^{*}(i+1)}{2}(b_{i}+b_{i+1})-b_{i}f^{*}(i)-b_{i+1}f^{*}(i+1)=\frac{(f^{*}(i+1)-f^{*}(i))(b_{i}-b_{i+1})}{2}>0$

since $f^{*}(i+1)<f^{*}(i)$ and $b_{i}<b_{i+1}$. Thus, a contradiction with
the optimality of $f^{*}$. Therefore, $f^{*}(i)=f^{*}(1)$ for all $i\leq k$.
Let $f^{*}(i)=x$ for $i\leq k$. If $f^{*}(j)\in\\{x,0\\}$ for $j>k$ we are
done. Otherwise let $j>k$ be the smallest index such that $x>f^{*}(j)>0$, and
let $f^{*}(j)=y$. This means $f^{*}(i)=x$ for $i<j$. Assume that
$f^{*}(j+1)>0$. Then, let $l>j$ be the largest index such that $f^{*}(l)>0$,
and let $f^{*}(l)=z$. Choose $\epsilon<\min(x-y,z)$ and consider $f^{**}$
defined by $f^{**}(j)=f^{*}(j)+\epsilon$, $f^{**}(l)=f^{*}(l)-\epsilon$, and
$f^{**}(i)=f^{*}(i)$ for $i\not\in\\{j,l\\}$. Note that $f^{**}$ is feasible
by the choice of $\epsilon$ since its entries are still decreasing and have
the same sum as those of $f$. The difference between the objective of $f^{**}$
and $f^{*}$ equals to

$(f^{*}(j)+\epsilon)b_{j}+(f^{*}(l)-\epsilon)b_{l}-f^{*}(j)b_{j}-f^{*}(l)b_{l}=\epsilon(b_{j}-b_{l})>0$

as $b_{j}>b_{l}$ because $l>j>k$, which contradicts the optimality of $f^{*}$.
Thus, we showed that $f^{*}(j+1)=0$, which finishes the proof of the Lemma.

Note that by Lemma 5.14 we know that the optimal value of (1) has the
following form

$c^{*}=x\Pr(Bin(2k-1,\frac{1}{2})\leq k+a-1)+y\Pr(Bin(2k-1,\frac{1}{2})=k+a)$
(2)

for some $x\geq y\geq 0$ satisfying $x(k+a)+y\leq k$, where $a\geq 0$. By
using these constraints we easily obtain that $y\leq x\leq\frac{k}{k+a}$. By
using this inequality in equation (2), we obtain that

$c^{*}\leq\frac{k}{k+a}\Pr(Bin(2k-1,\frac{1}{2})\leq k+a)$ (3)

We now show the final Lemma of this section, which provides an upper bound for
the RHS of (3).

###### Lemma 5.15

Let $a\in[0,k]$, then

$\frac{k}{k+a}\Pr(Bin(2k-1,\frac{1}{2})\leq k+a)\leq
1-\Omega(\sqrt{\frac{\log(k)}{k}})$

Proof. It is enough to show that

$\frac{k}{k+a}\Pr(Bin(2k-1,\frac{1}{2})\leq k+a)\leq
1-\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$ (4)

Let’s assume, for the sake of contradiction, that inequality (4) is not true.
By this assumption we have the following chain of inequalities

$\displaystyle 1-\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$
$\displaystyle<\frac{k}{k+a}\Pr(Bin(2k-1,\frac{1}{2})\leq k+a)$
$\displaystyle\leq\min\Bigg{(}\frac{k}{k+a},\Pr(Bin(2k-1,\frac{1}{2})\leq
k+a)\Bigg{)}$
$\displaystyle\leq\min\Bigg{(}\frac{k}{k+a},\Pr(Bin(2k-2,\frac{1}{2})\leq
k+a)\Bigg{)}$

where in the second line we used that each of the terms in the product is at
most 1 and in the third line that $Bin(2k-1,\frac{1}{2})$ stochastically
dominates $Bin(2k-2,\frac{1}{2})$. Thus,

$1-\frac{1}{100}\sqrt{\frac{\log(k)}{k}}<\min\Bigg{(}\frac{k}{k+a},\Pr(Bin(2k-2,\frac{1}{2})\leq
k+a)\Bigg{)}$ (5)

By (5), we get

$\displaystyle\frac{k}{k+a}$
$\displaystyle>1-\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$ $\displaystyle k$
$\displaystyle>k+a-\frac{k+a}{100}\sqrt{\frac{\log(k)}{k}}$ $\displaystyle a$
$\displaystyle<\frac{k+a}{100}\sqrt{\frac{\log(k)}{k}}\leq\frac{2k}{100}\sqrt{\frac{\log(k)}{k}}=\frac{1}{50}\sqrt{k\log(k)}\text{
(since $a\leq k$)}$

Combining the above inequality with (5) again we obtain

$\Pr(Bin(2k-2,\frac{1}{2})<k+\frac{1}{50}\sqrt{k\log(k)})\geq\Pr(Bin(2k-2,\frac{1}{2})\leq
k+a)>1-\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$

Subtracting one from both sides we get

$\Pr(Bin(2k-2,\frac{1}{2})\geq
k+\frac{1}{50}\sqrt{k\log(k)})<\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$ (6)

We will not use the following anti-concentration for binomial distribution
given in Proposition B.3. For $k^{\prime}\in[\frac{n}{2},\frac{5n}{8}]$ and
even $n$ we have

$\Pr(Bin(n,\frac{1}{2})\geq
k^{\prime})\geq\frac{1}{15}\exp\Big(-16n(\frac{1}{2}-\frac{k^{\prime}}{n})^{2}\Big{missing})$
(7)

Substituting $n=2k-2$ and $k^{\prime}=k+\frac{1}{50}\sqrt{k\log(k)}$ in (7) we
obtain

$\displaystyle\Pr(Bin(2k-2,\frac{1}{2})\geq k+\frac{1}{50}\sqrt{k\log(k)})$
$\displaystyle\geq\frac{1}{15}\exp\Big(-16(2k-2)\Big{(}\frac{1}{2}-\frac{k+\frac{1}{50}\sqrt{k\log(k)}}{2k-2}\Big{)}^{2}\Big{missing})$
$\displaystyle=\frac{1}{15}\exp\Big(-32(k-1)\Big{(}\frac{1+\frac{1}{50}\sqrt{k\log(k)}}{2k-2}\Big{)}^{2}\Big{missing})$
$\displaystyle=\frac{1}{15}\exp\Big(-8\frac{(1+\frac{1}{50}\sqrt{k\log(k)})^{2}}{k-1}\Big{missing})$
$\displaystyle\geq\frac{1}{15}\exp\Big(-8\frac{(\frac{2}{25}\sqrt{k\log(k)})^{2}}{k}\Big{missing})\text{
(for big enough $k$)}$
$\displaystyle=\frac{1}{15}\exp\Big(-\frac{32}{625}\log(k)\Big{missing})=\frac{1}{15}\frac{1}{k^{\frac{32}{625}}}$

Combining the last inequality with (6) we obtain

$\displaystyle\frac{1}{100}\sqrt{\frac{\log(k)}{k}}$
$\displaystyle>\frac{1}{15}\frac{1}{k^{\frac{32}{625}}}$
$\displaystyle\iff\frac{15}{100}\sqrt{\log(k)}$ $\displaystyle\geq
k^{\frac{1}{2}-\frac{32}{625}}=k^{\frac{561}{1250}}$

which fails to hold for large enough $k$. Thus, we obtain a contradiction.
Therefore, (4) is true, which proves the lemma.

###### Remark 5.16

The optimal solution to the LP in Lemma 5.13 turns out not have the same
values $f(i)$ as implied by the asymptotically optimal OCRS from [HKS07]
(Theorem 3.5). This is because the values implied by this OCRS would have an
asymptotically optimal performance as opposed to exactly instance optimal.

###  5.3 Proof of Theorem 5.1

By Lemma 5.13, we know that

$c\leq c^{*}$ (8)

Additionally,by combining (3) and Lemma 5.15 we know that

$c^{*}\leq 1-\Omega(\sqrt{\frac{\log(k)}{k}})$ (9)

Combining (8) and (9) we obtain

$c\leq 1-\Omega(\sqrt{\frac{\log(k)}{k}})$

finishing the proof of Theorem 5.1.

##  6 Conclusion

We provide a new, simple, and optimal OCRS for $k$-uniform matroids against a
fixed-order adversary. In particular, our algorithm has the advantage that it
is extremely simple to implement and it does not require solving a
mathematical program. Our analysis connects its performance to a random walk,
and follows by concluding properties of this random walk. We expect that the
tools we develop in analyzing our algorithm to be of independent interest and
to have a broader applicability within online stochastic optimization.

As our second main result, we show that no OCRS for $k$-uniform matroids can
be $(1-\Omega(\sqrt{\frac{\log k}{k}}))$-selectable against an almighty
adversary, establishing that the simple greedy OCRS implied by [HKS07] is
optimal.

## References

  * [AKW14] Pablo D Azar, Robert Kleinberg, and S Matthew Weinberg.  Prophet inequalities with limited information.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1358–1377. SIAM, 2014.
  * [Ala14] Saeed Alaei.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  SIAM Journal on Computing, 43(2):930–972, 2014.
  * [ANSS19] Nima Anari, Rad Niazadeh, Amin Saberi, and Ali Shameli.  Nearly optimal pricing algorithms for production constrained and laminar bayesian selection.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 91–92, 2019.
  * [AW18] Marek Adamczyk and Michal Wlodarczyk.  Random order contention resolution schemes.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 790–801, 2018.
  * [CCF+22] José R. Correa, Andrés Cristi, Andrés Fielbaum, Tristan Pollner, and S. Matthew Weinberg.  Optimal item pricing in online combinatorial auctions.  In Karen Aardal and Laura Sanità, editors, Integer Programming and Combinatorial Optimization - 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27-29, 2022, Proceedings, volume 13265 of Lecture Notes in Computer Science, pages 126–139. Springer, 2022.
  * [CDF+22] Constantine Caramanis, Paul Dütting, Matthew Faw, Federico Fusco, Philip Lazos, Stefano Leonardi, Orestis Papadigenopoulos, Emmanouil Pountourakis, and Rebecca Reiffenhäuser.  Single-sample prophet inequalities via greedy-ordered selection.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1298–1325, 2022.
  * [CDL20] Shuchi Chawla, Nikhil Devanur, and Thodoris Lykouris.  Static pricing for multi-unit prophet inequalities.  arXiv preprint arXiv:2007.07990, 2020.
  * [CHMS10] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan.  Multi-Parameter Mechanism Design and Sequential Posted Pricing.  In the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
  * [CVZ14] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing, 43(6):1831–1879, 2014.
  * [DFKL17] Paul Duetting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 540–551, 2017.  https://arxiv.org/pdf/1612.03161.pdf.
  * [DK15] Paul Dütting and Robert Kleinberg.  Polymatroid prophet inequalities.  In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 437–449. Springer, 2015.
  * [EFGT20] Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang.  Online stochastic max-weight matching: Prophet inequality for vertex and edge arrival models.  In Péter Biró, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia, editors, EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13-17, 2020, pages 769–787. ACM, 2020.
  * [FSZ16] Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1014–1033. SIAM, 2016.
  * [GHK+14] Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking.  Online independent set beyond the worst-case: Secretaries, prophets, and periods.  In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, pages 508–519, 2014.
  * [GW19] Nikolai Gravin and Hongao Wang.  Prophet inequality for bipartite matching: Merits of being simple and non adaptive.  In Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019., pages 93–109, 2019.
  * [HKS07] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm.  Automated online mechanism design and prophet inequalities.  In AAAI, volume 7, pages 58–65, 2007.
  * [JMZ22] Jiashuo Jiang, Will Ma, and Jiawei Zhang.  Tight guarantees for multi-unit prophet inequalities and online stochastic knapsack.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1221–1246. SIAM, 2022.
  * [JMZ23] 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, page 909, New York, NY, USA, 2023. Association for Computing Machinery.
  * [KS78] Ulrich Krengel and Louis Sucheston.  On semiamarts, amarts, and processes with finite value.  Advances in Probability and Related Topics, 4:197–266, 1978.
  * [KS23] Danish Kashaev and Richard Santiago.  A simple optimal contention resolution scheme for uniform matroids.  Theoretical Computer Science, 940:81–96, 2023.
  * [KW12] Robert Kleinberg and S. Matthew Weinberg.  Matroid prophet inequalities.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 123–136, 2012.
  * [LS18] Euiwoong Lee and Sahil Singla.  Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities.  In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57:1–57:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
  * [MMG23] Calum MacRury, Will Ma, and Nathaniel Grammel.  On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs.  In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1995–2014. SIAM, 2023.
  * [MV08] Jiri Matousek and Jan Vondrak.  Lecture notes on the probabilistic method, March 2008.
  * [RS17] Aviad Rubinstein and Sahil Singla.  Combinatorial prophet inequalities.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1671–1687, 2017.
  * [Rub16] Aviad Rubinstein.  Beyond matroids: secretary problem and prophet inequality with general constraints.  In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 324–332, 2016.
  * [Sam84] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  Annals of Probability, 12(4):1213–1216, 1984.
  * [SSZ23] Richard Santiago, Ivan Sergeev, and Rico Zenklusen.  Simple random order contention resolution for graphic matroids with almost no prior information.  In Symposium on Simplicity in Algorithms (SOSA), pages 84–95. SIAM, 2023.

##  Appendix A Omitted proofs

###  A.1 Omitted proofs from Section 3

#### Proof of Theorem 3.1

Assume the contrary, i.e. the naive greedy OCRS is $(b,c)$-selectable for some
$b,c$ satisfying $bc=1-O(\frac{1}{\sqrt{k}})$. Suppose $n=2k$ and
$x_{i}=\frac{b}{2}$ for all $i$. Suppose the offline adversary reveals the
elements in the order $e_{1},\ldots,e_{n}$. Then in order for $e_{n}$ to be
selected conditioned on it being active, it must be that the OCRS has selected
at most $k-1$ elements from $e_{1},\ldots,e_{n-1}$. By definition of the naive
greedy OCRS this implies there must be at most $k-1$ active elements from
$e_{1},\ldots,e_{n-1}$. The number of active elements amongst these is
distributed as $Bin(2k-1,\frac{b}{2})$. Thus, we have that

$\Pr(Bin(2k-1,\frac{b}{2})\leq k-1)\geq\Pr(\text{$e_{n}$ is
selected}|\text{$e_{n}$ is active})\geq c$

Thus by assumption,

$\min(b,\Pr(Bin(2k-1,\frac{b}{2})\leq k-1)\geq b\Pr(Bin(2k-1,\frac{b}{2})\leq
k-1)\geq bc\geq 1-\frac{C}{\sqrt{k}}$ (10)

So $b\geq 1-\frac{C}{\sqrt{k}}$. Using this we get

$\Pr(Bin(2k-1,\frac{1}{2}-\frac{C}{2\sqrt{k}})\geq
k)\leq\Pr(Bin(2k-1,\frac{b}{2})\geq k)$

because for $a\geq k$ the function
$\Pr(Bin(2k-1,x)=a)=\binom{2k-1}{a}x^{a}(1-x)^{2k-1-a}$ is increasing in
$x<\frac{1}{2}$. Therefore,

$\displaystyle\Pr(Bin(2k-1,\frac{1}{2}-\frac{C}{2\sqrt{k}})\geq k)$
$\displaystyle\leq\Pr(Bin(2k-1,\frac{b}{2})\geq k)$
$\displaystyle=1-\Pr(Bin(2k-1,\frac{b}{2})\leq k-1)\text{ (by
(\ref{min_ineq}))}$ $\displaystyle\leq
1-(1-\frac{C}{\sqrt{k}})=\frac{C}{\sqrt{k}}$

However, by Lemma A.1

$\lim_{k\to\infty}\Pr(Bin(2k-1,\frac{1}{2}-\frac{C}{2\sqrt{k}})\geq k)\geq
A(C)>0=\lim_{k\to\infty}\frac{C}{\sqrt{k}}$

which contradicts the above. $\square$

###### Lemma A.1

Let $Bin(n,p)$ denote the binomial distribution with $n$ trails and
probability of success $p$. Let $C>0$. There exists some $A(C)>0$ such that

$\lim_{k\to\infty}\Pr(Bin(2k-1,\frac{1}{2}-\frac{C}{2\sqrt{k}})\geq k)\geq
A(C)$

Proof. Let $a\in[0,\sqrt{k}]$ be an integer. We claim that

$\binom{2k-1}{k+a}(\frac{1}{2}-\frac{C}{2\sqrt{k}})^{k+a}(\frac{1}{2}+\frac{C}{2\sqrt{k}})^{k-a}\geq\frac{A(C)}{\sqrt{k}}$

for some constant $A(C)>0$ independent of $a$. Note that

$(\frac{1}{2}-\frac{C}{2\sqrt{k}})^{k+a}(\frac{1}{2}+\frac{C}{2\sqrt{k}})^{k-a}=(\frac{1}{4}-\frac{C^{2}}{4k})^{k}\frac{(1-\frac{C}{\sqrt{k}})^{a}}{(1+\frac{C}{\sqrt{k}})^{a}}\geq\frac{1}{4^{k}}(1-\frac{C^{2}}{k})^{k}\frac{(1-\frac{C}{\sqrt{k}})^{\sqrt{k}}}{(1+\frac{C}{\sqrt{k}})^{\sqrt{k}}}$

Note that $(1-\frac{C^{2}}{k})^{k}\to\frac{1}{e^{C^{2}}}$ so it is bounded by
a positive constant from below. Similarly
$\frac{(1-\frac{C}{\sqrt{k}})^{\sqrt{k}}}{(1+\frac{C}{\sqrt{k}})^{\sqrt{k}}}\to\frac{1}{e^{2C}}$
is bounded below by a positive constant (depending on $C$).
It remains to lower bound $\binom{2k-1}{k+a}\frac{1}{4^{k}}$. Define
$H(x)=x\log(\frac{1}{x})+(1-x)\log(\frac{1}{1-x})$. We will use the following
identity for binomial coefficients which holds for $m\in[1,\frac{n}{2}]$

$\binom{n}{m}=\sqrt{\frac{n}{2\pi
m(n-m)}}\exp(nH(\frac{m}{n}))(1+O(\frac{1}{n}+\frac{1}{m^{3}}+\frac{1}{(m-n)^{3}}))$
(11)

Substituting $n=2k-1$ and $m=k-1-a$ in (11) we get

$\binom{2k-1}{k+a}=\binom{2k-1}{k-a-1}=\sqrt{\frac{2k-1}{2\pi(k-a-1)(k+a)}}\exp(nH(\frac{1}{2}-\frac{a+\frac{1}{2}}{2k-1}))(1+O(\frac{1}{k}))$
(12)

Note that since $a\in[0,\sqrt{k}]$ we have
$\sqrt{\frac{2k-1}{2\pi(k-a-1)(k+a)}}\geq\frac{D}{\sqrt{k}}$ for some constant
$D>0$ and $1+O(\frac{1}{k})>\frac{1}{2}$. By Taylor’s expansion we have that

$H(x+\epsilon)=H(x)+\epsilon\log(\frac{1-x}{x})-\frac{\epsilon^{2}}{2x(1-x)}+O(\epsilon^{3})$
(13)

Substituting $x=\frac{1}{2}$ and $\epsilon=-\frac{a+\frac{1}{2}}{2k-1}$ in
(13) we get

$(2k-1)H(\frac{1}{2}-\frac{a+\frac{1}{2}}{2k-1})=(2k-1)H(\frac{1}{2})+\frac{2(a+\frac{1}{2})^{2}}{2k-1}+O(\frac{(a+\frac{1}{2})^{3}}{(2k-1)^{2}})$

Note that $H(\frac{1}{2})=log(2)$ and since $a\leq\sqrt{k}$ the lower order
terms are bounded from below by a (possibly negative) constant $F$. Thus,

$(2k-1)H(\frac{1}{2}-\frac{a+\frac{1}{2}}{2k-1})\geq(2k-1)log(2)+F$

for some constant $F$. Substituting the above inequalities in (12) we get

$\binom{2k-1}{k+a}\frac{1}{4^{k}}\geq\frac{D}{2\sqrt{k}}\exp((2k-1)log(2)+F)\frac{1}{4^{k}}=\frac{D^{\prime}}{\sqrt{k}}$

for some constant $D^{\prime}>0$. Combining this with the lower bounds in the
beginning we get that for all $a\in[0,\sqrt{k}]$ we have

$\binom{2k-1}{k+a}(\frac{1}{2}-\frac{C}{2\sqrt{k}})^{k+a}(\frac{1}{2}+\frac{C}{2\sqrt{k}})^{k-a}\geq\frac{A(C)}{\sqrt{k}}$
(14)

for some $A(C)>0$. Using this inequality we obtain

$\displaystyle\Pr(Bin(2k-1,\frac{1}{2}-\frac{C}{2\sqrt{k}})\geq k)$
$\displaystyle\geq\sum_{a\in[0,\sqrt{k}]}\binom{2k-1}{k+a}(\frac{1}{2}-\frac{C}{2\sqrt{k}})^{k+a}(\frac{1}{2}+\frac{C}{2\sqrt{k}})^{k-a}\text{
(by (\ref{ineq_tool}))}$ $\displaystyle\geq\sqrt{k}\frac{A(C)}{\sqrt{k}}=A(C)$

as desired. This finishes the proof of the lemma.

#### Proof of Theorem 3.2

Assume the contrary, i.e. there exists such an OCRS based on a partition
matroid that is $(b,c)$-selectable for some $b,c$ satisfying
$bc=1-O(\frac{1}{\sqrt{k}})$. Let the offline adversary commit the natural
order $e_{1},\ldots,e_{n}$. Suppose that $n=2k$ and consider the instance
$x_{i}=\frac{b}{2}$ for all $i$. Let the partition matroid for this $x$ be
given by $\\{(n_{i},k_{i},S_{i})\\}_{i=1}^{s}$. The OCRS greedily selects
active elements with only constraint that it selects at most $k_{i}$ elements
in $S_{i}$. Since $\sum_{i=1}^{s}k_{i}=k$ and $\sum_{i=1}n_{i}=2k$, there
exists some $i$ such that $n_{i}\geq 2k_{i}$. Let $e_{j}$ be the last element
in $S_{i}$ according to the order above (i.e. with largest index $j$). Then if
$e_{j}$ is selected, it must be the case that at most $k_{i}-1$ of the other
elements of $S_{i}$ have been selected. Since the OCRS is greedy there must be
at most $k_{i}-1$ active elements amongst them, because otherwise the OCRS
will select the first $k_{i}$ active elements in $S_{i}$ before $e_{j}$ is
revealed. The number of these active elements is distributed as
$Bin(n_{i}-1,\frac{b}{2})$. Thus, we have that

$\Pr(Bin(n_{i}-1,\frac{b}{2})\leq k_{i}-1)\geq\Pr(\text{$e_{j}$ is
selected}|\text{$e_{j}$ is active})\geq c$

By our assumption we have that

$b\Pr(Bin(n_{i}-1,\frac{b}{2})\leq k_{i}-1)\geq bc\geq 1-\frac{C}{\sqrt{k}}$

which implies that $b\geq 1-\frac{C}{\sqrt{k}}\geq 1-\frac{C}{\sqrt{k_{i}}}$
and

$\Pr(Bin(n_{i}-1,\frac{b}{2})\leq k_{i}-1)\geq 1-\frac{C}{\sqrt{k}}$

Subtracting one from both sides we obtain

$\Pr(Bin(n_{i}-1,\frac{b}{2})\geq k_{i})\leq\frac{C}{\sqrt{k}}$

Note that since $b\geq 1-\frac{C}{\sqrt{k_{i}}}$ and $n_{i}\geq 2k_{i}$ we get
the following chain of inequalities

$\displaystyle\Pr(Bin(2k_{i}-1,\frac{1}{2}-\frac{C}{2\sqrt{k_{i}}})\geq
k_{i})$ $\displaystyle\leq\Pr(Bin(2k_{i}-1,\frac{b}{2})\geq k_{i})$
$\displaystyle\leq\Pr(Bin(n_{i}-1,\frac{b}{2})\geq
k_{i})\leq\frac{C}{\sqrt{k}}$

Since $\frac{C}{\sqrt{k}}\leq\frac{C}{\sqrt{k_{i}}}$, if $k_{i}$ is
sufficiently large, the above inequality will stop being true due to Lemma
A.1. Thus, there exists some $M$ such that $k_{i}<M$. Then, we have that

$\frac{C}{\sqrt{k}}\geq\Pr(Bin(2k_{i}-1,\frac{b}{2})\geq
k_{i})\geq(\frac{b}{2})^{2k_{i}-1}\geq(\frac{b}{2})^{2M}\geq(\frac{1}{2}-\frac{C}{2\sqrt{k}})^{2M}$

which also fails for large $k$ because the LHS converges to $0$ while the RHS
stays bounded from below by $\frac{1}{4^{2M}}$. Thus we obtained a
contradiction. $\square$

#### Proof of Theorem 3.5

Consider the naive greedy OCRS, which greedily selects active elements until
it has selected $k$ elements, and suppose the adversary is almighty. Consider
$b,c$, which will be chosen later. Let $x\in b\cdot P_{k}$ be the input and
let’s suppose that $e_{i}\in N$ is active. Notice that if there are at most
$k-1$ active elements in $R(x)\setminus\\{e_{i}\\}$, then $e_{i}$ will
certainly be selected. Thus, we have that

$\Pr(e_{i}\text{ is selected}|e_{i}\text{ is
active})\geq\Pr(|R(x)\setminus\\{e_{i}\\}|\leq k-1)$

Note that

$\Pr(|R(x)\setminus\\{e_{i}\\}|\leq k-1)=1-\Pr(|R(x)\setminus\\{e_{i}\\}|\geq
k)$

Observe that $|R(x)\setminus\\{e_{i}\\}|$ is a sum of independent $\\{0,1\\}$
random variable corresponding to the indicators of whether each of $e_{j}\neq
e_{i}$ is active. Thus,

$\mu=\mathbb{E}[|R(x)\setminus\\{e_{i}\\}|]=\sum_{j\neq i}x_{j}\leq bk$

where the last inequality is because $x\in b\cdot P_{k}$. Thus, by the
multiplicative Chernoff bound (Theorem B.1),

$\Pr(|R(x)\setminus\\{e_{i}\\}|\geq
k)=\Pr(|R(x)\setminus\\{e_{i}\\}|\geq(1+\frac{k}{\mu}-1)\mu)\leq
e^{-\frac{(\frac{k}{\mu}-1)^{2}\mu}{2+\frac{k}{\mu}-1}}=e^{-\frac{(k-\mu)^{2}}{\mu+k}}$

Note that $\frac{(k-\mu)^{2}}{\mu+k}$ is decreasing for $\mu<k$, and since
$\mu<bk<k$ by above, we get

$\Pr(|R(x)\setminus\\{e_{i}\\}|\geq k)\leq e^{-\frac{(k-\mu)^{2}}{\mu+k}}\leq
e^{-\frac{(k-bk)^{2}}{bk+k}}=e^{-\frac{k(b-1)^{2}}{b+1}}\leq
e^{-\frac{k(b-1)^{2}}{2}}$

Thus combining the above inequalities we get

$\Pr(e_{i}\text{ is selected}|e_{i}\text{ is active})\geq
1-e^{-\frac{(b-1)^{2}k}{2}}=c$

and thus $bc=b(1-e^{-\frac{(b-1)^{2}k}{2}})$. Taking
$b=1-\sqrt{\frac{2\log(k)}{k}}$ we obtain

$bc=(1-\sqrt{\frac{2\log(k)}{k}})(1-\frac{1}{k})=1-O(\sqrt{\frac{\log(k)}{k}})$

as desired.

$\square$

###  A.2 Lemma about martingales from Section 4

###### Lemma A.2

Let $\\{Q_{i}\\}_{i\in\mathbb{N}_{0}}$ be discrete martingale with $Q_{0}=0$
and such that there exists $K>0$ such that $|Q_{i+1}-Q_{i}|\leq K$ a.s. for
all $i\geq 0$. Let $n\in\mathbb{N}$, $a>0$, and $b<0$. Also let
$M_{n}=\max_{1\leq i\leq n}Q_{i}$. Then,

$\Pr(M_{n}<a,Q_{n}\leq b)\leq\frac{a+K}{-b}$

Proof. Define the stopping time

$T=\inf\\{i\geq 0:Q_{i}\geq a\text{ or }Q_{i}\leq b\\}$

Notice that $T$ is a stopping time adapted to the filtration of the martingale
$Q$. Also note that since the martingale increments are bounded by $K$, we
have $|Q_{\min(i,T)}|\leq\max(a+K,|b|+K)<\infty$. Therefore, by the Optional
Stopping Theorem (Theorem B.2), $Q_{T}$ is an almost surely well-defined
random variable and

$\mathbb{E}[Q_{T}]=\mathbb{E}[Q_{0}]=0$

Therefore, we have that

$\displaystyle 0=\mathbb{E}[Q_{T}]$
$\displaystyle=\mathbb{E}[Q_{T}\mathbbm{1}\\{Q_{T}\geq
a\\}+Q_{T}\mathbbm{1}\\{Q_{T}\leq b\\}]$
$\displaystyle\implies\mathbb{E}[Q_{T}\mathbbm{1}\\{Q_{T}\geq a\\}]$
$\displaystyle=\mathbb{E}[-Q_{T}\mathbbm{1}\\{Q_{T}\leq b\\}]$

Notice that since the martingale has bounded increments by $K$, we have

$Q_{T}\mathbbm{1}\\{Q_{T}\geq a\\}\leq(a+K)\mathbbm{1}\\{Q_{T}\geq a\\}$ (15)

and

$-Q_{T}\mathbbm{1}\\{Q_{T}\leq b\\}\geq-b\mathbbm{1}\\{Q_{T}\leq b\\}$ (16)

By (15) and (16), we get

$(a+K)\Pr(Q_{T}\geq a)\geq E[Q_{T}\mathbbm{1}\\{Q_{T}\geq
a\\}]=E[-Q_{T}\mathbbm{1}\\{Q_{T}\leq b\\}]\geq-b\Pr(Q_{T}\leq b)$

Therefore, since $-b>0$ and $\Pr(Q_{T}\geq a)\leq 1$, we get

$\Pr(Q_{T}\leq b)\leq\frac{a+K}{-b}\Pr(Q_{T}\geq a)\leq\frac{a+K}{-b}$

Now, notice that if the event $\\{M_{n}<a,Q_{n}\leq b\\}$ holds then it must
the case that $Q$ has reached $b$ before $a$ and this has happened at most at
step $n$ i.e. $S_{T}\leq b$ and $T\leq n$. In particular, this implies that
$S_{T}\leq b$. Therefore,

$P(M_{n}<a,Q_{n}\leq b)\leq\Pr(Q_{T}\leq b)\leq\frac{a+K}{-b}$

as desired.

###  A.3 Omitted proofs from Section 5

#### Proof of Proposition 5.5

For the first statement, it is enough to show that
$(\pi_{\sigma})_{\sigma^{-1}}=\pi$ for all $\pi,\sigma$. By Definition 5.2,
when $(\pi_{\sigma})_{\sigma^{-1}}$ needs to take an action based on a
particular history $\overline{B}$, it takes the action $\pi_{\sigma}$ would
take on the history $\overline{B^{\prime}}$ obtained from $\overline{B}$ after
replacing every element in $a$ by $\sigma(a)$ (this history could also contain
the current revealed element which the OCRS hasn’t selected / discarded yet).
Further, the action $\pi_{\sigma}$ takes on history $\overline{B^{\prime}}$ is
obtained by the action $\pi$ would take on history
$\overline{B^{\prime\prime}}$ obtained from $\overline{B^{\prime}}$ by
replacing every element $a^{\prime}$ by $\sigma^{-1}(a^{\prime})$. Since
$\sigma^{-1}(\sigma(a))=a$, we know that $\overline{B^{\prime\prime}}$ is the
same history as $\overline{B}$. Thus, $(\pi_{\sigma})_{\sigma^{-1}}$ will take
the same action as $\pi$ when using the same history. This implies the first
statement.
For the second statement, it is enough to show that
$(\mathscr{A}_{\sigma})_{\sigma^{-1}}=\mathscr{A}$. By Definition 5.3, on
active elements $A$ and against OCRS $\pi$,
$(\mathscr{A}_{\sigma})_{\sigma^{-1}}$ queries $\mathscr{A}_{\sigma}$ on
active elements $\sigma(A)$ and OCRS $\pi_{\sigma}$. Upon this
$\mathscr{A}_{\sigma}$ queries $\mathscr{A}$ on active elements
$\sigma^{-1}(\sigma(A))=A$ against $(\pi_{\sigma})_{\sigma^{-1}}=\pi$ (by
earlier). If $a$ is the $i$-th element of the order $\mathscr{A}$ reveals
against $\pi$, by above $\sigma^{-1}(\sigma(a))=a$ is the $i$-th element
$(\mathscr{A}_{\sigma})_{\sigma^{-1}}$ reveals against $\pi$. This finishes
the proof. $\square$

##  Appendix B Tools from probability theory

###### Theorem B.1

(Multiplicative Chernoff bound) Suppose $X_{1},\ldots,X_{n}$ are independent
random variable taking values in $\\{0,1\\}$. Let $X$ denote their sum, and
let $\mu=E[X]$. Then for any $\delta>0$. We have

$P[X\geq(1+\delta)\mu]\leq e^{-\frac{\delta^{2}\mu}{2+\delta}}$

###### Theorem B.2

(Optional Stopping Theorem)
Let $Q=\\{Q_{i}\\}_{i\in\mathbb{N}_{0}}$ be a discrete martingale and $T$ a
stopping time. Assume that one of the following three conditions holds:
(i) $T$ is almost surely bounded i.e. $T\leq C$ for some constant $C$.
(ii) $\mathbb{E}[T]<\infty$ and there exists a constant $C$ such that
$\mathbb{E}[|Q_{i+1}-Q_{i}||\mathscr{F}_{i}]\leq C$ almost surely.
(iii) There exists a constant $C$ such that $|Q_{\min(i,T)}|\leq C$ for all
$i$.
Then $Q_{T}$ is an almost surely well defined random variable and
$\mathbb{E}[Q_{T}]=E[Q_{0}]$

###### Proposition B.3

(Anti-concentration for Binomial distribution, Prop 7.3.2, [MV08]) For
$\frac{n}{2}\leq k^{\prime}\leq\frac{5n}{8}$ and even $n$ we have

$\Pr(Bin(n,\frac{1}{2})\geq
k^{\prime})\geq\frac{1}{15}\exp\Big(-16n(\frac{1}{2}-\frac{k^{\prime}}{n})^{2}\Big{missing})$