# Non-Adaptive Matroid Prophet Inequalities

Kanstantsin Pashkovich  University of Waterloo
Department of Combinatorics & Optimization
200 University Avenue West
Waterloo, ON, Canada
N2L 3G1  Alice Sayutina  University of Waterloo
Department of Combinatorics & Optimization
200 University Avenue West
Waterloo, ON, Canada
N2L 3G1

###### Abstract

We consider the matroid prophet inequality problem. This problem has been
extensively studied in the case of adaptive mechanisms. In particular, there
is a tight $2$-competitive mechanism for all matroids [KW12].

However, it is not known what classes of matroids admit non-adaptive
mechanisms with constant guarantee. Recently, in [CGKM20] it was shown that
there are constant-competitive non-adaptive mechanisms for graphic matroids.
In this work, we show that various known classes of matroids admit constant-
competitive non-adaptive mechanisms.

##  1 Introduction

Let us consider the _classical prophet inequality problem_ [KS77]. A _gambler_
observes a sequence of non-negative independent random variables $X_{1}$,
$X_{2}$, …, $X_{n}$, which correspond to a sequence of values for $n$ _items_.
The gambler knows the distributions of $X_{1}$, $X_{2}$, …, $X_{n}$. The
gambler is allowed to accept at most one item; and the gambler is interested
in maximizing the value of the accepted item. However, the gambler cannot
simply select an item of the maximum value, because the values of the $n$
items are revealed to the gambler one by one; and each time a value of the
current item is revealed the gambler has to make an irrevocable choice whether
to accept the current item or not.

What stopping rule the gambler should use to maximize the expected value of
the item they accept? The gambler knows only the distributions of $X_{1}$,
$X_{2}$, …, $X_{n}$ while a _prophet_ knows the realization of $X_{1}$,
$X_{2}$, …, $X_{n}$. Thus, in contrast to the gambler the prophet can always
obtain the maximum item’s value. The seminal result of Krengel and Sucheston
[KS77] showed that the gambler can obtain at least a half of the expected
value obtained by the prophet.

The classical prophet inequality problem led to a series of works on different
variants of the problem. A natural variant of the problem is the
generalization of the problem where a gambler can buy more than one item, but
the set of bought items should satisfy a known feasibility constraint.
Formally, let us be given a collection $\mathcal{S}\subseteq 2^{[n]}$ of item
sets. Then both gambler and prophet can select any item set $S$ from
$\mathcal{S}$. So $\mathcal{S}$ defines a feasibility constraint for selecting
items. In most standard examples of feasibility constraints, $\mathcal{S}$ can
be defined as a collection of all item sets with cardinality at most $k$ for
some natural number $k$. More generally $\mathcal{S}$ can be defined as a
collection of all independent sets in some matroid, in this case we speak
about the  _matroid prophet inequality problem_.

The result in [SC84] showed that in the single-item setting a gambler can
obtain at least half of the prophet value by using the following threshold-
rule: determine a constant $T$ as a function of known distributions and accept
the first item exceeding $T$. This rule results in a $2$-competitive
mechanism, similar to the adaptive approach of [KS77]. Note, that this
approximation guarantee is known to be tight. There is also another method to
set a threshold presented in [KW12], which also results in a $2$-competitive
mechanism. This was extended by Chawla et al. in [CHMS10] and [CGKM20] to the
setting of several items.

The results presented in [KW12] further extend to the _matroid prophet
inequalities_ , where accepted items need to form an independent set in a
known matroid. It leads to a $2$-competitive mechanism for every matroid,
matching the single-item setting result. However, unlike the mechanism in the
single-item setting, the mechanism for matroids is adaptive: the thresholds
for items are computed based on the previously accepted items. By [KW12],
there also exists a constant-competitive adaptive mechanism for feasibility
constraints defined as an intersection of constant number of matroids. The
mechanism by Kleinberg and Weinberg was further extended to a $2$-competitive
mechanism for polymatroids by Dütting and Kleinberg in [DK15].

Gravin and Wang [GW19] studied the bipartite matching version of this problem:
in their version, the arriving items are the edges of the (known) bipartite
graph. Gravin and Wang obtained a $3$-competitive non-adaptive mechanism,
which assigns thresholds to each vertex in the graph and an edge is accepted
only if its weight is at least the sum of the thresholds associated with its
endpoints.

Feldman, Svensson and Zenklusen [FSZ16] studied online item selection
mechanisms called “online contention resolution schemes" (OCRS). They showed
that given special properties, OCRS translate directly into a constant-
competitive prophet inequality for the same problem against almighty
adversary, i.e. an adversary which knows in advance realizations of all the
items and the random bits generated by an algorithm. As a result, they develop
a constant-competitive mechanism for prophet inequalities of the intersection
of a constant number of matroids, knapsack and matching constraints. Those
mechanisms are “almost” non-adaptive in a sense that they fix thresholds for
all items, however their mechanisms also impose a subconstraint: an item
cannot be accepted if together with previously accepted items it forms one of
the fixed forbidden sets.

Finally, in a later version of their paper [FSZ21], they prove that pure non-
adaptive mechanisms cannot achieve a constant-competitive approximation even
against a “normal” adversary. They construct a family of gammoid matroids
showing a lower bound of $\Omega(\log n{/}\log\log n)$ for a guarantee of non-
adaptive mechanisms on gammoids with $n$ elements.

There have been works studying similar setups with other goals. Chawla et al.
[CHMS10] studied a Bayesian item selection process in a fixed item arrival
order or against an adversary in control of the order. They studied it from a
perspective of the revenue maximization for the auctioneer. The performance is
constant-competitive compared to the well-known Myerson mechanism [Mye81],
which achieves the largest possible expected revenue among truthful
mechanisms. The mechanism by Chawla et al. [CHMS10] has an advantage that it
determines static thresholds together with a subconstraint so that each agent
can be offered take-it-or-leave-it prices in an online fashion.

Recently, Chawla et al. [CGKM20] developed a $32$-competitive non-adaptive
mechanism for graphic matroids against adversary item ordering.

###  1.1 Our results

First, we list the known results for non-adaptive mechanism that were
mentioned in the previous section.

######  Theorem 1 (Uniform Rank $1$ Matroid [SC84]).

There exists a $2$-competitive non-adaptive mechanism for single-item setting.

######  Theorem 2 (Graphic Matroid [CGKM20]).

There exists a $32$-competitive non-adaptive mechanism for graphic matroids.

Now let us list our results. In case of a simple graph, i.e. a graph with no
parallel edges or loops, we can slightly improve the above theorem by
considering essentially the same mechanism as [CGKM20] but considering a
different scaling of a point from the matroid polytope. We provide this result
for the sake of completeness.

######  Theorem 3.

There exists a $16$-competitive non-adaptive mechanism for graphic matroids in
the case of simple graphs.

Furthermore, the mechanism [CGKM20] can be generalized to the setting of
$k$-column sparse matroids. This result we need later to obtain Theorem 8.

######  Theorem 4 ($k$-Column Sparse Matroids).

There exists a $(2^{k+2}k)$-competitive non-adaptive mechanism for $k$-column
sparse matroids.

Note, that Theorem 2 of [CGKM20] follows from Theorem 4, since a graphic
matroid is also a $2$-column sparse matroid over $\mathbb{F}_{2}$.

Using analogous approach to the one in [Sot13], we also develop a mechanism
for cographic matroids.

######  Theorem 5 (Cographic Matroids).

There exists a $6$-competitive non-adaptive mechanism for cographic matroids.

The approach in [Sot13] immediately leads to the following result for
$\gamma$-sparse matroids.

######  Theorem 6 ($\gamma$-Sparse Matroids).

There exists a $\gamma$-competitive non-adaptive mechanism for $\gamma$-sparse
matroids.

Combining the above results and using classic Seymour’s decomposition results
we obtain the following theorem.

######  Theorem 7 (Regular Matroids).

There exists a $256$-competitive non-adaptive mechanism for regular matroids.

Subject to the Structural Hypothesis 1 due to Geelen, Gerards and Whittle,
which is stated later, we can also derive the following result.

######  Theorem 8.

Subject to the Structural Hypothesis 1, for every prime number $p$ there
exists a constant-competitive mechanism for every proper minor-closed class of
matroids representable over $\mathbb{F}_{p}$.

We also would like to observe that some of the recent results on “single
sample prophet inequalities” (SSPI) lead to non-adaptive constant-competitive
mechanisms. For this, the single sample required by the gambler in SSPI can be
directly sampled by our gambler from the available distributions. In
particular, the results in [AKW19] and [CFPP21] on laminar matroids and
truncated partition matroids inspired by the mechanism in [MTW16] lead to non-
adaptive mechanisms for prophet inequalities. To obtain these results, it is
crucial that the mechanism in [MTW16] does not involve subconstraints, i.e.
each item is accepted as long as the item is not in the “observation phase”,
the item passes its threshold based only on the “observation phase” and the
item forms an independent set with previously accepted items. In comparison,
it is not clear how from the results on regular matroids in [AKW19] based on
the mechanism in [DK14] one can obtain non-adaptive mechanisms.

So the following results can be directly obtained from [AKW19] and [CFPP21],
respectively.

######  Theorem 9 (Laminar Matroid).

There exists a $9.6$-competitive non-adaptive mechanism for laminar matroids.

######  Theorem 10 (Truncated Partition Matroid).

There exists an $8$-competitive non-adaptive mechanism for truncated partition
matroids.

##  2 Comparison to known results

Our results for cographic matroids and $k$-column sparse matroids are obtained
through modifications of the arguments in [Sot13] and [CGKM20], respectively.
The results on regular matroids and minor-closed families of matroids follow
the approach outlined in [HN20] for the secretary problem. As necessary
building blocks we use our results for cographic and $2$-column sparse
matroids. Note that a biggest challenge for us is the compatibility of non-
adaptive thresholds with contractions. Indeed, standard tools for deriving
mechanisms for contraction minors need subconstraints, while subconstraints
are not permitted in non-adaptive mechanisms. To obtain our results, we
resolve this issue only in the context of matroids representable over finite
fields, see arguments in Lemma 8. It would be interesting to see whether
analogous results for contraction minors hold with no assumption about
representability over finite fields.

##  3 Preliminaries

In this paper, we consider the matroid prophet inequality problem, where items
arrive online in adversarial order. Here, the adversary knows the
distributions of all $X_{1}$, $X_{2}$, …, $X_{n}$ and knows the gambler’s
mechanism, but the realization of $X_{1}$, $X_{2}$, …, $X_{n}$ is not known to
the adversary. Based on the available information, the adversary can decide on
the order in which items and their values are observed by the gambler.

###  3.1 Prophet inequality

######  Definition 1.

Let $M$ be a matroid on the ground set $[n]:=\\{1,\ldots,n\\}$, where $[n]$
corresponds to $n$ items. Let $\vec{X}:=(X_{1},\ldots,X_{n})$ be non-negative
independent random variables representing the values of these $n$ items.

  * •

For every subset of items $S\subseteq[n]$ we define its weight as follows

$w(S):=\sum_{i\in S}X_{i}.$

  * •

Let $\textbf{PROPH}_{M}$ be the random variable corresponding to the value
obtained by the prophet

$\textbf{PROPH}_{M}:=\max_{S\in\mathcal{I}(M)}w(S)\,,$

where $\mathcal{I}(M)$ is a collection of independent sets for $M$.

  * •

Let $\textbf{EPROPH}_{M}$ be the expectation of the value obtained by prophet

$\textbf{EPROPH}_{M}:=E[\textbf{PROPH}_{M}]\,.$

######  Definition 2.

Let us be given a number $\alpha>0$.

  * •

We call a mechanism _$\alpha$ -competitive_ (alternatively, we say that the
mechanism _guarantees an $\alpha$-approximation_) on the matroid $M$ if the
expected value obtained by the gambler via this mechanism is at least
$\frac{1}{\alpha}\textbf{EPROPH}_{M}$.

  * •

We call a mechanism _$\alpha$ -competitive_ (alternatively, we say that the
mechanism _guarantees an $\alpha$-approximation_) on the matroid class
$\mathcal{M}$ if this mechanism is $\alpha$-competitive for every matroid
$M\in\mathcal{M}$.

###  3.2 Non-adaptive mechanism

We say that a mechanism is _non-adaptive_ if it has the following structure:

  * •

Given the distributions of $\vec{X}=(X_{1},\ldots,X_{n})$, the mechanism
determines the values of _thresholds_ $\vec{T}=(T_{1},\ldots,T_{n})$, where
each $T_{i}$, $i\in[n]$ is a real number or $+\infty$.

  * •

If the value of item $i\in[n]$ is observed, the gambler accepts the item $i$
if and only both conditions hold:

    1. 1.

the observed value of $X_{i}$ is at least $T_{i}$

    2. 2.

the item $i$ together with all previously selected items forms an independent
set with respect to the matroid $M$.

Note, that a non-adaptive mechanism does not change thresholds during its
course. So, none of the thresholds depends on the realization of
$\vec{X}=(X_{1},\ldots,X_{n})$.

Another crucial feature of a non-adaptive mechanism is that the mechanism
works only with the original matroid $M$. A non-adaptive mechanism does not
allow us to define a new matroid $M^{\prime}$, such that a set of items is
independent in $M^{\prime}$ only if it is independent in $M$, and modify the
condition (2) based on $M^{\prime}$.

In this work, we focus on non-adaptive mechanisms. From here and later we use
the term _mechanism_ to refer to non-adaptive mechanisms exclusively.

######  Remark 1.

In this work, non-adaptive mechanisms are allowed to make non-deterministic
decisions. Hence, we allow a non-adaptive mechanism to construct the
thresholds $\vec{T}=(T_{1},\ldots,T_{n})$ non-deterministically.

To measure the performance of such a mechanism we use the expected total
value, where the expectation is taken not only with respect to
$\vec{X}=(X_{1},\ldots,X_{n})$ but also with respect to
$\vec{T}=(T_{1},\ldots,T_{n})$.

###  3.3 Matroids

We provide a review of matroids here. Experienced readers should consider
skipping or skimming this section. For further results about matroids,
consider consulting [Oxl06].

A _matroid_ $M=(E,\mathcal{S})$ is a pair of a finite _ground set_ $E$ and a
collection $\mathcal{S}\subseteq 2^{E}$ of _independent_ sets. The collection
$\mathcal{S}\subseteq 2^{E}$ of subsets of $E$ satisfies the following
conditions:

  * (i)

Empty set is an independent set, so $\varnothing\in\mathcal{S}$.

  * (ii)

The collection $\mathcal{S}$ is closed with respect to taking subsets, so for
all $A\subseteq B\subseteq E$ if $B$ is in $\mathcal{S}$ then $A$ is in
$\mathcal{S}.$

  * (iii)

The collection $\mathcal{S}$ satisfies so called _augmenation property_. In
other words, for all $A,B\subseteq E$ such that $A,B\in\mathcal{S}$ and
$|A|>|B|$, there exists $c\in A\setminus B$ such that
$B\cup\\{c\\}\in\mathcal{S}$.

A subset of $E$ is called _dependent_ if it is not in $\mathcal{S}$. The
inclusion-maximal independent sets are called _bases_ and the inclusion-
minimal dependent sets are called _circuits_. For every two bases, their
cardinalities are equal: for every bases $A$ and $B$ of $M$ we have $|A|=|B|$.
A rank function for the matroid $M$ is a function $r_{M}:2^{E}\to\mathbb{N}$
such that for every $A\subseteq E$ the value $r_{M}(A)$ equals the cardinality
of an inclusion-maximal independent subset of $A$. In the cases when the
choice of the matroid is clear from the context, we write $r$ instead of
$r_{M}$.

Given a matroid $M$, we can define the _dual matroid_ $M^{*}$ over the same
ground set $E$. A set $A$ is independent for matroid $M^{*}$ if and only if
$E\setminus A$ contains a basis of $M$. An element $c\in E$ is called a _loop_
in $M$ if $r_{M}(c)=0$. An element $c\in E$ is called a _free element_ in $M$
if $r_{M^{*}}(c)=0$. To put it another way, an element $c$ is free, if and
only if for every set $A$, which is independent in $M$, $A\cup\\{c\\}$ is also
independent in $M$. We say that elements $c$ and $d\in E$ are _parallel_ in
matroid $M$, denoted by $c\parallel d$, if
$r_{M}(c)=r_{M}(d)=r_{M}(\\{c,d\\})=1$. One can show that “being parallel”
defines an equivalence relation on the non-loop elements of $M$. A matroid is
called _simple_ if it has no loops and no parallel edges.

Let $M=(E,\mathcal{S})$ be a matroid and $A\subseteq E$. The _contraction_ of
$M$ by $A$, denoted as $M/A$, is a matroid over ground set $E\setminus A$ with
the following independent sets

$\\{S\subseteq E\setminus A\,:\,S\cup A^{\prime}\in\mathcal{S}\\}\,,$

where $A^{\prime}$ is an inclusion-maximal independent subset of $A$.

The restriction of $M$ to $A$, denoted as $M\mid_{A}$ or
$M\setminus\overline{A}$, is a matroid over the ground set $A$ where a set
$S\subseteq A$ is independent in $M\mid_{A}$ if and only if it is independent
in $M$.

A matroid $M^{\prime}$ is called a _simple version_ of $M$ if $M^{\prime}$ is
obtained from $M$ by deleting all loops and contracting every parallel class
of elements into a single element.

For matroids $M$, $N$, we say that $N$ is a _minor_ of $M=(E,\mathcal{S})$ if
$N$ is isomorphic to $M{/}A{\setminus}B$ for some disjoint sets $A,B\subseteq
E$. A matroid class $\mathcal{M}$ is called _minor-closed_ if for any
$M\in\mathcal{M}$ every minor of $M$ is also in $\mathcal{M}$.

Let us now list some of the classical examples of matroids, which were
extensively studied in the context of various mathematical fields.

  * •

A _uniform_ matroid $M=(E,\mathcal{S})$ of rank $k$ is matroid where

$\mathcal{S}:=\\{A\subseteq E\,:\,|A|\leq k\\}\,.$

When $|E|=n$, we denote the uniform matroid of rank $k$ as $U_{k,n}$.

  * •

A _graphic_ matroid over graph $G=(V,E)$ is a matroid $M=(E,\mathcal{S})$,
where

$\mathcal{S}:=\\{A\subseteq E\,:\,A\text{ is acyclic}\\}\,.$

The graphic matroid over graph $G$ is denoted as $M(G)$.

  * •

A _cographic_ matroid over graph $G=(V,E)$ is a dual matroid
$M=(E,\mathcal{S})$ to the graphic matroid over the same graph $G$. In this
case we have

$\mathcal{S}:=\\{A\subseteq E\,:\,(V,E\setminus A)\text{ has the same number
of components as }(V,E)\\}\,.$

  * •

A _vector_ matroid $M=(E,\mathcal{S})$ is a matroid such that there is a
vector space $V$ and a map $\phi:E\rightarrow V$ satisfying

$\mathcal{S}:=\\{A\subseteq E\,:\,\text{multiset }\,\phi(A)\text{ is linearly
independent}\\}\,.$

Given a field $\mathbb{F}$, we say that $M$ is _representable_ over field
$\mathbb{F}$ if $M$ is isomorphic to the vector matroid where $V$ is a vector
space over field $\mathbb{F}$.

A matroid is called _regular_ if it is representable over every field. A
matroid is called _binary_ if it is representable over $\mathbb{F}_{2}$.

  * •

A _$k$ -column sparse_ matroid $M=(E,\mathcal{S})$ is a matroid such that
there is a field $\mathbb{F}$ and dimension $m$ and a map
$\phi:E\rightarrow\mathbb{F}^{m}$ such that

$\mathcal{S}:=\\{A\subseteq E\,:\,\text{multiset }\,\phi(A)\text{ is linearly
independent over }\mathbb{F}\\}\,;$

and moreover $\phi(c)\in\mathbb{F}^{m}$ has at most $k$ nonzero coordinates
for every $c\in E$.

  * •

A _$\gamma$ -sparse_ matroid $M=(E,\mathcal{S})$ is a matroid such that the
inequality $|S|\leqslant\gamma r_{M}(S)$ holds for every $S\subseteq E$.

  * •

A _laminar_ matroid $M=(E,\mathcal{S})$ is a matroid such that there exists a
laminar family $\mathcal{F}$ over the ground set $E$ and there are numbers
$c_{F}\in\mathbb{N}$, $F\in\mathcal{F}$ such that

$\mathcal{S}:=\\{A\subseteq E\,:\,|A\cap F|\leq c_{F}\text{ for every
}F\in\mathcal{F}\\}\,.$

Moreover, if $\mathcal{F}=\\{E,E_{1},\ldots,E_{k}\\}$, where $E_{1}$, …,
$E_{k}$ form a partition of the ground set $E$, then $M$ is called a
_truncated partition matroid_. Recall, that a family $\mathcal{F}$ is called
_laminar_ if for every $A$, $B\in\mathcal{F}$ we have $A\subseteq B$ or
$B\subseteq A$ or $A\cap B=\varnothing$.

Given a matroid $M=(E,\mathcal{S})$ we can define the corresponding polytope
$P_{M}\subseteq\mathbb{R}^{E}$ as the convex hull of points corresponding to
the characteristic vectors of independent sets. The polytope $P_{M}$ is known
to admit the following outer description [Sch03].

$\displaystyle P_{M}=\\{x\in\mathbb{R}^{E}\,:\,\,$ $\displaystyle x\geq
0\text{ and }$ $\displaystyle x(S)\leq r_{M}(S)\text{ for every }S\subseteq
E\\}\,,$

where $x(S)$ stands for $\sum_{c\in S}x_{c}$.

For a matroid $M=(E,\mathcal{S})$ and a set $A\subseteq E$ we can define the
_closure_ of $A$ as the following set

$\operatorname{cl}_{M}(A):=\\{c\in E\mid r_{M}(A\cup\\{c\\})=r_{M}(A)\\}\,.$

For a matroid $M=(E,\mathcal{S})$, we call the following function
$\sqcap_{M}\colon E\times E\to\mathbb{Z}$ a _local connectivity_ function

$\sqcap_{M}(X,Y)=r(X)+r(Y)-r(X\cup Y)\,.$

The following function $\lambda_{M}\colon E\to\mathbb{Z}_{\geqslant 0}$ is
called a _connectivity_ function

$\lambda_{M}(X):=\sqcap_{M}(X,E\setminus X)=r(X)+r(E\setminus X)-r(E)\,.$

Informally, connectivity functions measure dependence with respect to the
matroid between parts of the ground set. To illustrate it, let us consider the
connectivity function for vector matroids. Suppose $M=(E,\mathcal{S})$ is a
vector matroid defined by a vector space $V$ and a map $\phi:E\rightarrow V$.
Then we have

$\displaystyle\lambda_{M}(S)=$ $\displaystyle r(S)+r(E\setminus S)-r(E)=$
$\displaystyle\dim(\operatorname{span}\phi(S))+\dim(\operatorname{span}\phi(E\setminus
S))-\dim(\phi(E))=$
$\displaystyle\dim\left(\left(\operatorname{span}\phi(S)\right)\cap(\operatorname{span}\phi(E\setminus
S))\right)\,.$

###  3.4 Ex-ante relaxation to the matroid polytope

The goal of ex-ante relaxation [FSZ16] or [CGKM20] is to reduce the original
problem to the problem where item values are distributed as independent
Bernoulli random variables. Note, that both problems are using the same
matroid.

In the original problem item values $\vec{X}=(X_{1},\ldots,X_{n})$ are
independent random variables with known distributions. For $i\in[n]$ let
$F_{i}$ be the cumulative distribution function of $X_{i}$. The reduction of
the original problem to a new problem is done using a point $p$ in the matroid
polytope $P_{M}$. Let us first show that there is a point $p\in P_{M}$ with
properties that prove to be desirable later following the argumentation in
[CGKM20].

######  Lemma 1.

Given a matroid $M$ over the ground set $[n]$ and random variables
$\vec{X}=(X_{1},\ldots,X_{n})$, there exists $p\in P_{M}$ such that

$\textbf{EPROPH}_{M}\leqslant\sum_{i=1}^{n}p_{i}t_{i}\,,$

where $t_{i}:=E[X_{i}\mid X_{i}\geqslant F_{i}^{-1}(1-p_{i})]$ for every
$i\in[n]$111 Here, we assume that for every $i\in[n]$ the event
$X_{i}=F_{i}^{-1}(1-p_{i})$ happens with the zero probability, which is true
for all continuous distributions. In case of discrete distributions one needs
to introduce appropriate tie-breaking..

###### Proof.

Let $I_{opt}$ be a random variable indicating an optimal independent set in
$M$ with respect to $\vec{X}=(X_{1},\ldots,X_{n})$. In case when for some
realization of $\vec{X}=(X_{1},\ldots,X_{n})$ there are several optimal
independent sets, $I_{opt}$ can be selected as any of these sets. For
$i\in[n]$, let $p_{i}$ be the probability that element $i$ is in $I_{opt}$.
Note that $p=(p_{1},\ldots,p_{m})$ is a convex combination of independent sets
of $M$, and so lies in $P_{M}$.

Due to $\textbf{EPROPH}_{M}=E[\sum_{i\in I_{opt}}X_{i}]$, it remains to show
that

$E[\sum_{i\in I_{opt}}X_{i}]\leqslant\sum_{i=1}^{n}p_{i}t_{i}\,.$

We have

$E[\sum_{i\in I_{opt}}X_{i}]=\sum_{i=1}^{n}P[i\in I_{opt}]E[X_{i}\mid i\in
I_{opt}]=\sum_{i=1}^{n}p_{i}E[X_{i}\mid i\in I_{opt}]\,.$

For every $i\in[n]$ we have that $t_{i}$ and $E[X_{i}\mid i\in I_{opt}]$ are
expectations of the same random variable $X_{i}$ but conditioned on the event
$X_{i}\geqslant F_{i}^{-1}(1-p_{i})$ and on the event $i\in I_{opt}$,
respectively. Note, that the probability of both these events equals $p_{i}$.
However, the expectation of $X_{i}$ conditioned on $X_{i}\geqslant
F_{i}^{-1}(1-p_{i})$ is the “largest” conditional expectation of $X_{i}$ on an
event of probability $p_{i}$. Thus, we have $p_{i}E[X_{i}\mid i\in
I_{opt}]\leqslant p_{i}t_{i}$ for every $i\in[n]$ and so we get the desired
inequality

$\sum_{i=1}^{n}p_{i}E[X_{i}\mid i\in
I_{opt}]\leqslant\sum_{i=1}^{n}p_{i}t_{i}\,.$

∎

Let us show how one can use the point $p=(p_{1},\ldots,p_{n})$ guaranteed by
Lemma 1 to reduce the original problem. Let us define independent Bernoulli
random variables $\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$ as
follows, for each $i\in[n]$

$X^{\prime}_{i}=\begin{cases}t_{i}&\text{with probability~{}~{}}p_{i}\\\
0&\text{with probability~{}~{}}1-p_{i}\,,\end{cases}$

where $t_{i}:=E[X_{i}\mid X_{i}\geqslant F_{i}^{-1}(1-p_{i})]$.

Let us assume that we have a non-adaptive mechanism for the original matroid
$M$ and item values $\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$,
which sets nonnegative thresholds
$\vec{T}^{\prime}=(T^{\prime}_{1},\ldots,T^{\prime}_{n})$. By definition of
$\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$, for every $i\in[n]$
the exact value of $T^{\prime}_{i}$ is not relevant per se, but it is crucial
whether $t_{i}\geq T^{\prime}_{i}$ or $t_{i}<T^{\prime}_{i}$. If for some
$i\in[n]$ we have $T^{\prime}_{i}>t_{i}$ then this item $i$ is “inactive” and
so is never selected by the gambler working with $M$ and
$\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$.

The key is to construct a non-adaptive mechanism for the original matroid $M$
and item values $\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$ with
positive thresholds $\vec{T}^{\prime}=(T^{\prime}_{1},\ldots,T^{\prime}_{n})$
such that for each item $i\in[n]$ the probability that $i$ is selected by the
gambler is at least $\alpha p_{i}$. Now we can use such a non-adaptive
mechanism for the original matroid $M$ and item values
$\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$ to construct a non-
adaptive $\alpha$-competitive mechanism for the same matroid $M$ and random
variables $\vec{X}=(X_{1},\ldots,X_{n})$. Let us define the thresholds
$\vec{T}=(T_{1},\ldots,T_{n})$ as follows, for every $i\in[n]$

$T_{i}:=\begin{cases}+\infty&\text{if }t_{i}<T^{\prime}_{i}\\\
F_{i}^{-1}(1-p_{i})&\text{otherwise}\,.\end{cases}$

To see that the thresholds $\vec{T}=(T_{1},\ldots,T_{n})$ lead to an
$\alpha$-competitive mechanism for $M$ and $\vec{X}=(X_{1},\ldots,X_{n})$, let
us couple random variables $X^{\prime}_{i}$ with random variables $X_{i}$ as
follows

$X^{\prime}_{i}:=\begin{cases}t_{i}&\text{if }X_{i}\geq F_{i}^{-1}(1-p_{i})\\\
0&\text{otherwise}\,.\end{cases}$

Note that $\vec{X}^{\prime}=(X^{\prime}_{1},\ldots,X^{\prime}_{n})$ are
independent Bernoulli random variables, where for each $i\in[n]$ the variable
$X^{\prime}_{i}$ equals $t_{i}$ with probability $p_{i}$ and equals $0$ with
probability $1-p_{i}$. When $\vec{X}^{\prime}$ are coupled with $\vec{X}$ this
way, $X_{i}$ and $X^{\prime}_{i}$ have the same expected value when
conditioned on $X^{\prime}_{i}$ being $t_{i}$. The mechanism with thresholds
$\vec{T}$ selects an item $i\in[n]$ when run for $\vec{X}$ only if the
mechanism with thresholds $\vec{T}^{\prime}$ selects the item $i$ when run for
$\vec{X}^{\prime}$. Moreover, for both of these algorithms, conditionally on
the event that the item $i$ is selected the expected value of $i$ equals
$t_{i}$. Now, $\alpha$-competitiveness guarantee of the thresholds $\vec{T}$
for $M$ and $\vec{X}$ follows from Lemma 1.

##  4 Graphic and $k$-column sparse matroids

First, we construct a $16$-competitive non-adaptive mechanism for graphic
matroids without parallel edges. Our construction is done through the ex-ante
relaxation to the matroid polytope, following the works in [FSZ16] or
[CGKM20]. Later, we present a constant-competitive non-adaptive mechanism for
$k$-column sparse matroids whenever $k$ is constant.

###  4.1 Graphic matroids

Now we are ready to provide a $16$-competitive non-adaptive mechanism for
graphic matroid. The provided mechanism is essentially the one constructed in
[CGKM20] but with saving a factor of $2$ in the guarantee, which is achieved
by rescaling the point from the matroid polytope by $2$ and not by $4$.

Let us be given a simple graph $G=(V,E)$ and let us consider the corresponding
graphic matroid $M$ over the ground set $E$. Recall that a subset of $E$ is
independent with respect to $M$ if and only if it is acyclic in $G$. Let us
also assume that the graph $G$ has $n$ edges and so
$E=\\{e_{1},e_{2},\ldots,e_{n}\\}$.

######  Lemma 2.

Let $p=(p_{1},\ldots,p_{n})$ be a point in the polytope $P_{M}$. Thus we
assume that for every $i\in[n]$ the coordinate $p_{i}$ of $p$ corresponds to
the edge $e_{i}$. Then there exists an orientation of edges
$E=\\{e_{1},e_{2},\ldots,e_{n}\\}$ in the graph $G=(V,E)$ such that for every
vertex $v\in V$ we have $\sum_{i\in[n]:e_{i}\in\delta^{-}(v)}p_{i}\leq 2$.

###### Proof.

Observe that the average degree of a vertex in a forest on $|V|$ vertices is
at most $(2|V|-2)/|V|=2-1/|V|\leqslant 2$.

Let us use this fact to prove the desired statement by induction on the number
of vertices in the graph $G$.

If the graph $G$ has at most two vertices then the orientation is trivial.
Otherwise, since $p$ is a convex combination of points corresponding to
forests in $G$, we have that the average of the value
$\sum_{i\in[n]:e_{i}\in\delta(v)}p_{i}$ over all vertices $v\in V$ is at most
$2$. Thus there exists a vertex $v\in V$ such that we have
$\sum_{i\in[n]:e_{i}\in\delta(v)}p_{i}\leq 2$. We orient all edges incident to
$v$ as edges in $\delta^{-}(v)$, so these edges are incoming with respect to
$v$. Then we remove the vertex $v$ and all edges incident to it and orient the
remaining edges according to the orientation guaranteed by the inductive
hypothesis. ∎

Now we present an algorithm for graphic matroids of simple graphs.

1:Let $p$ be a point in the polytope $P_{M}$ so that the statement of Lemma 1
is satisfied.

2:Let the edges of the original graph $G=(V,E)$ be oriented so that the
statement of Lemma 2 is satisfied.

3:For every edge $e_{i}\in E$, $i\in[n]$, mark the edge $e_{i}$ as “discarded"
independently at random with probability $1/2$.

4:Select a cut $S\subseteq V$ uniformly at random, mark all edges not in
$[S;\overline{S}]$ as “discarded". Here, $[S;\overline{S}]$ stands for the set
of edges which are oriented such that their tail is in $S$ and their head is
in $\overline{S}$.

5:Set thresholds $\vec{T}=(T_{1},\ldots,T_{n})$ as follows, for each $i\in[n]$
$T_{i}:=\begin{cases}+\infty&\text{if }e_{i}\text{ is ``discarded''}\\\
F_{i}^{-1}(1-p_{i})&\text{otherwise}\,.\end{cases}$

Algorithm 1 A non-adaptive 16-competitive mechanisms for graphic matroids of a
simple graph

######  Lemma 3.

For every $i\in[n]$, we have

$P[e_{i}\text{ is selected}\mid X_{i}\geq T_{i}\text{ and }e_{i}\text{ is not
``discarded''}]\geq 1/2\,.$

###### Proof.

Let us assume that the vertex $v$ is the head of the oriented edge $e_{i}$.
Let us also assume that $e_{i}$ is not marked as “discarded” and $X_{i}\geq
T_{i}$.

Since the edge $e_{i}$ is not “discarded”, the edge $e_{i}$ is in the selected
set $[S;\overline{S}]$. Hence, every not “discarded” edge incident to $v$ has
the vertex $v$ as its head.

Thus, as long as no other edge with the head at the vertex $v$ is selected by
the gambler, the gambler has to select $e_{i}$. We claim, that with
probability at least $1/2$ no other edge with the head at $v$ was selected by
the gambler.

Let $I$ be the event indicating that "the gambler selected an edge $e_{j}$,
$j\neq i$ such that $v$ is the head of $e_{j}$", in other words “there is
$j\in[n]$, $j\neq i$ such that $v$ is the head of $e_{j}$ and $X_{j}\geq
T_{j}$ and $e_{j}$ is not “discarded”". Let $J$ indicate the event that
"$e_{i}$ is not marked as “discarded” after the selection of the cut", in
other words, "the head of $e_{i}$ is in $\overline{S}$ and the tail of $e_{i}$
is in $S$".

Let us show

$P[I\mid J]\leq 1/2\,.$

By the union bound, we have

$P[I\mid
J]\leqslant\sum_{j\in[n]\setminus\\{i\\}:e_{j}\in\delta^{-}(v)}P[X_{j}\geq
T_{j}\text{ and $e_{j}$ is not ``discarded''}\mid J]$

Note that for each edge $e_{j}\in\delta^{-}(v)$ we have $P[X_{j}\geq
T_{j}|J]=p_{j}$ and we also have $P[\text{$e_{j}$ is not
``discarded''}|J]=1/4$. Note that any edge is not “discarded” in Step 3 of
Algorithm 1 with probability $1/2$, and not “discarded” in Step 4 of Algorithm
1 with probability $1/4$. However, since the probabilities are with respect to
the edge $e_{j}\in\delta^{-}(v)$ and are counted conditioned on the event $J$,
the conditioned probability of not being “discarded” in Step 4 of Algorithm 1
is $1/2$. Moreover, even conditioned on $J$ the events "$X_{j}\geq T_{j}$" and
"$e_{j}$ is not “discarded”" are independent events. Thus we have

$\displaystyle\sum_{j\in[n]\setminus\\{i\\}:e_{j}\in\delta^{-}(v)}P[X_{j}\geq
T_{j}\text{ and $e_{j}$ is not ``discarded''}\mid J]\leq$
$\displaystyle\sum_{j\in[n]\setminus\\{i\\}:e_{j}\in\delta^{-}(v)}p_{j}/4\leqslant
1/2\,,$

where the last inequality follows from the orientation. ∎

We are ready to prove Theorem 3 by showing that Algorithm 1 is a
$16$-competitive for graphic matroids without parallel edges.

###### Proof of Theorem 3.

By Lemma 3 for every $i\in[n]$ the probability of edge $e_{i}$ being accepted
conditional on $X_{i}\geq T_{i}$ and being not “discarded” is at least $1/2$.

Overall, the probability of edge $e_{i}$ being accepted is at least
$\frac{1}{16}p_{i}$. Thus mechanism guarantees at least
$\sum_{i=1}^{n}\frac{1}{16}p_{i}t_{i}$ of the expected total value. By Lemma
1, we have
$\sum_{i\in[n]}\frac{1}{16}p_{i}t_{i}\geqslant\frac{1}{16}\textbf{EPROPH}_{M}$,
finishing the proof. ∎

###  4.2 $k$-column sparse matroids

There are known constant-competitive mechanisms for $k$-column sparse matroids
in the context of the secretary problem [Sot13]. However they do not
immediately lead to a non-adaptive mechanism of constant competitiveness
guarantee. The reason for that are not the updated thresholds but implicit
changes to the considered matroid.

Here, we present a constant competitive mechanism for $k$-column sparse
matroid class for each constant $k$. Note, graphic matroids form a subclass of
$2$-column sparse matroids . Because of their significance, $2$-column sparse
matroids are also known in literature as _represented frame matroids_. Later,
we use $2$-column sparse matroids to prove results in Section 6.4.

Suppose $M$ is a $k$-column sparse matroid over field $\mathbb{F}$. In this
section, we prove that there exists a $(2^{k+2}k)$-competitive mechanism for
$M$.

Suppose a $k$-sparse representation of $M=(E,\mathcal{S})$ is defined by a map
$\phi:E\rightarrow\mathbb{F}^{d}$. Note, if for some element $t\in E$ the
vector $\phi(t)$ is a zero vector then $c$ is a loop and therefore can be
removed from consideration.

Now we consider an undirected hyper-multigraph $G$ with vertex set $[d]$. Each
matroid element $t\in E$ induces a hyperedge $e_{t}$ in this graph between
non-zero coordinates of $\phi(t)$. Formally, the hyperedge $e_{t}$ is defined
as follows $e_{t}:=\\{i\in[d]\,:\,\phi(t)_{i}\neq 0\\}$. We say that a vertex
$i\in[d]$ of the hyper-multigraph $G$ is incident to every edge $e$ of $G$
such that $i\in e$. For a vertex $i\in[d]$ we denote the collection of
incident hyperedges by $\delta(i)$. The degree of a vertex $i$ in the hyper-
multigraph $G$ equals $|\delta(i)|$.

######  Claim 1.

Suppose $I$ is an independent set of the matroid $M$. Then the average degree
of a vertex is at most $k$ when one considers the hyper-multigraph with
vertices $[d]$ and hyperedges $\\{e_{t}\,:\,t\in I\\}$.

###### Proof.

Observe that $|I|\leqslant d$ because having more than $d$ vectors in
$d$-dimensional vector space $\mathbb{F}^{d}$ leads to a a linear dependency.

Since $M$ is $k$-column sparse, we have that every edge in $\\{e_{t}\,:\,t\in
I\\}$ is incident to at most $k$ vertices in $[d]$. Hence, the total degree is
at most $kd$ and thus the average degree of a vertex is at most $k$. ∎

Now we consider _orientations_ of the graph $G$. An orientation of the graph
$G$ is a function $\varphi$ which maps every edge $e_{t}$ into one vertex of
$G$ incident to $e_{t}$. We call $\varphi(e_{t})$ to be the head of the edge
$e_{t}$, and all other vertices, if any, to be tails. For every vertex
$i\in[d]$ we denote the set of incoming edges by $\delta^{-}(i)$, formally
$\delta^{-}(i)=\\{e_{t}\,:\,\varphi(e_{t})=i,\,t\in E\\}$.

######  Lemma 4.

Let $p$ be a point in the polytope $P_{M}$. We assume that for every $t\in E$,
the coordinate $p_{t}$ of $p$ corresponds to the element $t$. Then there
exists an orientation $\varphi$ of hyperedges in the hyper-mulrigraph $G$ such
that for every vertex $i\in[d]$ we have $\sum_{t\in
E:e_{t}\in\delta^{-}(i)}p_{t}\leqslant k$.

The proof of Lemma 4 is analogous to the proof of Lemma 2. Now let us describe
an algorithm for $k$-column sparse matroids.

1:Let $p$ be a point in the polytope $P_{M}$ so that the statement of Lemma 1
is satisfied.

2:Let the edges of the hyper-multigraph $G$ be oriented so that the statement
of Lemma 4 is satisfied.

3:For every edge $e_{i}\in E$, $i\in[n]$, mark the edge $e_{i}$ as “discarded"
independently at random with probability $1-\frac{1}{2k}$.

4:Select a cut $S\subseteq[d]$ uniformly at random, mark all edges not in
$[S;\overline{S}]$ as “discarded”. Here, $[S;\overline{S}]$ stands for the set
of edges which are oriented such that all their tails are in $S$ and their
head is in $\overline{S}$. In particular, for $t\in E$ we say that $e_{t}$
lies in a cut $[S;\overline{S}]$ with respect to the orientation $\varphi$ if
$\varphi(e_{t})\in\overline{S}$ and for every $i\in
e_{t}\setminus\\{\varphi(e_{t})\\}$ we have $i\in S$.

5:Set thresholds $\\{T_{t}\,:\,t\in E\\}$ as follows, for each $t\in E$
$T_{t}:=\begin{cases}+\infty&\text{if }t\text{ is ``discarded''}\\\
F_{t}^{-1}(1-p_{t})&\text{otherwise}\,.\end{cases}$

Algorithm 2 A non-adaptive $2^{k+2}k$-competitive mechanisms for $k$-column
sparse matroids

######  Lemma 5.

For every $t\in E$ we have

$P[t\text{ is selected}\mid X_{t}\geq T_{t}\text{ and }t\text{ is not
``discarded''}]\geq 1/2\,.$

###### Proof.

Note that item $t\in E$ is accepted whenever $X_{t}\geq T_{t}$ and no other
item was selected from non-discarded edges in $\delta^{-}(\varphi(t))$. By the
union bound, for every event $J$ we can upper bound the probability that

$\displaystyle P[\text{there $j\in E\setminus\\{t\\}$ such that $j$ is
selected and $e_{j}\in\delta^{-}(\varphi(t))$}\mid J]\leqslant$
$\displaystyle\sum_{j\in
E\setminus\\{t\\}:e_{j}\in\delta^{-}(\varphi(t))}P[\text{$e_{j}$ is not
``discarded'' and }X_{j}\geq T_{j}\mid J]\,.$

Let $J$ indicate the event that "$e_{t}$ is not marked as “discarded” after
the selection of the cut". Then for each $j\in E\setminus\\{t\\}$ we have
$P[\text{$e_{j}$ is not ``discarded'' and }X_{j}\geq T_{j}\mid
J]\leq\frac{1}{2k}p_{j}$. By Lemma 4, we have $\sum_{j\in
E:e_{j}\in\delta^{-}(\varphi(t))}p_{j}\leqslant k$, leading to the desired
inequality. ∎

Note that the proof of Lemma 5 is analogous to the proof of Lemma 3. We are
ready to prove Theorem by showing that the Algorithm 2 is a
$2^{k+2}k$-competitive for $k$-column sparse matroids.

###### Proof of Theorem 4.

For every item $t\in E$ we have $P[X_{t}\geq T_{t}]=p_{t}$ and $P[t\text{ is
not ``discarded''}]\geq\frac{1}{2^{k+1}k}$. By Lemma 5, we have that with
probability at least $1/2$ the item $t$ is selected when it is not “discarded”
and $X_{t}\geq T_{t}$. Thus the expected total value of Algorithm 2 is at
least $\sum_{j\in E}\frac{1}{2^{k+2}k}p_{j}t_{j}$ which is at least
$\frac{1}{2^{k+2}k}\textbf{EPROPH}_{M}$ by Lemma 1.

∎

##  5 Cographic and gamma-sparse matroids

###  5.1 Cographic matroids

Let us revisit a mechanism of Soto [Sot13] for the cographic matroid secretary
problem which is based on the following corollary of Edmond’s matroid
partitioning theorem [Edm65]. This mechanism leads to a non-adaptive mechanism
for cographic matroids.

######  Proposition 1.

Let $G=(V,E)$ be a three edge-connected graph. Then there exist spanning trees
$H_{1},H_{2},H_{3}$ in $G$ such that the union of their complements contains
all the edges $E$, i.e. $E=(E\setminus H_{1})\cup(E\setminus
H_{2})\cup(E\setminus H_{3})$.

1:Let $H_{1}$, $H_{2}$ and $H_{3}$ be the spanning trees as in Proposition 6.

2:Uniformly at random select a spanning tree $H^{*}$ from $H_{1}$, $H_{2}$ and
$H_{3}$. Set thresholds $\\{T_{e}\,:\,e\in E\\}$ as follows, for each $e\in E$
$T_{e}:=\begin{cases}+\infty&\text{if }e\text{ is not in }H^{*}\\\
0&\text{otherwise}\,.\end{cases}$

Algorithm 3 A non-adaptive $3$-competitive mechanisms for cographic matroids
in the case of three edge-connectivity

######  Lemma 6.

Let $G=(V,E)$ be a three edge-connected graph and let $M$ be the cographic
matroid over $G$. Then Algorithm 3 is a $3$-competitive non-adaptive mechanism
for the matroid $M$.

###### Proof.

The expected total value of the mechanism provided by Algorithm 3 equals
$E[\sum_{e\in E\setminus H^{*}}X_{e}]$ which can be estimated as follows

$E[\sum_{e\in E\setminus H^{*}}X_{e}]=\frac{1}{3}E[\sum_{i\in[3]}\sum_{e\in
E\setminus H_{i}}X_{e}]\geq\frac{1}{3}E[\sum_{e\in
E}X_{e}]\geq\frac{1}{3}\textbf{EPROPH}_{M}\,.$

∎

1:Delete all loops of $M$ to obtain a matroid $M^{\prime}$. Remove all bridges
from $G=(V,E)$ and obtain a graph $G^{\prime}=(V^{\prime},E^{\prime})$.

2:Let $C_{1}$,…, $C_{k}$ be equivalence classes of $M^{\prime}$ with respect
to the relation of being parallel. Construct the matroid $M^{\prime\prime}$
from $M^{\prime}$ by contracting all but one edge in each class $C_{1}$,
$C_{2}$, …, $C_{k}$. Note, that the ground set of $M^{\prime\prime}$ has $k$
elements and matroid $M^{\prime\prime}$ is the cographic matroid over a graph
$G^{\prime\prime}$, where each connected component of $G^{\prime\prime}$ is
three edge-connected. Abusing the notation we refer to the elements of the
ground set of $M^{\prime\prime}$ as $C_{1}$, $C_{2}$, …, $C_{k}$.

3:Let $H_{1}$, $H_{2}$ and $H_{3}$ be forests in $G^{\prime\prime}$ such that
the restriction of $H_{1}$, $H_{2}$ and $H_{3}$ to each connected component of
$G^{\prime\prime}$ satisfies Proposition 6 for the respective connected
component.

4:Uniformly at random select a forest $H^{*}$ from $H_{1}$, $H_{2}$ and
$H_{3}$.

5:For each $i\in[k]$ select thresholds $\overline{T}_{e}$, $e\in C_{i}$
according to Theorem 1 when the gambler is allowed to accept only one item of
$C_{i}$ and the distributions of $X_{e}$, $e\in C_{i}$ are the same as
original distributions of values for $e\in C_{i}$.

6:Set thresholds $\\{T_{e}\,:\,e\in E\\}$ as follows, for each $e\in E$
$T_{e}:=\begin{cases}\overline{T}_{e}&\text{if }e\in C_{i}\text{ and }C_{i}\in
H^{*}\text{ for some }i\in[k]\\\ +\infty&\text{otherwise}\,.\end{cases}$

Algorithm 4 A non-adaptive $6$-competitive mechanisms for cographic matroids

The next theorem provides a proof for Theorem 5.

######  Theorem 11.

Let $G=(V,E)$ be a graph and let $M$ be the cographic matroid over $G$. Then
Algorithm 4 is a $6$-competitive non-adaptive mechanism for the matroid $M$.

###### Proof.

We can assume that $G$ does not have bridges, because every such bridge is a
loop in $M$. Thus these edges can be selected neither by the gambler nor by
the prophet. So we can assume $G=G^{\prime}$ and $M=M^{\prime}$.

In the case when each connected component of $G$ is three edge-connected, then
Algorithm 4 runs Algorithm 3 for each component to obtain a $3$-competitive
non-adaptive mechanism.

Otherwise, there is one or more pairs of edges $e$,$e^{\prime}$ such that
$\\{e,e^{\prime}\\}$ corresponds to a cut in $G$. In this case, the edges
$e$,$e^{\prime}$ correspond to parallel elements of the cographic matroid $M$.

Algorithm 4 considers the partition of $E$ into classes of parallel elements
$C_{1}$, $C_{2}$, …, $C_{k}$. Let us construct the matroid $M^{\prime\prime}$
from $M$ by contracting all but one edge in each class $C_{1}$, $C_{2}$, …,
$C_{k}$. Note, that the ground set of $M^{\prime\prime}$ has $k$ elements.
Abusing the notation we refer to these elements of the ground set as $C_{1}$,
$C_{2}$, …, $C_{k}$. The matroid $M^{\prime\prime}$ is isomorphic to the
cographic matroid over a graph $G^{\prime\prime}$, where each connected
component of $G^{\prime\prime}$ is three edge-connected. Following Lemma 6,
Algorithm 4 constructs forests $H_{1}$, $H_{2}$, $H_{3}$ for the graph
$G^{\prime\prime}$.

So Algorithm 4 leads us to a $6$-competitive mechanism. Indeed, the prophet
with $M$ and with the original distributions of $X_{e}$, $e\in E$ performs
exactly as the prophet with $M^{\prime\prime}$ and with the corresponding
distributions of $X^{\prime\prime}_{i}:=\max_{e\in C_{i}}X_{e}$, $i\in[k]$. By
selecting forests in Algorithm 4 the gambler acheives in expectation
$E[\sum_{i\in[k]}X^{\prime\prime}_{i}]/3$ when all classes $C_{1}$, $C_{2}$,
…, $C_{k}$ are singletons. However, for classes that are not singletons we
need to take into account another $2$ approximation factor with respect to the
prophet, who can achieve the expected value $E[X^{\prime\prime}_{i}]$ for each
$i\in[k]$, while the gambler is guaranteed in expectation to achieve only
$E[X^{\prime\prime}_{i}]/2$ for each $i\in[k]$. ∎

###  5.2 Gamma-sparse matroids

Let us also revisit a mechanism of Soto [Sot13] for $\gamma$-sparse matroids
to verify that it directly leads to a non-adaptive mechanism.

######  Theorem 12.

Let $M=(E,\mathcal{S})$ be a $\gamma$-sparse matroid. There exists a
$\gamma$-competitive non-adaptive mechanism for $M$.

###### Proof.

First observe that the point $x:=\mathbb{1}{/}\gamma$ lies in the matroid
polytope $P_{M}$. Indeed, it is non-negative and for every set $S\subseteq
E(M)$ we have $x(S)=|S|{/}\gamma\leqslant r_{M}(S)$.

Then $x$ can be expressed as a convex combination of indicator variables
corresponding to the independent sets of $M$. In other words, we have
$x=\sum_{S\in\mathcal{S}}\alpha_{S}\mathbb{1}_{S}$ for some $\alpha\geqslant
0$, $\sum_{S\in\mathcal{S}}\alpha_{S}=1$, where $\mathbb{1}_{S}$ refers to the
characteristic vector of $S$.

Now sample an independent set $S$ in matroid $M$ randomly with probability
$\alpha_{S}$. Let the gambler select all items in $S$ and let the gambler
leave all the items not in $S$ unselected.

If $X_{e}$ is the random variable corresponding to the weight of element $e\in
E(M)$, then this mechanism results in a total expected value as follows

$\sum_{S\in\mathcal{S}}\alpha_{S}\sum_{e\in S}E[X_{e}]=\sum_{e\in
E}(1/\gamma)E[X_{e}]=E[\sum_{e\in
E}X_{e}]/\gamma\geqslant\textbf{EPROPH}/\gamma\,,$

finishing the proof. ∎

Observe that Proposition 1 implies that for a three edge-connected graph $G$,
the cographic matroid of $G$ is $3$-sparse. Thus Lemma 6 is a corollary of
Theorem 12.

Similarly, for a planar graph $G$ the graphic matroid is $3$-sparse, leading
us to the following corollary.

######  Corollary 1.

Let $G$ is a planar graph and let $M$ be the corresponding graphic matroid.
There is a $3$-competitive non-adaptive mechanism for $M$.

##  6 Representable matroids

Many results in the theory of matroids make use of minors coming from
restrictions and contractions. To get access to the toolbox provided by
matroid theory, we need to understand how prophet inequality guarantees change
when we consider minors.

###  6.1 Preliminaries

######  Lemma 7.

Let $M$ be a matroid and let matroid $N$ be a restriction of the matroid $M$.
If there exists an $\alpha$-competitive non-adaptive mechanism on $M$, then
there is an $\alpha$-competitive non-adaptive mechanism for $N$.

###### Proof.

To obtain a mechanism for the matroid $N$, we can impose thresholds $+\infty$
for the items that were removed from the ground set to obtain the restriction
$N$ from the matroid $M$. The remaining items are assigned the same thresholds
in both mechanisms. ∎

A similar result for contractions is harder to obtain in the case of non-
adaptive mechanisms. Indeed, a straightforward approach would require us to
impose the thresholds $+\infty$ for the contracted items, while using the
given mechanism on the remaining items. Unfortunately, this would also require
us to “change" the underlying matroid, in other words a gambler might be
forced to reject an item even though its value is over the assigned threshold
and its addition to the currently selected items keeps the selected set
independent with respect to $M$.

Because of this difficulty, in this work we provide a matching result for
contractions only for matroids representable over a finite field. This result
is sufficient for the purpose of this work.

######  Lemma 8.

Let $M=(E,\mathcal{S})$ be a matroid representable over the field
$\mathbb{F}_{p}$ for some $p$. Let $T\subseteq E$ be a subset of the ground
set such that $\lambda_{M}(T)\leqslant k$ for some $k$.

Then there exists $S\subseteq T$ so that every set that is independent in
$M\mid_{S}$ is also independent in $M{/}_{\overline{T}}$ and

$\textbf{EPROPH}_{M\mid_{S}}\geqslant\frac{1}{p^{k+1}}{\textbf{EPROPH}_{M{/}_{\overline{T}}}}\,.$

Recall that $\overline{T}$ stands for the complement of $T$ with respect to
the ground set $E$.

###### Proof.

Consider the representation of the matroid $M$ over $\mathbb{F}_{p}$. Let
$\phi:E\rightarrow\mathbb{F}^{m}_{p}$ be the map describing the representation
of $M$. Thus, for every $S\subseteq E$ we have that the set
$\phi(S)=\\{\phi(e)\in\mathbb{F}_{p}^{m}\,:\,e\in S\\}$ is independent over
the field $\mathbb{F}_{p}$ if and only if $S$ is an independent set for the
matroid $M$.

Since $\lambda_{M}(T)\leqslant k$ holds, by definition of $\lambda_{M}$ we
have

$r_{M}(T)+r_{M}(\overline{T})-r_{M}(E)\leqslant k\,.$

We have $r_{M}(R)=\dim\operatorname{span}(\phi(R))$ for every $R\subseteq E$.
Thus, we have

$\dim\operatorname{span}\phi(E)=\dim\operatorname{span}\phi(T)+\dim\operatorname{span}\phi(\overline{T})-\dim\left((\operatorname{span}\phi(T))\cap(\operatorname{span}\phi(\overline{T}))\right).$

and so

$\dim\left((\operatorname{span}\phi(T))\cap(\operatorname{span}\phi(\overline{T}))\right)\leqslant
k\,.$

Since we are working over the field $\mathbb{F}_{p}$, the linear space
$L:=(\operatorname{span}\phi(T))\cap(\operatorname{span}\phi(\overline{T}))$
has at most $p^{k}$ vectors. Let $C$ be the orthogonal complement of the
linear space $L$ in the space $\operatorname{span}\phi(T)$. Thus, we can
represent $\operatorname{span}\phi(T)$ as $L\oplus C$. For every vector
$v\in\operatorname{span}\phi(T)$ we denote $v$ orthogonal projection to $L$
and $C$ by $v\mid_{L}$ and $v\mid_{C}$, respectively.

For each vector $a\in L$, define the set $T_{a}:=\\{t\in
T\,:\,\phi(t)\mid_{L}=a,\,\phi(t)\neq a\\}$. Note that by definition for every
$a\in L$ we have $T_{a}\cap L=\varnothing$. Now let us select $a$ uniformly at
random from $L$.

######  Claim 2.

$E_{a}[\textbf{EPROPH}_{M\mid_{T_{a}}}]\geq\frac{1}{p^{k}}\textbf{EPROPH}_{M{/}_{\overline{T}}}$.

###### Proof.

To prove the desired inequality, we prove the corresponding inequality for any
realization of item values. From now on we consider the realization of item
values fixed and thus we prove the following inequality

$E_{a}[\textbf{PROPH}_{M\mid_{T_{a}}}]\geq\frac{1}{p^{k}}\textbf{PROPH}_{M{/}_{\overline{T}}}$

Let us consider the set $I_{opt}$ on which the prophet achieves
$\textbf{PROPH}_{M{/}_{\overline{T}}}$. Note that the set $I_{opt}$ does not
contain any item $e$ such that $\phi(e)$ is in $L$, because every such an item
$e$ is a loop in $M{/}_{\overline{T}}$. Thus, the set $I_{opt}$ can be
partitioned into sets $I_{opt,a}$, ${a\in L}$ where $I_{opt,a}$ is a subset of
$T_{a}$.

The set $I_{opt}$ is independent in $M{/}_{\overline{T}}$ and so $I_{opt}$ is
also independent in $M$. Hence the sets $I_{opt,a}$, ${a\in L}$ are also
independent in $M$. Thus for every $a\in L$,
$\textbf{PROPH}_{M\mid_{T_{a}}}\geqslant w(I_{opt,a})$. Then we have

$E_{a}[\textbf{PROPH}_{M\mid_{T_{a}}}]\geqslant\frac{\sum_{a\in
L}w(I_{opt,a})}{|L|}=\frac{1}{|L|}w(I_{opt})\geqslant\frac{1}{p^{k}}\textbf{PROPH}_{M{/}_{\overline{T}}}\,,$

finishing the proof of the claim.

∎

Let us now select $a^{*}\in L$ such that $\textbf{EPROPH}_{M\mid_{T_{a}}}$ is
maximized. By the previous claim, we have

$\textbf{PROPH}_{M\mid_{T_{a^{*}}}}\geqslant\frac{1}{p^{k}}\textbf{PROPH}_{M{/}_{\overline{T}}}\,.$

Now for every $c\in C$ define set $H_{c}:=\\{t\in
T_{a^{*}}\,:\,(\phi(t)\mid_{C})\cdot c=1\\}$. Now let us select $c$ uniformly
at random from $C$.

######  Claim 3.

$E_{c}[\textbf{EPROPH}_{M\mid_{H_{c}}}]\geq\frac{1}{p}\textbf{EPROPH}_{M{\mid}_{\overline{T}_{a^{*}}}}.$

###### Proof.

To prove the desired inequality, we prove the corresponding inequality for any
realization of item values. From now on we consider the realization of item
values fixed and thus we prove the following inequality

$E_{c}[\textbf{PROPH}_{M\mid_{H_{c}}}]\geq\frac{1}{p}\textbf{PROPH}_{M{\mid}_{\overline{T}_{a^{*}}}}\,.$

Let $I_{opt}$ be the set corresponding to
$\textbf{PROPH}_{M\mid_{T_{a^{*}}}}$. Thus, we have that for every $e\in
I_{opt}$, $\phi(e)$ is not in $L$ and hence $\phi(e)\mid_{C}$ is not the zero
vector. Due to $P_{c}[c\cdot t=1]=1{/}p$, for every $t\in T_{a^{*}}$, we have

$E_{c}[w(I_{opt}\cap H_{c})]=\sum_{t\in I_{opt}}P_{c}[c\cdot
t=1]w(t)=\frac{1}{p}\sum_{t\in
I_{opt}}w(t)=\frac{1}{p}w(I_{opt})=\textbf{PROPH}_{M\mid_{T_{a^{*}}}}\,.$

Finally, since $I_{opt}$ is independent in $M$ so is $I_{opt}\cap H_{c}$.
Thus, we have

$E_{c}[\textbf{PROPH}_{M\mid_{H_{c}}}]\geq\frac{1}{p}\textbf{PROPH}_{M{\mid}_{\overline{T}_{a^{*}}}}\,,$

finishing the proof of the claim. ∎

Now let us select $c^{*}$ so that $\textbf{EPROPH}_{M\mid_{H_{c}}}$ is
maximized and let $S^{*}:=H_{c^{*}}$. Then we have
$\textbf{EPROPH}(M\mid_{S^{*}})\geqslant\frac{1}{p^{k+1}}\textbf{EPROPH}(M{/}_{\overline{T}})$.

Finally, we need to show that every set independent in $M\mid_{S^{*}}$ is an
independent set in $M{/}_{\overline{T}}$. Suppose the contrary, i.e. there
exists a set that is independent in $M\mid_{S^{*}}$ but is not an independent
set in $M{/}_{\overline{T}}$. Then $\operatorname{span}S^{*}$ has a non-
trivial intersection with $\operatorname{span}\overline{T}$, suppose
$x\in(\operatorname{span}\phi(S^{*}))\cup(\operatorname{span}\phi(\overline{T}))$.
Let us show that $x$ is a zero vector. Since $x\in\operatorname{span}S^{*}$,
we have $x=\sum_{s\in S^{*}}\alpha_{s}\phi(s)$ for some
$\alpha_{s}\in\mathbb{F}_{p}$, $s\in S^{*}$.

Let us consider the projections of $x$ on $C$ and $L$. Since
$x\in\operatorname{span}\phi(\overline{T})$ we have that $x$ lies in $L$ and
so $x\mid_{C}$ is the zero vector. Thus $x\mid_{C}=\sum_{s\in
S^{*}}\alpha_{s}(\phi(s)\mid_{C})$ is the zero vector.

Note that by definition, $\phi(s)\mid_{L}=a^{*}$ and
$c^{*}\cdot(\phi(s)\mid_{C})=1$ hold for every $s\in S^{*}$ . Thus over the
field $\mathbb{F}_{p}$ we have

$\displaystyle\sum_{s\in S^{*}}\alpha_{s}=\sum_{s\in
S^{*}}\alpha_{s}(c^{*}\cdot(\phi(s)\mid_{C}))=c^{*}\cdot\left(\sum_{s\in
S^{*}}\alpha_{s}(\phi(s)\mid_{C})\right)=$ $\displaystyle
c^{*}\cdot\left(x\mid_{C}\right)=0\,.$

Now let us consider $x\mid_{L}$. We have

$x\mid_{L}=\sum_{s\in S^{*}}\alpha_{s}(\phi(s)\mid_{L})=\left(\sum_{s\in
S^{*}}\alpha_{s}\right)a^{*}\,,$

where the last expression equals the zero vector since $\sum_{s\in
S^{*}}\alpha_{s}=0$. Thus we have a vector $x\in L\oplus C$ such that both
projections $x\mid_{L}$ and $x\mid_{C}$ are the zero vector. Hence, the vector
$x$ is the zero vector, finishing the proof.

∎

###  6.2 Tree Decompositions

Similarly to the approach [HN20] for the matroid secretary problem, we
extensively use the tree decomposition of matroids. A tree decomposition of
bounded thickness allows us to construct non-adaptive mechanisms with good
approximation ratios. Before proceeding with these constructions, let us
introduce tree decompositions.

A _tree decomposition_ of a matroid $M=(E,\mathcal{S})$ is a pair
$(T,\mathcal{X})$ where $T$ is a tree and $\mathcal{X}=\\{X_{v}\subseteq
E\,:\,v\in V(T)\\}$, where sets in $\mathcal{X}$ form a partition of $E$.
Here, we refer to the vertex and edge sets of the tree $T$ as $V(T)$ and
$E(T)$, respectively.

Given an edge $e=\\{v_{1},v_{2}\\}\in E(T)$ of the tree $T$, let $T_{1}$ and
$T_{2}$ be two connected components of $T-e$, in other word the removal of the
edge $e$ from $T$ leads to two connected components $T_{1}$ and $T_{2}$. The
thickness of the edge $e=(v_{1},v_{2})$ is denoted as $\lambda(e)$ and is
defined as follows

$\lambda(e):=\lambda_{M}(\cup_{v\in V(T_{1})}X_{v})\,.$

The _thickness of the tree decomposition_ is the maximum thickness of the edge
$e$ in $E(T)$.

Let $\mathcal{M}$ be a family of matroids, $M$ be a matroid and
$(T,\mathcal{X})$ be a tree decomposition of $M$. We say that tree
decomposition $(T,\mathcal{X})$ is _$\mathcal{M}$ -tree decomposition_ if
$M\mid_{cl_{M}(X_{v})}\in\mathcal{M}$ holds for every $v\in V(T)$. Let
$t_{k}(\mathcal{M})$ be a set of matroids which have $\mathcal{M}$-tree
decomposition of thickness at most $k$.

######  Theorem 13.

Let $\mathcal{M}_{\alpha,p}$ be the family of matroids which admit
$\alpha$-competitive non-adaptive mechanisms and are representable over the
finite field $\mathbb{F}_{p}$. Then for every natural number $k$ and every
matroid $M$ in $t_{k}(\mathcal{M}_{\alpha,p})$, the matroid $M$ has an
$(\alpha p^{k+1})$-competitive non-adaptive mechanism.

###### Proof.

For a natural number $m$, let $t_{k,m}(\mathcal{M}_{\alpha,p})$ be the set of
matroids which have an $\mathcal{M}_{\alpha,p}$-tree decomposition
$(T,\mathcal{X})$ of thickness at most $k$ satisfying $|V(T)|=m$.

Let us prove the statement of the lemma by induction on $m$. The base case
follows from the definition of the family $\mathcal{M}_{\alpha,p}$ and the
fact that $\mathcal{M}_{\alpha,p}=t_{k,1}(\mathcal{M}_{\alpha,p})$.

Let us now show how to do the inductive step. Let us assume $m\geq 2$ and
consider a matroid $M=(E,\mathcal{S})$ in $t_{k,m}(\mathcal{M}_{\alpha,p})$
with its $\mathcal{M}_{\alpha,p}$-tree decomposition $(T,\mathcal{X})$ of
thickness at most $k$ and with $|V(T)|=m$. Let $\ell$ be a leaf of the tree
$T$ and let $u$ be the neighbour of the vertex $\ell$ in the tree $T$.

Observe that the tree $(V(T)\setminus\\{\ell\\},E(T)\setminus\\{\ell u\\})$
together with the subfamily $\\{X_{w}\,:\,w\in V(T)\setminus\\{\ell\\}\\}$
defines an $\mathcal{M}_{\alpha,p}$-tree decomposition of the matroid
$M\setminus X_{\ell}$. Thus the matroid $M\setminus X_{\ell}$ is in $M\in
t_{k,m-1}(\mathcal{M}_{\alpha,p})$. Hence, by the inductive hypothesis there
are thresholds $T^{\prime}_{e}$, $e\in E\setminus X_{\ell}$ guaranteeing
$\alpha p^{k+1}$-competitiveness of the gambler in comparison to the prophet
on the matroid $M\setminus X_{\ell}$.

######  Claim 4.

There are thresholds $T^{\prime\prime}_{e}$, $e\in X_{\ell}$ leading to an
$(\alpha\cdot p^{k+1})$-competitive non-adaptive mechanism for matroid
$M\mid_{X_{\ell}}$, such that the gambler always selects a set that is
independent in $M/_{\overline{X_{\ell}}}$.

###### Proof.

By Lemma 8 there exists a set $S\subseteq X_{l}$ such that every set
independent in $M\mid_{S}$ is also independent in the matroid
$M/\overline{X_{\ell}}$ and

$\textbf{EPROPH}_{M\mid_{S}}\geqslant\frac{1}{p^{k+1}}\textbf{EPROPH}_{M{/}_{\overline{X_{\ell}}}}\,.$

By definition of $\mathcal{M}_{\alpha,p}$ and the appearance of $X_{\ell}$ in
the tree decomposition, we have that $M\mid_{X_{\ell}}$ is in the family
$\mathcal{M}_{\alpha,p}$. By Lemma 7, since $S$ is a subset of $X_{\ell}$ the
matroid $M\mid_{S}$ is also in the family $\mathcal{M}_{\alpha,p}$. Thus,
there are thresholds $T^{\prime\prime}_{e}$, $e\in S$ that lead to an
$\alpha$-competitive non-adaptive mechanism on $M\mid_{S}$. The thresholds
$T^{\prime\prime}_{e}$, $e\in X_{\ell}\setminus S$ can be defined as
$+\infty$, finishing the proof of the claim. ∎

Now we can define thresholds $T_{e}$, $e\in E$ for all elements of the matroid
$M$ as follows

$T_{e}:=\begin{cases}T^{\prime}_{e}&\text{if }e\not\in X_{\ell}\\\
T^{\prime\prime}_{e}&\text{otherwise}\,.\end{cases}$

Let us now demonstrate that such thresholds $T_{e}$, $e\in E$ lead to an
$(\alpha p^{k+1})$-competitive non-adaptive mechanism for $M$.

First, by the above claim the selected items from $X_{\ell}$ always form an
independent set in $M/\overline{X_{\ell}}$ when used with the thresholds
$T_{e}$, $e\in X_{\ell}$ on the matroid $M\mid_{X_{\ell}}$. Thus the
definition of the thresholds guarantees that in expectation the value of
selected items from $X_{\ell}$ is at least
$\textbf{EPROPH}_{M\mid_{X_{\ell}}}/(\alpha p^{k+1})$; and in expectation the
value of selected items from $E\setminus X_{\ell}$ is at least
$\textbf{EPROPH}_{M\setminus{X_{\ell}}}/(\alpha p^{k+1})$.

To finish the proof, note that we have

$\textbf{PROPH}_{M\mid_{X_{\ell}}}+\textbf{PROPH}_{M\setminus{X_{\ell}}}\geq\textbf{PROPH}_{M}$

and so

$\textbf{EPROPH}_{M\mid_{X_{\ell}}}+\textbf{EPROPH}_{M\setminus{X_{\ell}}}\geq\textbf{EPROPH}_{M}\,.$

∎

###  6.3 Regular matroids

In this section, we prove Theorem 7. Before we proceed to the proof, let us
define key notions related to regular matroids.

A subset of the matroid’s ground set is called a _circuit_ , if it is an
inclusion-minimal dependent set. A _cycle_ is a subset of the ground set which
can be partitioned into a disjoint union of circuits.

Let $M_{1}=(E_{1},\mathcal{S}_{1})$, $M_{2}=(E_{2},\mathcal{S}_{2})$ be two
binary matroids. Then the matroid sum $M_{1}\triangle M_{2}$ has the ground
set $E_{1}\triangle E_{2}$ and the cycles of $M_{1}\triangle M_{2}$ are all
sets of the form $C_{1}\triangle C_{2}$, where $C_{1}$ is a cycle for $M_{1}$
and $C_{2}$ is a cycle for $M_{2}$.

######  Definition 3.

Consider two binary matroids $M_{1}=(E_{1},\mathcal{S}_{1})$,
$M_{2}=(E_{2},\mathcal{S}_{2})$ and $M=M_{1}\triangle M_{2}$.

  1. 1.

If $|E_{1}\cap E_{2}|=0$, and $E_{1}\neq\varnothing$, $E_{2}\neq\varnothing$,
$M$ is called a _$1$ -sum_ of $M_{1}$ and $M_{2}$.

  2. 2.

If $|E_{1}\cap E_{2}|=1$, $|E_{1}|\geq 3$, $|E_{2}|\geq 3$ and $E_{1}\cap
E_{2}$ is not a loop of $M_{1}$ or $M_{2}$ or their dual matroids, $M$ is
called a _$2$ -sum_ of $M_{1}$ and $M_{2}$.

  3. 3.

If $|E_{1}\cap E_{2}|=3$, $|E_{1}|\geq 7$, $|E_{2}|\geq 7$ and $E_{1}\cap
E_{2}$ is a circuit in both $M_{1}$ and $M_{2}$, and $E_{1}\cap E_{2}$ does
not contain a circuit in their dual matroids, then $M$ is called a _$3$ -sum_
of $M_{1}$ and $M_{2}$.

###### Proof of Theorem 7.

By Seymour’s regular matroid decomposition theorem [Sey80], every regular
matroid $M$ can be obtained from graphic, cographic or a special matroid
$R_{10}$ through a sequence of $1$-sums, $2$-sums or $3$-sums.

This gives a tree decomposition $(T,\mathcal{X})$ of thickness at most $2$ so
that each $M\mid_{X_{v}}$, $v\in V(T)$ is either a graphic, cographic or a
special matroid $R_{10}$.

By performing parallel extensions of the elements to be deleted before each
$2$-sum and $3$-sum, we construct a matroid $M^{\prime}$, so that $M$ is a
restriction of $M^{\prime}$ and $M^{\prime}$ has a tree decomposition
$(T,\mathcal{X}^{\prime})$ so that each
$M^{\prime}\mid_{\operatorname{cl}_{M^{\prime}}(X^{\prime}_{v})}$, $v\in V(T)$
is either graphic, cographic or a parallel extension of $R_{10}$.

By Theorem 2, every graphic matroid has a $32$-competitive non-adaptive
mechanism. By Theorem 5, every cographic matroid has a $6$-competitive non-
adaptive mechanism. Since matroid $R_{10}$ has ground set of size $10$, by
Theorem 1 every parallel extension of $R_{10}$ has a $20$-competitive non-
adaptive mechanism.

Note that by definition every regular matroid is representable over finite
field $\mathbb{F}_{2}$. Thus, by Theorem 13 with $p=2$, $k=2$ and $\alpha=32$
there is a $256$-competitive non-adaptive mechanism for matroid $M^{\prime}$.
Since $M$ is a restriction of $M^{\prime}$, by Lemma 7, there is a
$256$-competitive non-adaptive mechanism for $M$, finishing the proof. ∎

###  6.4 Minor-closed representable matroid families

In this section we show that every minor-clossed subclass of matroids
representable over $\mathbb{F}_{p}$ has a constant-competitive non-adaptive
mechanism, where the constant is a function only of $p$. The proof of this
fact is analogous to the proof in [HN20].

######  Theorem 14 (Theorem 4.3 in [Gee11]).

Given natural numbers $q\geqslant 2$ and $n\geqslant 1$, let
$M=(E,\mathcal{S})$ be a matroid with no $U_{2,q+2}$ or $M(K_{n})$ minors.
Then we have $|E|\leq q^{q^{3n}}r_{M}(E)$.

######  Corollary 2.

Given natural numbers $q\geqslant 2$ and $n\geqslant 1$, let
$M=(E,\mathcal{S})$ be a matroid with no $U_{2,q+2}$ or $M(K_{n})$ minors.
Then there exists a $q^{q^{3n}}$-competitive non-adaptive mechanism for $M$.

###### Proof.

If $M$ has no $U_{2,q+2}$ or $M(K_{n})$ minors, then every restriction of $M$
also has no $U_{2,q+2}$ or $M(K_{n})$ minors. Thus for every $X\subseteq E$ we
have $|X|\leqslant q^{q^{3n}}r_{M}(X)$. So, $M$ is a $q^{q^{3n}}$-sparse
matroid and by Theorem 12 there exists a $q^{q^{3n}}$-competitive non-adaptive
mechanism for $M$. ∎

####  6.4.1 Projections and lifts

Let $M$ be a matroid and $x$ be an element of the ground set, which is a not a
loop and not a free element of the matroid $M$. Then $M/x$ is called a
_projection_ of $M\setminus x$; $M\setminus x$ is called a _lift_ of $M/x$.
Note that here and later we write $M/x$ and $M\setminus x$ instead of
$M/{\\{x\\}}$ and $M\setminus{\\{x\\}}$, repsectively.

Let $M$ and $N$ be two matroids with the same ground set. We say that the
distance between $M$ and $N$ is $t$, denoted by $\operatorname{dist}(M,N)=t$
if $t$ is the smallest integer such that there exists a sequence of matroids
$P_{0}$, $P_{1}$, …, $P_{t}$ where $P_{0}=M$ and $P_{t}=N$ and for every
$i\in[t]$ the matroid $P_{i}$ is either a lift or a projection of $P_{i-1}$.

######  Lemma 9.

Let $N$ be a lift of the matroid $M$. If there is an $\alpha$-competitive non-
adaptive mechanism for $M$ then there exists a $(2\alpha+2)$-competitive non-
adaptive mechanism for $N$.

###### Proof.

Since $N$ is a lift of $M$, there exists a matroid $L=(E,\mathcal{S})$ and an
element $x$ of its ground set, such that $M=L{/}x$, $N=L{\setminus}x$. Here,
$x$ is not a loop and not a free element of $L$.

Let $P$ be the set of elements in $L$ that are parallel to $x$, in other words
$P:=\\{x^{\prime}\in E\,:\,x^{\prime}\parallel x\\}$. Note that
$N\mid_{P\setminus\\{x\\}}$ is a uniform matroid of rank $1$. Note also that
elements in $P\setminus\\{x\\}$ are loops in $M$ and so
$\textbf{EPROPH}_{M}=\textbf{EPROPH}_{M\setminus P}$.

Let $T^{\prime}_{e}$, $e\in E\setminus\\{x\\}$ be the thresholds imposed by an
$\alpha$-competitive non-adaptive mechanism for the matroid $M$. Let
$T^{\prime\prime}_{e}$, $e\in P$ be the thresholds guaranteeing
$2$-competitive non-adaptive mechanism as in Theorem 1 for the uniform matroid
of rank $1$ on the ground set $P\setminus\\{x\\}$; and let
$T^{\prime\prime}_{e}$, $e\in E\setminus(P\cup\\{x\\})$ be $+\infty$. We
select one of these two sets of thresholds for the matroid $N$ as described
below. The constructed mechanism for the matroid $N$ selects one of those two
sets at random, where first set of thresholds $T^{\prime}_{e}$, $e\in
E\setminus\\{x\\}$ is selected with probability $\gamma:=\alpha{/}(\alpha+1)$
and the second set $T^{\prime\prime}_{e}$, $e\in E\setminus\\{x\\}$ with
probability $1-\gamma=1{/}(\alpha+1)$.

Next part is dedicated to the analysis of how thresholds $T^{\prime}_{e}$,
$e\in E\setminus\\{x\\}$ perform on the matroid $N$. Note, that these
thresholds are coming from a mechanism for the matroid $M$, while they are
used for the matroid $N$ with probability $\gamma$. We show that the total
expected value achieved by thresholds $T^{\prime}_{e}$, $e\in
E\setminus\\{x\\}$ on $N$ is at least the total expected value achieved by
these thresholds on $M$. For this we can assume that for every realization of
item values, the orders of items in matroid $N$ and $M$ are the same. To see
that this assumption is valid, we can assume that the order for $N$ is chosen
in an adversarial way and is used also as the items order for $M$.

######  Claim 5.

Let us assume that the items order for $M$ and $N$ is the same for a given
realization of item values. Let us also assume that for every item $e\in
E\setminus\\{x\\}$ the threshold $T^{\prime}_{e}$ is used. Then the gambler
with matroid $N$ selects all items that the gambler with matroid $M$ selects.

###### Proof.

We fix the item values realization and items order. Let $e_{1}$, $e_{2}$,…,
$e_{k}$ be the items with their values being at least their threshold and with
the corresponding order.

Now we need to show that if the gambler with matroid $N$ selects items
greedily from $e_{1}$, $e_{2}$,…, $e_{k}$ starting from $e_{1}$, then the set
of selected items is a superset of the items greedily selected by the gambler
with matroid $M$. If both gamblers end up selecting exactly the same set of
items, then proof of the claim is complete. Otherwise consider the first index
$i\in[k]$ such that the item $e_{i}$ is selected by exactly one of the two
gamblers. Since $N=L{\setminus}x$ and $M=L{/}x$ we have that it is only
possible if $e_{i}$ is selected by the gambler with the matroid $N$ and
rejected by the gambler with the matroid $M$.

Now we claim that every subsequent item, in other words an item in $e_{i+1}$,
…, $e_{k}$, is either selected by both gamblers or rejected by both gamblers.
Suppose the contrary and consider the first item $e_{j}$, $i+1\leq j\leq k$
that is selected by one gambler and rejected by another gambler. Let
$S:=\\{e_{1},e_{2},\ldots,e_{j-1}\\}$ and let $T$ be the set of items selected
by the gambler with $M$ from the set $S$. Thus the gambler with $N$ selected
$T\cup\\{e_{i}\\}$ from the set $S$. So $T\cup\\{e_{i}\\}$ is a basis of
$(L\setminus x)\mid_{S}$ and $T$ is a basis of $(L/x)\mid_{S}$. Thus, both
$T\cup\\{e_{i}\\}$ and $T\cup\\{x\\}$ are bases of $L\mid_{S}$. If only one of
the two gamblers accepts the item $s_{j}$ then the matroid
$L\mid_{S\cup\\{s_{j}\\}}$ has two bases of different cardinality, attaining a
contradiction and finishing the proof. ∎

Thus we have that the thresholds $T^{\prime}_{e}$, $e\in E\setminus\\{x\\}$
guarantee at least $\textbf{EPROPH}_{M}$ as the expected total value of the
gambler with $N$. To prove that the constructed mechanism is
$1/(2\alpha+2)$-competitive it is enough to show the following claim. Note
that in our construction we used $\alpha$-competitive non-adaptive mechanism
for the matroid $M$ and $2$-competitive non-adaptive mechanism for the uniform
matroid of rank $1$ on $P\setminus\\{x\\}$.

######  Claim 6.

$\gamma\frac{1}{\alpha}\textbf{EPROPH}_{M}+(1-\gamma)\frac{1}{2}\textbf{EPROPH}_{P\setminus\\{x\\}}\geqslant\frac{1}{2\alpha+2}\textbf{EPROPH}_{N}$

###### Proof.

Let us consider the inclusion-maximal set $I_{opt}$ on which the prophet
achieves $\textbf{PROPH}_{N}$. Let $C_{opt}$ be a random variable
corresponding to the unique circuit of $I_{opt}\cup\\{x\\}$ in $L$. Recall
that $x$ is not a free element of $L$ so such a circuit exists and is unique
and contains $x$.

First consider the events when $|C_{opt}|\geqslant 3$. Note that by definition
of a circuit, for every $y\in C_{opt}\setminus\\{x\\}$ the set
$(I_{opt}\cup\\{x\\})\setminus\\{y\\}$ is independent in $L$. Hence, for every
$y\in C_{opt}\setminus\\{x\\}$ the set $I_{opt}\setminus\\{y\\}$ is
independent in $M$. So we have that conditioned on $|C_{opt}|\geqslant 3$ we
have $\textbf{PROPH}_{M}\geq w(I_{opt}\setminus\\{y\\})$ for every $y\in
C_{opt}\setminus\\{x\\}$. Let $y_{opt}$ be the random variable representing
the element in $C_{opt}\setminus\\{x\\}$ of smallest value. Then conditioned
on $|C_{opt}|\geqslant 3$, we have $w(C_{opt}\setminus\\{y_{opt},x\\})\geq
w(C\setminus\\{x\\})/2$. Thus, conditioned on $|C_{opt}|\geqslant 3$ we have

$\displaystyle\textbf{PROPH}_{M}\geqslant
w(I_{opt}\setminus\\{y_{opt}\\})=w(I_{opt}\setminus
C_{opt})+w(C_{opt}\setminus\\{y_{opt}\\})$ $\displaystyle\geq
w(I_{opt}\setminus
C_{opt})+\frac{1}{2}w(C_{opt}\setminus\\{x\\})\geq\frac{1}{2}w(I_{opt})=\frac{1}{2}\textbf{PROPH}_{N}\,.$

Second consider the event that $|C_{opt}|<3$. Since $x$ is not a loop of $L$
by definition, we have $|C_{opt}|=2$ and so $C_{opt}=\\{x,x_{opt}\\}$ for some
random variable element $x_{opt}\in P\setminus\\{x\\}$. For the event
$|C_{opt}|\geq 3$ let us define the random variable element $x_{opt}$ to be an
arbitrary element in $C_{opt}\setminus\\{x\\}$. Thus, if $|C_{opt}|<3$ we have
$\textbf{PROPH}_{P\setminus\\{x\\}}\geq w(x_{opt})$. Now let us define
$J_{opt}:=I_{opt}\setminus\\{x_{opt}\\}$ and note that $J_{opt}$ is
independent in the matroid $M$. Moreover, since $I_{opt}$ is the set on which
the prophet achieves $\textbf{PROPH}_{N}$, we have that conditioned on
$|C_{opt}|<3$ the prophet achieves $\textbf{PROPH}_{M}$ on the set $J_{opt}$.

Combining everything together we have

$\displaystyle\gamma\frac{1}{\alpha}\textbf{EPROPH}_{M}+(1-\gamma)\frac{1}{2}\textbf{EPROPH}_{P\setminus\\{x\\}}=$
$\displaystyle\frac{1}{\alpha+1}\textbf{EPROPH}_{M}+\frac{1}{2\alpha+2}\textbf{EPROPH}_{P\setminus\\{x\\}}\geq$
$\displaystyle\qquad
E\left[\frac{w(x_{opt})}{2\alpha+2}+\frac{\textbf{PROPH}_{M}}{\alpha+1}\,\middle|\,|C_{opt}|<3\right]P\left[|C_{opt}|<3\right]$
$\displaystyle\qquad+E\left[\frac{\textbf{PROPH}_{M}}{\alpha+1}\,\middle|\,|C_{opt}|\geqslant
3\right]P\left[|C_{opt}|\geqslant 3\right]=$ $\displaystyle\qquad
E\left[\frac{w(x_{opt})}{2\alpha+2}+\frac{w(I_{opt}\setminus\\{x_{opt}\\})}{\alpha+1}\,\middle|\,|C_{opt}|<3\right]P\left[|C_{opt}|<3\right]$
$\displaystyle\qquad+E\left[\frac{\textbf{PROPH}_{M}}{\alpha+1}\,\middle|\,|C_{opt}|\geqslant
3\right]P\left[|C_{opt}|\geqslant 3\right]\geq$ $\displaystyle\qquad
E\left[\frac{\textbf{PROPH}_{N}}{2\alpha+2}\,\middle|\,|C_{opt}|<3\right]P\left[|C_{opt}|<3\right]$
$\displaystyle\qquad+E\left[\frac{\textbf{PROPH}_{M}}{\alpha+1}\,\middle|\,|C_{opt}|\geqslant
3\right]P\left[|C_{opt}|\geqslant
3\right]\geq\frac{1}{2\alpha+2}\textbf{EPROPH}_{N}\,.$

∎

∎

######  Lemma 10.

Let $N$ be a matroid obtained from a matroid $M$ by a sequence of $t$
projections. Let $L$ be the set of loops in the matroid $N$. Let there exist
an $\alpha$-competitive non-adaptive mechanism for the matroid $M$. Then there
exists a non-adaptive mechanism for $N{\setminus}L$ such that the expected
total value of this mechanism is at least $\frac{1}{\alpha\cdot
3^{t}}\textbf{EPROPH}_{M{\setminus}L}$.

In the context of Lemma 10, every set that is independent for the matroid
$N\setminus L$ is also independent for the matroid $M\setminus L$. Hence, we
have $\textbf{EPROPH}_{M\setminus L}\geq\textbf{EPROPH}_{N\setminus L}$. Thus
in case $t=1$, Lemma 10 leads us to the following corollary.

######  Corollary 3.

Let $N$ be a projection of the matroid $M$. If there is an
$\alpha$-competitive non-adaptive mechanism for $M$ then there exists a
$3\alpha$-competitive non-adaptive mechanism for $N$.

###### Proof of Lemma 10.

Let us prove the statement by induction. Of course, in case $t=0$ we have
$M=N$ and the statement is trivially true.

Let us now assume that $t$ is at least $1$. Let $N^{\prime}$ be a matroid such
that $N^{\prime}$ is obtained from the matroid $M$ by a sequence of $t-1$
projections and $N$ is a projection of $N^{\prime}$. Since $N$ is a projection
of $N^{\prime}$ there is a matroid $P=(E,\mathcal{S})$ and $x\in E$ such that
$P\setminus x=N^{\prime}$ and $P/x=N$. Let $L^{\prime}$ be the set of loops in
the matroid $N^{\prime}$.

By induction hypothesis, there exist thresholds $T^{\prime}_{e}$, $e\in
E\setminus(L^{\prime}\cup\\{x\\})$ such that the gambler with the matroid
$N^{\prime}{\setminus}L^{\prime}$ achieves at least $\frac{1}{\alpha\cdot
3^{t-1}}\textbf{EPROPH}_{M{\setminus}L^{\prime}}$ as the expected total value.
Let us assume that to compute thresholds $T^{\prime}_{e}$, $e\in
E\setminus(L^{\prime}\cup\\{x\\})$ the values of items in $L$ were set to be
$0$ while the distribution of values for other items remain the same. Since
$L^{\prime}\subseteq L$, analogously to Lemma 7 we can define thresholds

$T^{\prime\prime}_{e}:=\begin{cases}+\infty&\text{if }e\in L\\\
T^{\prime}_{e}&\text{otherwise}\end{cases}$

such that the gambler with the matroid $N^{\prime}{\setminus}L$ achieves at
least $\frac{1}{\alpha\cdot 3^{t-1}}\textbf{EPROPH}_{M{\setminus}L}$ as the
expected total value. Let $T^{\prime\prime\prime}_{e}$, $e\in
E\setminus(L\cup\\{x\\})$ be the thresholds guaranteeing $2$-competitive non-
adaptive mechanism as in Theorem 1 for the uniform matroid of rank $1$ on the
ground set $E\setminus(L\cup\\{x\\})$.

The constructed mechanism for the matroid $N\setminus L$ selects one of two
threshohold sets at random, where first set of thresholds
$T^{\prime\prime}_{e}$, $e\in E\setminus(L\cup\\{x\\})$ is selected with
probability $1/3$ and the thresholds $T^{\prime\prime\prime}_{e}$, $e\in
E\setminus(L\cup\\{x\\})$ with probability $2/3$. Note that the thresholds
$T^{\prime\prime}_{e}$, $e\in E\setminus(L\cup\\{x\\})$ were designed for the
matroid $N^{\prime}\setminus L$ but are used for the matroid $N\setminus L$;
hence less items might be selected than when it is used for
$N^{\prime}\setminus L$. Also note, that the thresholds
$T^{\prime\prime\prime}_{e}$, $e\in E\setminus(L\cup\\{x\\})$ are used for
$N\setminus L$ but were designed for the uniform matroid of rank $1$.

For the analysis, let $I_{alg}$ be the random variable indicating the items
set selected by the gambler with matroid $N^{\prime}\setminus L$ when the
thresholds $T^{\prime\prime}_{e}$, $e\in E\setminus(L\cup\\{x\\})$ are used.
Analogously to a claim in the proof of Lemma 9, we can assume that when the
thresholds $T^{\prime\prime}_{e}$, $e\in E\setminus(L\cup\\{x\\})$ are used
the gambler with $N\setminus L$ select all items in $I_{alg}$ with an
exception for possibly one item. Let $x_{opt}$ be the random variable
indicating the element of maximum value in $E\setminus(L\cup\\{x\\})$.

To finish the proof it is enough to show the following inequality

$\frac{1}{3}E[w(I_{alg})-w(x_{opt})]+\frac{2}{3}\frac{1}{2}E[w(x_{opt})]\geq\frac{1}{\alpha\cdot
3^{t}}\textbf{EPROPH}_{M{\setminus}L}\,.$

To obtain this inequality we can do estimations as follows

$\frac{1}{3}E[w(I_{alg})-w(x_{opt})]+\frac{2}{3}\frac{1}{2}E[w(x_{opt})]=\frac{1}{3}E[w(I_{alg})]\geq\frac{1}{3}\frac{1}{\alpha\cdot
3^{t-1}}\textbf{EPROPH}_{M{\setminus}L}\,.$

∎

Now let us combine Corollary 3 and Lemma 9.

######  Lemma 11.

Let $M$ and $N$ be matroids such that $\operatorname{dist}(M,N)\leq t$. If
there exists an $\alpha$-competitive non-adaptive mechanism for the matroid
$M$ with $\alpha\geq 2$ then there exists a $3^{t}\alpha$-competitive non-
adaptive mechanism for the matroid $N$.

###### Proof.

Note that for $\alpha\geq 2$ we have $3\alpha\geq 2\alpha+2$. Since $N$ can be
obtained from $M$ by a sequence of $t$ projection and lift steps, we can use
Corollary 3 or Lemma 9 for each of these steps to obtain the desired
competitiveness ratio. ∎

####  6.4.2 Minor-closed families theorem

######  Lemma 12 (Lemma 6 in [HN20]).

Let $p$ and $n$ be integers such that $p\leqslant n-2$ and $p$ is prime. The
matroid $U_{2,n}$ is not representable over the field $\mathbb{F}_{p}$.

The following Structural Hypothesis is due to Geelen, Gerards and Whittle. The
proof of this Structural Hypothesis has not appeared in print.

######  Hypothesis 1.

Let $p$ be a prime number and $\mathcal{M}$ is a proper minor-closed class of
matroids representable over $\mathbb{F}_{p}$.

Then there exist $k$, $n$, $t$ such that every $M\in\mathcal{M}$ is a
restriction of an $\mathbb{F}_{p}$-representable matroid $M^{\prime}$ having a
full tree-decomposition $(T,\mathcal{X})$ of thickness at most $k$ so that for
every $v\in V(T)$ if $M^{\prime}\mid_{\operatorname{cl}_{M^{\prime}}(X_{v})}$
has a $M(K_{n})$ minor, then there exists a $2$-column sparse matroid $N$ with
$\operatorname{dist}(M^{\prime}\mid_{\operatorname{cl}_{M^{\prime}}(X_{v})},N)\leqslant
t$.

###### Proof of Theorem 8.

Let $k$, $n$, $t$ are as stated in the Structural Hypothesis 1 on
$\mathcal{M}$.

Let $\mathcal{M}_{1}$ be the set of matroids on distance $t$ or less from some
$2$-column sparse matroid and are representable over $\mathbb{F}_{p}$. By
Theorem 4 all $2$-column sparse matroids have a $32$-competitive non-adaptive
mechanism. By Lemma 11 there exists a $(3^{t}\cdot 32)$-competitive mechanism
for matroids in $\mathcal{M}_{1}$.

Let $\mathcal{M}_{2}$ be the set of matroids without $M(K_{n})$ minor and are
representable over $\mathbb{F}_{p}$. By Lemma 12 all matroids in
$\mathcal{M}_{2}$ do not have $U_{2,p+2}$ as a minor. Then by Corollary 2, we
have that there is a $p^{p^{3n}}$-competitive non-adaptive mechanism for every
matroid in $\mathcal{M}_{2}$.

By the Structural Hypothesis 1 we have that every $M\in\mathcal{M}$ is a
restriction of some $M^{\prime}$ with a full tree-decomposition
$(T,\mathcal{X})$ of thickness at most $k$ so that for every $v\in V(T)$
$M^{\prime}\mid_{\operatorname{cl}_{M^{\prime}}(X_{v})}\in\mathcal{M}_{1}\cup\mathcal{M}_{2}$.

Thus by Theorem 13, matroid $M^{\prime}$ has a $\gamma:=(\max(3^{t}\cdot
32,p^{p^{3n}})\cdot p^{k+1})$-competitive non-adaptive mechanism. By Lemma 7
the matroid $M$ has also a $\gamma$-competitive non-adaptive mechanism.

∎

## References

  * [AKW19] Pablo D. Azar, Robert Kleinberg, and S. Matthew Weinberg.  Prior independent mechanisms via prophet inequalities with limited information.  Games and Economic Behavior, 118:511–532, 2019.
  * [CFPP21] Constantine Caramanis, Matthew Faw, Orestis Papadigenopoulos, and Emmanouil Pountourakis.  Single-sample prophet inequalities revisited.  ArXiv, abs/2103.13089, 2021.
  * [CGKM20] Shuchi Chawla, Kira Goldner, Anna R Karlin, and J Benjamin Miller.  Non-adaptive matroid prophet inequalities.  arXiv preprint arXiv:2011.09406, 2020.
  * [CHMS10] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In Proceedings of the forty-second ACM symposium on Theory of computing, pages 311–320, 2010.
  * [DK14] Michael Dinitz and Guy Kortsarz.  Matroid secretary for regular and decomposable matroids.  SIAM Journal on Computing, 43(5):1807–1830, 2014.
  * [DK15] Paul Dütting and Robert Kleinberg.  Polymatroid prophet inequalities.  In Algorithms-ESA 2015, pages 437–449. Springer, 2015.
  * [Edm65] Jack Edmonds.  Minimum partition of a matroid into independent subsets.  J. Res. Nat. Bur. Standards Sect. B, 69:67–72, 1965.
  * [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.
  * [FSZ21] Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes with applications to bayesian selection problems.  SIAM Journal on Computing, 50(2):255–300, 2021.
  * [Gee11] Jim Geelen.  Small cocircuits in matroids.  European Journal of Combinatorics, 32(6):795–801, 2011.
  * [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, pages 93–109, 2019.
  * [HN20] Tony Huynh and Peter Nelson.  The matroid secretary problem for minor-closed classes and random matroids.  SIAM Journal on Discrete Mathematics, 34(1):163–176, 2020.
  * [KS77] Ulrich Krengel and Louis Sucheston.  Semiamarts and finite values.  Bulletin of the American Mathematical Society, 83(4):745–747, 1977\.
  * [KW12] Robert Kleinberg and Seth Matthew Weinberg.  Matroid prophet inequalities.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 123–136, 2012.
  * [MTW16] Tengyu Ma, Bo Tang, and Yajun Wang.  The simulated greedy algorithm for several submodular matroid secretary problems.  Theory of Computing Systems, 58(4):681–706, 2016.
  * [Mye81] Roger B Myerson.  Optimal auction design.  Mathematics of operations research, 6(1):58–73, 1981.
  * [Oxl06] James G. Oxley.  Matroid Theory.  Oxford graduate texts in mathematics. Oxford University Press, 2006.
  * [SC84] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  the Annals of Probability, pages 1213–1216, 1984.
  * [Sch03] A. Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Number Bd. 1 in Algorithms and Combinatorics. Springer, 2003.
  * [Sey80] Paul D Seymour.  Decomposition of regular matroids.  Journal of combinatorial theory, Series B, 28(3):305–359, 1980\.
  * [Sot13] José A Soto.  Matroid secretary problem in the random-assignment model.  SIAM Journal on Computing, 42(1):178–211, 2013.