text:
\section{0pt}{12pt plus 2pt minus 2pt}{-1pt plus1pt minus 1pt}
\titlespacing\subsection{0pt}{12pt plus 2pt minus 2pt}{-1pt plus 1pt minus 1pt}
\titlespacing\subsubsection{0pt}{12pt plus 2pt minus 2pt}{-1pt plus 1pt minus 1pt}

\setlist{topsep = 0pt plus1pt}

\newcommand{\tuple}[1]{\ensuremath{\left \langle #1 \right \rangle }}
\newcommand{\proofcase}[1]{\par\smallskip\noindent{\textbf{#1}}}
\renewcommand{\hat}{\widehat}
\newcommand{{\mathbb R}}{{\mathbb R}}
\newcommand{{\mathbb G}}{{\mathbb G}}
\newcommand{\text{Cycles}}{\text{Cycles}}
\newcommand{\text{Ext}}{\text{Ext}}
\newcommand{{\mathcal A}}{{\mathcal A}}
\newcommand{{\mathcal C}}{{\mathcal C}}
\newcommand{{\mathcal I}}{{\mathcal I}}
\newcommand{{\mathcal J}}{{\mathcal J}}
\newcommand{{\mathcal K}}{{\mathcal K}}
\newcommand{{\mathcal L}}{{\mathcal L}}
\newcommand{{\mathcal M}}{{\mathcal M}}
\newcommand{{\mathcal N}}{{\mathcal N}}
\newcommand{{\mathcal O}}{{\mathcal O}}
\newcommand{{\mathcal P}}{{\mathcal P}}
\newcommand{{\mathcal T}}{{\mathcal T}}
\newcommand{\mathcal{L}}{\mathcal{L}}
\newcommand{\mathcal{W}}{\mathcal{W}}
\newcommand{\mathcal{C}}{\mathcal{C}}
\newcommand{\textrm{unrev}}{\textrm{unrev}}
\newcommand{\textrm{rev}}{\textrm{rev}}
\newcommand{\textrm{sig}}{\textrm{sig}}
\newcommand{\textrm{extsig}}{\textrm{extsig}}
\newcommand{\textrm{sig}^\textrm{opt}}{\textrm{sig}^\textrm{opt}}
\newcommand{=}{=}
\newcommand{\mathcal{M}}{\mathcal{M}}
\newcommand{\text{Order}}{\text{Order}}
\newcommand{\text{Pa}}{\text{Pa}}
\newcommand{\text{PO}}{\text{PO}}
\newcommand{{P_{poset}}}{{P_{poset}}}
\newcommand{{P_{poset}^k}}{{P_{poset}^k}}
\newcommand{\sigma}{\sigma}
\newcommand{\text{Top}}{\text{Top}}
\newcommand{\text{TTC}}{\text{TTC}}
\newcommand{\text{Type}}{\text{Type}}
\newcommand{\red}[1]{{\color{red} #1 }}
\newcommand{\vsays}[1]{{\color{red}***V says: #1****}}
\newcommand{\ns}[1]{\textcolor{red}{#1}}

\algnewcommand{\LeftComment}[1]{\State \(\triangleright\) #1}

\newenvironment{proof*}[1][\proofname]{
	\renewcommand*{\qedsymbol}{\(\square\)}
	\begin{proof}[#1]}{\end{proof}}

\pagestyle{plain}
\allowdisplaybreaks

\def0{0}
\def0{0}

\title{Necessarily Optimal One-Sided Matchings}

 \author{
    Hadi Hosseini\footnote{College of Information Sciences and Technology, Penn State University.\ \ttfamily hadi@psu.edu
 	}
 	\and
 	Vijay Menon\footnote{David R.\ Cheriton School of Computer Science, University of Waterloo.\ \ttfamily vijay.menon@uwaterloo.ca}
 	\and
 	Nisarg Shah\footnote{Department of Computer Science, University of Toronto.\ \ttfamily nisarg@cs.utoronto.ca
 	}
 	\and
 	Sujoy Sikdar\footnote{Department of Computer Science, Binghamton University.\ \ttfamily ssikdar@binghamton.edu
 	}
}

\date{}

\begin{document}

	\maketitle
	\input{abstract.tex}
	\input{intro.tex}
	\input{prelims}
\input{npo}
\input{nrm}
\input{discuss}

\printbibliography

\end{document}

\section*{Appendix}

\section{Material Omitted From \Cref{sec:npo}}\label{app:sec3-proofs}

\subsection{An algorithm to check whether a matching is NPO} \label{app:sec3-proofs:algo}

The following algorithm proceeds by constructing a potential trading cycle among the agents. If such cycle potentially exists, then there exists a possible Pareto improvement. Otherwise, the given matching is necessarily Pareto optimal.

\begin{algorithm}[htb]
	\centering
	\noindent\fbox{%
		\begin{varwidth}{\dimexpr\linewidth-4\fboxsep-4\fboxrule\relax}
			\begin{algorithmic}[1]
				\footnotesize
				\Input Top-$k$ preference profile $P = (P_1, \ldots, P_n)$, set of agents $N$, set of objects $O$, and matching $M$.
				\Output YES if $M$ is NPO w.r.t. $P$, and NO otherwise.
				\LeftComment{\textbf{Step 1.} Construct a directed graph ${\mathbb G} =(N, E)$.}
				\State $E\gets \emptyset$
				\For{each $i \in [n]$}
					\If{$(a_i,M(a_i))\in\textrm{rev}(P)$}
						\State For every agent $j\neq i$ such that $M(a_j) \succ_{P_i} M(a_i)$, add an edge $(a_i,a_j)$.
					\Else
						\State For every agent $j\neq i$, add an edge $(a_i,a_j)$.
					\EndIf
				\EndFor
				\LeftComment{\textbf{Step 2.} Check if ${\mathbb G}$ has a cycle.}
				\If{${\mathbb G} = (N,E)$ has a cycle}
					\State \Return NO
				\Else
				    \State \Return YES
				\EndIf
			\end{algorithmic}
	\end{varwidth}}
	\caption{An algorithm to determine whether a given matching is NPO.}
	\label{algo:checkNPO}
\end{algorithm}

\subsection{Proof of \Cref{thm:lb-elicit-po}} \label{app:sec3proofs:thm:lb-elicit-po}

\thmLBnpo*
\input{Proofs/lb-npo}

\subsection{Proof of \Cref{clm:qm1-ub}} \label{app:sec:proofs:clm1}
\input{Proofs/claim-npo-ub}

\section{Material Omitted From \Cref{sec:nrm}}\label{app:sec4-proofs}

\subsection{Proof of Lemma~\ref{lemm:optsig}} \label{app:sec4lemm:optsig}

First, we remark that \citet{irving2006rank} define rank-maximal matchings more generally for weak preference orders, in which several objects can be tied at the same position in the preference ranking of an agent. The signature of a matching with respect to a weak order profile still encodes, for all $\ell$, the number of agents who are matched to one of the objects in the $\ell^{\text{th}}$ position in their preference list. \citet{irving2006rank} construct an edge-labeled bipartite graph ${\mathbb G}$, where edge $(a_i,o_k)$ has label $\ell$ if $o_k$ appears in position $\ell$ in agent $a_i$'s weak preference order. By doing so, they extend the notion of rank-maximal matchings to such edge-labeled bipartite graphs. We note that their efficient algorithm to compute a rank-maximal matching for such a graph remains valid even when some of the edges of the graph are deleted, as we do in Algorithm~\ref{algo:optsig}.

\begin{restatable}{lemma}{lemmOptsig} \label{lemm:optsig}
	Given a top-$k$ preference profile $P$ over a set of agents $S\subseteq N$ and a set of objects $T \subseteq O$, and a set of pairs $F \subseteq S \times T$, Algorithm~\ref{algo:optsig} computes $\textrm{sig}^\textrm{opt}_P(S,T,F)$ and $\arg \textrm{sig}^\textrm{opt}_P(S,T,F)$ in polynomial time.
\end{restatable}
\input{Proofs/lemm-optsig}

\subsection{Proof of Theorem~\ref{thm:checkNRM}} \label{app:sec4proofs:thm:checkNRM}

Algorithm~\ref{algo:checkNRM} checks whether a given matching is NRM w.r.t. a given top-$k$ preference profile $P$. This is later used in checking whether an NRM matching exists given $P$, and computing one if it does.

\thmCheckNRM*
\input{Proofs/thm-checkNRM}

\subsection{Proof of Theorem~\ref{thm:nrm}}\label{app:nrm-proof-of-elicitation-bound}
\thmLBnrm*
\input{Proofs/lb-nrm}

\section{Discussion}\label{sec:disc}

As discussed in \Cref{sec:nrm}, the most immediate open question that stems from our work is to design an online elicitation algorithm to compute an NRM matching, and analyze its competitive ratio. In particular, we believe that there exists an algorithm with a constant competitive ratio.

Note that our online algorithm to compute an NPO matching from \Cref{sec:npo} is a constructive procedure, and uses our result that the existence of an NPO matching can be reduced to a simple analytical condition. Given that such a simple condition seems out of reach for the case of NRM, it may be interesting to explore a different approach to designing an online algorithm to compute an NRM matching. For example, one can train a machine learning model to select which agent to query next as a function of the preferences elicited so far. At each step, we can first use this algorithm to make one more query, and then call our efficient algorithm to check if the elicited preference reveal an NRM matching. It would be interesting to study if this approach can lead to a low competitive ratio, at least in practice.

More broadly, the literature on learning a desirable matching of agents to objects from partial preferences or historical data is still in its infancy, and many interesting directions, such as studying other models of partial preferences or other models of querying agents, remain unexplored.

\section*{Acknowledgments}
Hadi Hosseini acknowledges support from NSF grant \#1850076. Nisarg Shah was partially supported by an NSERC Discovery grant.
We are grateful to Lirong Xia for his insights in shaping the initial core of this project.
We thank the anonymous reviewers for their very helpful comments and suggestions.
\section{Introduction}\label{sec:intro}

\section{Introduction}\label{sec:intro}
Resource allocation is a fundamental problem in artificial intelligence and multi-agent systems. One particular type of resource allocation deals with assigning a number of indivisible objects to agents according to their preferences. These problems have given rise to a wide array of research in economics~\citep{moulin2004fair} and theoretical computer science~\citep{david2013algorithmics}.

The focus of our work is the special case of allocating $n$ objects to $n$ agents (so each agent is matched to a single object), which models many real-world applications (see, e.g., \cite{hylland1979efficient,abdulkadirouglu1999house}). For instance, imagine allocating office spaces to faculty members in a building. Instead of asking each faculty member to report a full preference ranking over the available offices, the department head may ask them to reveal their top choices, and then, if need be, she may ask individual faculty members to reveal their next best choices, and so on. The goal is to come up with a matching that \emph{necessarily} satisfies some form of ``economic efficiency'' while asking as few queries as possible. That is, it must satisfy the economic efficiency property regardless of the parts of the preferences that were not elicited, because otherwise some faculty may find the final matching undesirable.

What form of economic efficiency might one want for a matching? Luckily, decades of research in matching theory offers two prominent desiderata: \emph{Pareto optimality}~\cite{shapley1974cores,cirillo2012economics} and \textit{rank-maximality}~\cite{irving2003greedy,irving2006rank}. Informally, Pareto optimality requires that no other matching be able to make some agents better off without making any agent worse off.
Despite its wide use, Pareto optimality may be a weak guarantee in many practical settings. Hence, a stronger guarantee called rank-maximality is often used in practical applications such as assigning papers to referees~\cite{garg2010assigning}, assigning rented resources to customers~\cite{abraham2006assignment}, and assigning students to schools~\cite{abraham2009matching}. Informally, rank-maximality requires matching as many agents to their top choice as possible, subject to that matching as many agents to their second choice as possible, and so on.

The study of these axioms, along with axioms of fairness and incentive-compatibility, has led to the design of elegant rules such as random priority and probabilistic serial~\cite{bogomolnaia2001new,che2010asymptotic}, which have been made easily accessible by not-for-profit endeavors such as MatchU.ai (\url{www.matchu.ai}). However, in many real-life situations, one rarely has access to complete preferences which can simply be fed to these rules. More often than not, the problem at hand is to come up with a desirable matching of agents to objects with only partial information about agents' preferences. While the role of partial preferences has been well-explored in the sister problem known as \emph{two-sided matching}~\cite{rastegari2013two,liu2014stable}, in which agents are matched to other agents (for example matching roommates, kidney donors to patients, or men to women), it has been significantly understudied for one-sided matching. This is the primary focus of our work.
In particular, we consider the following  three research questions.
\begingroup
\begin{quote}
    \emph{Given partial preferences, can we efficiently check if a given matching is NPO or NRM? Can we efficiently check if an NPO or NRM matching exists (and if so, find one)?

    How much online elicitation of preferences is needed to find an NPO or NRM matching?
    }
\end{quote}
\endgroup

\subsection{Our Results}\label{sec:results}
We study the \emph{next-best} query model which allows, in each query, asking one agent to reveal her next best choice. Partial preferences elicited under this model are referred to as \emph{top}-$k$ preferences as each agent reveals a prefix of her preference ranking consisting of the top $k$ items (where $k$ can be different for each agent). As mentioned above, our goal is to design online algorithms that ask few queries and learn a matching that is necessarily Pareto optimal or necessarily rank-maximal w.r.t.\ the elicited partial preferences. We study their performance in terms of their competitive ratio~\cite{borodin2005online}.

Note that these algorithms need to check if there already exists a matching that is NPO or NRM w.r.t.\ the elicited preferences in order to decide if further elicitation is required. Along the way, it is also useful to know if a \emph{given} matching is NPO or NRM w.r.t.\ the given partial preferences. Thus, we also study these two questions for NPO and NRM.

For necessary Pareto optimality, we show that checking whether a given matching is NPO reduces to computing the maximum weight matching in a bipartite graph, which can be solved efficiently. We also show that there exists an NPO matching if and only if there exists a matching that matches at least $n-1$ agents to objects they have revealed, where $n$ is the number of agents; this can be checked in polynomial-time, and if this is the case, our algorithm efficiently finds an NPO matching. Our main result is an online algorithm for finding an NPO matching that has a competitive ratio of $O(\sqrt{n})$. By proving a matching lower bound, we show that our algorithm is asymptotically optimal.

For necessary rank-maximality, we design efficient algorithms for checking whether a given matching is NRM. For checking whether an NRM matching exists; unlike in the case of NPO, these questions do not seem to reduce to checking a simple analytical condition. In the supplementary material, we show that a simple characterization can be obtained in the special case where each agent has revealed exactly the same number of objects. For online elicitation, we show a constant lower bound on the competitive ratio, and conjecture that the optimal competitive ratio is in fact constant, unlike in the case of NPO.

\subsection{Related Work}\label{sec:related}
The problem of matching $n$ agents to $n$ objects models a number of scenarios and is well-studied, sometimes as the house allocation or one-to-one object allocation problem (e.g., \cite{hylland1979efficient,abdulkadirouglu1998random,abra04,irving2003greedy}). There are two approaches to learning a desirable matching given only partial information about agents' preferences. One approach is to consider the worst case scenario over missing preferences; imposing a property $X$ in the worst case leads to the ``necessarily $X$'' concept. This concept has been considered in other contexts such as in voting \cite{xia08} and in one-sided matching problems where an agent may be assigned to more than one good \cite{bou10,aziz15,aziz19}. However, in the latter case, even having access to agents' full preference rankings over individual goods is not sufficient for checking Pareto optimality, which leads \citet{aziz19} to consider NPO given full rankings. In contrast, in our one-to-one matching setting, full preference rankings over individual goods are sufficient to check whether a given matching is PO, which leads us to consider partial (top-$k$) rankings.

Another approach is to assume that the underlying preferences are drawn from a known distribution~\cite{rastegari2013two}, and consider the probability of satisfying $X$~\cite{aziz2019pareto}. We note that asking whether a matching satisfies $X$ with probability $1$ often coincides with the ``necessarily $X$'' concept.

We focus on the top-$k$ model of partial preferences, which is commonly used in the literature~\cite{aziz2015possible,drummond2013elicitation}. However, there are also other interesting models; one such model is where the information available regarding each agent's preferences is in the form of a set of pairwise comparisons among objects~\cite{aziz2019pareto}. In general, the goal of this line of work is to make matching algorithms more practically relevant, to which our work contributes.

Other than economic efficiency, researchers have also focused on notions of fairness and incentive-compatibility in matching agents to objects, which has led to the design of rules such as random priority and probabilistic serial~\cite{bogomolnaia2001new,abdulkadirouglu1998random,hosseini2018investigating}. A related line of research considers two-sided matching markets, where agents are matched to other agents. Working with partial preferences is well-explored in such markets~\cite{rastegari2013two,liu2014stable}.

\section{Necessarily Pareto optimal matchings} \label{sec:npo}
We begin, in \Cref{sec:checkNPO}, by presenting an algorithm that determines if a given matching is NPO w.r.t.\ to a profile of top-$k$ preferences. Following this, we provide a useful characterization for when NPO matchings exist. This in turn is used in \Cref{sec:npo-elicit} in designing an elicitation algorithm that is $2(\sqrt{n} + 1)$-competitive. We also show that no elicitation algorithm can achieve a competitive ratio of $o(\sqrt{n})$, establishing our algorithm as asymptotically optimal.

\subsection{Determining whether a matching is NPO} \label{sec:checkNPO}
We present a polynomial time algorithm to determine whether a given matching $M$ is NPO w.r.t.\ a profile of top-$k$ preferences $P$. The algorithm proceeds in two steps: In Step 1, we build a directed graph ${\mathbb G}=(N, E)$, where $E$ consists of directed edges $(a_i,a_j)$ such that $M(a_j) \succ_{R_i} M(a_i)$ under some $R_i \in {\mathcal C}(P_i)$. That is, there exists an edge when agent $i$ prefers the object allocated to agent $j$ over her own under some completion of her partial preferences. In Step 2, we efficiently check if this directed graph admits a cycle. If it does, matching $M$ is not NPO; otherwise, it is NPO.

\begin{restatable}{theorem}{thmchecknpo} \label{thm:checkNPO}
Given a top-$k$ preference profile $P$ and a matching $M$, there is a polynomial time algorithm to check if $M$ is NPO w.r.t.\ $P$.
\end{restatable}

\input{Proofs/thm-checkNPO}

At a high level, correctness of the algorithm follows from the observation that if there is a cycle in the directed graph constructed above, then one can construct a complete preference profile $R \in {\mathcal C}(P)$ such that each agent in the cycle strictly prefers the object allocated to the next agent in the cycle under $M$. Then, trading objects along this cycle would result in a matching $M'$ that, under this completion $R$, Pareto-dominates $M$, establishing that $M$ is not NPO.

\subsection{Computing an NPO matching, when it exists} \label{sec:npo-iff}
Next, we find a necessary and sufficient condition for a given top-$k$ preference profile $P$ to admit an NPO matching. In the case that an NPO matching exists, we also provide an algorithm to compute one in polynomial time.

\begin{theorem} \label{thm:npo-iff}
    A top-$k$ preference profile $P$ admits an NPO matching if and only if there is a matching of size at least $n-1$ w.r.t.\ $P$. Moreover, there is a polynomial time algorithm to determine whether a top-$k$ preference profile admits an NPO matching, and to compute an NPO matching if it exists.
\end{theorem}
\begin{proof}
\noindent{($\Rightarrow$)}
 Consider a top-$k$ preference profile $P$ that admits an NPO matching $M$. Suppose for the sake of contradiction that there is no matching w.r.t.\ $P$ that is of size larger than $n-2$. Then, $|M\cap\textrm{rev}(P)|\le n-2$, which implies that there are at least two agents, w.l.o.g.\ agents $a_1$ and $a_2$, who are matched to objects they have not revealed under $P$. It is easy to see that one can now construct a completion $R\in{\mathcal C}(P)$ such that $M(a_2) \succ_{R_{1}} M(a_1)$ and $M(a_1) \succ_{R_{2}} M(a_2)$. Under this completion, exchanging the objects assigned to $a_1$ and $a_2$ would Pareto-dominate $M$, contradicting the fact that $M$ is NPO w.r.t. $P$.

\noindent{($\Leftarrow$)}
 Let $P$ be a top-$k$ preference profile such that there exists a matching of size at least $n-1$ w.r.t.\ $P$. Construct a weighted bipartite graph ${\mathbb G} = (N \cup O, \textrm{rev}(P))$, where each edge $(a_i, o_j)\in \textrm{rev}(P)$ has weight equal to the rank of $o_j$ in $P_i$. Let $M$ be a matching of min.\ weight among all matchings of max.\ cardinality in ${\mathbb G}$. Note that $|M|\ge n-1$.

 Let us first consider the case when $|M|=n$. If so, then it is easy to see that $M$ is an NPO matching w.r.t. $P$. This is because any matching that Pareto-dominates $M$ in any completion $R \in {\mathcal C}(P)$ must have size $n$ w.r.t. $P$ as well and a strictly lower weight than $M$, which is a contradiction.

 Now, consider the case when $|M|=n-1$. So exactly one agent and one object are not matched. Without loss of generality, suppose these are $a_n$ and $o_n$. Construct a matching $\hat{M}$ of our problem by adding $(a_n,o_n)$ to $M$. Thus, $|\hat{M} \cap \textrm{rev}(P)| = |M| = n-1$. We wish to show that $\hat{M}$ is NPO. Suppose for the sake of contradiction that there exists a matching $M'$ which Pareto dominates $\hat{M}$ w.r.t.\ some completion $R\in{\mathcal C}(P)$. Hence, $M'$ must assign each agent an object she prefers (under $R$) at least much as what she receives under $\hat{M}$, and at least one agent a strictly better (under $R$) object than what she receives under $\hat{M}$. Thus, $M'$, when viewed as a matching in ${\mathbb G}$, must have  cardinality $n-1$ and weight at most the weight of $M$. Further, weight of $M'$ is equal to the weight of $M$ only if $M'$ assigns each agent $a_i \neq a_n$ the same object that $\hat{M}$ assigns. However, any two matchings that differ must differ in the assignment to at least two agents. Hence, we have that $M'$ is a matching in ${\mathbb G}$ with cardinality $n-1$ and weight strictly less than the weight of $M$, which is a contradiction.

Now, we provide a polynomial-time algorithm to compute an NPO matching, when it exists. From the argument above, it is sufficient to be able to compute a min-weight max-cardinality matching $M$ of the graph ${\mathbb G}$. This can be done in polynomial time using the Hungarian algorithm \cite{munkres1957algorithms}. Then, if $|M| = n$, the algorithm returns $M$, and if $|M| = n-1$, the algorithm returns $\hat{M}$ by adding the unmatched agent-object pair.
\end{proof}

\subsection{Elicitation to compute an NPO matching} \label{sec:npo-elicit}

In this section we turn to the question of elicitation. As mentioned in \Cref{sec:prelims-qm}, we use the next-best query model, and informally our main goal is to understand how to elicit as little information as possible in order to compute an NPO matching. Towards this end, we first prove, in \Cref{thm:lb-elicit-po}, a lower bound that shows that any elicitation algorithm has a competitive ratio of $\Omega(\sqrt{n})$.

\begin{restatable}{theorem}{thmLBnpo} \label{thm:lb-elicit-po}
In the next-best query model, if there exists an $\alpha$-competitive elicitation algorithm for finding a necessarily Pareto optimal matching, then $\alpha \in \Omega(\sqrt{n})$.
\end{restatable}

\if\npoSecProofsinApp0
\input{Proofs/lb-npo}
\fi

A natural strategy to elicit preferences is to simultaneously ask all the $n$ agents to reveal their next best object until the point at which the designer has enough information to compute an NPO matching. Recall that we can check the latter condition at every step by leveraging our Theorem~\ref{thm:npo-iff} from Section~\ref{sec:npo-iff}. Although this approach is natural, it is not difficult to see that it results in a competitive ratio of $\Omega(n)$.

Let us describe the high-level idea of our algorithm (Algorithm~\ref{algo:elicit}), although the exact details vary slightly in the algorithm in order to optimize the competitive ratio. We follow the aforementioned na\"{\i}ve approach of asking all agents to report their next best object only up to a point where we can match at least $n-\sqrt{n}$ agents to objects they have revealed. At that point, we compute one such matching, focus on the unmatched agents (at most $\sqrt{n}$ of them), and then just ask these agents for their next best object until there is a matching of size at least $n-1$, which, by \Cref{thm:npo-iff}, is a sufficient condition for the existence of an NPO matching. Once we know an NPO matching exists, we use the polynomial time algorithm from \Cref{thm:npo-iff} to find one. This strategy, with the details optimized, results in an improved competitive ratio of $2(\sqrt{n} + 1)$, which, given Theorem~\ref{thm:lb-elicit-po}, is asymptotically optimal.

\begin{algorithm}[tb]
	\centering
	\noindent\fbox{%
		\begin{varwidth}{\dimexpr\linewidth-4\fboxsep-4\fboxrule\relax}
			\begin{algorithmic}[1]
				\footnotesize
				\Input A profile of top-$k$ preferences $P = (P_1, \ldots, P_n)$, a set of agents $N$, and a set of objects $O$.
				\Output An NPO matching

				\State for each $i \in [n]$, initialize $P_i = \emptyset$

				\State $\mathcal{M} \leftarrow \emptyset$; $k \leftarrow 1$; $s \leftarrow | \mathcal{M} |$

				\While{$s < (n - 1)$} \label{algstep:l3}
				\If{$s \leq (n - 1) - \min(\{k-1, \sqrt{n}\})$} \label{algstep:l1}
				\For{each $i \in [n]$}
					\State $o \leftarrow \mathcal{Q}(a_i, |P_i|+1)$

					\State update $P_i$ by adding object $o$ at position $|P_i| + 1$
				\EndFor \label{algstep:l2}
				\ElsIf{$s > (n - 1) - \min(\{k-1, \sqrt{n}\})$}  \label{algstep:l4}

					\State $U \leftarrow$ the set of unmatched agents in $\mathcal{M}$ \label{algstep:l5}
					\For{each $i \in U$}
					\State $o \leftarrow \mathcal{Q}(a_i, |P_i|+1)$
					\State update $P_i$ by adding object $o$ at position $|P_i| + 1$
					\EndFor

				\EndIf \label{algstep:l6}
				\State $k \leftarrow k+1$
				\State $\mathcal{M} \leftarrow$ max.\ matching in $\mathbb{G}\left(N \cup O,\textrm{rev}(P) \right)

				\State $s \leftarrow | \mathcal{M} |$
				\EndWhile
				\State use algorithm described in Theorem~\ref{thm:npo-iff} to return a matching that is NPO w.r.t.\ ${P} = (P_1, \cdots, P_n)$

			\end{algorithmic}
	\end{varwidth}}
	\caption{A $2(\sqrt{n} + 1)$-competitive elicitation algorithm}
	\label{algo:elicit}
\end{algorithm}

\begin{theorem} \label{thm:ub-elicit-po}
	Algorithm~\ref{algo:elicit} is a $2(\sqrt{n} + 1)$-competitive elicitation algorithm in the next-best query model for computing a necessarily Pareto optimal matching.
\end{theorem}

\if\npoSecProofsinApp1
In order to prove this result, we first introduce the following notation. We maintain a graph ${\mathbb G} = (N \cup O,\textrm{rev}(P))$, where $P$ denotes the top-$k$ preference profile elicited so far. Let $s_j$ denote the size of the maximum matching in this graph during the $j$-th iteration of line~\ref{algstep:l3}. Next, let $m$ denote the number of times lines~\ref{algstep:l1}--\ref{algstep:l2} are run in Algorithm~\ref{algo:elicit}. Note that $m \geq 1$ (since $s_1 = 0$ and hence lines \ref{algstep:l1}--\ref{algstep:l2} are executed at least during the first iteration), and that the total number of iterations of the algorithm is $m+1$ (since the `else if', i.e., lines~\ref{algstep:l4}--\ref{algstep:l6} is executed just once). Also, note that for all $j \in [m]$, $s_j$ is also the size of the maximum matching when all agents have revealed their top $(j-1)$ objects in Algorithm~\ref{algo:elicit}. Finally, for $j \in [m]$, let $X_j$ denote the number of agents who are asked at least $j$ queries by the optimal algorithm. Now, we have the following claim, whose proof appears in \Cref{app:sec:proofs:clm1}.

\else
 In order to prove this result, we first introduce the following notation and prove the claim below. Let $s_j$ denote the size of the maximum matching during the $j$-th iteration of line~\ref{algstep:l3}. Note that for all $j \in [m]$, $s_j$ is also the size of the maximum matching when all agents have revealed their top $(j-1)$ objects in Algorithm~\ref{algo:elicit}. Next, let $m$ denote the number of times lines~\ref{algstep:l1}--\ref{algstep:l2} are run in Algorithm~\ref{algo:elicit}. Note that $m \geq 1$, since $s_1 = 0$ and hence lines \ref{algstep:l1}--\ref{algstep:l2}, are executed at least during the first iteration, and that the total number of iterations of the algorithm is $m+1$ (since the `else if', i.e., lines~\ref{algstep:l4}--\ref{algstep:l6} is executed just once). Finally, for $j \in [m]$, let $X_j$ denote the number of agents who are asked at least $j$ queries by the optimal algorithm. Given this notation, we have the following claim about $\text{X}_j$.
\fi

\begin{claim} \label{clm:qm1-ub}
	For every $j \in [m]$, $X_j \geq (n-s_j-1)$.
\end{claim}

\if\npoSecProofsinApp0
\input{Proofs/claim-npo-ub.tex}
\fi

Equipped with the notations and the claim above, we can now prove our theorem.

\begin{proof}[Proof of Theorem~\ref{thm:ub-elicit-po}]

	Let $\text{ALG}$ denote the number of queries asked in Algorithm~\ref{algo:elicit} and $m$ be as defined above. Since the algorithm asks $n$ queries during each time lines~\ref{algstep:l1}--\ref{algstep:l2} is run and it asks at most $(n-s_{m+1}) \cdot (n-m)$ queries during the execution of lines~\ref{algstep:l4}--\ref{algstep:l6} (the first term is maximum number of agents in set $U$ in line~\ref{algstep:l5} and the second arises from the fact that all these agents have revealed their top $m$ preferences), we have that
	\begin{align}
	\text{ALG} &\leq n\cdot m + (n-s_{m+1}) \cdot (n-m) \nonumber \\
	&< n\cdot m + (\min(\{m, \sqrt{n}\}) + 1) \cdot (n-m), \label{eq:qm1-1}
	\end{align}
	where the second step follows from the fact that $(n - s_{m+1}) < (1+\min(\{m, \sqrt{n}\}))$ (see line~\ref{algstep:l4} in Algorithm~\ref{algo:elicit}).

	Next, let $\text{OPT}$ denote the number of queries asked by the optimal algorithm. From Claim~\ref{clm:qm1-ub} we know that $X_j$, which is the number of agents who are asked at least $j$ queries by the optimal algorithm, is at least $(n-s_j-1)$. Therefore,
	\begin{align}
		\text{OPT} &\geq m\cdot X_m + \sum_{j=1}^{m-1} (m-j) \cdot (X_{m-j} - X_{m-j+1}) \nonumber \\
		&= X_m + X_{m-1} + \cdots + X_1 \nonumber \\
		&\geq n-1 + \sum_{j=2}^m (n-s_j-1) \tag{{\footnotesize using Claim~\ref{clm:qm1-ub} and the fact that $s_1 = 0$}} \nonumber  \\
		&\geq n-1 + (m-1)\cdot (n-s_m-1) \tag{{\footnotesize since $\forall j\in[m], s_j \leq s_{j+1}$}} \nonumber  \\
		&\geq n-1 + (m-1) \cdot \min(\{m-1, \sqrt{n}\}), 		\label{eq:qm1-2}
	\end{align}
		where the final inequality follows from the fact that $(n - 1 - s_{m}) \geq  \min(\{m-1, \sqrt{n}\})$ (see line~\ref{algstep:l1} in Algorithm~\ref{algo:elicit}).
Therefore, using~(\ref{eq:qm1-1}) and~(\ref{eq:qm1-2}), we have
\begin{align*}
\frac{\text{ALG}}{\text{OPT}} &\leq \frac{n\cdot m + (\min(\{m, \sqrt{n}\}) + 1) \cdot (n-m)}{n-1 + (m-1) \cdot \min(\{m-1, \sqrt{n}\})}\\
&\leq 2(\min(\{m, \sqrt{n}\}) + 1),
\end{align*}
where the last inequality follows by using $n \geq 2$, $m \geq 1$, and by considering the cases $m\leq \sqrt{n}$ and $m> \sqrt{n}$.
\end{proof}

\section{Necessarily rank-maximal matchings}\label{sec:nrm}
In the previous section, we devised algorithms for computing an NPO matching when one exists and when given a top-$k$ preference profile, and for eliciting a small amount of information to determine such matchings.
Here, we focus on rank-maximality, which is a stronger notion of economic efficiency than Pareto optimality and widely used in real-world applications (see, e.g., \cite{garg2010assigning,abraham2006assignment,abraham2009matching}). To illustrate this notion, consider the top-$k$ preference profile $P$ with three agents, where $P_1=o_1\succ o_2 \succ o_3$, $P_2=o_1\succ o_2$ and $P_3=o_1$. The matching $M=\set{(a_1,o_3),(a_2,o_2),(a_3,o_1)}$ is NPO, but not NRM. To see this, consider the completion $R$ of $P$, where $R_1=o_1\succ o_2 \succ o_3$, $R_2=o_1\succ o_2 \succ o_3$, and $R_3=o_1\succ o_3 \succ o_2$. While $M$ has signature $(1,1,1)$ under $R$, matching $M'=\set{(a_1,o_1),(a_2,o_2),(a_3,o_3)}$ has a better signature $(1,2,0)$ under $R$. In fact, it is easy to verify that $M'$ is NRM w.r.t.\ $P$.

We begin, in \Cref{sec:determinNRM}, by presenting an algorithm that determines whether a given matching is necessarily rank-maximal (NRM) w.r.t.\ a given top-$k$ preference profile. In \Cref{sec:existNRM}, we build upon this algorithm to design another algorithm that decides if a given top-$k$ preference profile admits an NRM matching, and computes one if it does. Finally, we turn to the elicitation question, where we provide a lower bound on the competitive ratio of any elicitation algorithm that returns an NRM matching. We first introduce necessary additional definitions and notations.

\begin{definition}[rank-maximality w.r.t.\ top-$k$ preferences]
Given a top-$k$ preference profile $P$ and a matching $M$, let the \textit{signature} of $M$ w.r.t.\ $P$, denoted $\textrm{sig}_P(M)$, be the tuple $(x_1,\ldots,x_n)$, where $x_\ell$ is the number of $(a_i, o_j) \in M\cap\textrm{rev}(P)$ such that $o_j$ is the $\ell^{\text{th}}$ most preferred choice of $a_i$. We say that $(x_1,\ldots,x_n) \succ_{\text{sig}} (x'_1,\ldots,x'_n)$ if there exists a $h \in [n]$ such that $x_h > x'_h$ and $x_i = x'_i$ for all $i < h$; this is the lexicographic comparison of signatures. A matching $M$ is rank-maximal w.r.t.\ $P$ if  $\textrm{sig}_P(M)$ is maximum under $\succ_{\text{sig}}$. In plain words, a matching is rank-maximal w.r.t.\ partial preference profile $P$ if it maximizes the number of agents matched to their top choice, subject to that the number of agents matched to their second choice, and so on.
\end{definition}

\begin{definition}[Extended signature]  Following Definition~\ref{def:RMM}, we define the \textit{extended signature} of a matching $M$ w.r.t.\ $P$, denoted $\textrm{extsig}_P(M)$, to be the tuple $(x_1,\ldots,x_n)$, where, for all $i \in [n-1]$, $x_i$ is defined as in $\textrm{sig}_P(M)$, while $x_n$ counts not only the number of agents matched to their $n^\text{th}$ choice revealed in $P$, but also the number of agents matched to an object they did not reveal in $P$.
\end{definition}

\begin{definition}[Optimal signature] Given a top-$k$ preference profile $P$ over a subset of agents $S \subseteq N$ and a subset of objects $T \subseteq O$, as well as a set of ``forbidden'' pairs $F \subseteq S \times T$, let $\mathcal{M}(S,T,F)$ denote the set of all matchings $M$ that match agents in $S$ to objects in $T$ and satisfy $M \cap F = \emptyset$. We define $\textrm{sig}^\textrm{opt}_P(S,T,F) = \sup_{M \in \mathcal{M}(S,T,F), R \in \mathcal{C}(P)} \textrm{sig}_R(M)$. Informally, this is the \textit{best possible signature} that any matching can achieve under any completion of $P$ while avoiding pairings from $F$. We use $\arg\textrm{sig}^\textrm{opt}_P(S,T,F)$ to denote the matching $M \in {\mathcal M}(S, T, F)$ that obtains this best signature under some completion $R \in \mathcal{C}(P)$. Note that sometimes we use $\textrm{sig}^\textrm{opt}_P$ to denote $\textrm{sig}^\textrm{opt}_P(N,O,\emptyset)$.
\end{definition}

\subsection{Determining whether a matching is NRM} \label{sec:determinNRM}

At a high level, our algorithm to determine if a given matching $M$ is NRM under a given top-$k$ preference profile $P$ works as follows. It leverages the fact that given any $S \subseteq N$, $T \subseteq O$, and $F \subseteq S \times T$, we can efficiently compute $\textrm{sig}^\textrm{opt}_P(S, T, F)$. \Cref{algo:optsig} formally describes how to do this and the following lemma shows its proof of correctness. However, before that we make the following remark.

\textbf{Remark:} \citet{irving2006rank} define rank-maximal matchings more generally for weak preference orders, in which several objects can be tied at the same position in the preference ranking of an agent. The signature of a matching with respect to a weak order profile still encodes, for all $\ell$, the number of agents who are matched to one of the objects in the $\ell^{\text{th}}$ position in their preference list. \citet{irving2006rank} construct an edge-labeled bipartite graph ${\mathbb G}$, where edge $(a_i,o_k)$ has label $\ell$ if $o_k$ appears in position $\ell$ in agent $a_i$'s weak preference order. By doing so, they extend the notion of rank-maximal matchings to such edge-labeled bipartite graphs. We note that their efficient algorithm to compute a rank-maximal matching for such a graph remains valid even when some of the edges of the graph are deleted, as we do in Algorithm~\ref{algo:optsig}.

\begin{restatable}{lemma}{lemmOptsig} \label{lemm:optsig}
	Given a top-$k$ preference profile $P$ over a set of agents $S\subseteq N$ and a set of objects $T \subseteq O$, and a set of pairs $F \subseteq S \times T$, Algorithm~\ref{algo:optsig} computes $\textrm{sig}^\textrm{opt}_P(S,T,F)$ and $\arg \textrm{sig}^\textrm{opt}_P(S,T,F)$ in polynomial time.
\end{restatable}
\input{Proofs/lemm-optsig}

Given the result above, our algorithm first checks if $M$ has size at least $n-1$ w.r.t.\ $P$; this is necessary for $M$ to even be NPO w.r.t.\ $P$, as the proof of \Cref{thm:npo-iff} shows. If $M$ has size $n$ w.r.t.\ $P$, then we argue that its signature w.r.t.\ $P$ (which is the same as its signature w.r.t.\ any completion $R$ of $P$) must be $\textrm{sig}^\textrm{opt}_P$. On the other hand, suppose $M$ has size $n-1$ w.r.t.\ $P$, with $(a_i,o_j) \in M \cap \textrm{unrev}(P)$ being the pair where an agent is matched to an object she did not reveal under $P$. Then, we argue that two conditions need to be met: (a) to ensure that another matching $M'$ with $(a_i,o_j) \in M'$ cannot have a better signature under any completion $R$, we require that the signature of $M$ w.r.t.\ $P$ be at least as good as $\textrm{sig}^\textrm{opt}_P(N\setminus\set{a_i},O\setminus\set{o_j},\emptyset)$, and (b) to ensure that another matching $M'$ with $(a_i,o_j) \notin M'$ cannot have a better signature under any completion $R$, we require that the extended signature of $M$ w.r.t.\ $P$ be at least as good as $\textrm{sig}^\textrm{opt}_P(N,O,\set{(a_i,o_j)})$. \Cref{algo:checkNRM} formalizes this and we show  its correctness below.

\begin{algorithm}[!tb]
	\centering
	\noindent\fbox{%
		\begin{varwidth}{\dimexpr\linewidth-4\fboxsep-4\fboxrule\relax}
			\begin{algorithmic}[1]
				\footnotesize
				\Input A top-$k$ preference profile $P$ over a set of agents $S\subseteq N$ and a set of objects $T \subseteq O$, and $F \subseteq S \times T$.

				\Output $\textrm{sig}^\textrm{opt}_P(S,T,F)$ and $\arg \textrm{sig}^\textrm{opt}_P(S,T,F)$

				\State For all $a_i \in S$, let $k_i \gets |P_i|$

				\State $P' \gets$ weak order profile which matches $P$ on the preferences revealed under $P$, and for every $(a_i, o_j) \in \textrm{unrev}(P)$, has object $o_j$ at position $k_i+1$ in $P'_i$ \label{algo:optsig-l2}

				\State Create a bipartite graph $\mathbb{G} = (S \cup T, E)$, where $E = S \times T \setminus F$, and each edge $(a_i, o_j) \in E$ is labelled with $\ell$ if $o_j$ appears in position $\ell$ in $P'_i$.

				\State $M \gets$ compute a rank-maximal matching of $\mathbb{G}$ using the algorithm by \citet{irving2006rank}

				\State \Return $\textrm{sig}_{P'}(M)$ and $M$
			\end{algorithmic}
		\end{varwidth}}
	\caption{Algorithm to compute $\textrm{sig}^\textrm{opt}_P(S,T,F)$ and $\arg \textrm{sig}^\textrm{opt}_P(S,T,F)$.}
	\label{algo:optsig}
\end{algorithm}

\begin{algorithm}[!tb]
	\centering
	\noindent\fbox{%
		\begin{varwidth}{\dimexpr\linewidth-4\fboxsep-4\fboxrule\relax}
			\begin{algorithmic}[1]
				\footnotesize
				\Input A top-$k$ preference profile $P$, a set of agents $N$, a set of objects $O$, and a matching $M$.

				\Output Is $M$ NRM w.r.t.\ $P$?
				\State $c \gets |M \cap \textrm{rev}(P)|$.

				\If{$c = n$ and $\textrm{sig}_P(M) = \textrm{sig}^\textrm{opt}_P$}
				\State \Return YES \label{algo:checkNRM-l5}
				\ElsIf{$c = n-1$}
				\State Pick $(a_i,o_j) \in M \cap \textrm{unrev}(P)$ \Comment{this is unique since $M$ has cardinality $n-1$ w.r.t.\ $P$.}

				\If {$\textrm{sig}_P(M) \succeq_{\text{sig}} \textrm{sig}^\textrm{opt}_P(N\setminus \{a_i\}, O\setminus \{o_j\}, \emptyset)$ and $\textrm{extsig}_P(M) \succeq_{\text{sig}} \textrm{sig}^\textrm{opt}_{P}(N, O, \set{(a_i, o_j)})$}
				\State \Return YES \label{algo:checkNRM-l11}
				\EndIf
				\EndIf
				\State \Return NO
			\end{algorithmic}
	\end{varwidth}}
	\caption{Algorithm to check if a given matching is NRM given a top-$k$ preference profile.}
	\label{algo:checkNRM}
\end{algorithm}

\begin{restatable}{theorem}{thmCheckNRM} \label{thm:checkNRM}
	Given a top-$k$ preference profile $P$ and a matching $M$, there exists a polynomial-time algorithm that determines if $M$ is NRM w.r.t.\ $P$.
\end{restatable}
\input{Proofs/thm-checkNRM}

\subsection{Computing an NRM matching, when it exists} \label{sec:existNRM}

The results from \Cref{sec:determinNRM} are key to devising an algorithm that determines if a given top-$k$ preference profile admits an NRM matching and computes one if it does. Specifically, note again that a matching that is NRM w.r.t.\ a top-$k$ preference profile $P$ must have size at least $n-1$ w.r.t.\ $P$. If there is an NRM matching of size $n$ w.r.t.\ $P$, then we argue that it must be rank-maximal w.r.t.\ $P$ and have signature $\textrm{sig}^\textrm{opt}_P$. We can check this efficienty using the results from \Cref{sec:determinNRM}. If there is an NRM matching of size $n-1$ w.r.t.\ $P$ with $(a_i,o_j) \in M \cap \textrm{unrev}(P)$, then we argue that $M \setminus \set{(a_i,o_j)}$ must be a rank-maximal matching of $N\setminus\set{a_i}$ to $O\setminus\set{o_j}$ w.r.t.\ $P$. By iterating over all agent-object pairs $(a_i, o_j)$, we can again check this efficiently. \Cref{algo:existNRM} formalizes this and the next result proves its correctness.

\begin{algorithm}[!t]
	\centering
	\noindent\fbox{%
		\begin{varwidth}{\dimexpr\linewidth-4\fboxsep-4\fboxrule\relax}
			\begin{algorithmic}[1]
				\footnotesize
				\Input A top-$k$ preference profile $P$, agents $N$, and objects $O$.

				\Output Returns an NRM matching if $P$ admits one, and returns NO otherwise.

				\State $M' \gets$ rank-maximal matching w.r.t.\ $P$

				\If{$|M' \cap rev(P)| = n$ and $\textrm{sig}_P(M) = \textrm{sig}^\textrm{opt}_P$} \label{algo:existNRM-l2}
				\State \Return $M'$

				\Else

				\For{$(a_i,o_j) \in \textrm{unrev}(P)$}

				\State $X \gets$ rank-maximal matching of $N \setminus \{a_i\}$ to $O \setminus\{o_j\}$ w.r.t.\ $P$ \label{algo:existNRM-l7}

				\State $M' \gets X \cup \set{(a_i,o_j)}$

				\State \textbf{if} {$M'$ is NRM w.r.t.\ $P$}, \textbf{then} return $M'$ \label{algo:existNRM-l9}

				\EndFor
				\EndIf

				\State \Return NO
			\end{algorithmic}
	\end{varwidth}}
	\caption{Algorithm to check if an NRM matching exists given a top-$k$ preference profile.}
	\label{algo:existNRM}
\end{algorithm}

\begin{restatable}{theorem}{thmExistNRM} \label{thm:existNRM}
Given a top-$k$ preference profile $P$, there exists a polynomial-time algorithm that returns a necessarily rank-maximal matching if one exists, and returns NO otherwise.
\end{restatable}
\input{Proofs/thm-existNRM}

\subsection{Elicitation to compute an NRM matching}

We are now ready to consider the question of eliciting information to compute an NRM matching. Below we provide a lower bound on the competitive ratio of any elicitation algorithm.

\begin{restatable}{theorem}{thmLBnrm} \label{thm:nrm}
In the next-best query model, for $n \ge 2$, if there exists an $\alpha$-competitive elicitation algorithm for finding a necessarily rank-maximal matching, then $\alpha \ge \frac{4}{3} - \frac{2}{n}$, if $n$ is even, and $\alpha \ge \frac{4}{3} - \frac{20}{9n-3}$, if $n$ is odd.
\end{restatable}

\input{Proofs/lb-nrm}

Note that our lower bound converges to $\frac{4}{3}$ as $n$ goes to infinity. So, a natural question is whether one can design an online algorithm to compute an NRM matching that has constant competitive ratio. We conjecture that this should be possible, but leave it as an open problem for future work.
\section{Preliminaries} \label{sec:prelims}
Let $N = \{a_1, \cdots, a_n\}$ denote the set of agents and $O = \{o_1, \cdots, o_n\}$ be the set of objects.
We use $[k]$ to denote the set $\{1,\dots, k\}$.
Thus, for $i\in [n]$, $a_i$ and $o_i$ represent agent and object $i$ respectively.
A \textit{matching} of agents to objects is a bijection $M: N\to O$. We sometimes refer to a matching as a collection of pairs $\set{(a_i, M(a_i) \mid i \in [n])}$ and use $\mathcal{M}$ to denote the set of all possible matchings.

Each agent $a_i \in N$ has an underlying linear order $R_i$ over $O$, where a linear order over $O$ is a transitive, antisymmetric, and total relation on $O$. We use ${\mathcal L}(O)$ to denote the set of all linear orders over $O$, and refer to $R = (R_1, \cdots, R_n) \in {\mathcal L}(O)^n$  as a \textit{(complete) preference profile}. Additionally, for $i, j, k \in [n]$, if $a_i$ prefers $o_j$ to $o_k$ according to $R_i$, then we denote this by $o_j \succ_{R_i} o_k$ or $o_k \prec_{R_i} o_j$.

We formally describe two notions of economic efficiency, namely Pareto optimality and rank-maximality.

\begin{definition}[Pareto optimality]
	Given a preference profile $R = (R_1,\ldots,R_n)$, a matching $M$ is said to be Pareto optimal w.r.t.\ $R$ if no other matching can make an agent happier without making some other agent less happy, i.e., if
	 $ \forall M' \in \mathcal{M}: \; \left(\exists a_i \in N, M'(a_i) \succ_{R_i} M(a_i) \right) \Rightarrow\\ \left(\exists a_j \in N, M'(a_j) \prec_{R_j} M(a_j)\right).$
\end{definition}

\begin{definition}[rank-maximality]\label{def:RMM}
Given a preference profile $R$ and a matching $M$, let the \textit{signature} of $M$ w.r.t. $R$, denoted $\textrm{sig}_R(M)$, be the tuple $(x_1,\ldots,x_n)$, where $x_\ell$ is the number of $(a_i, o_j) \in M$ such that $o_j$ is the $\ell^{\text{th}}$ most preferred choice of $a_i$. We say that $(x_1,\ldots,x_n) \succ_{\text{sig}} (x'_1,\ldots,x'_n)$ if $\exists k \in [n]$ such that $x_k > x'_k$ and $x_i = x'_i$ for all $i < k$; this is the lexicographic comparison of signatures. A matching $M$ is rank-maximal w.r.t.\ $R$ if  $\textrm{sig}_R(M)$ is maximum under $\succ_{\text{sig}}$. In words, a matching is rank-maximal if it matches max.\ number of agents to their top choice, subject to that the max.\ number of agents to their second choice, and so on.
\end{definition}

\subsection{Partial preferences}

In this paper, we study a partial preference model called \emph{top-$k$ preferences}, in which each agent $i$ may reveal a prefix of her preference ranking, that is, a ranking of her $k_i$ most favorite objects for some $k_i \in [n]$. Specifically, agent $i$ may reveal $P_i$ which is a linear order over some $L \subseteq O$ such that any object in $L$ are preferred to any object in $L \setminus O$ by the agent; we say that agent $i$ has revealed object $o$ in $P_i$ if $o \in L$. Also, we sometimes use $|P_i| = |L| = k_{i}$ to denote the size of $P_i$, i.e., the number of objects revealed in $P_i$.
We refer to $P = (P_1,\ldots,P_n)$ as a top-$k$ preference profile and say that a linear order $R_i$ is \textit{consistent} with $P_i$ if, for all $j, k \in [n]$, $o_j \succ_{P_i}  o_k \Rightarrow o_j \succ_{R_i}  o_k$. We use $\mathcal{C}(P_i)$ to denote the set of linear orders over $O$ that are consistent with $P_i$, and $\mathcal{C}(P)$ to denote $\mathcal{C}(P_1) \times \ldots \times \mathcal{C}(P_n)$.

Given a top-$k$ preference profile $P = (P_1, \cdots, P_n)$, we use  $\textrm{rev}(P)$ to denote the set of all pairs $(a_i, o_j)$ such that $a_i$ has revealed object $o_j$ in $P_i$, and $\textrm{unrev}(P)$ to denote $(N \times O) \setminus \textrm{rev}(P)$. Throughout, whenever we refer to the size of a matching $M$ w.r.t.\ to $P$, we mean $|M \cap \textrm{rev}(P)|$.

We are interested in the notion of ``necessarily efficient'' matchings, which are guaranteed to satisfy an efficiency notion such as Pareto optimality or rank-maximality given only a top-$k$ preference profile~\citep{GNNW14,xia08,aziz2015possible}.

\begin{definition}[necessary Pareto optimality (NPO) and necessary rank-maximality (NRM)]
	Given a top-$k$ preference profile $P$, a matching $M$ is said to be necessarily Pareto optimal (resp.\ necessarily rank-maximal) w.r.t.\ $P$ if it is Pareto optimal (resp.\ rank-maximal) w.r.t.\ any profile of linear orders that is consistent with $P$, i.e., for any $R \in \mathcal{C}(P)$.
\end{definition}

\subsection{Query model and elicitation} \label{sec:prelims-qm}
We consider algorithms that can elicit preferences by asking agents to reveal their ``next-best'' objects---meaning if the agent has already revealed their $k-1$ most preferred objects, then it asks the agent to reveal their $k$-th most preferred object. We formally define this query model below.

\begin{definition}[next-best query model] \label{def:qmodel1}
	For $a_i \in N$ and $k \in [n]$, query $\mathcal{Q}(a_i, k)$, which asks agent $a_i$ to reveal the object in the $k$-th position in her preference list, is a valid query in the next-best query model if query $\mathcal{Q}(a_i,j)$ has already been made for all $j \in [k-1]$.
\end{definition}

We are interested in \textit{online} elicitation algorithms that find NPO or NRM matchings in the next-best query model and measure their performance against an all-powerful optimal algorithm. An all-powerful optimal algorithm is a hypothetical offline algorithm that can identify the minimum number of queries of the form $\mathcal{Q}(a_i, j)$ that are sufficient to guarantee an NPO  or NRM matching. That is, for $i \in [n]$ and $k_i \in [n]$, the optimal algorithm can minimize $\sum_{i \in [n]} k_i$, and can claim that asking every agent $i$ for their top-$k_i$ order, $P_i$, is sufficient to compute a matching that is NPO or NRM w.r.t.\ all consistent completions of $P = (P_1, \ldots, P_n)$.
We say that an online elicitation algorithm is \textit{$\alpha$-competitive} (or, equivalently, it achieves a competitive ratio of $\alpha$) if the number of queries it requires to ask in the worst-case across all possible instances is at most $\alpha \cdot \text{OPT}$, where $\text{OPT}$ is the number of queries asked by the optimal algorithm.

redpajama_set_name: RedPajamaArXiv


text:
\section{Introduction}

Top physics, together with Higgs boson studies and searches for Beyond
the Standard Model (BSM) phenomena, is one of the three pillars of the
research programme for future high energy $\epem$ colliders.
As the top quark is the heaviest known elementary particle, with an
expected value of the Yukawa coupling of the order of one, the precise
determination of its properties is a key to understanding
electroweak symmetry breaking.
The determination of top properties is also essential for many ``new
physics'' searches, as the top quark gives large loop contributions to many
precision measurements that are sensitive to BSM effects.
Stringent constraints on the new physics scenarios are also
expected from direct searches for rare top decays.
Both future linear colliders, the International Linear Collider (ILC)
and the Compact Linear Collider (CLIC), provide an opportunity to
study the top quark with unprecedented precision via direct production
of thousands of $\PQt\PAQt$ pairs in $\epem$ collisions.

This contribution presents the prospects of constraining
the branching ratio for the flavour changing top decays $\PQt \rightarrow \PQc \PGg$\xspace and
$\PQt \rightarrow \PQc \PH$\xspace with CLIC running
at $\sqrt{s} = 380$~GeV \cite{staging_baseline_yellow_report}.
These decays are very strongly suppressed in the Standard Model with the
expected branching ratios~\cite{Agashe:2013hma}:
\begin{eqnarray*}
\textrm{BR}(\PQt \rightarrow \PQc \PGg) &  \approx & 5 \cdot 10^{-14}, \\
\textrm{BR}(\PQt \rightarrow \PQc \PH) &  \approx & 3 \cdot 10^{-15}.
\end{eqnarray*}
At the same time a significant enhancement of these decays is
expected in many extensions of the Standard Model, resulting from
either the introduction of the direct tree level FCNC couplings or
being due to the loop level
contributions of new particles (or SM particles with modified couplings).
For the  $\PQt \rightarrow \PQc \PGg$\xspace decay an enhancement up to the level
of $10^{-5}$ is expected for some SUSY models with $R$-parity
violation~\cite{Mele:1999zx},
while for the $\PQt \rightarrow \PQc \PH$\xspace channel loop induced branching ratio of up to $10^{-4}$ is
predicted in many models~\cite{Bejar:2001sj}, with enhancement of up to
$10^{-2}$ possible on the tree level~\cite{DiazCruz:2006qy}.
Existing LHC constraints on the considered FCNC decays of the top quark are
rather weak, at the level of $2 \cdot 10^{-3}$
\cite{Aaboud:2017mfd,Khachatryan:2016atv,Khachatryan:2015att}
and the expected limits from HL-LHC are of the order of
$2 \cdot 10^{-4}$ \cite{Agashe:2013hma,ATL-PHYS-PUB-2016-019}.
Measurements at CLIC can be competitive for these channels thanks
to the large sample of produced top quarks, clean environment and well
constrained kinematics.
The observation of any such decay would be a direct signature
for ``new physics''.

\section{Event simulation and reconstruction}

Detailed detector level analysis was performed for  $\epem$ collisions
at CLIC at $\sqrt{s} = 380$~GeV.
With the assumed lumionosity of 500~fb$^{-1}$ and electron beam
polarisation of -80\%  about 400~000 top quark pairs are expected.
Dedicated signal samples were generated with
WHIZARD 2.2.8 \cite{Kilian:2007gr,Moretti:2001zz}.
For the $\PQt \rightarrow \PQc \PGg$\xspace channel the model with anomalous top couplings
(\verb|SM_top_anom|) with vector type tensor $\PQt\PQc\PGg$ coupling
was used while for the $\PQt \rightarrow \PQc \PH$\xspace channel the simulation was based on the
2HDM(III) model implemented in SARAH~\cite{Staub:2015kfa}.
For both models the parameter values were tuned to obtain a FCNC
branching ratio of $10^{-3}$ so that the contribution from events with two
FCNC decays is negligible.
Detailed beam spectra for CLIC as well as beam induced backgrounds
and the assumed electron beam polarization were taken into account.
Generated events were passed to PYTHIA~6.4 for
hadronisation with quark masses and other settings adjusted to the
configuration used previously in CLIC CDR studies~\cite{CLIC_PhysDet_CDR}.
Signal samples were then processed with a standard event
simulation and reconstruction chain of the CLICdp collaboration using
the CLIC\_ILD\_CDR500 detector configuration.
The background sample considered in the presented analysis included a
full set of six-fermion event samples originally produced for CLICdp
studies of top pair production at $\sqrt{s} = 380$~GeV.
All sub-samples corresponded to an integrated luminosity of at least
500~fb$^{-1}$.

Analysis of the two top decay channels presented in this contribution was
based on the so-called particle flow reconstruction performed using
\pandora \cite{thomson:pandora, Marshall2013153, Marshall:2015rfa}.
The reconstructed object collection resulting from loose background
rejection cuts \cite{CLIC_PhysDet_CDR} was used as an input
for jet reconstruction with the Valencia
algorithm~\cite{Boronat:2016tgd} as well as for primary and secondary
vertex reconstruction, and flavour tagging with \textsc{LcfiPlus}\xspace
\cite{Suehara:2015ura}.

\section{$\PQt \rightarrow \PQc \PGg$\xspace analysis}

In this channel we search for top pair production events in which one of
the top quarks decays into a charm quark and a photon.
Due to the large top mass this decay results in a very striking
signature:  a high energy photon, with an energy of at least 50 GeV.
Only the fully hadronic decay channel is considered where the
second (spectator) top quark decays into a b-quark and a W-boson, which
decays hadronically into two light quarks.
The analysis requires that an isolated photon with an energy of at
least 50 GeV is reconstructed in each selected event.
This simple cut reduces the background from standard $\PQt \PAQt$\xspace decays
by a factor of 20 while keeping 92\% of the signal events.
Selected events are then subjected to kinematic fits, based on the jets
reconstructed using the Valencia jet clustering algorithm, for both the
signal  (\PGg + 4 jets) and background (6 jet) hypotheses.
The final selection of signal events is then based on a Boosted
Decision Tree (BDT) algorithm, as
implemented in the TMVA framework \cite{TMVA:2010}.
A total of 42 input variables were used to train the BDT, including photon
properties, jet properties, flavour tagging information, invariant
masses and $\chi^2$ values from the kinematic fits.
The distribution of the BDT classifier response for the considered
signal (FCNC decay events) and background (SM top decays) samples is
shown in Fig.~\ref{fig:tcg_bdt}.
\begin{figure}
\begin{center}
\includegraphics[width=0.6\textwidth]{Naomi_BDT_wip.pdf}
\end{center}
\caption{Distribution of the BDT classifier response for events with
    FCNC top decay  $\PQt \rightarrow \PQc \PGg$\xspace (signal, blue histogram)
    and SM top pair events (background, red histogram), for FCNC selection at 380 GeV
    CLIC. The background sample is normalised to 500~fb$^{-1}$ and the
    assumed signal level corresponds to  BR($\PQt \rightarrow \PQc \PGg$\xspace) $=10^{-3}$.
\label{fig:tcg_bdt} }
\end{figure}
Shown in Fig.~\ref{fig:tcg_mtop} is the reconstructed invariant mass
distribution for the signal top quark, after the final selection cut based
on the BDT response, BDT$>$0.2.
\begin{figure}
\begin{center}
\includegraphics[width=0.6\textwidth]{Naomi_Mtop_BDT20_wip.pdf}
\end{center}
\caption{Invariant mass distribution of the top quark from the
    FCNC decay $\PQt \rightarrow \PQc \PGg$\xspace reconstructed at 380~GeV CLIC after final
    selection cuts, for an integrated luminosity of 500~fb$^{-1}$ and
    assuming BR($\PQt \rightarrow \PQc \PGg$\xspace) $=10^{-3}$.
\label{fig:tcg_mtop} }
\end{figure}
With this cut  60\% of the signal events are selected while reducing the
background contamination in the sample by a factor of about 500.
The total selection efficiency resulting from the initial selection and
BDT based selection is 55\% for signal events and $9.4 \cdot 10^{-5}$
for $\PQt\PAQt$ background.
Assuming the nominal integrated luminosity of 500~fb$^{-1}$ collected at
380~GeV CLIC, the expected 95\% C.L. limit on the top FCNC decay
(assuming no signal contribution) is
\begin{eqnarray*}
   \textrm{BR}(\PQt \rightarrow \PQc \PGg)  & < & 3 \cdot 10^{-5} \; .
  \end{eqnarray*}

\section{$\PQt \rightarrow \PQc \PH$\xspace analysis}

The sensitivity of CLIC at 380 GeV to FCNC decay $\PQt \rightarrow \PQc \PH$\xspace was studied for the
dominant Higgs boson decay channel $\PH \rightarrow \PQb \PAQb$\xspace.
Six jets are expected in the final state for top pair production
events with one FCNC top quark decay and a hadronic decay of
the second (spectator) top quark, while four jets, an isolated lepton
and missing momentum are expected for events having a leptonic spectator decay.
These final states have topologies that are compatible with the
Standard Model top pair production events, which is therefore the dominant
background contribution for this analysis.
Discrimination between FCNC signal and SM top pair production events
has to be based on the kinematic fit results and the flavour
tagging information.
For signal events we expect three jets in the final state to be tagged
as b-quark jets (two from the Higgs boson and one from the
spectator top quark decay) with two of them consistent with the invariant
mass of the Higgs boson.
A cut based approach, which was considered at the initial stage of the
analysis \cite{Zarnecki:2017cmf}, was found to be too inefficient
for the considered process, as many observables had to be considered
at the same time.
This contribution presents the new analysis approach based on
the use of multivariate analysis.
BDT classifiers were used in the three analysis stages:
classification of top pair candidate events (into hadronic,
semi-leptonic and leptonic samples), estimation of the event reconstruction
quality and the final signal-background discrimination.

For selection of hadronic and semi-leptonic event samples, two
independent BDT classifiers, based on total event
energy-momentum, event shape variables, isolated lepton
information and jet reconstruction parameters were prepared.
Only SM background samples were used for BDT training at this stage,
with hadronic and purely leptonic top pair events used as a signal
when training the hadronic and leptonic BDT classifiers respectively.
Shown in Fig.~\ref{fig:tch_hadlep} are the response distributions for
these classifiers for different samples of top pair events.
\begin{figure}
\begin{center}
\includegraphics[width=0.49\textwidth]{Hadronic_BDT_hist_wip.pdf}
\includegraphics[width=0.49\textwidth]{Leptonic_BDT_hist_wip.pdf}
\end{center}
\caption{Response distributions for BDT classifiers trained to recognize
    hadronic top pair events (left) and leptonic top pair events
    (right), for different samples of $\PQt \PAQt$\xspace SM background events,
    for 500~ fb$^{-1}$ at 380 GeV CLIC.
\label{fig:tch_hadlep}   }
\end{figure}
A cut on the hadronic BDT response was used to select the hadronic event
sample, while a cut on both the hadronic and leptonic BDT responses was
required for semi-leptonic event selection.
Identification of the final state isolated lepton (electron or muon)
was also required for the semi-leptonic events.
The pre-selection based on the event classification included also the
initial (loose) cut on the flavour tagging results: three jets were
required to have a b-tag value of at least 0.4 and the fourth jet (jet
coming from the \PQc quark from FCNC decay) should have a sum of b-tag
and c-tag values of at least 0.4.

As mentioned above, the signal-background discrimination for $\PQt \rightarrow \PQc \PH$\xspace channel
has to be based on the kinematic fit results.
However, the quality of the kinematic fit turned out to be very poor
for a significant fraction of events, both for the signal and for the
SM $\PQt\PAQt$ sample.
Figure~\ref{fig:tch_goodbad} shows two example top pair
production events from the hadronic sample.
Compared are the generator level directions of the final state quarks
with the reconstructed particle flow objects and clustering results of
Valencia algorithm (as used in the kinematic fit) and the anti-k$_{T}$ jet
clustering algorithms.
For the majority of the events (as the one shown in Fig.~\ref{fig:tch_goodbad}
left), reconstructed jets correspond closely to the partonic final state on
the generator level.
For such well-reconstructed events a kinematic fit allows for
precise determination of event kinematics and can be used for efficient
discrimination between FCNC and SM top quark decays.
However, for a significant fraction of events (like the one shown in
Fig.~\ref{fig:tch_goodbad} right) final state particles and the
reconstructed particle flow objects do not follow the initial quark
directions.
\begin{figure}
\begin{center}
\includegraphics[width=0.49\textwidth]{fcnc_event_12_new.pdf}
\includegraphics[width=0.49\textwidth]{fcnc_event_16_new.pdf}
\end{center}
\caption{Schematic view of two SM top pair production
    events with fully hadronic final state.
    Directions in ($\cos\theta$, $\phi$) of final state quarks
    (solid green circles) and reconstructed particle flow objects
    (solid red circles) are compared with clustering results of Valencia (open
    magenta circles) and anti-k$_{T}$ (open blue circles) jet
    algorithms.
\label{fig:tch_goodbad}   }
\end{figure}
This is mainly due to higher order QCD effects.
The quality of the kinematic fit is very poor for such poorly
reconstructed events and it cannot be used for efficient signal event
selection.
It is therefore important to try to discriminate between well
reconstructed and poorly reconstructed events.

The results of the kinematic fits should not be used to make any
selection at this stage, as they will be used in the final step to
discriminate between signal ($\PQt \rightarrow \PQc \PH$\xspace) and background ($\PQt \rightarrow
\PQb\PWp$) hypotheses.
However, one can notice that for poorly reconstructed events the clustering
results have a much stronger dependence on the clustering algorithm applied.
It is therefore possible to estimate the event reconstruction quality
by comparing results of different clustering algorithms.
The BDT algorithm was trained separately for hadronic and
semi-leptonic events using the angular distances and energy
differences between jets reconstructed with three different jet
algorithm configurations.
The angular distance between the Valencia jets and the six-fermion
final state on the generator level was used to define the reference
samples for BDT training.
The obtained event quality estimate (BDT response, BDT$_{jet}$) is
only weakly correlated with the true parton-jet matching, but it does
improve significantly the quality of kinematic reconstruction.
Shown in Fig.~\ref{fig:tch_minv} is the influence of the cut on the
quality estimate on the reconstructed invariant mass of the \PWpm
boson and the top quark, for the sample of hadronic $\PQt\PAQt$ events.
The cut applied on the quality estimate significantly reduces
the tails of the invariant mass distributions.
\begin{figure}
\begin{center}
\includegraphics[width=0.49\textwidth]{BDT_jet_mw_hist_3_wip.pdf}
\includegraphics[width=0.49\textwidth]{BDT_jet_mtop_hist_3_wip.pdf}
\end{center}
\caption{Influence of the cut on the event quality classifier
    response, BDT$_{jet}$, on the kinematic reconstruction of hadronic events.
    Reconstructed invariant masses of the W bosons (left)
     and top quarks (right) for SM top pair events (normalised to  500~fb$^{-1}$).
\label{fig:tch_minv}   }
\end{figure}

In the final step of the analysis, kinematic fits are performed for
signal and background hypotheses.
The jet combination which minimises the $\chi^2$ value for the event is
selected separately for each hypothesis.
Flavour tagging results are used to reduce the number of possible
configurations.
Results from kinematic fits and the flavour tagging results are
then used as an input for the final BDT selection optimised to discriminate
between signal and background events.
Resulting response distributions from the BDT classifiers trained to
select signal events in hadronic and semi-leptonic samples are
presented in Fig.~\ref{fig:tch_bdt}.
\begin{figure}
\begin{center}
\includegraphics[width=0.49\textwidth]{had_s2b_fit19_ch1_bold_wip.pdf}
\includegraphics[width=0.49\textwidth]{lep_s2b_fit19_ch1_bold_wip.pdf}
\end{center}
\caption{ Response distribution of the BDT classifiers used for the final
    signal event selection for hadronic (left) and semi-leptonic
    (right) events. The background (red histogram) sample is
    normalized to 500~fb$^{-1}$ while the
    signal (events with FCNC decay; blue histogram)
    to \mbox{BR($\PQt \rightarrow \PQc \PH$\xspace)}$\times$\mbox{BR($\PH \rightarrow \PQb \PAQb$\xspace)} $=10^{-3}$ for the same
    integrated luminosity.
\label{fig:tch_bdt}  }
\end{figure}
Final cuts on the BDT response were optimised to obtain the best
expected limit on FCNC branching ratio, for the assumed luminosity of
500~fb$^{-1}$.
The resulting cuts turned out to be relatively tight.
The final selection efficiency for FCNC events is 10.4\% while the
background suppression is at the level of $10^{-4}$.
This results in the expected 95\% C.L. limits of
\begin{eqnarray}
  \textrm{BR}(\PQt \rightarrow \PQc \PH) \times \textrm{BR}(\PH \rightarrow \PQb \PAQb)  & < & 1.6 \cdot 10^{-4}
\end{eqnarray}
for 500 fb$^{-1}$ collected at 380 GeV (hadronic and semi-leptonic
samples combined).
Details of the event selection efficiency for hadronic and
semi-leptonic channel are presented in Tab.~\ref{tab:tch_effi}.
\begin{table}
  \begin{center}
\begin{tabular}{l|c|c|c|c}
  & \multicolumn{2}{c|}{Hadronic}
  & \multicolumn{2}{c}{Semi-leptonic} \\ \cline{2-5}
  & Signal & SM $\PQt\PAQt$
  & Signal & SM $\PQt\PAQt$ \\ \hline
  Classification & 0.66 & 0.42 & 0.19 & 0.28 \\
  Flavour tagging & 0.54 & 0.059 & 0.42 & 0.013 \\
  Event quality & 0.89  & 0.90  & 0.92  &  0.90  \\
  Final MVA cut & 0.23 & 0.0038 & 0.44 & 0.013 \\ \hline
  Total  & 0.072 & 0.000086 & 0.032 & 0.000044
 \end{tabular}
  \end{center}
  \caption{Summary of selection efficiency for analysis of the FCNC top
    quark decay $\PQt \rightarrow \PQc \PH$\xspace. Shown are the selected fractions of
    hadronic and semi-leptonic events, for FCNC signal and SM top pair
    production background, at different analysis stages as well as the
    total selection efficiency.
    \label{tab:tch_effi}}
\end{table}

\section{Conclusions}

Considered in this contribution was  the feasibility of measuring the FCNC
top decay $\PQt \rightarrow \PQc \PGg$\xspace and \mbox{$\PQt \rightarrow \PQc \PH$\xspace} at CLIC running at 380 GeV.
Results based on the full detector simulation were presented, taking
luminosity distribution, beam polarization and beam induced background
into account.
For the $\PQt \rightarrow \PQc \PGg$\xspace decay, based on the analysis of the hadronic channel
only, the expected sensitivity (expected 95\% C.L. limit on the FCNC
branching ratio) is $3 \cdot 10^{-5}$, while for the $\PQt \rightarrow \PQc \PH$\xspace decay the
corresponding limit is $1.6 \cdot 10^{-4}$ (including Higgs branching
ratio to $\PQb\PAQb$).
Presented results should be considered as a ``Work in Progress'' report,
the study is ongoing and publication of the final results is in preparation.

\section*{Acknowledgments}

This work benefited from services provided by the ILC Virtual
Organisation, supported by the national resource providers of the EGI
Federation.

\printbibliography[title=References]

\end{document}