  We study ordinal approximation algorithms for maximum-weight bipartite
matchings. Such algorithms only know the ordinal preferences of the
agents/nodes in the graph for their preferred matches, but must compete with
fully omniscient algorithms which know the true numerical edge weights
(utilities). %instead of only their relative orderings. Ordinal approximation
is all about being able to produce good results with only limited information.
Because of this, one important question is how much better the algorithms can
be as the amount of information increases. To address this question for forming
high-utility matchings between agents in $\mathcal{X}$ and $\mathcal{Y}$, we
consider three ordinal information types: when we know the preference order of
only nodes in $\mathcal{X}$ for nodes in $\mathcal{Y}$, when we know the
preferences of both $\mathcal{X}$ and $\mathcal{Y}$, and when we know the total
order of the edge weights in the entire graph, although not the weights
themselves. We also consider settings where only the top preferences of the
agents are known to us, instead of their full preference orderings. We design
new ordinal approximation algorithms for each of these settings, and quantify
how well such algorithms perform as the amount of information given to them
increases.
