\section{Introduction}
Image captioning is an active research area due to the large number of applications where it can be used. It provides a gateway for scene understanding where the task is not just object recognition but also to capture the relations between the objects present in the image. Convolutional Neural Networks (CNNs) are known to perform well for feature extraction in images. Long Short Term Memory Networks (LSTMs) as variant of Recurrent Neural Networks (RNNs) have shown great potential in natural language modeling and text generation tasks. The idea to combine the two into an encoder-decoder architecture for image generation was first proposed by \cite{DBLP:journals/corr/VinyalsTBE14,7298932} in which the pre-trained CNN was used to extract the latent features of an image and represent it in a reduced form which are then fed to a modified RNN coupled with the word embedding inputs and history of the RNN to generate sequence of words, i.e., caption for the image. The extension of this work \cite{xu2015show} introduced a visual attention network along with the encoder-decoder framework. The intuition was that while captioning an image, rather than looking at the complete image at once, one can  look over different regions at each time step to caption it. The objective of attention network was to provide an attention map for the image pixels at each time step of caption generation which allowed the model to look into specific regions of the image while captioning.

We further extend the architecture mentioned above by using beam search \cite{zhou2018tree} at the time of caption generation. It helps in finding the most optimal caption that can be generated by the model instead of greedily choosing the word with best score at each decoding step. Though beam search has been previously used for image captioning \cite{ma2019image}, we show that using this simple heuristic search along with better training schemes such as teacher forcing gives better scores for different evaluation metrics such as BLEU-1,2,3,4, METEOR, CIDEr and ROUGE-L.

\noindent\shadowbox{\begin{minipage}[t]{.95\columnwidth}
Our code and dataset available at \url{https://bit.ly/2kUU4g8} and a demo video is available at \url{https://youtu.be/bO4bvjYyvQE}. A graphical user interface is also created to consume the trained model (see supplementary).
\end{minipage}}

\begin{table*}[t]
\centering
\resizebox{0.90\textwidth}{!}
{
\begin{tabular}{cc|ccccccc|}
\cline{3-9}
 & \multicolumn{1}{c|}{} & \multicolumn{7}{c|}{\textbf{Evaluation metric}} \\ \hline
\multicolumn{1}{|c|}{\textbf{Dataset}} & \multicolumn{1}{c|}{\textbf{Model}} & \multicolumn{1}{c|}{\textbf{BLEU-1}} & \multicolumn{1}{c|}{\textbf{BLEU-2}} & \multicolumn{1}{c|}{\textbf{BLEU-3}} & \multicolumn{1}{c|}{\textbf{BLEU-4}} & \multicolumn{1}{c|}{\textbf{METEOR}} & \multicolumn{1}{c|}{\textbf{CIDEr}} & \multicolumn{1}{c|}{\textbf{ROUGE-L}} \\ \hline
\multicolumn{1}{|c|}{\multirow{5}{1in}{Flickr8k \\ \cite{hodosh2013framing}}} &\citeauthor{DBLP:journals/corr/VinyalsTBE14}$^{\dagger \Sigma}$ & 63 & 41 & 27 & --- & --- & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Soft Attention) & 67 & 44.8 & 29.9 & 19.5 & 18.93 & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Hard Attention) & \textbf{67} & 45.7 & 31.4 & 21.3 & 20.3 & --- & --- \\
\multicolumn{1}{|c|}{} & Ours (Beam = 1) & 60.8 & 43 & 29.4 & 19.8 & 20.9 & 50.7 & 46.4 \\
\multicolumn{1}{|c|}{} & Ours (Beam = 4) & 64 & \textbf{45.8} & \textbf{32.2} & \textbf{22.3} & \textbf{21} & \textbf{55.3} & \textbf{47.1} \\ \hline
\multicolumn{1}{|c|}{\multirow{5}{1in}{Flickr30k \\ \cite{young2014image}}} &\citeauthor{DBLP:journals/corr/VinyalsTBE14}$^{\dagger \Sigma}$ & 66.3 & 42.3 & 27.7 & 18.3 & --- & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Soft Attention) & 66.7 & 43.4 & 28.8 & 19.1 & 18.49 & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Hard Attention) & 66.9 & 43.9 & 29.6 & 19.9 & 18.46 & --- & --- \\
\multicolumn{1}{|c|}{} & Ours (Beam = 1)& 65.1 & 46.4 & 32.5 & 22.7 & 20.3 & 48 & 46 \\
\multicolumn{1}{|c|}{} & Ours (Beam = 4)& \textbf{67.4} & \textbf{49.5} & \textbf{36} & \textbf{26} & \textbf{20.1} & \textbf{52} & \textbf{47} \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{1in}{MS COCO \\ \cite{lin2014microsoft}}} &\citeauthor{DBLP:journals/corr/VinyalsTBE14}$^{\dagger \Sigma}$ & 66.6 & 46.1 & 32.9 & 24.6 & --- & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Soft Attention) & 70.7 & 49.2 & 34.4 & 24.3 & 23.9 & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{xu2015show} (Hard Attention) & 71.8 & 50.4 & 35.7 & 25 & 23.04 & --- & --- \\
\multicolumn{1}{|c|}{} &\citeauthor{ma2019image} (Beam = 3) & 70.6 & 54.0 & 40.6 & 30.5 & 25.3 & 97.1 & 52.8 \\
\multicolumn{1}{|c|}{} & Ours (Beam = 1) & 77.1 & 61.4 & 47.1 & 35.9 & 27.9 & 114.8 & 57.3 \\
\multicolumn{1}{|c|}{} & Ours (Beam = 4) & \textbf{77.9} & \textbf{62.8} & \textbf{49.7} & \textbf{39.3} & \textbf{28.7} & \textbf{120.3} & \textbf{58.5} \\ \hline
\end{tabular}
}
\caption{Performance of all the competing methods for image caption generation: -- indicates unknown metric; $\dagger$ indicates a different split; $\Sigma$ indicates an ensemble. \textit{Beam = 1} is same as not using beam search.}
\label{tab:table1}
\end{table*}

\section{Proposed Approach}
We propose an encoder-decoder attention based architecture. The encoder is a ResNet-101 model pre-trained on ImageNet dataset. We remove the final classification layer of the model to use it as a feature extractor. The decoder is an LSTM model which takes the feature vector extracted by the encoder as input along with the attention map given by the visual attention model. The attention model gives a weight between $0$ and $1$ to each pixel in the image. The weighted image along with the word embedding is fed to the LSTM model at each time step which then gives a hidden state and a predicted word for current time step. It is then used by attention and LSTM network for the next decoding step (see supplementary architecture diagram).
We use soft attention where the weights of the pixels add up to $1$. If there are $P$ pixels in our encoded image, then at each time step $t$,
$
    \sum_{p}^{P} \alpha_{p, t} = 1
$,
where $\alpha_{p, t}$ denotes the probability or importance of pixel $p$ at time step $t$. The other attention mechanism is to use hard attention in which we choose to just sample some pixels from a distribution defined by $\alpha$. However, it is non-deterministic and non-stochastic. It gives only marginal improvements as compared to soft attention.

The following optimizations and heuristics are applied in the proposed model:

\begin{itemize}
    \item Doubly Stochastic Regularization loss function is used for the attention network. The motivation is to encourage the weights at a single pixel $p$ to sum to 1 across all time steps $T$ so that the model to attends to every pixel over the course of generating the entire sequence:
    $\sum_{t}^{T} \alpha_{p, t} \approx 1$.
    \item Fine-tune the final layers of ResNet-101 with a smaller learning rate for the purpose of image captioning as it is originally trained for image classification on ImageNet.
    \item Use Teacher Forcing to train the decoder in which the ground-truth captions are used as input to the decoder at each time step instead of the word predicted in the previous time step. This speeds up the training time by a significant margin.
    \item Beam search for better captions. A beam width $k$, (in our case $k=4$), is chosen. The algorithm selects the word sequence which has the highest cumulative score of all the words in its sequence as the caption (see supplementary).
\end{itemize}

\section{Results}
\textbf{Data:} The experiments are performed using three benchmark datasets -- Flickr8k, Flickr30k and MS COCO, which have 8,000, 30,000 and 82,783 images, respectively. Due to the unavailability of standardized splits for Flickr30k and MS COCO, we use the splits provided in \cite{7298932}. \\
\textbf{Quantitative Analysis:} We use BLEU-1,2,3,4, METEOR, CIDEr and ROUGE-L as our evaluation metric (see supplementary for formulae). The results with various baselines are shown in Table \ref{tab:table1}. Beam search is also used by \cite{ma2019image}, but our model gives better results due to the other optimizations and heuristics in the training step.\\
\textbf{Qualitative Analysis:}  Figure \ref{fig:compare_captions} shows captions generated by different competing methods. We also compare captions generated with and without beam search, low CIDEr score captions, and visualise the attention network weights (see supplementary).

\begin{figure}[t]
    \centering
    \includegraphics[width=0.45 \textwidth]{images/compare_captions.png}
    \caption{Captions generated by different competing methods.}
    \label{fig:compare_captions}
\end{figure}

\section{Conclusion}
We proposed beam search heuristic for better caption generation for images on three benchmark datasets which shows that it beats the state-of-the-art approach. The heuristic can be applied to any given image captioning model as well as other language modeling tasks.

{\fontsize{9.0pt}{10.0pt} \selectfont
\section{Proposed Approach}
\subsection{Architecture}
Figure \ref{fig:proposed_model} shows our encoder-decoder architecture along with the attention network. The complete model is trained end to end and does not use any ensemble techniques.

\textbf{Encoder} is a pretrained ResNet-101\cite{he2016deep} whose classification layer has been pruned to get the image feature vector. We also fine tune convolutional blocks 2 through 4 in the ResNet with a smaller learning rate of $1e-4$ to better adapt for image captioning task.

\textbf{Attention network} takes in input the encoded image feature vector and decoder hidden state of the same dimension, these are then added and passed through a ReLU activation function followed by a linear layer which gives an output of dimension $1$ over which softmax is applied to generate the attention weights for each pixel in the image.
We use soft attention where the weights of the pixels add up to $1$. If there are $P$ pixels in our encoded image, then at each time step $t$,
$
    \sum_{p}^{P} \alpha_{p, t} = 1
$,
where $\alpha_{p, t}$ denotes the probability or importance of pixel $p$ at time step $t$.

\textbf{Decoder} is a Long Short Term Memory (LSTM) newtwork which takes in the flattened feature vector, initialized hidden state and the $<start>$ symbol embedding along with the attention-weighted encoding to generate the new hidden state and predict the next word in sequence along with a new hidden state.
The attention model gives a weight between $0$ and $1$ to each pixel in the image. The weighted image along with the word embedding is fed to the LSTM model at each time step which then gives a hidden state and a predicted word for current time step. It is then used by attention and LSTM network for the next decoding step.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.45 \textwidth]{images/model.png}
    \caption{Model architecture.}
    \label{fig:proposed_model}
\end{figure}

\begin{figure*}[ht]
    \centering
    \includegraphics[width=0.75 \textwidth]{images/beam_search.png}
    \caption{Beam search example with beam width $k$ = 3.}
    \label{fig:beam_search}
\end{figure*}

\subsection{Beam Search}
Figure \ref{fig:beam_search} shows an example of how beam search prunes with a beam width $k = 3$. The algorithm selects the word sequence which has the highest cumulative score of all the words in its sequence as the caption. Beam width $k = 1$ performs greedy search, that is, taking the max probability word at each decoding step. Large $k$ value gives a good chance for better caption generation, but takes more space and time. Whereas, small $k$ value is faster, but does not give good results. The following steps are followed to generate caption using beam search:

\begin{itemize}
    \item At first decoding step, top $k$ probability words are selected from the softmax prediction.
    \item At the next time step, generate $k$ words for each of the previous $k$ words.
    \item Choose the top $k$ [first word, second word] combinations considering additive scores of both the words.
    \item Repeat the process until $\langle end \rangle$ token is found and then select the caption with highest additive score of individual words (see Figure \ref{fig:beam_search}).
\end{itemize}

\begin{figure}[ht]
\centering
\begin{subfigure}{.46\textwidth}
  \centering

  \includegraphics[width=0.98\linewidth]{images/ui-view0.png}
  \caption{first screen takes saved model, wordmap path and beam width as input}
  \label{fig:sub-first}
\end{subfigure}
\begin{subfigure}{.23\textwidth}
  \centering

  \includegraphics[width=0.95\linewidth, height=3cm]{images/ui-view1.png}
  \caption{second screen with camera video feed}
  \label{fig:sub-second}
\end{subfigure}
\begin{subfigure}{.23\textwidth}
  \centering

  \includegraphics[width=0.95\linewidth, height=3.3cm]{images/ui-view3.png}
  \caption{third screen displays the caption generated for the captured image}
  \label{fig:sub-third}
\end{subfigure}
\caption{Graphical User interfaces for Attention Beam Image Captioning system.}
\label{fig:ui}
\end{figure}

\section{Graphical User Interface}
The proposed model can be consumed using the graphical user interface as shown in Figure \ref{fig:ui} which has the following interactions:
\begin{itemize}
    \item Allows the user to use their trained model, word-map and give a beam width parameter ($k$) value.
    \item Allows to capture an image from the video feed, save the captured image.
    \item Generate and display the caption for image present at the specified path on the system.
\end{itemize}
A demo video on how to use the given user interface is available at \url{https://youtu.be/bO4bvjYyvQE}.

\section{Evaluation Metric Formulae}
\label{section:eval_formulae}
Following are the formulae for different evaluation metrics. Here, $a$ is the candidate sentence or generated by the model, $b$ is the set of reference sentences or ground truth, $w_n$ is n-gram, $c_x(y_n)$ is the count of n-gram $y_n$ in sentence $x$
\begin{enumerate}
    \item BLEU \cite{papineni2002bleu}(BiLingual Evaluation Understudy): It is based on n-gram precision and is geometric mean of n-gram scores from $BLEU_1$ to $BLEU_4$.
    \begin{equation}
    \begin{split}
    x &= c_{a}(w_{n}) \\
    y &= max_{j=1..|b|}c_{bj}(w_{n}) \\
    BLEU_n(a, b) &= \frac{\sum _{(w_{n}\in a)}(min (x, y))}{\sum _{(w_{n}\in a)} x}
    \end{split}
    \end{equation}

    \item ROUGE \cite{lin2004rouge}(Recall Oriented Understudy of Gisting Evaluation): It is based on n-gram recall.
    \begin{equation}
    \begin{split}
    x &= c_{a}(w_{n}) \\
    y &= c_{bj}(w_{n}) \\
    ROUGE_{n}(a,b) &= \frac{\sum _{j=1..|b|} \sum_{(w_{n}\in b_{j}}(min (x, y))}{\sum _{j=1..|b|} \sum_{(w_{n}\in b_{j})} y}
    \end{split}
    \end{equation}

    \item CIDEr \cite{vedantam2015cider}(Consensus-based Image Description Evaluation): It gives more weightage to important n-grams and is based on higher correlation with human consensus scores. Here, $g^{n}(x)$ is a vector formed by TF-IDF scores of all n-grams in $x$.
    \begin{equation}
    \begin{split}
    CIDEr_{n}(a,b) &= \frac{1}{|b|} \sum _{j=1..|b|} \frac{g^{n}(a)*g^{n}(b_{j})}{||g^{n}(a)||*||g^{n}(b_{j})||}
    \end{split}
    \end{equation}

    \item METEOR \cite{banerjee2005meteor}(Metric for Evaluation of Translation with Explicit Ordering): An alignment between a and b is computed. It uses unigram precision and unigram recall. It gives smoother penalization for different ordering of chunks and is also based on higher correlation with human consensus scores. If $x$ is the number of set of unigrams adjacent in $a$ and $b_j$, $y$ is the number of matched unigrams, $P$ is unigram precision and $R$ is unigram recall, then
    \begin{equation}
    \begin{split}
    METEOR &= max_{j=1..|b|} \frac{10 PR}{R + 9P} (1- (0.5 (\frac{x}{y} )^{3}) )
    \end{split}
    \end{equation}
\end{enumerate}

\section{Results}
Figure \ref{fig:bad_captions} shows the difference in generated captions when using a beam width $k = 1$ and $k = 4$, these images had a low CIDEr score, that is, both the models produced bad captions, but it is evident from the captions that $k = 4$ produces better captions as compared to $k = 1$. Figure \ref{fig:attention} shows the weights given by the attention network to different regions of an image at different decoding time steps. This visualization gives an extra layer of interpretability to the model.

\begin{figure}[ht]
    \centering
    \includegraphics[width=0.45 \textwidth]{images/bad_captions.png}
    \caption{Low CIDEr score captions generated using beam width $k = 1$ and $k = 4$}
    \label{fig:bad_captions}
\end{figure}

\begin{figure}[ht]
\centering
    \frame{\raisebox{-\totalheight}{\includegraphics[width=.35\linewidth]{images/1.png}}
    \raisebox{-\totalheight}{\includegraphics[width=.64\linewidth]{images/1a.png}}}
    \\
    \frame{\raisebox{-\totalheight}{\includegraphics[width=.35\linewidth]{images/2.png}}
    \raisebox{-\totalheight}{\includegraphics[width=.64\linewidth]{images/2a.png}}}
    \\
    \frame{\raisebox{-\totalheight}{\includegraphics[width=.35\linewidth]{images/3.png}}
    \raisebox{-\totalheight}{\includegraphics[width=.64\linewidth]{images/3a.png}}}
\caption{Visualizing attention weights at different time step in image caption generation.}
\label{fig:attention}
\end{figure}

{\small


\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}