



\section{Introduction}
\label{sec:intro}
\input{intro}

\subsection{Our Techniques}
\label{sec:tech}
\input{techniques}

\input{related}



\section{Model and Preliminaries}
\label{sec:model}
\input{model}

\section{Secretary Matching with Vertex Arrival}
\input{vertex-arrival}

\section{Upper Bound for Vertex Arrival}
\input{vertex-lower}


\section{Secretary Matching with Edge Arrival}
\label{sec:edge_arrival}
\input{edge-arrival}




	\bibliographystyle{alpha}
	


\subsection{An Upper Bound for the Ordinal Setting}
\label{sec:upper-bound-ordinal}


In this section we study the ordinal setting. 
Based on the analysis of Section~\ref{sec:reduction}, we restrict ourselves, without loss of generality, to algorithms that decide at each step whether to match the top two vertices so far, and the decision depends only on the time $t$ and whether this matching is possible.
Such an algorithm can be fully characterized by a vector $\vec{c} \in [0,1]^n$, where $c_i$ is the probability that the algorithm matches the top two vertices so far at step $i$, given that it is possible to match them. 
	
Our main theorem in this section is an upper bound of $5/12$ on the competitive ratio of any algorithm in the ordinal setting.
\begin{theorem}
	\label{thm:ordinal-5-12}
	In the oridinal setting, for any $\vec{c} \in [0,1]^n$, the corresponding algorithm matches the top two vertices with probability at most $\frac{5}{12} + O(\frac{1}{n})$.
\end{theorem}
\begin{proof}
Let $v_i$ denote the vertex that arrives at time $i$, and let $\mathbbm{1}_i,\mathbbm{2}_i$ denote the respective top and second-top vertices among $v_1, \ldots, v_i$. 
Let $O_i$ be the event that $\mathbbm{1}_i$ remains unmatched by the end of step $i$, and let $p_i = \Prx{O_i}$, where the randomness is taken over the arrival order of the first $i$ vertices. 
Clearly, $p_1=1$. In what follows, ``$\matat{e}{t}$" denotes the event that edge $e$ is matched exactly at time $t$.
For $i>1$, we can express $p_i$ by the following recursive formula:  
\begin{align}
p_{i} = & \Prx{O_{i} \wedge (v_i = \mathbbm{1}_i) } + \Prx{O_{i} \wedge (v_i = \mathbbm{2}_i)} + \Prx{O_{i} \wedge (v_i \ne \mathbbm{1}_i,\mathbbm{2}_i)} \nonumber \\
= & \frac{1}{i} \cdot \Prx{O_{i} \big| v_i=\mathbbm{1}_i} + \frac{1}{i} \cdot \Prx{O_{i} \big| v_i = \mathbbm{2}_i} + \frac{i-2}{i} \cdot \Prx{O_{i} \big| v_i \ne \mathbbm{1}_i,\mathbbm{2}_i} \nonumber \\
= & \frac{1}{i} \cdot \Prx{\widebar{O_{i-1}} \vee \overline{\matat{v_i \mathbbm{1}_{i-1}}{i}} ~\big|~ v_i=\mathbbm{1}_i} + \frac{1}{i} \cdot \Prx{O_{i-1} \wedge \overline{\matat{v_i \mathbbm{1}_{i-1}}{i}}~ \big|~ v_i=\mathbbm{2}_i} \nonumber \\
& + \frac{i-2}{i} \cdot \Prx{O_{i-1}} \nonumber \\
= & \frac{1}{i} \cdot (1-p_{i-1}c_i) + \frac{1}{i} \cdot p_{i-1} (1-c_i) + \frac{i-2}{i} \cdot p_{i-1} \nonumber \\
= & \frac{1}{i} \cdot (1+(i-1)p_{i-1} - 2p_{i-1}c_i). \label{eq:pi}
\end{align}
The first equality follows by considering three disjoint cases for vertex $v_i$; the second equality holds since the distribution over the arrival order of $\{v_j\}_{j\in[i]}$ is uniform; to get the third equality we further consider cases where $\mathbbm{1}_i$ will be matched: (a) if $v_i$ is the top vertex so far, then it stays unmatched if either the $\mathbbm{2}_i=\mathbbm{1}_{i-1}$ is already matched, \emph{or} we don't match $v_i$ to $\mathbbm{1}_{i-1}$, (b) if $v_i$ is the second top vertex so far, then $\mathbbm{1}_i=\mathbbm{1}_{i-1}$ stays unmatched if it is unmatched at the step $i-1$ \emph{and} it is not matched to $v_i$ at step $i$, (c) if $v_i$ is ranked lower than $\mathbbm{1}_i,\mathbbm{2}_i$, then $\mathbbm{1}_i=\mathbbm{1}_{i-1}$ stays unmatched if it is unmatched at step $i-1$; to obtain the fourth equality, we use the fact that the probability $c_i$ of matching $\mathbbm{1}_i$ and $\mathbbm{2}_i$ (if it is possible) depends only on the time step $i$.

We next claim that the expected performance of the algorithm can be written as
\begin{equation}
	\label{eq:obj}
	\textsf{ALG}(\vec{c}) = \frac{1}{\binom{n}{2}} \sum_{i=2}^{n} (i-1) \cdot p_{i-1} \cdot c_i.
\end{equation}
To see this, note that
\begin{align}
\textsf{ALG}(\vec{c}) = & \sum_{i=2}^{n} \Prx{\{\mathbbm{1}_i,\mathbbm{2}_i \} = \{\mathbbm{1}_n,\mathbbm{2}_n\} \wedge v_i \in \{\mathbbm{1}_i, \mathbbm{2}_i\} \wedge O_{i-1} \wedge \matat{\mathbbm{1}_i \mathbbm{2}_i}{i} } \nonumber \\
= & \sum_{i=2}^n \Prx{\{\mathbbm{1}_i,\mathbbm{2}_i\} = \{\mathbbm{1}_n,\mathbbm{2}_n\}} \cdot \frac{2}{i} \cdot p_{i-1} \cdot c_i \nonumber \\
= & \sum_{i=2}^{n} \frac{\binom{n-2}{i-2}}{\binom{n}{i}} \cdot \frac{2}{i} \cdot p_{i-1} \cdot c_i \nonumber \\
= & \frac{1}{\binom{n}{2}} \sum_{i=2}^{n} (i-1) \cdot p_{i-1} \cdot c_i, \nonumber
\end{align}
where the first equality follows from the law of total probability; the second equality follows from the following facts:
1) conditioned on $\{\mathbbm{1}_i,\mathbbm{2}_{i}\} = \{\mathbbm{1}_n,\mathbbm{2}_n\}$, the arrival order of $v_1, \ldots, v_i$ is chosen uniformly at random,
2) the events $v_i \in \{\mathbbm{1}_i,\mathbbm{2}_i\}$ and $O_{i-1}$ are independent,
3) our algorithm matches $\mathbbm{1}_i\mathbbm{2}_{i}$ with probability $c_i$ when possible, i.e., when $v_i \in \{\mathbbm{1}_i, \mathbbm{2}_i\}$ and $\mathbbm{1}_{i-1}$ is unmatched.


For notation simplicity, let $q_i = i p_i$ for $i \in [n]$.
By equations~\eqref{eq:pi} and \eqref{eq:obj}, in order to find the optima$\vec{c} \in [0,1]^n$, it suffices to find the maximum of the following function\footnote{$f$ does not depend on $c_1$.} on $\vec{c} \in [0,1]^n$:
\begin{equation}
\label{eq:qi-recursive}
f(\vec{c},\vec{q}) \overset{\mathrm{def}}{=\mathrel{\mkern-3mu}=} \sum_{i=2}^n q_{i-1} c_i
\quad\quad\text{where } q_i = 1+ \left(1-\frac{2c_i}{i-1}\right) \cdot q_{i-1}, \text{ and }q_1 = 1
\end{equation}
We calculate the derivative of $f(\vec{c},\vec{q}(\vec{c}))$ over $c_i$ (note that $\vec{q}$ also depends on $\vec{c}$).
\begin{align*}
\frac{df}{dc_i} = & q_{i-1} + \sum_{j=i+1}^{n} c_j \cdot \frac{dq_{j-1}}{d c_i} & \mbox{($q_j$ does not depend on $c_i$ for $j < i$)}\\
= & q_{i-1} + \sum_{j=i+1}^{n} c_j \cdot \frac{dq_{j-1}}{dq_{j-2}} \cdot \frac{dq_{j-2}}{dq_{j-3}} \cdots \frac{dq_{i}}{dc_i} & \mbox{(by the chain rule)}\\
= & q_{i-1} + \sum_{j=i+1}^{n} c_j \cdot \prod_{k=i+1}^{j-1} \left( 1-\frac{2c_k}{k-1} \right) \cdot \left( -\frac{2q_{i-1}}{i-1} \right) & \mbox{(by the recursive formula of $q_j$, see Equation~\eqref{eq:qi-recursive})}\\
= & q_{i-1} \cdot \left( 1 - \frac{2}{i-1} \cdot \sum_{j=i+1}^{n}c_j \prod_{k=i+1}^{j-1} \left( 1- \frac{2c_{k}}{k-1} \right) \right).
\end{align*}
Notice that $\frac{df}{dc_i}$ does not depend on $c_i$, i.e., f is a linear function of $c_i$. In particular, it means that the maximum of $f(\vec{c})$ on $\vec{c}\in[0,1]^n$ is achieved at either $c_i=0$, or $c_i=1$ depending on the sign of $\frac{df}{dc_i}$. Note that the maximum of $f$ must be attained by some $\vec{c}$, since $[0,1]^n$ is a compact space and $f$ is a continuous function. Moreover, we observe the following ``monotonicity'' property of the derivatives $\frac{df}{dc_i}$.
\begin{claim}
	\label{cl:derivative}
Let $i\ge 3$. If $\frac{df}{dc_i} \le 0$, then $\frac{df}{dc_{i-1}} < 0$.
\end{claim}
\begin{proof}
Let $x_{i-1} = \sum_{j=i}^{n}c_j \prod_{k=i}^{j-1} \left( 1- \frac{2c_{k}}{k-1} \right)$ and $x_i = \sum_{j=i+1}^{n} c_j\prod_{k=i+1}^{j-1} \left( 1- \frac{2c_{k}}{k-1} \right)$. Thus $x_{i-1} = x_i \cdot \left(1-\frac{2c_i}{i-1}\right) + c_i$.
Then, $\frac{df}{dc_i} \le 0$ iff $1-\frac{2x_i}{i-1}\le 0$ iff $x_i \ge \frac{i-1}{2}$. 

We get:
\begin{multline*}
x_{i-1} = x_i \cdot \left(1-\frac{2c_i}{i-1}\right) + c_i =
x_i + c_i\cdot\left(1-\frac{2x_i}{i-1} \right)
\ge
x_i + 1\cdot \left(1-\frac{2x_i}{i-1} \right)\\
=
x_i\cdot\frac{i-3}{i-1}+1
\ge\frac{i-1}{2}\cdot\frac{i-3}{i-1}+1
=\frac{i-1}{2}>\frac{i-2}{2}.
\end{multline*}
Consequently $\frac{df}{dc_{i-1}} < 0$.
\end{proof}

Let $\vec{c}\in[0,1]^n$ be the vector at which $f(\vec{c})$ attains its maximum. 
Let $\ell$ be the largest index $i\in[n]$ such that $\frac{df}{dc_{i}}\le 0$. Then, $\frac{df}{dc_{i}}> 0$ for all $i>\ell$, and 
by Claim~\ref{cl:derivative}, $\frac{df}{dc_{i}}< 0$ for all $i<\ell$. 
Since $f$ attains its maximum at $\vec{c}$, it must be that $c_i=1$ for all $i>\ell$ and $c_i=0$ for all $i<\ell$. 
We can also assume without loss of generality that $c_{\ell}=0$, as 
$\frac{df}{dc_{\ell}}\le 0$ (if $\frac{df}{dc_{\ell}}= 0$, then $f$ does not depend on $c_{\ell}$). 
We conclude that $c_i=0$ for all $i \leq \ell$ and $c_i=1$ for $i>\ell$.
In other words, the algorithm is deterministic: it matches no vertices up to step $\ell$, and thereafter matches the top two vertices so far whenever possible.





Next, we calculate the value of $q_i$ for all $i$.
\begin{itemize}
	\item For $i \le \ell$, $c_i=0$, and we get $q_i=1+q_{i-1}\cdot(1-\frac{2\cdot c_i}{i-1})=1+q_{i-1}$. Thus, $q_i=i$.
	\item For 
 $i > \ell$, $c_i=1$, and we get $q_{i} = 1+q_{i-1}\cdot(1-\frac{2\cdot c_i}{i-1})=1 + \frac{i-3}{i-1} \cdot q_{i-1}$.
 Multiplying the last equality by $(i-1)(i-2)$ gives
\begin{equation}
\label{eq:diff1}
	(i-1)(i-2)q_{i} - (i-2)(i-3) q_{i-1} = (i-1)(i-2). 
\end{equation}
Summing the LHS of \eqref{eq:diff1} over $j=\ell+1,\ldots,i$ (with $j$ in the role of $i$) gives $(i-1)(i-2)q_{i} - \ell (\ell-1)(\ell-2)$ due to telescopic sum.
Summing the RHS of \eqref{eq:diff1} over $j=\ell+1,\ldots,i$ (with $j$ in the role of $i$) gives $\sum_{j=\ell+1}^{i} (j-1)(j-2) = \frac{i(i-1)(i-2)}{3}-\frac{\ell(\ell-1)(\ell-2)}{3}$.
We get that
$q_i = \frac{i}{3} + \frac{2\ell (\ell-1)(\ell-2)}{3(i-1)(i-2)}$.
\end{itemize}
 

We are now ready to calculate the performance of the algorithm. Using Equation~\eqref{eq:obj}, the fact that $c_i=0$ for all $i\leq \ell$ and $c_i=1$ for all $i>\ell$, and the values of $q_i$ as calculated above gives
\begin{align*}
\binom{n}{2}\cdot \textsf{ALG} = & \sum_{i=2}^{n} q_{i-1}c_i = \sum_{i=\ell}^{n-1} q_i = \sum_{i=\ell}^{n-1} \left( \frac{i}{3} + \frac{2\ell(\ell-1)(\ell-2)}{3(i-1)(i-2)} \right) \\
=& \frac{ \sum_{i=1}^{n-1} i -\sum_{i=1}^{\ell-1} i}{3} +
 \frac{2\ell(\ell-1)(\ell-2)}{3} \sum_{i=\ell}^{n-1}\left[\frac{1}{i-2}-\frac{1}{i-1}\right] \\
= & \frac{n^2-n-\ell^2+\ell}{6} + \frac{2}{3}\ell(\ell-1)(\ell-2)\left(\frac{1}{\ell-2} - \frac{1}{n-2}\right) \\
= & \frac{n^2}{6}+ \frac{\ell^2}{2} - \frac{2\ell^3}{3n}+\left[\frac{\ell-n}{6}-\frac{2\ell}{3}+\frac{2(3\ell^2-2\ell)}{3n}-\frac{4\ell(\ell-1)(\ell-2)}{3n(n-2)} \right]\\
= & n^2 \cdot\left(\frac{1}{6}+\frac{\ell^2}{2n^2} - \frac{2\ell^3}{3n^3} + O\left(\frac{1}{n}\right) \right)
\le \frac{5}{24} n^2 +O(n),
\end{align*}
where the  last equality holds since $0<\ell\le n$; and the last inequality holds since the cubic function
$g(x)\overset{\mathrm{def}}{=\mathrel{\mkern-3mu}=} \frac{1}{6}+\frac{x^2}{2} -\frac{2x^3}{3}$ with $x=\frac{\ell}{n}$ attains its maximum on the interval $x\in[0,1]$ at $x=0.5$, where the maximum value is $\frac{5}{24}$.
Therefore, $\textsf{ALG} \le \frac{5}{12} + O(\frac{1}{n})$, concluding the proof of Theorem~\ref{thm:ordinal-5-12}.
\end{proof}




\subsection{Reduction: From Cardinal to Ordinal (through Intermediate)}
\label{sec:reduction}






We shall focus on the following family of instances. An instance is described by a complete graph $G$ on $n$ vertices. Each vertex $v$ of the graph is associated with a value $\lambda_v \in {\mathbb N}$, where ${\mathbb N}$ is the set of positive integers. The weight of each edge $uv$ is determined by the values of the two endpoints:  $w_{uv} = n^{3(i+j)}$ where $i=\lambda_u, j=\lambda_v$ are the values of its two endpoints.
We assume that $\lambda_u \neq \lambda_v$ for every two distinct vertices $u,v$. Thus, every instance can be specified by a set of values $\Lambda \subset {\mathbb N}$ of size $n=|\Lambda|$ on the graph vertices. Let $\subsets{n}$ denote the set of all such subsets $\Lambda$ and in general $\subsets[T]{i}$ denote the set of all subsets $\Lambda\subset T$ with $|\Lambda|=i$.
Without loss of generality, we assume that the algorithm observes the vertex values directly, rather than the edge weights. 
When clear in the context we refer to $ij$ as the edge between vertices with values $i$ and $j$, and denote the weight of this edge by $w_{ij}$.

The reduction from the cardinal setting to the ordinal setting proceeds in three main steps; an overview is given in Figure~\ref{fig:proof-overview}.
In what follows, we give details for each step. 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth]{proof-overview.png}
	\caption{An overview of the proof steps. 
		\label{fig:proof-overview}}
\end{figure}

\paragraph{Step 1: Introducing the intermediate variant, and reducing the cardinal variant to the intermediate variant.}
The {\em intermediate} variant of the matching problem bridges between the cardinal and ordinal variants.
In the intermediate variant, every vertex $v$ is associated with value $\lambda_v$, which is observed upon $v$'s arrival (as in the cardinal settings), but the objective is to maximize the probability to match together the two vertices with the highest values (similar to the ordinal setting). 
The following lemma reduces the cardinal variant of the problem to the intermediate variant.

\begin{lemma}
\label{lem:obj_ordinal}
Let  $\Lambda\in \subsets{n}$. If $\textsf{ALG}(\Lambda) \ge \alpha \cdot \textsf{OPT}(\Lambda)$ in the cardinal setting, then $\textsf{ALG}$ matches the top two vertices in $\Lambda$ with probability $\alpha - O(\frac{1}{n})$.
\end{lemma}
\begin{proof}
Let $i_1, i_2$ be the two largest values of $\Lambda$. 
Consider the performance of the algorithm.
\begin{align}
\textsf{ALG}(\Lambda) = & \sum_{ \{i,j\} \in {\Lambda \choose 2}} \Prx{ij \text{ is selected}} \cdot \lambda_{i j} \nonumber \\
\le & \Prx{i_1i_2 \text{ is selected}} \cdot \lambda_{i_1 i_2} + \sum_{ \{i,j\} \in {\Lambda \choose 2}-\{i_1,i_2\}} \lambda_{i j} \nonumber \\
\le & \Prx{i_1i_2 \text{ is selected}} \cdot \lambda_{i_1 i_2} + \left({n \choose 2} - 1\right) \cdot \frac{\lambda_{i_1 i_2}}{n^3} \nonumber \\
= & \left( \Prx{i_1i_2 \text{ is selected}} + O\left(\frac{1}{n}\right) \right) \cdot \lambda_{i_1 i_2}, \label{eq:exp2prob}
\end{align}
where the second inequality follows from the fact that for every $i,j$, $w_{ij} = n^{3(i+j)} \le n^{3(i_1+i_2)-3} = \frac{\lambda_{i_1 i_2}}{n^3}$.

Finally, we have that $\textsf{ALG}(\Lambda) \ge \alpha \cdot \textsf{OPT}(\Lambda) \ge \alpha \cdot \lambda_{i_1 i_2}$. Combining this with equation~\eqref{eq:exp2prob} concludes the proof.
\end{proof}

Lemma~\ref{lem:obj_ordinal} reduces the cardinal setting to the intermediate setting. 
As such, it allows to change the objective in the cardinal setting to the objective in the ordinal setting. 
Note, however, that changing only the objective is not sufficient, as the online algorithm in the ordinal setting does not observe the values of the vertices, rather it observes only the relative ranking among them. 
In the following steps we reduce the intermediate variant to the ordinal variant.

\paragraph{Step 2: Simplifying the description of the algorithm for the intermediate variant.}
We now show that any $\alpha$-competitive online algorithm for the intermediate variant admits a simplified description. 
Claim~\ref{cl:only_top_two} shows that the algorithm's decision at each step $t$ is simply a binary decision, and 
Claim~\ref{cl:history_independent} shows that this decision is history independent.

\begin{claim}
\label{cl:only_top_two}
Let $\textsf{ALG}$ be any $\alpha$-competitive online algorithm in the intermediate setting. 
Then, there is an $\alpha$-competitive algorithm $\textsf{ALG}'$ that in every step $t$, may (but not necessarily) only match the top two vertices up to step $t$.
\end{claim}
\begin{proof}
Suppose that at some step $t$, $\textsf{ALG}$ matches two vertices $u$ and $v$ which are not the top two vertices up to step $t$. Consider a modified algorithm $\textsf{ALG}'$ that in such cases does not match any vertices, and proceeds as $\textsf{ALG}$ thereafter as if $u$ and $v$ were matched. Then $\textsf{ALG}'(\Lambda)=\textsf{ALG}(\Lambda)$ for any set of values $\Lambda$.
\end{proof}

Thus, the algorithm's decision at time $t$ is just a choice between (at most) two options: match the top two vertices so far, or not match them. However, such decision may still be quite complex: it may be randomized, it may depend on the values of the available vertices, on the arrival order, or on the previous choices of the algorithm. Our next claim simplifies the algorithm further. It shows that an optimal online algorithm is \emph{history-independent}, i.e., the decision depends only on the vertex values and on whether matching the top two vertices is possible. 

\begin{claim}
\label{cl:history_independent}
Given set of vertex values $\Lambda_t$ at time $t$, 
we may assume without loss of generality that the algorithm's binary decision depends only on
\begin{enumerate}
\item whether the top two vertices in $\Lambda_t$ are not matched yet; and
\item whether the last arriving vertex is one of the top two vertices in $\Lambda_t$. 
\footnote{Interestingly, it does not matter whether the last arriving vertex is the highest or second-highest, only whether it is one of the top two vertices.}
\end{enumerate}
\end{claim}

\begin{proof}
To be formal, let us denote 
the arrival order of the vertices in $\Lambda_t$ and prior decisions of the algorithm as a history $H(t,\Lambda_t)$. Consider any optimal online algorithm $\textsf{ALG}$. We are going to modify $\textsf{ALG}$ so that it becomes \emph{history-independent} at time $t$ with the same performance guarantee.

Fix the set of values $\Lambda_t$. We consider the set $\mathcal{DH}(t, \Lambda_t)$ of all histories $H(t,\Lambda_t)$ for which the online algorithm has an option to match the two vertices with the highest values in $\Lambda_t$, i.e., situations that satisfy both conditions 1 and 2 from the statement of the Claim~\ref{cl:history_independent}. Let us define an online algorithm $\textsf{ALG}'$ that for every observed history $H(t,\Lambda_t)\in\mathcal{DH}(t,\Lambda_t)$ forgets the real history and instead generates a contrafactual history $H'(t,\Lambda_t)$ drawn independently at random from $\mathcal{DH}(t, \Lambda_t)$, i.e., we generate a history $H'\in \mathcal{DH}(t, \Lambda_t)$ with the probability proportional to $\Prx{H(t, \Lambda_t) = H' ~~|~~ \Lambda_t}$. We keep $\textsf{ALG}'$ unchanged for any other set of values $\Lambda_t$ or history $H\notin\mathcal{DH}(t, \Lambda_t)$.
Starting from time $t$ the algorithm $\textsf{ALG}'$ assumes that the real history was $H'$ (not $H$) and makes all its future decisions according to $H'$. Note that by Claim~\ref{cl:only_top_two} $\textsf{ALG}'$ would be a feasible algorithm. The performance of $\textsf{ALG}'(H ~|~\Lambda_t)=\textsf{ALG}(H' ~|~\Lambda_t)$, since all previous decisions of $\textsf{ALG}$ before time $t$ did not affect the two highest value vertices in $\Lambda_t$ and, therefore, did not affect the two highest value vertices in $\Lambda$. Furthermore, the distribution of the contrafactual histories $H'$ coincides by construction with the distribution of the actual histories $H\in\mathcal{DH}(t, \Lambda_t)$. Thus the expected performance of $\textsf{ALG}'$ is the same as $\textsf{ALG}$. Note that $\textsf{ALG}'$ is history independent for the given set of values $\Lambda_t$.

To conclude the proof, we need to apply the above transformation of an optimal algorithm $\textsf{ALG}$ for every possible set of values $\Lambda_t$ and every time $t\in [n]$. That can be easily done using, e.g., a backward induction on $n$.
\end{proof}

By Claims~\ref{cl:only_top_two} and~\ref{cl:history_independent} we may restrict our attention to history-independent, binary-decision online algorithms. Any such algorithm can be characterized by a collection of $n$ set functions  $f_i : \subsets{i} \to [0,1]$ for each $i\in[n]$, where for every $\Lambda_i\in\subsets{i}$, $f_i(\Lambda_i)$ denotes the probability that the algorithm matches the top two vertices in $\Lambda_i$ given that it is {\em possible}; i.e., that (i) one of these vertices arrives at time $i$, and (ii) both of them are unmatched. 

\paragraph{Step 3: Reducing the intermediate variant to the ordinal variant.}
To complete the reduction from the intermediate setting to the ordinal setting, we use a similar approach to the upper bound proof from \citet{CorreaDFS19}. We fix an $\alpha$-competitive online algorithm $\textsf{ALG}$ for the intermediate variant, which is represented by a set of functions $f_i$ for every $i\in [n]$.

Our goal is to find an infinite (or sufficiently large) subset $T \subseteq {\mathbb N}$ of values on which the algorithm's decisions do not depend on the actual values of the vertices, i.e., every function $f_i$ is a constant on each $\Lambda_i\in\subsets[T]{i}$. In this case $\textsf{ALG}$ does not use any information about the actual values for every set of values $\Lambda\subset T$ with $|\Lambda|\le n$. That is, we can use $\textsf{ALG}$ in the ordinal setting.
We achieve this goal within an arbitrary small additive error $\varepsilon$, i.e., $f_i(\Lambda_i)=c_i \pm O(\varepsilon)$ for every $i\in [n]$, and every $\Lambda_i\in\subsets[T]{i}$. 

\begin{claim}
\label{cl:ramsey}
For any collection of set functions $f_i:\subsets{i}\to [0,1]$, $i\in[n]$ and any $\varepsilon>0$ there is an infinite set $T\subset{\mathbb N}$ and constants $c_1,\ldots,c_n\in[0,1]$, s.t. $f_i(\Lambda_i)=c_i+O(\varepsilon)$ for all $\Lambda_i\in\subsets[T]{i}$, $i\in[n]$.
\end{claim}
\begin{proof}
The proof uses the infinite version of Ramsey theorem. We find such a set $T$ iteratively for $i\in[k]$, starting with $k=1$ and up to $k=n$. We proceed by induction on $k$. The base of the induction is the case of $k=0$, which holds trivially. 
Suppose, by the induction hypothesis, that we have an infinite set $T_{k}\subset {\mathbb N}$ and a set of constants $c_1,\ldots,c_k$ such that
$f_i(\Lambda_i)=c_i+O(\varepsilon)$ for all $\Lambda_i\in\subsets[T_k]{i}$ and $i\in[k]$. Our goal is to find an infinite subset $T_{k+1}\subset T_k$
that satisfies the desired condition for $f_{k+1}$. Consider a complete hyper-graph on the set of vertices $T_k$ with hyper-edges of size $k+1$. Each edge $\Lambda\subset T_k$,  $|\Lambda|=k+1$, is colored in one of $1/\varepsilon$ colors: assign color $\left\lfloor f_{k+1}(\Lambda)/ \varepsilon\right\rfloor$ to the edge $\Lambda$. By the infinite version of Ramsey theorem \cite{ramsey2009problem}
, this hyper-graph admits an infinite monochromatic clique. Let the color of such a clique be $C_{k+1}$, and let the set of vertices in the clique be $T_{k+1}\subset T_k$. Set the constant $c_{k+1}=\varepsilon\cdot C_{k+1}$. Then  $c_{k+1}\le f_{k+1}(\Lambda) < c_{k+1}+\varepsilon$ for any $\Lambda\in\subsets[T_{k+1}]{k+1}$, i.e., $f_{k+1}(\Lambda)=c_{k+1}+O(\varepsilon)$ for any $\Lambda\subset T_{k+1}$, $|\Lambda|=k+1$.
\end{proof}

With this, we can conclude the reduction from the cardinal setting to the ordinal setting. 
As a bonus, we also reveal useful properties of an optimal algorithm in the ordinal setting.

\begin{theorem}
\label{th:reduction_ordinal}
Let $\textsf{ALG}$ be an $\alpha$-competitive online algorithm for the cardinal matching setting. 
Then, there is a $\alpha-O(\frac{1}{n})$-competitive online randomized algorithm $\textsf{ALG}^o$ for the ordinal setting. 
Moreover, in every time $t$, $\textsf{ALG}^o$ makes a binary decision on whether to match the two top vertices up to time $t$, and this decision may only depend on the time $t$ and on whether this matching is possible.
\end{theorem}
\begin{proof}
We use Lemma~\ref{lem:obj_ordinal} to convert $\textsf{ALG}$ into an $\alpha-O(\frac{1}{n})$-competitive algorithm $\textsf{ALG}^{\text{int}}$ for the intermediate setting. By Claims~\ref{cl:only_top_two} and~\ref{cl:history_independent} we can assume without loss of generality that $\textsf{ALG}^{\text{int}}$ makes decisions that depend only on the set of values $\Lambda_t$ at time $t$ and the possibility of matching the top two vertices in $\Lambda_t$. Finally, we can choose $\varepsilon$ in Claim~\ref{cl:ramsey} to be $\varepsilon=O(\frac{1}{n^2})$ and find set $T\subset {\mathbb N}$ such that $f_i(\Lambda_i)=c_i+O(\varepsilon)$ for every $\Lambda_i\in\subsets[T]{i}$ and $i\in[n]$. 
Define the algorithm $\textsf{ALG}^o$ for the ordinal setting as follows: 
Upon the arrival of the $i$th vertex, match the two top vertices up to time $i$ with probability $c_i$, if this is possible. 
By the union bound,for every set $\Lambda\in\subsets[T]{n}$, $\textsf{ALG}^o(\Lambda)=\textsf{ALG}^{\text{int}}(\Lambda)+n\cdot O(\varepsilon)=\textsf{ALG}^{\text{int}}(\Lambda)+O(\frac{1}{n})$ for every set. 
Thus, $\textsf{ALG}^o$ is an $\alpha-O(\frac{1}{n})$-competitive online algorithm for the ordinal setting, whose binary decisions depend only on the time $t$ and the possibility of matching the two top vertices in $\Lambda_t$ at time $t$.
This concludes the proof
\end{proof}




\subsection{Related work}

The 1-sided secretary matching problem studied by \citet{KorulaP09} is a generalization of the matroid secretary problem on transversal matroids, which was first introduced by \citet{BabaioffIKK18}. They designed constant competitive algorithms for graphs with bounded degrees, and \citet{DimitrovP12} generalized this result to arbitrary graphs. These results affirmatively answer the famous matroid secretary conjecture by \citet{BabaioffIKK18} for transversal matroids. Whether $\Omega(1)$-competitive algorithms exist for the secretary problem on general matroids remains an intriguing question. Currently, the best known ratio is $\Omega(1/\log \log \text{rank})$ \citet{Lachish14} and \citet{FeldmanSZ18}. 

The $1/e$-competitive algorithm by \citet{KesselheimRTV13} for 1-sided secretary matching is further extended to a truthful mechanism that attains the same competitive ratio by \citet{Reiffenhauser19}. \citet{KorulaP09} also studied the secretary matching on hypergraphs and proposed $\Omega(1/d^2)$-competitive algorithms for $d$-hypergraphs\footnote{A $d$-hypergraph is a hypergraph such that all its hyperedges have size at most $d$.}. This result is improved to $\Omega(1/d)$-competitive by \citet{KesselheimRTV13}. 

Another line of work considers the secretary problem in the ordinal setting. That is, the algorithm is restricted to do pairwise comparisons between elements, without knowing the exact values of their weights. \citet{HoeferK17} designed constant competitive algorithms for several families of constraints, including matching, packing LPs and independent set with bounded local independence number. Specifically, they studied the same vertex-arrival model for general graphs as our model and designed an $\frac{e+1}{12e}$-competitive algorithm that only uses ordinal information. \citet{SotoTV18} studied the ordinal matroid secretary problem and achieved improved competitive ratios for transversal matroids, matching matroids, laminar matroids, etc.

The general vertex arrival model adopted in this paper is first introduced by \citet{WangW15} in the online matching literature, where the focus is to select maximum size matching under adversarial vertex arrivals. This model is a natural generalization of the 1-sided online bipartite matching model by \citet{KarpVV90}. \citet{WangW15} designed a $0.526$-competitive algorithm for the fractional version of the problem. \citet{GamlathKMSW19} proposed a $1/2+\Omega(1)$-competitive algorithm for the integral version of the problem. They also proved that no algorithm has a competitive ratio larger than $1/2$ in the edge arrival setting. Motivated by online ride-sharing, there has been a growing interest in online matching in the past few years and other extensions of the 1-sided online bipartite matching model have been studied, including fully online matching~\cite{HuangPTTWZ19, HuangKTWZZ20, HuangTWZ20} and edge-weighted online windowed matching~\cite{AshlagiBDJSS19}.

The matching prophet problem with edge arrivals is first studied by \citet{KleinbergW19} under the more general framework of matroid intersections. \citet{GravinW19} explicitly studied the bipartite matching setting and designed a threshold-based $\frac{1}{3}$-competitive algorithm. They also showed an upper bound of $\frac{4}{9}$. The upper bound was improved to $\frac{3}{7}$ in \cite{Tristanthesis}.
\citet{EzraFGT20} designed an improved $0.337$-competitive algorithm for general graphs.




\subsection{The Ordinal Variant}
\label{sec:ordinal}

The {\em ordinal} variant of the matching problem is the following:
	\begin{itemize}
		\item A set of $n$ vertices are ranked, according to an unknown ranking, from 1st to $n$th. The 1st and 2nd vertices are referred to as the top two vertices.
		\item The vertices arrive sequentially, in a random order; let $v_1, \ldots, v_n$ denote the vertices in their arrival order.
		\item Upon the arrival of vertex $v_t$, the algorithm observes the relative rank of $v_t$ among $v_1, \ldots, v_t$ (its rank is in $\{1, \ldots, t\}$), and must decide immediately and irrevocably whether to match it to an earlier unmatched vertex.
		\item The objective is to maximize the probability of matching together the top two vertices. 
	\end{itemize}


In the remainder of this section, we refer to our original matching secretary setting as the \emph{cardinal} setting, and to this variant as the \emph{ordinal} setting. 
Note that the two settings differ both in (i) the assumption about what is observable (a vertex's weight in the cardinal setting versus its relative rank in the ordinal setting), and in (ii) the objective function (maximize the expected total weight in the cardinal setting versus maximize the probability to match the top two vertices in the ordinal setting). 
The reduction will go through a third variant, which we refer to as the {\em intermediate} setting, which shares properties with both variants, as will be explained in Section~\ref{sec:reduction}.

An algorithm in the ordinal and intermediate settings is said to be $\alpha$-competitive if it matches together the top two vertices with probability at least $\alpha$.


\paragraph{Ordinal vs. Cardinal Classical Secretary}
It is worthwhile to mention that the classical secretary problem has two variants as well: (i) the ordinal secretary problem, where the algorithm observes the relative rank of the arriving element, and aims to maximize the probability of selecting the best element, and (ii) the cardinal secretary problem, where each element is associated with a value, which is observed upon arrival, and the algorithm aims to maximize the expectd value of the selected element.

It is straightforward to see that any algorithm in the ordinal setting preserves its competitive ratio when applied to the cardinal setting. 
On the other direction, a folklore result says that the cardinal setting is not easier than the ordinal one (recall that the best competitive ratios in both settings is $\frac{1}{e}$). The upper bound for the cardinal setting is nicely explained in the recent work of \citet{CorreaDFS19}.

Our ordinal and cardinal variants for matching can be viewed as analogs of the cardinal and ordinal settings in the classic secretary problem. 
However, the matching setting is more involved in its combinatorial structure, and the multiple decisions that should be made. 
Indeed, it is not clear to us whether it is possible to adapt an algorithm for the ordinal setting to the cardinal matching setting (like in the classical secretary problem).
Nevertheless, we establish a reduction from the cardinal setting to the ordinal setting. 





\input{reduction}

\input{ordinal}



